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.


11
Pertanyaan bagus! [Edit:} Satu pertanyaan. Di mana kita menggambar garis antara algoritma dan struktur data? Bagaimana jika wawasan kunci untuk suatu algoritma terkait erat dengan struktur data (misalnya UNION FIND dalam fungsi Ackermann terbalik)?
Ross Snider

4
sumber hebat dan mungkin seorang kandidat untuk buku semacam itu adalah "Encyclopedia of Algorithms" springer.com/computer/theoretical+computer+science/book/…
Marcos Villagra

21
Saya sedikit terkejut bahwa algoritma yang saya anggap cukup rumit (KMP, linear suffix array) dianggap oleh orang lain sebagai "dari Buku." Bagi saya, "from the Book" berarti sederhana dan jelas, tetapi hanya dengan melihat ke belakang. Saya ingin tahu bagaimana orang lain mengartikan "elegan".
Radu GRIGore

49
@supercooldave Anda tidak harus percaya pada Tuhan, tetapi Anda harus percaya pada bukunya. ;-)
Ross Snider

10
Selama ceramah pada tahun 1985, Erd berkata, "Anda tidak harus percaya pada Tuhan, tetapi Anda harus percaya pada Kitab."
Robert Massaioli

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.


4
Agak membingungkan untuk menyadari bahwa itu adalah sesuatu yang tidak jelas pada suatu waktu dan hanya jelas sekarang karena mereka datang dengan itu dan kami mempelajarinya ... Saya pikir kita harus menerapkan teori sejarah Carr untuk Matematika dan Ilmu Komputer .
Ritwik Bose

1
Dengan uraian, saya akan mengatakan ini terkait dengan pencarian substring cepat Boyer-Moore.
bart

2
@Mechko Fakta bahwa algoritma ini ditemukan secara bersamaan dan independen oleh orang-orang yang terpisah merupakan indikasi bahwa hal itu jelas sampai batas tertentu. Apakah sesuatu itu "jelas" adalah fungsi dari kendala proyek dan lingkungan pemrograman yang lebih luas. Jika Anda memerlukan (1) pencarian teks cepat dan (2) Anda menyadari pentingnya algoritma O (n) yang sesungguhnya, dan (3) Anda pernah menemukan teks dengan kecocokan sebagian sebelumnya, dan (4) Anda punya waktu untuk melakukan hal-hal "benar", maka algoritma ini mungkin jelas.
Matt Gallagher

Dalam sebuah wawancara, Knuth mengatakan bahwa ide untuk algoritma tersebut berasal dari mempelajari otomat terbatas dua arah Stephen Cook untuk palindrom.
Kaveh

@Kaveh Silakan baca Bagian 7 (Catatan Sejarah) dari kertas KMP asli. Ini memiliki komentar yang bagus. Tentang Morris menulis editor teks yang "terlalu rumit untuk dipahami oleh pelaksana sistem lainnya". Tentang Knuth "pertama kali dalam pengalaman Knuth bahwa teori automata telah mengajarinya cara memecahkan masalah pemrograman nyata lebih baik daripada yang bisa dia pecahkan sebelumnya". Dan "Knuth dicekik untuk mengetahui bahwa Morris sudah menemukan algoritma, tanpa mengetahui teorema Cook;". MENYENANGKAN.
Hendrik

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.

3
Ini adalah salah satu algoritma favorit saya. Saya menyukai intuisi yang saya pelajari dari buku ketidaksesuaian Chazelle: himpunan median kelompok elemen seperti jaring untuk interval dalam daftar nomor input yang dipesan. Jadi algoritma mengikuti paradigma umum: hitung -net cepat, selesaikan masalah di internet, ulangi pada beberapa bagian input untuk menyaring solusi, sampai Anda memiliki solusi yang tepat. itu teknik yang sangat bergunaϵ ϵ1/ϵϵϵ
Sasho Nikolov

5
BTW begitu Anda menentukan ukuran kelompok, konstanta tidak begitu ajaib. mereka tentu saja dioptimalkan untuk memberikan hal yang benar dalam teorema Master
Sasho Nikolov

Implementasi Ruby, gist.github.com/chadbrewbaker/7202412 Apakah ada versi algoritma yang menggunakan ruang (konstan, log), atau apakah Anda harus menggunakan ruang awal linear untuk menahan median?
Chad Brewbaker

2
Klaim bahwa "ini hanya berfungsi karena angka-angka yang tepat untuk pas dalam teorema master" tidak sepenuhnya benar. Jika Anda mengganti angka dengan angka yang lebih besar , mudah untuk melihat bahwa dua angka yang harus dijumlahkan menjadi kurang dari konvergen menjadi dan , jadi semua cukup besar bekerja. hanyalah angka pertama yang berfungsi, bukan satu-satunya. n 1 3 / 4 0 n 55n13/40n5
Will Sawin

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


Saya akan mengganti elegan dengan intuitif. Tidak ada yang elegan tentang hal itu; kesederhanaannya adalah keindahan aslinya.
Robert Massaioli

