Algorytmy probabilistyczne (randomizowane) przed pojawieniem się „nowoczesnej” informatyki

27

Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r.

To delikatne pytanie.

Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi?

W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy algorytm losowy (rok ???). Lipton wprowadził algorytm Rabina jako początek ery nowożytnej losowych algorytmów tutaj , ale nie jako pierwszy. Znam również wiele algorytmów probabilistycznych automatów skończonych (bardzo prosty model obliczeniowy) odkrytych w latach 60.

Czy znasz jakieś probabilistyczne / randomizowane algorytmy (lub metody) jeszcze przed 1960 rokiem?

lub

Które odkrycie można uznać za pierwszy algorytm probabilistyczny / randomizowany?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
źródło
25
Odwieczny pomysł spróbowania łyżki wrzącej zupy, aby sprawdzić, czy smakuje dobrze, to w zasadzie losowe pobieranie próbek, algorytm probabilistyczny z możliwymi do udowodnienia gwarancjami.
arnab
3
Algorytm Rabina został opublikowany w 1976 r., Długo po ugruntowaniu „nowoczesnej” informatyki.
Jeffε
Czy mógłbyś wyjaśnić, czy istnieją jakieś kryteria, które chciałbyś nałożyć na „algorytmy”, aby wyjaśnić, czy uważasz, że np. Te naturalne zjawiska, które poprzedzają ludzkość o miliardy lat, reprezentują „algorytmy”, jak sugerują niektóre odpowiedzi? poniżej?
Niel de Beaudrap,
@NieldeBeaudrap: Moim zdaniem były to matematyczne dobrze zdefiniowane algorytmy. (Ale osobiście bardzo lubię odpowiedź arnaba :))
Abuzer Yakaryilmaz,

Odpowiedzi:

33

Jest to omówione nieco w moim artykule z HC Williams, „Factoring Integers before Computers”

W artykule z 1917 r. HC Pocklington omówił algorytm znajdowania sqrt (a), modulo p, który polegał na losowym wybieraniu elementów, aby uzyskać nieresztę pewnej postaci. Powiedział w nim: „Musimy to zrobić [znaleźć nieresztę] na drodze prób, stosując Prawo Wzajemności Kwadratowej, co jest wadą metody. Ale jak dla każdej wartości u połowa wartości t jest odpowiednia, nie powinno być trudności ze znalezieniem ”.

Jest to więc jeden z pierwszych wyraźnych wzmianek o losowym algorytmie.

Jeffrey Shallit
źródło
3
To naprawdę miłe odniesienie. Czy algorytm Pocklington od tego czasu został zdandaryzowany? Stycznie podoba mi się twoja praca - zarówno w CS, jak i poza nią - w szczególności twój algorytm dla przypuszczeń Bachta (choć trudno było znaleźć kopię!), Ale także twoja swoboda obywatelska. Czy oglądałeś „Pana Śmierci” Errola Morrisa?
Ross Snider,
ciekawy. przypomina losowe testy pierwotności
Sasho Nikolov,
3
A także algorytm Las Vegas! Niezłe referencje.
David Eppstein,
Bardzo miłe referencje.
Jérémie
Mówiąc o faktorowaniu przed komputerami, czy ktoś wie, co Lehmer wiedział o algorytmie Pocklington lub jakimkolwiek innym algorytmie randomizowanym, lub czy Lehmer kiedykolwiek zaimplementował go na swoim komputerze faktoringowym ? obaj najwyraźniej mają jakiś związek z testem pierwotności Pocklington-Lehmera według wikipedii
dniu
28

Algorytm igły Buffons do szacowania , w zasadzie metody Monte Carlo , datuje się na publikację w 1777 roku. Zauważ, że metody Monte Carlo pochodzą z lat 40. XX wieku z amerykańskim projektem bomby atomowej „Manhattan” i zostały opracowane wspólnie przez Ulama, von Neumanna i Metropolis.π

