Algoritma probabilistik (acak) sebelum ilmu komputer "modern" muncul

27

Sunting: Saya memilih jawaban dengan skor tertinggi pada 06 Desember 2012.

Ini pertanyaan lembut.

Konsep algoritma (deterministik) kembali ke SM. Bagaimana dengan algoritma probabilistik?

Dalam entri wiki ini , algoritma Rabin untuk masalah pasangan terdekat dalam geometri komputasi diberikan sebagai algoritma acak pertama (tahun ???). Lipton memperkenalkan algoritma Rabin sebagai awal era modern dari algoritma acak di sini , tetapi bukan sebagai yang pertama. Saya juga tahu banyak algoritma untuk automata terbatas probabilistik (model komputasi yang sangat sederhana) ditemukan selama 1960-an.

Apakah Anda tahu algoritma probabilistik / acak (atau metode) bahkan sebelum tahun 1960-an?

atau

Temuan mana yang dapat dilihat sebagai algoritma probabilistik / acak pertama?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
sumber
25
Gagasan kuno untuk mencicipi sesendok sup mendidih untuk mengecek apakah rasanya benar pada dasarnya adalah sampling acak, suatu algoritma probabilistik dengan jaminan yang terbukti.
arnab
3
Algoritma Rabin diterbitkan pada tahun 1976, jauh setelah ilmu komputer "modern" telah mapan.
Jeffε
Bisakah Anda mengklarifikasi jika ada kriteria yang ingin Anda terapkan pada "algoritma", untuk memperjelas apakah Anda berpikir misalnya bahwa fenomena alam yang mendahului umat manusia oleh miliaran tahun mewakili "algoritma", seperti yang disarankan oleh beberapa tanggapan di bawah?
Niel de Beaudrap
@NieldeBeaudrap: Apa yang ada dalam pikiran saya adalah beberapa algoritma yang didefinisikan secara matematis (Tapi, secara pribadi, saya sangat suka jawaban arnab :))
Abuzer Yakaryilmaz

Jawaban:

33

Ini dibahas sedikit dalam makalah saya dengan HC Williams, "Factoring Integers before Computers"

Dalam sebuah makalah 1917, HC Pocklington membahas algoritma untuk menemukan sqrt (a), modulo p, yang bergantung pada pemilihan elemen secara acak untuk mendapatkan nonresidue dari bentuk tertentu. Di dalamnya, ia berkata, "Kita harus melakukan ini [menemukan nonresidue] dengan persidangan, menggunakan Hukum Timbal Balik Quadratic, yang merupakan cacat dalam metode ini. Tetapi untuk setiap nilai u setengah nilai t cocok, seharusnya tidak ada kesulitan dalam menemukan satu. "

Jadi ini adalah salah satu dari penyebutan eksplisit pertama dari algoritma acak.

Jeffrey Shallit
sumber
3
Ini adalah referensi yang sangat bagus. Apakah Algoritma Pocklington sejak itu telah diacak? Intinya, saya suka pekerjaan Anda - baik di dalam maupun di luar CS - khususnya algoritma Anda untuk dugaan Bachet (makalah itu sulit untuk menemukan salinannya!) Tetapi juga kebebasan sipil Anda berfungsi. Pernahkah Anda menonton "Tuan Kematian?"
Ross Snider
menarik. ini mengingatkan pada pengujian primitif acak
Sasho Nikolov
3
Dan algoritma Las Vegas juga! Referensi yang bagus.
David Eppstein
Referensi yang sangat bagus.
Jérémie
berbicara tentang anjak di depan komputer, apakah ada yang tahu apa yang diketahui Lehmer tentang algoritma pocklington, atau algoritma acak lainnya, atau apakah Lehmer benar-benar pernah menerapkannya pada komputer anjak saringannya ? keduanya tampaknya memiliki beberapa hubungan dengan tes primality Pocklington-Lehmer menurut wikipedia
vzn
28

Algoritma jarum buffons untuk mengestimasi , pada dasarnya metode Monte Carlo , akan dipublikasikan pada tahun 1777. catat bahwa metode Monte Carlo dimulai pada tahun 1940-an dengan proyek bom atom "Manhattan" AS & ditimbun oleh Ulam, Von Neumann, dan Metropolis.π

