Manakah algoritma signifikan untuk umat manusia dalam beberapa dekade terakhir? [Tutup]

Algoritma terpenting di dunia mana yang paling banyak berkontribusi bagi umat manusia dalam beberapa dekade terakhir?

Saya pikir ini adalah pengetahuan umum yang baik untuk diketahui pengembang.

Pembaruan:
Jika memungkinkan, harap simpan jawaban untuk algoritme pemrograman tertentu .
Saya ingin mendapatkan daftar yang paling penting, hanya satu algoritma per jawaban.
Harap pertimbangkan untuk menyatakan mengapa algoritme ini penting dan penting ...

Enkripsi kunci publik / pribadi sangat penting. Perdagangan internet tidak akan ada di mana-mana tanpa itu.

Algoritma Dijkstra

Algoritma ada di setiap router di dunia, untuk mengidentifikasi rute terbaik antara dua node dalam jaringan.

Transformasi Fourier Cepat (FFT)

FFT adalah metode yang sangat penting dan banyak digunakan untuk mengekstraksi informasi yang berguna dari sinyal sampel .

Transformasi Fourier cepat (FFT) adalah algoritma yang efisien untuk menghitung transformasi Fourier diskrit (DFT) dan kebalikannya.

Peringkat halaman

PageRank adalah algoritma analisis tautan, dinamai menurut Larry Page, digunakan oleh mesin pencarian Internet Google yang memberikan bobot numerik untuk setiap elemen kumpulan dokumen yang hyperlink, seperti World Wide Web, dengan tujuan "mengukur" relatifnya pentingnya dalam set.

Algoritma kompresi data

Dalam ilmu komputer dan teori informasi, kompresi data atau pengkodean sumber adalah proses pengkodean informasi menggunakan bit lebih sedikit (atau unit pembawa informasi lainnya) daripada representasi yang tidak didekode akan menggunakan, melalui penggunaan skema pengkodean tertentu.

Smith-Waterman (dan Needleman-Wunsch)

Ini mungkin terlalu jauh, jadi tolong beri komentar.

Smith-Waterman: Algoritma Sequence Alignment

Saya pikir salah satu contohnya adalah algoritma Smith-Waterman dan Needleman-Wunsch dan perkiraannya. Semuanya pada dasarnya melakukan hal yang sama: mereka menyelaraskan dua atau lebih string (urutan) . Ada arti penting dalam Biologi. Ketika sekuens DNA atau Protein diselaraskan - daerah kesamaan struktural, fungsional, dan evolusioner terungkap.

BLAST sebagai keturunan Smith-Waterman

Heuristik yang mendekati Smith-Waterman adalah BLAST. Ini memungkinkan pencarian urutan database besar untuk kesamaan Biologis. Popularitas BLAST benar-benar hebat - kemungkinan besar algoritma yang paling banyak digunakan dalam Biologi. Area yang lebih baru dalam Bioinformatika dan Genomik memiliki perkiraan yang lebih baru dan lebih baik dari algoritma Smith-Waterman / Needleman-Wunsch yang lebih akurat daripada BLAST.

Majelis Genom sebagai keturunan Smith-Waterman

Perkiraan throughput tinggi dari Smith-Waterman dan Needleman-Wunsch yang lebih cepat dari BLAST digunakan untuk merakit Genom dari sekuensing senapan - di mana produk dari mesin sequencer adalah sejumlah besar DNA yang dibaca (miliaran) dari bagian acak dari Genome yang sangat pendek (50 hingga 100 nukleotida). Pendekatan ini digunakan untuk menyelesaikan Proyek Genom Manusia. Semua urutan modern dilakukan dengan cara ini.

Multiple Sequence Alignment merupakan perpanjangan dari Smith-Waterman

Algoritma Multiple Sequence Alignment Banyak ada - mereka mendekati versi multi-urutan Smith-Waterman / Needleman-Wunsch. Berbagai urutan disejajarkan sebagai satu kelompok secara bersamaan satu sama lain. Ini adalah masalah yang jauh lebih sulit daripada pasangannya yang berpasangan, tetapi solusinya memberikan lebih banyak wawasan tentang fungsi, struktur, dan sejarah evolusi dari sekuens terkait.

Siam menyebut berikut ini sebagai algoritma terpenting abad ke-20:

1946: Algoritma Metropolis untuk Monte Carlo . Melalui penggunaan proses acak, algoritma ini menawarkan cara yang efisien untuk menemukan jawaban atas masalah yang terlalu rumit untuk dipecahkan secara tepat.

1947: Metode Simpleks untuk Pemrograman Linier . Solusi elegan untuk masalah umum dalam perencanaan dan pengambilan keputusan.