@Robert Massaili: Saya menggantikan yang elegan dengan yang cantik. Anda benar tentang itu.
michalmocny

2
Dan sangat sulit untuk menulis dengan benar - lihat " Apakah Anda salah satu dari 10% programmer yang dapat menulis pencarian biner? "
jon

Dalam kursus algoritma lulusan pertama saya, kami memiliki 15 kuis menit di mana kami harus menyelesaikan 2-3 masalah dengan tangan. Kuis seperti pertama termasuk pohon pencarian biner dan dua pertanyaan tentang tumpukan. Saya merasa malu dan kecewa ketika mengetahui bahwa saya salah dalam mencari masalah biner, sebelum diberi tahu bahwa di kelas yang terdiri dari sekitar 30 orang ada dua jawaban yang benar. Tetapi bahkan mengetahui itu, fakta bahwa butuh 15 tahun bagi komunitas profesional untuk mendapatkan yang benar sangat mengejutkan.
Stella Biderman

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(n3)O(n2)


2
Algoritma ini juga dapat digeneralisasi dengan cara yang sangat rapi. Lihat misalnya r6.ca/blog/20110808T035622Z.html dan cl.cam.ac.uk/~sd601/papers/semirings.pdf
Mikhail Glushenkov


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.


10
Quicksort juga menimbulkan pertanyaan menarik tentang apa sebenarnya inti dari suatu algoritma. Misalnya implementasi standar Haskell yang elegan terlihat persis seperti definisi kode pseudo standar, tetapi memiliki kompleksitas asimptotik yang berbeda. Jadi, apakah Quicksort hanya tentang membagi-dan-menaklukkan atau apakah pintar-in-situ pointer-mengutak-atik bagian penting dari Quicksort? Dapatkah Quicksort bahkan diimplementasikan dalam pengaturan yang berfungsi murni atau apakah itu memerlukan kemampuan berubah-ubah?
Jörg W Mittag

2
Gagasan tentang "esensi" atau "moral" dari suatu algoritma tentu saja berasal dari makalah yang indah The Genuine Sieve of Eratosthenes oleh Melissa E. O'Neill ( cs.hmc.edu/ ~ oneill / papers / Sieve-JFP. pdf ) dan diskusi quicksort berasal dari diskusi LtU dari makalah itu ( lambda-the-ultimate.org/node/3127 ), secara khusus dimulai dari komentar ini: lambda-the-ultimate.org/node/3127/#comment-45549
Jörg W Mittag

8
@ Jörg: Menerapkan quicksort pada daftar tertaut benar-benar masuk akal, dan memiliki waktu berjalan asimptotik yang sama dengan implementasi in-place pada array (heck, bahkan implementasi out-of-place yang naif pada array memiliki waktu berjalan yang sama) - keduanya aktif rata-rata dan dalam kasus terburuk. Adapun penggunaan ruang, ini memang berbeda tetapi harus dikatakan bahwa bahkan "di tempat" versi memerlukan ruang ekstra tidak konstan (panggilan stack!), Sebuah fakta yang mudah diabaikan.
Konrad Rudolph

Juga perlu disebutkan Duals Pivot Quicksort karya Vladimir Yaroslavskiy. Itu harus setidaknya 20% lebih cepat lebih cepat. Quicksort asli permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/…
SaveTheRbtz

Quicksort secara teori sederhana (dapat diuraikan dalam 4 langkah) dan bisa sangat dioptimalkan, tetapi dalam praktiknya sangat sulit untuk kode dengan benar. Itu sebabnya tidak mendapatkan suara saya.
Dennis


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.


Ini seharusnya sudah disarankan sejak lama! Terima kasih!
arnab

1
Ada beberapa algoritma acak lainnya yang pantas mendapat tempat menonjol dalam Buku. Untuk ini kontras antara alternatif deterministik dan probabilistik kurang mencolok: algoritma deterministik biasanya ada tetapi jauh lebih rumit.
Per Vognsen

Saya secara mandiri menemukan algoritma yang sama ketika saya sedang mengerjakan kertas beberapa tahun yang lalu sampai seseorang bertanya kepada saya bukankah itu Schwartz-Zippel lemma? Dan saya berkata, apa itu? :)
Helium

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?


1
Ini juga merupakan dasar dari eksekusi Prolog!
muad

1
Apa gunanya BFS dengan tumpukan yang saya lewatkan? Saya akan berpikir bahwa jawabannya adalah "ya, Anda mendapatkan DFS".
Omar Antolín-Camarena

1
Yah, semua orang tampaknya menganggap masalah ini sepele. Juga, semua orang tampaknya berpikir jawabannya adalah "ya", yang salah. Jawabannya sebenarnya "tergantung pada implementasi BFS mana Anda mulai". Lihat cs.stackexchange.com/questions/329/… (Ini adalah pertanyaan yang saya posting untuk membantu fase beta CS.SE)
Radu GRIGore