ay
sumber
8
Sebenarnya ini terkait dengan pertanyaan yang saya ajukan . Tidak ada yang tahu persis siapa yang merancang algoritma yang banyak orang ambil sebagai jarum Buffon saat ini.
Jérémie
dinyatakan lebih tepatnya— ada algoritma jarum Buffon yang jelas yang melibatkan menjatuhkan jarum pada garis-garis, dan algoritma "titik acak vs lingkaran" yang tampaknya jauh berbeda seperti yang Anda sebutkan dalam pertanyaan yang beberapa orang keliru mengaitkan dengan Buffon, dengan perbedaan, lebih banyak asal modern, tetapi tidak pasti.
vzn
19

The Metropolis-Hastings algoritma diterbitkan pada tahun 1953 dan tanggal kembali lebih awal untuk proyek Manhattan, jauh sebelum Rabin. Seperti banyak metode acak awal yang diberikan dalam jawaban lain, itu adalah algoritma Monte Carlo.

Mungkinkah klaim pada halaman Wikipedia adalah bentuk klaim yang kacau bahwa Rabin adalah algoritma Las Vegas pertama ?

David Eppstein
sumber
11

The Gaussian yang normal kurva / distribusi statistik dapat "dihitung" oleh banyak proses fisik yang sangat sederhana. Salah satu yang paling sederhana adalah papan dengan pin array dalam kotak segitiga (juga dikenal sebagai "kotak Galton" berasal dari tahun 1800-an) di mana pin diimbangi jarak 1/2 persegi pada baris bergantian. Menjatuhkan bola berulang kali dari posisi yang sama, bola-bola secara acak bergeser ke kiri atau kanan dengan probabilitas 0,5. Distribusi kumulatif yang dicatat pada posisi bawah menghasilkan kurva Gaussian / normal.

vzn
sumber
+1 hanya karena saya sedang merancang logo untuk grup riset statistik kami dan Galton Box adalah ide pertama kami (tetapi ternyata terlalu kompleks untuk sebuah logo).
Konrad Rudolph
10

Menurut pendapat saya, evolusi alami adalah algoritma probabilistik yang baik dan agak lama :-)

Marzio De Biasi
sumber
1
+1 meskipun deskripsi proses sebagai probabilistik kami jauh lebih baru. ;-)
Konrad Rudolph
7
"Algoritma" menunjukkan bahwa ada masalah yang coba dipecahkannya; tapi ternyata tidak. Bahkan tidak "mencoba" untuk membuat hewan yang lebih baik bertahan hidup; menciptakan hewan yang disesuaikan dengan lingkungannya hanyalah produk sampingan (sesuatu yang tidak selalu tercapai, seperti yang ditunjukkan oleh kepunahan dan kepunahan massal). Dalam hal ini, evolusi tidak lebih dari algoritma daripada gravitasi; hanya saja ini yang terjadi.
Niel de Beaudrap
MDB sudah mati! evolusi adalah algoritma genetika yang memilih untuk kebugaran evolusioner dan ilmu pengetahuan masih mengejar semua implikasi dari ini .... yaitu bidang penelitian yang aktif. itu belum banyak ditunjukkan atau dihargai secara luas, tetapi keberhasilan fenomenal GA di CS sebenarnya adalah bukti matematika / ilmiah yang kuat dari realitas teori evolusi biologis. Namun, mengakui itu pasti berbeda dari "algoritma" lainnya dalam beberapa cara kunci.
vzn
2
@vzn: "algoritma genetika", pertama-tama, memilih untuk fungsi kebugaran yang kami berikan untuk tujuan tertentu. Kami menggunakan evolusi sebagai alat untuk melakukan sesuatu dalam kasus itu. Tetapi itu tidak berarti bahwa evolusi biologis adalah suatu algoritma untuk melakukan apa saja. Menggunakan analogi gravitasi lagi, adakah arti yang bermakna di mana semua air terjun adalah algoritma, hanya karena kita kadang-kadang menggunakan air terjun untuk menghasilkan listrik?
Niel de Beaudrap
4
@ vzn: Saya hanya menyatakan bahwa "suatu algoritma" harus melibatkan parameter probabilitas keberhasilan yang terdefinisi dengan baik, belum lagi bahwa harus ada agen yang melaksanakannya . Satu-satunya 'agen' yang bisa dikatakan melakukan "evolusi" adalah seluruh ekosistem. Apa yang harus kita katakan bahwa ekosistem "berusaha" untuk mencapainya? Saya dengan mudah mengatakan bahwa Anda adalah sifat antropomorfisasi . Saya hanya menuntut bahwa "menerapkan suatu algoritma" memerlukan sejumlah intensionalitas berorientasi tujuan, diterapkan oleh manusia atau tidak. Dalam arti apa suatu proses tanpa tujuan dapat mewakili suatu "algoritma"?
Niel de Beaudrap
6