vzn
źródło
8
W rzeczywistości jest to związane z pytaniem, które zadałem . Nikt nie wie dokładnie, kto opracował algorytm, który wielu ludzi uważa za igłę Buffona.
Jérémie,
powiedział bardziej precyzyjnie - istnieje wyraźny algorytm igły Buffona, który polega na upuszczaniu igieł na paski, i najwyraźniej znacznie inny algorytm „losowy punkt vs okrąg”, jak wspominasz w tym pytaniu, który niektórzy ludzie wydają się błędnie przypisywać Buffonowi, z innym, więcej nowoczesne, ale niepewne początki.
vzn
19

Algorytm Metropolis-Hastings została opublikowana w 1953 roku i sięga wcześniej z projektem Manhattan, na długo przed Rabina. Podobnie jak wiele wczesnych metod randomizowanych podanych w innych odpowiedziach, jest to algorytm Monte Carlo.

Czy to możliwe, że twierdzenie na stronie Wikipedii jest zniekształconą formą twierdzenia, że ​​Rabin był pierwszym algorytmem Las Vegas ?

David Eppstein
źródło
11

Gaussa krzywej normalnej / dystrybucja statystyk może być „obliczona” przez wielu bardzo prostych procesów fizycznych. Jedną z najprostszych jest tablica z układem pinów w trójkątnej siatce (znanej również jako „pudełko Galtona” z 1800 roku), w której szpilki są przesunięte o 1/2 kwadratu na przemian w rzędach. Wielokrotnie upuszczając piłki z tej samej pozycji, losowo przemieszczają się w lewo lub w prawo z prawdopodobieństwem 0,5. Skumulowany rozkład zarejestrowany w dolnych pozycjach daje krzywą Gaussa / normalną.

vzn
źródło
+1 tylko dlatego, że obecnie projektuję logo dla naszej grupy badawczej ds. Statystyk, a Galton Box był naszym pierwszym pomysłem (ale okazuje się, że jest zbyt skomplikowany dla logo).
Konrad Rudolph
10

Moim zdaniem naturalna ewolucja jest dobrym i raczej starym algorytmem probabilistycznym :-)

Marzio De Biasi
źródło
1
+1, chociaż opis procesu jako probabilistyczny jest o wiele bardziej aktualny. ;-)
Konrad Rudolph
7
„Algorytm” sugeruje, że istnieje problem, który próbuje rozwiązać; ale tak nie jest. Nie chodzi nawet o „próbowanie” stworzenia zwierząt, które lepiej przetrwają; tworzenie zwierząt, które są dostosowane do jego środowiska, jest tylko produktem ubocznym (takiego, który nie zawsze jest osiągany, jak dowodzą przypadki wymierania i masowego wymierania). Pod tym względem ewolucja nie jest bardziej algorytmem niż grawitacja; po prostu tak się dzieje.
Niel de Beaudrap,
MDB nie działa! ewolucja jest algorytmem genetycznym, który wybiera ewolucyjną sprawność, a nauka wciąż dogania wszystkie implikacje tego ... tzn. jest to aktywny obszar badań. nie zostało to zauważone ani powszechnie docenione, ale fenomenalny sukces GA w CS jest tak naprawdę silnym matematycznym / naukowym dowodem na rzeczywistość teorii ewolucji biologicznej. przyznać jednak, że pod pewnymi kluczowymi względami zdecydowanie różni się od innych „algorytmów”.
vzn
2
@vzn: „algorytm genetyczny” wybiera przede wszystkim funkcję fitness, którą nakładamy na określony cel. Używamy ewolucji jako narzędzia do zrobienia czegoś w tym przypadku. Ale to nie znaczy, że ewolucja biologiczna jest algorytmem do robienia czegokolwiek. Czy używając ponownie analogii grawitacji, istnieje sensowne znaczenie, w którym wszystkie wodospady są algorytmami, tylko dlatego, że czasami używamy wodospadów do generowania elektryczności?
Niel de Beaudrap,
4
@vzn: Po prostu twierdzę, że „algorytm” powinien zawierać dobrze zdefiniowane parametry prawdopodobieństwa sukcesu, nie wspominając już o tym, że powinien istnieć agent, który go realizuje . Jedynym „agentem”, o którym można by powiedzieć, że dokonuje „ewolucji” byłby cały ekosystem. Co powinniśmy powiedzieć, że ekosystem „próbuje” osiągnąć? Z chęcią powiedziałbym, że jesteś naturą antropomorficzną . Żądam tylko, aby „zastosowanie algorytmu” pociągało za sobą pewną celowość ukierunkowaną na cel, stosowaną przez ludzi lub nie. W jakim sensie proces bez celu może reprezentować „algorytm”?
Niel de Beaudrap,
6