1950: Metode Iterasi Subruang Krylov . Suatu teknik untuk dengan cepat menyelesaikan persamaan linear yang berlimpah dalam perhitungan ilmiah.

1951: Pendekatan Dekomposisi untuk Komputasi Matriks . Serangkaian teknik untuk aljabar linear numerik.

1957: Kompiler Pengoptimasi Fortran . Mengubah kode tingkat tinggi menjadi kode yang dapat dibaca komputer yang efisien.

1959: Algoritma QR untuk Komputasi Nilai Eigen . Operasi matriks penting lainnya dibuat cepat dan praktis.

1962: Algoritma Quicksort untuk Penyortiran . Untuk penanganan database besar secara efisien.

1965: Transformasi Fourier Cepat . Mungkin algoritma yang paling umum digunakan saat ini, memecah bentuk gelombang (seperti suara) menjadi komponen periodik.

1977: Deteksi Hubungan Integer . Metode cepat untuk menemukan persamaan sederhana yang dipenuhi oleh koleksi angka yang tampaknya tidak berhubungan.

1987: Metode Multipole Cepat . Sebuah terobosan dalam berurusan dengan kompleksitas perhitungan n-tubuh, diterapkan dalam masalah mulai dari mekanika langit hingga pelipatan protein.

Secara pribadi saya akan mengganti Deteksi Hubungan Integer dengan PageRank .

PageRank, suka atau benci, tetapi ini memengaruhi keputusan dan tindakan jutaan orang di seluruh dunia yang menggunakan Google setiap hari.

Jika saya harus membuat daftar 3 algoritma paling penting yang digunakan hari ini di komputer, saya akan mengatakan:

1. Pencarian Biner
2. Quicksort
3. Algoritma Dijkstra

The Binary Search algoritma digunakan terus-menerus untuk mempersempit pada item dalam daftar diurutkan, sebagian besar indeks pencarian akan menggunakan sesuatu di sepanjang garis-garis ini di beberapa titik. Algoritma ini menyediakan pencarian daftar yang diurutkan dalam waktu (log n).

The Quicksort algoritma akhirnya berhasil mendapatkan semacam turun ke O (n log n) rata-rata kasus dan O (n ^ 2) kasus yang lebih buruk. Penyortiran adalah salah satu tugas data yang paling umum di komputer dan salah satu yang paling mahal, meningkatkan penyortiran kasus rata-rata adalah langkah besar dalam efisiensi.

Algoritma Dijkstra seperti telah dikatakan menghasilkan jalur terpendek antara titik-titik dalam grafik. Ini digunakan secara luas untuk semua jenis aplikasi perutean, yang paling luas berkenaan dengan internet itu sendiri memastikan bahwa jalur tercepat melalui web kusut router yang saling terhubung digunakan.

Teorema Bayes

Ini mungkin berkontribusi paling besar untuk menjaga jumlah spam yang membuang waktu di kotak masuk saya ke tingkat yang dapat dikelola.

Tentu saja, saya telah digunakan di banyak aplikasi berharga lainnya, tetapi membunuh SPAM adalah favorit saya.

TimSort

Ini adalah algoritma pengurutan yang sekarang digunakan dalam Python , Java 7 dan Android

Pada dasarnya:

• O (N log N) kasus terburuk (tidak merosot)
• O (N) untuk daftar yang hampir diurutkan (sebenarnya N-1persis pada daftar yang sudah diurutkan)

Dan keindahannya? Itu stabil ! Dan oleh karena itu cocok untuk penyortiran multipass sesuai dengan berbagai kriteria.

Omong-omong, jika ada yang memiliki implementasi C ++ yang dioptimalkan di tangan ...

Semua algoritma yang digunakan untuk menyelesaikan Masalah Visibilitas dalam Animasi Komputer 3D tampaknya penting bagi saya.

Algoritma Painter

Algoritma pelukis, juga dikenal sebagai isian prioritas, adalah salah satu solusi paling sederhana untuk masalah visibilitas dalam grafik komputer 3D. Saat memproyeksikan adegan 3D ke bidang 2D, pada titik tertentu perlu untuk memutuskan poligon mana yang terlihat, dan mana yang disembunyikan.

Z-buffering

Dalam grafik komputer, z-buffering adalah manajemen koordinat kedalaman gambar dalam grafik tiga dimensi (3-D), biasanya dilakukan dalam perangkat keras, kadang-kadang dalam perangkat lunak. Ini adalah salah satu solusi untuk masalah visibilitas, yang merupakan masalah menentukan elemen pemandangan yang diberikan yang terlihat, dan yang disembunyikan. Algoritma pelukis adalah solusi umum lain yang, meskipun kurang efisien, juga dapat menangani elemen adegan non-buram. Buffer-Z juga dikenal sebagai buffering dalam.

