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
źródło
Odpowiedzi:
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.
źródło
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.π
źródło
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 ?
źródło
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ą.
źródło
Moim zdaniem naturalna ewolucja jest dobrym i raczej starym algorytmem probabilistycznym :-)
źródło
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.
źródło
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.
źródło
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 ini ni
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
źródło
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.
źródło
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.]
źródło