Jest artykuł na temat algorytmów losowych w kulturach „prymitywnych” .

Używanie wyroczni (np. Kości kurczaka, kamieni), aby zdecydować, gdzie polować, może być postrzegane jako algorytm losowy. Można argumentować, że randomizacja terenów łowieckich uniemożliwia dostosowanie gry i przeludnienie.

adrianN
źródło
0

jeden z artykułów o „ cudach ” Einsteinsa z 1905 r. był w ruchu Browna , klasyczny fizyczny przykład przypadkowego spaceru i daje wzór (tj. zasadniczo algorytm, jeśli proces fizyczny jest „komputerem”) do szacowania / obliczania cząstek (cząsteczki) średnica z uwzględnieniem innych znanych stałych fizycznych i obserwacja / pomiar (losowego) przemieszczenia cząstek w czasie. praca ta posłużyła również jako wczesny teoretyczny / eksperymentalny / fundamentalny dowód na atomową teorię materii.

vzn
źródło
4
Podobnie jak w przypadku ewolucji: chociaż ruch może być losowy i może być modelowany przez losowy spacer, jaki algorytm to reprezentuje? Chociaż niektóre algorytmy używają losowych spacerów, nie oznacza to, że wszystkie losowe spacery reprezentują algorytmy (podobnie jak dowolny ciąg słów w języku angielskim reprezentuje prozę tylko dlatego, że cała angielska proza ​​składa się ze słów w języku angielskim).
Niel de Beaudrap,
-4

kolejna odpowiedź w duchu teorii liczb JS. jednym z pierwszych zbudowanych komputerów analogowo-cyfrowych jest sito Lehmera z ok. 1932 r., wyprzedzające komputery elektroniczne o około dekadę. w zasadzie oblicza resztę z dzielenia mod dla skończonej liczby i stosuje resztę chińską thm . dla większych liczb oblicza probabilistyczne odpowiedzi na pytania teorii liczb, w tym faktoring. chociaż ówczesna terminologia mogła nie odnosić się do „algorytmów probabilistycznych”, w niektórych przypadkach mogła być stosowana w ten sposób. (w ten sposób ma również pewne podobieństwo do probabilistycznego testu podstawowego Fermata).n inini

maszyna ma również pewne podobieństwo do silnika różnicowego Babbage'a (~ 1830). nie jest całkowicie nie do pomyślenia, że ​​Babbage lub Lovelace mogli przewidzieć coś podobnego do algorytmów probabilistycznych. maszyny można z pewnością wykorzystać do implementacji algorytmów probabilistycznych, zapożyczenia nowoczesnej teorii i nałożenia jej na przeszłość.

[1] Maszyna faktoringowa Lehmer

[2] Silnik Babbage


Lehmer mod n i maszyna faktoringowa