Ada sebuah makalah tentang algoritma acak dalam budaya 'primitif' .

Menggunakan nubuat (misalnya tulang ayam, batu) untuk memutuskan di mana berburu dapat dilihat sebagai algoritma acak. Orang dapat berargumen bahwa mengacak tempat perburuan mencegah adaptasi dan perburuan berlebihan.

adrianN
sumber
0

salah satu makalah "keajaiban" Einstein tahun 1905 adalah tentang gerak brown , contoh fisik klasik dari jalan acak dan menghasilkan rumus (yaitu, pada dasarnya sebuah algoritma, jika proses fisik adalah "komputer") untuk memperkirakan / menghitung partikel (molekul) diameter diberikan konstanta fisik lainnya yang diketahui dan pengamatan / pengukuran perpindahan partikel (acak) dari waktu ke waktu. makalah ini juga berfungsi sebagai bukti teoritis / eksperimental / dasar awal untuk teori atom materi.

ay
sumber
4
Lagi-lagi dengan evolusi: meskipun gerakannya mungkin acak, dan mungkin dimodelkan dengan jalan acak, algoritma apa yang dilambangkannya? Sementara beberapa algoritma menggunakan walks acak, ini tidak berarti bahwa semua walks acak mewakili algoritma (lebih dari string kata apa pun dalam bahasa Inggris mewakili prosa hanya karena semua prosa bahasa Inggris terdiri dari kata-kata dalam bahasa Inggris).
Niel de Beaudrap
-4

jawaban lain sesuai dengan arah teori bilangan JS. salah satu komputer analog-digital paling awal yang dibangun adalah saringan Lehmer yang berasal dari ~ 1932, mendahului komputer elektronik sekitar satu dekade. itu pada dasarnya menghitung sisa mod divisi untuk jumlah terbatas dan menerapkan sisa cina thm . untuk angka yang lebih besar itu menghitung jawaban probabilistik untuk pertanyaan teori bilangan termasuk anjak piutang. walaupun terminologi pada saat itu mungkin tidak merujuk pada "algoritma probabilistik" itu mungkin digunakan dengan cara ini dalam beberapa kasus. (dengan cara ini juga memiliki beberapa kemiripan dengan tes prime probabilistic Fermat.)n inini

mesin juga memiliki beberapa kesamaan dengan mesin diferensial Babbage (~ 1830-an). itu tidak sepenuhnya tak terbayangkan bahwa Babbage atau Lovelace mungkin telah membayangkan sesuatu yang mirip dengan algoritma probabilistik. mesin-mesin itu tentu saja dapat digunakan untuk mengimplementasikan algoritma probabilistik, meminjam teori modern dan menempatkannya di masa lalu.

[1] Mesin anjak Lehmer

[2] Mesin Babbage


Lehmer mod n & mesin anjak piutang