Penentuan permukaan yang tersembunyi

Dalam grafik komputer 3D, penentuan permukaan tersembunyi (juga dikenal sebagai penghapusan permukaan tersembunyi (HSR), oklusi culling (OC) atau penentuan permukaan yang terlihat (VSD) adalah proses yang digunakan untuk menentukan permukaan dan bagian permukaan mana yang tidak terlihat dari sudut pandang tertentu. Algoritma penentuan permukaan tersembunyi adalah solusi untuk masalah visibilitas, yang merupakan salah satu masalah utama pertama di bidang grafik komputer 3D. Proses penentuan permukaan tersembunyi kadang-kadang disebut bersembunyi, dan algoritma semacam itu kadang-kadang disebut penyembunyi. Analog untuk rendering garis adalah penghapusan garis tersembunyi, penentuan permukaan tersembunyi diperlukan untuk membuat gambar dengan benar, sehingga orang tidak dapat melihat melalui dinding dalam realitas virtual, misalnya.

Apapun yang Anda butuhkan untuk menyelesaikan masalah Anda saat ini.

Soundex adalah algoritma fonetik untuk mengindeks nama dengan suara.

Algoritma Viterbi

Awalnya digunakan untuk memecahkan kode kode koreksi kesalahan konvolusional, sekarang digunakan untuk memecahkan masalah pengenalan kelas yang luas (mulai dari pengenalan ucapan hingga bioinformatika). Anda dapat menemukannya di beberapa perangkat komunikasi dan penyimpanan.

MP3

Meskipun ini adalah istilah yang lebih umum daripada algoritma tertentu, saya akan menyebut MP3 sebagai agregasi dari berbagai algoritma dan teknik yang bekerja sama untuk menghasilkan format audio yang hilang ini.

Sudah pasti sangat signifikan di "era digital".

Integrasi numerik Runge-Kutta . Tanpanya banyak simulasi tidak akan mungkin terjadi. Tidak ada program luar angkasa, tidak ada tenaga nuklir, tidak ada balistik, tidak ada simulasi olahraga, tidak ada rompi anti peluru, tidak ada simulasi uji tabrakan, tidak ada simulasi gerakan fluida, tidak ada simulasi interaksi kimia, tidak ada bangunan tahan gempa ... daftar berjalan.

Algoritma penyortiran.

Quicksort

Penyisipan Sortir

Mudah diimplementasikan, sangat cepat pada daftar kecil dan digunakan dalam implementasi Merge Sort / Quicksort untuk mempercepatnya. Ini stabil, dan beroperasi di O (n) pada daftar yang diurutkan (ketika diurutkan dalam urutan menaik).

Gauss-Jordan dalam perhitungan matriks

Filter Kalman

Ini akan banyak digunakan dalam navigasi, pelacakan target (untuk hampir semua sensor: radar, sonar, FLIR, ladar). Satu buku teks menunjukkan aplikasi dalam pengontrol disk drive. Sistem kontrol robot sering menggunakan filter Kalman.

Bahasa lisan dan tulisan.

Mereka saat ini adalah salah satu algoritma yang paling efisien untuk mentransfer pengetahuan dari satu hal ke hal lainnya. Tanpa bahasa, masyarakat sipil tidak akan ada, dan informasi tidak dapat disampaikan.

The tumpukan struktur data dan algoritma yang terkait untuk konstruksi timbunan dan pemeliharaan.

Dan menunjukkan rasa hormat untuk quicksort. Bahkan jika itu tidak selalu menjadi pilihan, itu adalah salah satu algoritma mendasar dalam perkembangan historis ilmu komputer, dan merupakan kendaraan yang bagus untuk memahami rekursi dan analisis algoritma. Itu indah, dan ya, saya menyukainya.

Algoritma pengindeksan seperti B-tree, B + -tree, indeks hash, indeks pohon biner dll. Untuk mengindeks sejumlah besar data.

MapReduce sebagai cara untuk membagi, menaklukkan, dan memparalelkan pemrosesan set data besar.

Algoritma Brute Force!

Banyak orang meremehkan algoritma brute force ini. Sebenarnya itu sebagian besar digunakan untuk menyelesaikan masalah yang tidak memiliki pola. Saya sangat menyukainya!

Bubble Sort!

Bubble sort tidak seburuk Bogosort . Itu sebabnya saya memilih jenis Bubble.