vzn
źródło
1
Czy potrafisz opisać sens, w jakim obliczył on odpowiedzi probabilistyczne dla dużych liczb? Szybkie wyszukiwanie nie wydaje się, że nie mogę znaleźć żadnych odniesień do tego w Internecie.
Niel de Beaudrap,
rozumiem, że został użyty [między innymi] do znalezienia mniejszych czynników o dużej liczbie testowej podobnych do sita eratostenów. jeśli duża liczba minęła, to „prawdopodobnie nie jest złożony”, „prawdopodobnie główny” lub „główny kandydat”. niestety internet nie jest zbyt dobry z odniesieniami historycznymi i pochodzeniem [nawet wikipedia], książki są lepsze. Więcej szczegółów na dole tej strony , „rodzaje problemów Lehmer była usiłujących rozwiązać” przez dr Mike Williams, głowa kustosz Muzeum Historii Komputerów CA
vzn
1
maszyny można z pewnością wykorzystać do implementacji algorytmów probabilistycznych - więc? W przeciwieństwie do innych maszyn, które nie mogą?
Jeffε
2
chociaż ówczesna terminologia mogła nie odnosić się do „algorytmów probabilistycznych”, w niektórych przypadkach była prawdopodobnie stosowana w ten sposób - [potrzebne źródło] Jeśli masz dowody, że „prawdopodobnie pierwsza” jest formalnym stwierdzeniem o prawdopodobieństwie, a nie tylko heurystyczny opis, proszę go cytować. W przeciwnym razie przestańcie spekulować.
Jeffε
nie ma dostępnej pełnej zawartości artykułów Lehmersa (nie jestem nawet pewien, co wszystko opublikował), ale losowy artykuł w pocklington jest obsługiwany przez jedną linię jednego z jego artykułów. jakie są kryteria wydaje się, że wszystko, co jest wymagane, aby Lehmer uruchomił maszynę na liczbie większej niż dla największego na maszynie i dokonał pewnego rodzaju rozsądnej obserwacji wyniku, niekoniecznie spisanej ... wydaje mi się prawdopodobne .... xn1∗n2∗n3∗nxx
wer 16'12
-6

oto kilka przykładów wczesnych, a nawet starożytnych / prehistorycznych początków pojęć związanych z algorytmami losowymi.

  • rozważmy sito Eratostenesa, około 2 tysiąclecia. nieco ukrytym w algorytmie byłby pomysł „wczesnego zatrzymania” w zaznaczaniu pierwszych przedziałów, zanim wszystkie przedziały do zostaną zaznaczone. jasne jest, że „późniejsze” dłuższe przedziały są mniej prawdopodobne, aby zaznaczyć daną liczbę pod uwagę. innymi słowy, jego przybliżona wizualizacja podstawowego faktu teorii liczb, że „większość liczb zespolonych ma małe czynniki” i że przetestowanie szeregu małych czynników jest wystarczające, aby wykluczyć wiele liczb zespolonych. pojęcie to prawdopodobnie zrozumieliby Grecy.n/2

  • gry losowe i hazardowe są bardzo stare. według współczesnej teorii gry mają silne podobieństwa, jeśli nie bezpośrednie połączenia z algorytmami. kości hazardu / hazardu mają co najmniej pięć tysięcy lat.

  • Grecy i Rzymianie mieli również pomysł rysowania słomek, w których stracił osobę wyciągającą najkrótszą. podobny do kości, jest w pewnym sensie najprostszym możliwym algorytmem do dokonania jednego losowego wyboru.

  • pełne ujawnienie, jest odrobina krwawej historii i związku. w innej odpowiedzi MDB wspomina o ewolucji . częścią ewolucji jest dobór naturalny, który ma również podobieństwo do ludzkiej wojny - najwyraźniej nieodłączny element ewolucji ludzkich miast / społeczeństw. w pewnym sensie wojna jest prymitywnym algorytmem półirandomowym dla „czegoś”, co socjologowie i historycy wciąż spierają się o dokładne przyczyny. kradzież / grabież? Lokowanie zasobów? terytorium? władza polityczna? niewolnicy? (itp.) Rzymianie mieli również makabryczną praktykę zwaną zdziesiątkowaniem(współczesne słowo faktycznie wywodzi się z etymologii od starożytnego!), w którym jako karę za bunt lub tchórzostwo, co 10. losowo wybrany żołnierz został stracony przez pozostałych żołnierzy. może się to wydawać zapomnianą i atawistyczną praktyką, ale wydaje się, że ma pewną analogię do współczesnej rosyjskiej ruletki , „nowoczesnej” losowej quasi-gry samobójczej.