vzn
sumber
1
Bisakah Anda menggambarkan arti perhitungan jawaban probabilistik untuk jumlah besar? Pencarian cepat sepertinya saya tidak bisa menemukan referensi ke online itu.
Niel de Beaudrap
Pemahaman saya, digunakan [di antara tujuan lain] untuk menemukan faktor yang lebih kecil dari jumlah tes besar mirip dengan ayakan eratosthenes. jika jumlah besar berlalu, itu "mungkin bukan komposit" atau "mungkin prima" atau "kandidat utama". sayangnya internet tidak terlalu bagus dengan referensi sejarah & asal [bahkan wikipedia], buku lebih baik. lebih detail di bagian bawah halaman ini , "jenis masalah yang berusaha diselesaikan oleh Lehmer " oleh Dr mike williams, kepala kurator museum sejarah komputer CA
vzn
1
mesin tentu saja dapat digunakan untuk mengimplementasikan algoritma probabilistik - Jadi? Berbeda dengan mesin lain yang tidak bisa?
Jeffε
2
meskipun terminologi pada saat itu mungkin tidak merujuk pada "algoritma probabilistik" itu mungkin digunakan dengan cara ini dalam beberapa kasus - [rujukan?] Jika Anda memiliki bukti bahwa "mungkin prima" adalah pernyataan formal tentang probabilitas, dan bukan sekadar deskripsi heuristik, harap sebutkan. Kalau tidak, harap berhenti berspekulasi.
Jeffε
dont memiliki isi penuh makalah Lehmers yang tersedia (bahkan tidak yakin apa yang dia terbitkan), tetapi referensi acak pocklington didukung oleh satu baris dari salah satu makalahnya. apa kriterianya? tampaknya semua yang diperlukan bahwa Lehmer menjalankan mesin pada beberapa nomor lebih besar dari untuk terbesar pada mesin, dan membuat semacam pengamatan yang masuk akal tentang hasilnya, belum tentu dituliskan .... tampaknya masuk akal bagi saya .... xn1∗n2∗n3∗nxx
vzn
-6

berikut adalah beberapa kasus konsep awal dan bahkan kuno / prasejarah terkait dengan algoritma acak.

  • pertimbangkan Saringan Eratosthenes, kira-kira berumur 2 milenia. agak tersirat dalam algoritma akan menjadi ide "berhenti lebih awal" dalam menandai interval prima, sebelum semua interval hingga telah ditandai. jelas bahwa interval "nanti" yang lebih panjang lebih kecil kemungkinannya untuk menandai angka yang diberikan dalam pertimbangan. dengan kata lain, ini merupakan visualisasi kasar dari fakta dasar teori bilangan bahwa "sebagian besar bilangan komposit memiliki faktor kecil" dan bahwa pengujian sekelompok faktor kecil sudah cukup untuk mengesampingkan banyak bilangan komposit. konsep ini mungkin akan dipahami oleh orang Yunani.n/2

  • permainan kebetulan dan judi sangat kuno. dari teori modern, game memiliki kesamaan kuat jika tidak koneksi langsung ke algoritma. judi / permainan dadu diketahui berusia setidaknya lima milenia .

  • orang-orang Yunani & Romawi juga memiliki konsep menggambar sedotan di mana orang yang menggambar sedotan tersingkat hilang. mirip dengan dadu, ini dalam arti algoritma yang paling sederhana untuk membuat pilihan acak tunggal.

  • pengungkapan penuh, ada sedikit sejarah dan koneksi berdarah. dalam jawaban lain MDB menyebutkan evolusi . bagian dari evolusi adalah seleksi alam yang juga memiliki kesamaan dengan peperangan manusia - tampaknya merupakan bagian intrinsik dari evolusi kota / masyarakat manusia. dalam arti tertentu perang adalah algoritma semi-acak kasar untuk "sesuatu" yang masih diperdebatkan oleh para sosiolog & sejarawan tentang penyebab pasti. pencurian / penjarahan? mengalokasikan sumber daya? wilayah? kekuatan politik? budak? (dll.) bangsa Romawi juga memiliki praktik mengerikan yang disebut penghancuran(kata modern sebenarnya berasal dari etimologi dari kata kuno!) di mana, sebagai hukuman untuk pemberontakan atau pengecut, setiap prajurit ke-10 yang dipilih secara acak dieksekusi oleh tentara yang tersisa. ini mungkin tampak sebagai praktik yang dilupakan dan atavistik, tetapi tampaknya memiliki paralel dengan rolet Rusia modern , permainan kuasi acak "modern" untuk bunuh diri.

