Algoritma dari Kitab.

Paul Erdos berbicara tentang "Buku" di mana Tuhan menyimpan bukti paling elegan dari setiap teorema matematika. Ini bahkan mengilhami buku (yang saya percaya sekarang dalam edisi ke-4): Bukti dari Buku .

Jika Tuhan memiliki buku yang serupa untuk algoritma, menurut Anda algoritma apa yang akan dijadikan kandidat?

Jika memungkinkan, berikan juga referensi yang dapat diklik dan wawasan kunci yang membuatnya berfungsi.

Tolong, hanya satu algoritma per jawaban.

Union-find adalah masalah yang indah yang algoritma / datastructure terbaiknya ( Disjoint Set Forest ) didasarkan pada tumpukan spaghetti. Meskipun sangat sederhana dan cukup intuitif untuk dijelaskan kepada anak yang cerdas, butuh beberapa tahun untuk mendapatkan ikatan yang kuat pada runtime-nya. Pada akhirnya, perilakunya ditemukan terkait dengan Fungsi Ackermann terbalik, sebuah fungsi yang penemuannya menandai pergeseran perspektif tentang perhitungan (dan pada kenyataannya dimasukkan dalam Hilbert's On the Infinite ).

Wikipedia menyediakan pengantar yang bagus untuk Disjoint Set Forests .

Pencocokan string Knuth-Morris-Pratt . Delapan baris kode paling licin yang pernah Anda lihat.

Algoritma Blum, Floyd, Pratt, Rivest, dan Tarjan untuk menemukan k th unsur daftar disortir dalam waktu linear adalah algoritma yang indah, dan hanya bekerja karena jumlahnya tepat untuk cocok Master Teorema. Bunyinya sebagai berikut:

1. Urutkan setiap urutan lima elemen.
2. Pilih median di masing-masing.
3. Berulang untuk menemukan median daftar ini.
4. Berputar di median median (seperti di Quicksort)
5. Pilih sisi yang tepat dari daftar dan posisi dalam daftar itu, dan ulangi.

Binary Search adalah algoritma paling sederhana, indah, dan berguna yang pernah saya temui.

Saya terkejut tidak melihat algoritma Floyd-Warshall untuk semua-pasangan jalur terpendek di sini:

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

$O(n^3)$$O(n^2)$

Algoritma Euclidean untuk menghitung pembagi umum terbesar (GCD)

Mungkin terlihat agak sepele (terutama dibandingkan dengan jawaban lain), tapi saya pikir Quicksort sangat elegan. Saya ingat ketika saya pertama kali melihatnya saya pikir itu benar-benar rumit, tetapi sekarang tampaknya terlalu sederhana.

Pengodean Huffman untuk kompresi data.

The tes primality Miller-Rabin (dan tes serupa) harus dalam The Book. Idenya adalah untuk mengambil keuntungan dari sifat-sifat bilangan prima (yaitu menggunakan teorema kecil Fermat) untuk secara probabilistik mencari saksi untuk nomor yang tidak menjadi bilangan prima. Jika tidak ada saksi yang ditemukan setelah tes acak yang cukup, jumlah tersebut diklasifikasikan sebagai prima.

Pada catatan itu, tes primality AKS yang menunjukkan PRIMES ada di P pastinya ada di The Book!

Pengujian identitas polinomial dengan lemma Schwartz-Zippel :

Jika seseorang membangunkan Anda di tengah malam dan meminta Anda untuk menguji dua ekspresi polinomial univariat untuk identitas, Anda mungkin akan menguranginya menjadi jumlah bentuk normal produk dan membandingkannya dengan identitas struktural. Sayangnya, pengurangan bisa memakan waktu eksponensial; itu analog dengan mengurangi ekspresi Boolean menjadi bentuk normal disjungtif.

Dengan asumsi Anda adalah jenis yang suka algoritma acak, upaya Anda berikutnya mungkin akan mengevaluasi polinomial pada titik yang dipilih secara acak untuk mencari contoh tandingan, menyatakan polinom sangat mungkin identik jika mereka lulus tes yang cukup. Lemma Schwartz-Zippel menunjukkan bahwa ketika jumlah poin bertambah, peluang positif palsu berkurang dengan sangat cepat.

Tidak ada algoritma deterministik untuk masalah yang diketahui yang berjalan dalam waktu polinomial.

Pencarian Pertama Kedalaman . Ini adalah dasar dari banyak algoritma lainnya. Hal ini juga akalan sederhana: Misalnya, jika Anda mengganti antrian dalam implementasi BFS oleh stack, Anda mendapatkan DFS?

Algoritma Dijkstra : masalah jalur terpendek sumber tunggal untuk grafik dengan biaya jalur tepi tidak negatif. Ini digunakan di mana-mana, dan merupakan salah satu algoritma paling indah di luar sana. Internet tidak dapat dialihkan tanpa itu - itu adalah bagian inti dari protokol routing IS-IS dan OSPF (Open Shortest Path First).

1. Tetapkan nilai jarak untuk setiap simpul. Setel ke nol untuk simpul awal kami dan hingga tak terhingga untuk semua simpul lainnya.
2. Tandai semua node sebagai belum dikunjungi. Atur simpul awal sebagai arus.
3. Untuk simpul saat ini, pertimbangkan semua tetangganya yang belum dikunjungi dan hitung jarak tentatifnya (dari simpul awal). Misalnya, jika simpul saat ini (A) memiliki jarak 6, dan tepi yang menghubungkannya dengan simpul lain (B) adalah 2, jarak ke B melalui A akan menjadi 6 + 2 = 8. Jika jarak ini kurang dari jarak yang direkam sebelumnya (tak terhingga di awal, nol untuk simpul awal), timpa jarak tersebut.
4. Ketika kita selesai mempertimbangkan semua tetangga dari simpul saat ini, tandai sebagai dikunjungi. Node yang dikunjungi tidak akan diperiksa lagi; jarak yang direkam sekarang adalah final dan minimal.
5. Jika semua node telah dikunjungi, selesai. Jika tidak, atur simpul yang belum dikunjungi dengan jarak terkecil (dari simpul awal) sebagai "simpul saat ini" berikutnya dan lanjutkan dari langkah 3.

The Sieve of Eratosthenes , sederhana & intuitif.

Saya juga suka keindahan Algoritma Horner .

Skema Enkripsi Homomorfik Sepenuhnya Gentry (baik di atas kisi-kisi ideal atau di atas bilangan bulat) sangat indah. Ini memungkinkan pihak ketiga untuk melakukan perhitungan sewenang-wenang pada data terenkripsi tanpa akses ke kunci pribadi.

Skema enkripsi ini disebabkan oleh beberapa pengamatan yang tajam.

• Untuk mendapatkan skema enkripsi sepenuhnya homomorfik, seseorang hanya perlu memiliki skema yang homomorfik atas penambahan dan perkalian. Ini karena penambahan dan perkalian (mod 2) sudah cukup untuk mendapatkan gerbang AND, OR dan NOT (dan karenanya Turing Completeness).
• Bahwa jika skema semacam itu diperoleh, tetapi karena beberapa batasan hanya dapat dieksekusi untuk rangkaian dengan kedalaman yang terbatas, maka seseorang dapat secara homomorfis mengevaluasi prosedur dekripsi dan reencyption untuk mengatur ulang batasan kedalaman sirkuit tanpa mengorbankan privasi kunci.
• Bahwa dengan "menekan" kedalaman versi sirkuit dari fungsi dekripsi untuk skema, seseorang dapat mengaktifkan skema yang semula terbatas hingga, sirkuit dangkal sejumlah perhitungan acak.

Dalam tesisnya, Craig Gentry memecahkan masalah terbuka lama (dan indah) dalam kriptografi. Fakta bahwa ada skema homomorfis sepenuhnya menuntut kita mengakui bahwa ada beberapa struktur yang melekat pada kemampuan komputasi yang mungkin kita abaikan.

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

The Cooley-Tukey Algoritma FFT .

Algoritma Strassen untuk perkalian matriks.

The Gale-Shapley algoritma pernikahan yang stabil . Algoritma ini serakah dan sangat sederhana, pada awalnya tidak jelas mengapa itu akan berhasil, tetapi kemudian bukti kebenarannya lagi mudah dipahami.

Algoritme waktu linier untuk membangun susunan sufiks benar-benar indah, meskipun tidak benar-benar menerima pengakuan yang layak untuknya. Http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

Eliminasi gaussian. Ini melengkapi urutan generalisasi dari algoritma Euclidean GCD ke Knuth-Bendix.

Saya terkesan ketika saya pertama kali melihat algoritma untuk pengambilan sampel reservoir dan buktinya. Ini adalah tipe puzzle "asah otak" yang khas dengan solusi yang sangat sederhana. Saya pikir itu pasti milik buku, baik untuk algoritma maupun untuk teorema matematika.

Adapun buku itu, ceritanya bahwa ketika Erdös meninggal dan pergi ke surga, ia meminta untuk bertemu dengan Tuhan. Permintaan itu dikabulkan dan untuk pertemuan itu Erdös hanya punya satu pertanyaan. "Bolehkah aku mencari di buku?" Tuhan berkata ya dan memimpin Erdös ke sana. Tentu sangat bersemangat, Erdös membuka buku hanya untuk melihat yang berikut ini.

Teorema 1: ...
Bukti: Jelas.

Teorema 2: ...
Bukti: Jelas.

Teorema 3: ...
Bukti: Jelas.

Algoritma Kura - kura dan Kelinci . Saya suka karena saya yakin bahwa bahkan jika saya menghabiskan seluruh hidup saya untuk menemukannya, tidak mungkin saya akan menghasilkan ide seperti itu.

Sebuah contoh yang fundamental dan "sepele" seperti bukti Euclid tentang bilangan prima yang tak terhingga banyaknya:

2-aproksimasi untuk MAX-CUT - Secara independen untuk setiap simpul, tetapkan ke salah satu dari dua partisi dengan probabilitas yang sama.

Saya selalu menyukai Algoritma Christofides yang memberikan (3/2) -roksimasi untuk metrik TSP. Sebenarnya, panggil aku mudah untuk menyenangkan, tapi aku bahkan menyukai algoritma 2-aproksimasi yang datang sebelumnya . Trik Christofides untuk membuat pohon spanning minimum Eulerian dengan menambahkan pencocokan simpul derajat anehnya (alih-alih menduplikasi semua sisi) adalah sederhana dan elegan, dan hanya perlu sedikit meyakinkan bahwa pencocokan ini tidak lebih dari setengah beratnya. dari tur yang optimal.

Gabungkan Sortir . Sederhana, elegan, efisien.

$O(\sqrt N)$

Algoritma untuk pemrograman linier : Simplex, Ellipsoid, dan metode titik interior.

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Algoritma Robin Moser untuk memecahkan kelas tertentu instance SAT. Contoh seperti itu dipecahkan oleh Lovasz Local Lemma. Algoritma Moser memang merupakan de-pengacakan dari pernyataan lemma.

Saya pikir itu adalah beberapa tahun algoritmanya (dan teknik untuk pembuktian kebenarannya) akan dicerna dengan baik dan disempurnakan hingga menjadi kandidat yang layak untuk Algoritma dari Buku .

Versi ini merupakan perpanjangan dari karya aslinya, ditulis dengan Gábor Tardos.

Algoritma Marcus Hutter yang Tercepat dan Terpendek untuk Semua Masalah yang Didefinisikan Dengan Baik .

Semacam ini bertentangan dengan semangat persembahan lain dalam daftar ini, karena itu hanya kepentingan teoritis dan tidak praktis, tetapi sekali lagi judul semacam mengatakan itu semua. Mungkin itu harus dimasukkan sebagai kisah peringatan bagi mereka yang hanya akan melihat perilaku asimptotik dari suatu algoritma.

Algoritma X dari Knuth menemukan semua solusi untuk masalah sampul yang tepat . Apa yang begitu ajaib tentang itu adalah teknik yang ia usulkan untuk menerapkannya secara efisien: Dancing Links .

Saya pikir kita harus memasukkan Schieber-Vishkin , yang menjawab pertanyaan leluhur umum terendah dalam waktu konstan, preprocessing hutan dalam waktu linear.

Saya suka eksposisi Knuth di Volume 4 Fascicle 1, dan renungannya . Dia mengatakan butuh dua hari penuh untuk memahaminya, dan saya ingat kata-katanya:

Saya pikir itu cukup indah, tetapi luar biasa itu mendapat pers yang buruk dalam literatur (..) Ini didasarkan pada matematika yang menggairahkan saya.