Ini juga dibahas secara singkat di sini: ics.uci.edu//~eppstein/161/960215.html
Radu GRIGore

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.


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



Algoritma Strassen untuk perkalian matriks.


Mungkin akan menunggu sampai kita tahu apakah itu optimal.
Thomas Ahle

Itu tidak optimal, setidaknya, tanpa gejala ... Saya pikir bahwa dengan memasukkan algoritma Strassen memaksa Anda untuk memasukkan algoritma Karatsuba terlebih dahulu.
Timothy Sun


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


Saya tidak berpikir bahwa itu telah menerima pengakuan yang layak - apa yang membuat Anda berpikir sebaliknya? Misalnya, ini diterapkan di pustaka analisis urutan C ++ SeqAn.
Konrad Rudolph

Perlu disebutkan bahwa sekarang ada sejumlah algoritma konstruksi susunan sufiks waktu linear dan non linier lainnya yang, meskipun tidak cukup cantik, mungkin dalam praktiknya jauh lebih cepat. "Pendekatan efisien, serbaguna untuk pemilahan sufiks", Journal of Experimental Algorithmics (JEA), Volume 12, Juni 2008 memiliki beberapa hasil eksperimental di sepanjang garis ini.
Raphael

@ Raphael: Saya agak waspada dengan kenyataan bahwa pada hal. 3 dari makalah JEA itu, mereka hanya memberikan apa yang mereka "yakini" adalah batasan "longgar" dari O (n ^ 2 log n) ... Apakah Anda tahu makalah dengan algoritma waktu linear yang terbukti yang lebih cepat dalam praktik daripada Algoritma Miring?
user651

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


BTW, apa urutan generalisasi, dan di mana algoritma Buchberger untuk Grobner masuk ke dalamnya? (Tampaknya analog dengan Knuth-Bendix, tetapi saya telah melihat sebutan di suatu tempat bahwa itu semacam menggeneralisasi eliminasi Gaussian ...)
ShreevatsaR

6
urutannya adalah: Euclidean GCD -> Gaussian Elimination -> Buchberger -> Knuth-Bendix. Satu juga dapat dimasukkan ke dalam (bukan Gaussian Elimination) divisi polinomial univariat dan modulo (dalam urutan generalisasi itu 'terpisah' dari Gaussian Elimination, GE adalah multivariat derajat 1, cincin polinomial adalah derajat tidak terbatas univariat, Buchberger's adalah gelar tak terbatas multivariat. The lompatan generalisasi terbesar dari EGCD ​​ke GE atau ring polinomial karena penambahan variabel, dan kemudian juga besar dari Buchberger ke KB karena tanda tangan tak terbatas
Mitch

+1: Algoritma Euclidean memecahkan persamaan ax-by = 1 yang paling terkenal dalam matematika. Mengapa itu tidak muncul di CS lebih sering adalah sebuah misteri.
Tegiri Nenashi

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.


4
Teorema 4: ... Bukti: berolahraga untuk pembaca.
jon

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.


6
Apakah Anda tahu algoritma bodoh yang menyelesaikan masalah dengan asimptotik yang sama dan mengikuti pola desain algoritmik? Saya berbicara tentang pendalaman berulang. Dalam iterasi ke-n Anda mulai pada penerus ke-2 dari akar dan mencari penerus ke-2 untuk mencari pengulangan. Meskipun Anda menelusuri kembali beberapa langkah Anda dengan setiap iterasi, laju pertumbuhan geometris dari jari-jari pencarian berarti bahwa itu tidak mempengaruhi asimptotik.
Per Vognsen

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.


6
Ya, algoritma yang sangat bagus. Kurang sepele, pada biaya faktor lain dari 2, algoritma ini juga bekerja untuk memaksimalkan setiap fungsi submodular, bukan hanya fungsi grafik dipotong. Ini adalah hasil dari Feige, Mirrokni, dan Vondrak dari FOCS 07
Aaron Roth

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.


Memang, ada juga banyak algoritma perkiraan sederhana dan elegan lainnya dengan jaminan perkiraan yang layak.
Janne H. Korhonen



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

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


Dan memang, beberapa hadiah Nobel diberikan untuk memajukan pemahaman kita tentang masalah ini.
Ross Snider

@Ross Kantorovich memenangkan hadiah Nobel dalam bidang Ekonomi karena menciptakan LP dan menerapkannya pada alokasi sumber daya. Hadiah apa lagi yang Anda pikirkan?
Mark Reitblatt

@Mark Koopermans dianugerahi hadiah nobel bersama Kantorovich, tetapi saya masih belum akurat untuk mengatakan "beberapa."
Ross Snider

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 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.


10
Tunggu, mungkin itu indah, tetapi jika butuh Knuth dua hari penuh untuk memahaminya, apakah ini benar-benar "dari buku"?
ShreevatsaR

@ShreevatsaR Buku ini memiliki cetakan yang bagus di catatan kaki :)
hsmyers
Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.