vzn
sumber
1
Bukan itu yang saya tanyakan; Saya bertanya apakah mereka beralasan tentang frekuensi relatif dari angka komposit dengan cara yang Anda gambarkan.
Niel de Beaudrap
1
Saya khawatir saya tidak tertarik dengan generalisasi yang tidak jelas, dan tampaknya cukup jelas bahwa kami tidak setuju secara mendasar tentang apa itu "algoritma". Saya tertarik pada lebih dari sekedar "fenomena". Kalau tidak, kita bisa juga mengutip semua peristiwa mekanika kuantum setelah Big Bang sebagai contoh "algoritma acak", yang membuat seluruh subjek sepele.
Niel de Beaudrap
1
"pertanyaan lunak" tidak berarti pertanyaan dengan batas-batas yang sangat fleksibel; "tinjauan sejarah" tidak sama dengan revisionisme historis.
Niel de Beaudrap
2
'Petunjuk' Anda kepada saya tentang evolusi, atau Anda memberi saya waktu yang terbuang untuk pertanyaan yang tidak saya sukai, atau penghindaran Anda terhadap pertanyaan saya sebelumnya, adalah rasa hormat. Dan nyatanya, spekulasi Anda bahwa orang Yunani mungkin tahu tentang apa yang Anda bicarakan tetapi tidak repot-repot menuliskannya adalah salah satu hal yang dapat dirujuk oleh "revisionisme historis". (Mungkin Archimedes menciptakan notasi desimal, tetapi tidak repot-repot membuat catatan; setelah semua, Sand Reckoner cukup dekat dengan notasi tempat, dan orang-orang Yunani memang menggunakan sistem basis-10-seperti. ? Tidak.)
Niel de Beaudrap
1
Saya setuju bahwa itu dapat dipercaya, dan itu bahkan tidak dibuat-buat - selain, tentu saja, dari fakta bahwa kita tampaknya tidak memiliki catatan tentang orang Yunani yang berbicara tentang probabilitas per se. Tetapi jika ada catatan aktualnya, Anda harus bisa menunjukkannya. Kalau tidak, itu spekulasi, bukan sejarah.
Niel de Beaudrap
-7

JS menyebutkan teori bilangan. Fermat dikreditkan dengan tes primality Fermat , sebuah algoritma probabilistik yang berasal dari tahun 1600-an dan berfungsi sebagai pendahulu untuk tes primality yang lebih modern seperti Solovay-Strassen dan Miller-Rabin. [diperlukan sejarawan yang berspesialisasi dalam teori matematika & bilangan untuk mencoba menunjukkan dengan tepat apa yang Fermat ketahui tentang hal itu versus pengetahuan modern yang jauh lebih lengkap tentang struktur pseudoprime (false positive) dll.]

ay
sumber
2
Bisakah Anda mengutip Fermat yang menggunakan tesnya sebagai cara memfilter bilangan bulat yang dipilih secara acak sebagai bilangan prima (bukan hanya properti menarik yang dimiliki bilangan prima)? Atau mungkin mengutip penulis awal yang menyarankan melakukannya?
Niel de Beaudrap
sebagaimana dinyatakan, detail yang tepat lebih baik diserahkan kepada sejarawan profesional. namun perhatikan [addendum; seharusnya menyebutkan ini] fakta sejarah sederhana bahwa fermat dikreditkan sebagai pendiri koin teori probabilitas bersama dengan pascal, meletakkan dasar dalam serangkaian huruf pada pertengahan 1600-an.
vzn
2
itu tidak benar-benar tepat untuk mengusulkan jawaban berdasarkan apa yang Anda yakini dapat ditampilkan oleh orang lain. Sekali lagi, itu spekulasi.
Niel de Beaudrap
3
@vzn: Jika Fermat menyadari bahwa Teorema Kecil Fermat adalah tes primality yang baik, ia akan menghitung bahwa nomor Fermat ke-5 tidak prima . Ini tidak dilakukan sampai Euler memperhitungkannya lebih dari 60 tahun setelah kematian Fermat.
Peter Shor
2
@vzn: [rujukan?]
Jeffε