vzn
źródło
1
Nie o to pytam; Pytam o to, czy rozumowali względną częstotliwość liczb zespolonych w sposób, który opisujesz.
Niel de Beaudrap,
1
Obawiam się, że nie interesują mnie niejasne ogólniki i wydaje się dość oczywiste, że zasadniczo nie zgadzamy się co do tego, czym jest „algorytm”. Interesuje mnie coś więcej niż tylko „zjawiska”. W przeciwnym razie równie dobrze możemy przytoczyć wszystkie mechanizmy kwantowe po Wielkim Wybuchu jako przykłady „algorytmów losowych”, co czyni cały przedmiot trywialnym.
Niel de Beaudrap,
1
„miękkie pytanie” nie oznacza pytania o nieskończenie elastycznych granicach; „przegląd historyczny” to nie to samo, co rewizjonizm historyczny.
Niel de Beaudrap,
2
Twoja „wskazówka” dla mnie na temat ewolucji, ani rzucanie mnie na marnowanie czasu na pytanie, które mi się nie podoba, ani unikanie mojego wcześniejszego pytania były pełne szacunku. W rzeczywistości spekulowanie, że Grecy prawdopodobnie wiedzieli o tym, o czym mówisz, ale nie zawracali sobie głowy pisaniem o tym, jest dokładnie jedną z rzeczy, do których może odnosić się „rewizjonizm historyczny”. (Być może Archimedes wynalazł notację dziesiętną, ale nie zadał sobie trudu, aby dokonać zapisu; w końcu Sand Reckoner jest dość blisko notacji miejsca, a Grecy zastosowali system podobny do bazy 10. Ale czy powinniśmy potraktować ten pomysł poważnie ? Nie.)
Niel de Beaudrap,
1
Zgadzam się, że jest to możliwe i że nie jest nawet zbyt daleko idące - poza tym, oczywiście, że nie wydaje się, abyśmy mieli jakieś wzmianki o tym, że Grecy mówią o prawdopodobieństwie per se. Ale jeśli istnieje jakiś fakt, powinieneś być w stanie to wskazać. W przeciwnym razie to spekulacje, a nie historia.
Niel de Beaudrap,
-7

JS wspomina teorię liczb. Fermat przypisuje się testowi pierwszeństwa Fermata , algorytmowi probabilistycznemu, który pochodzi z 1600 roku i służy jako prekursor dla bardziej nowoczesnych testów pierwotności, takich jak Solovay-Strassen i Miller-Rabin. [zajęłoby to historykowi specjalizującemu się w matematyce i teorii liczb, aby dokładnie wskazać, co Fermat wiedział na ten temat, w porównaniu do współczesnej wiedzy, która jest o wiele bardziej kompletna o strukturze jej pseudopierwszych liczb (fałszywie dodatnich) itp.]

vzn
źródło
2
Czy możesz przytoczyć Fermata, który wykorzystał swój test do odfiltrowania losowo wybranych liczb całkowitych jako liczb niepierwszych (w przeciwieństwie do interesującej właściwości liczb pierwszych)? A może zacytować wczesnego autora, który to sugeruje?
Niel de Beaudrap,
jak stwierdzono, dokładne szczegóły lepiej pozostawić profesjonalnemu historykowi. jednak uwaga [uzupełnienie; powinien był o tym wspomnieć] prosty fakt historyczny, że fermat jest uważany za współtwórcę teorii prawdopodobieństwa wraz z pascalem, kładąc podwaliny pod szereg liter w połowie XVI wieku.
vzn
2
proponowanie odpowiedzi na podstawie tego, co Twoim zdaniem może być w stanie pokazać ktoś inny, nie jest właściwe. To znowu spekulacja.
Niel de Beaudrap,
3
@vzn: Gdyby Fermat zdał sobie sprawę, że małe twierdzenie Fermata było dobrym testem pierwotności, obliczyłby, że 5. liczba Fermata nie jest liczbą pierwszą . Nie zrobiono tego, dopóki Euler nie uwzględnił tego ponad 60 lat po śmierci Fermata.
Peter Shor,
2
@vzn: [potrzebne źródło]
Jeffε