Probabilistische (randomisierte) Algorithmen, bevor die „moderne“ Informatik auftauchte

27

Bearbeiten: Ich wähle die Antwort mit der höchsten Punktzahl bis zum 06. Dezember 2012.

Das ist eine weiche Frage.

Das Konzept der (deterministischen) Algorithmen geht auf BC zurück. Was ist mit den probabilistischen Algorithmen?

In diesem Wiki-Eintrag wurde Rabins Algorithmus für das nächste Paarproblem in der Rechengeometrie als erster randomisierter Algorithmus (Jahr ???) angegeben. Lipton führte Rabins Algorithmus als Beginn der modernen Ära der Zufallsalgorithmen ein , jedoch nicht als den ersten. Ich kenne auch viele Algorithmen für probabilistische endliche Automaten (ein sehr einfaches Rechenmodell), die in den 1960er Jahren entdeckt wurden.

Kennen Sie schon vor den 1960er Jahren probabilistische / randomisierte Algorithmen (oder Methoden)?

oder

Welcher Befund kann als erster probabilistischer / randomisierter Algorithmus angesehen werden?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
quelle
25
Die uralte Idee, einen Esslöffel kochende Suppe zu kosten, um zu prüfen, ob sie richtig schmeckt, ist im Wesentlichen eine Zufallsauswahl, ein probabilistischer Algorithmus mit nachweisbaren Garantien.
Arnab
3
Rabins Algorithmus wurde 1976 veröffentlicht, lange nachdem sich die "moderne" Informatik etabliert hatte.
Jeffs
Könnten Sie vielleicht klären, ob es irgendwelche Kriterien gibt, die Sie "Algorithmen" auferlegen möchten, um zu klären, ob z. B. die Naturphänomene, die Milliarden von Jahren vor der Menschheit liegen, "Algorithmen" darstellen, wie in einigen Antworten vorgeschlagen unten?
Niel de Beaudrap
@NieldeBeaudrap: Was ich dachte, waren einige mathematisch gut definierte Algorithmen. (Aber ich persönlich wie arnab ‚s Antwort sehr viel :))
Abuzer Yakaryilmaz

Antworten:

33

Dies wird in meinem Artikel mit HC Williams, "Factoring Integers before Computers", ein wenig besprochen.

In einer Arbeit von 1917 diskutierte HC Pocklington einen Algorithmus zum Auffinden von sqrt (a), modulo p, der davon abhängt, ob Elemente zufällig ausgewählt werden, um einen Nichtrest einer bestimmten Form zu erhalten. Darin sagte er: "Wir müssen dies durch einen Versuch unter Verwendung des Gesetzes der quadratischen Reziprozität tun, was ein Fehler in der Methode ist. Aber für jeden Wert von u ist die Hälfte der Werte von t geeignet. es sollte keine Schwierigkeit geben, einen zu finden. "

Dies ist also eine der ersten expliziten Erwähnungen eines randomisierten Algorithmus.

Jeffrey Shallit
quelle
3
Dies ist eine wirklich schöne Referenz. Wurde der Pocklington-Algorithmus seitdem derandomisiert? Tangential finde ich Ihre Arbeit - sowohl innerhalb als auch außerhalb von CS - großartig, insbesondere Ihren Algorithmus für Bachets Vermutung (das Papier war allerdings schwer zu finden!), Aber auch Ihre Arbeit mit bürgerlichen Freiheiten. Haben Sie Errol Morris '"Mr. Death" gesehen?
Ross Snider
interessant. es erinnert an randomisierte Primärtests
Sasho Nikolov
3
Und ein Las Vegas-Algorithmus auch! Schöne Referenz.
David Eppstein
Sehr schöne Referenz.
Jérémie
Wenn man von Factoring vor Computern spricht, weiß jemand, was Lehmer über den Pocklington-Algorithmus oder andere zufällige Algorithmen wusste, oder ob Lehmer ihn tatsächlich jemals auf seinem Sieb-Factoring-Computer implementiert hat ? Die beiden haben offenbar einen Zusammenhang mit dem Pocklington-Lehmer-Primalitätstest nach Wikipedia
vzn 20.09.12
28

π

vzn
quelle
8
Eigentlich hängt das mit einer Frage zusammen, die ich gestellt habe . Niemand weiß genau, wer den Algorithmus erfunden hat, den viele Leute heutzutage für Buffons Nadel halten.
Jérémie
Genauer gesagt: Es gibt einen eindeutigen Buffon-Nadel-Algorithmus, der das Ablegen von Nadeln auf Streifen beinhaltet, und einen anscheinend sehr unterschiedlichen "Random Point vs Circle" -Algorithmus, wie Sie in dieser Frage erwähnen, den einige Leute Buffon fälschlicherweise zuschreiben moderne, aber unsichere Herkunft.
vzn
19

Der Metropolis-Hastings-Algorithmus wurde 1953 veröffentlicht und geht auf das Manhattan-Projekt zurück, lange vor Rabin. Wie viele der frühen randomisierten Methoden, die in anderen Antworten angegeben wurden, handelt es sich um einen Monte-Carlo-Algorithmus.

Ist es möglich, dass die Behauptung auf der Wikipedia-Seite eine verstümmelte Form der Behauptung ist, dass Rabin der erste Las Vegas-Algorithmus war ?

David Eppstein
quelle
11

Die Gaußsche Normalkurve / Verteilung von Statistiken kann durch viele sehr einfache physikalische Prozesse "berechnet" werden. Eine der einfachsten ist eine Platine mit einer Stiftanordnung in einem dreieckigen Raster (auch als "Galton-Box" bekannt ), bei der die Stifte in abwechselnden Reihen um einen halben Quadratabstand versetzt sind. Wenn die Bälle wiederholt aus derselben Position fallen, verschieben sich die Bälle zufällig mit einer Wahrscheinlichkeit von 0,5 nach links oder rechts. Die kumulative Verteilung an den unteren Positionen ergibt die Gaußsche Kurve / Normal.

vzn
quelle
+1, nur weil ich gerade ein Logo für unsere Statistik-Forschungsgruppe entwerfe und die Galton-Box unsere erste Idee war (die sich jedoch als zu komplex für ein Logo herausstellt).
Konrad Rudolph
10

Nach meiner Meinung ist die natürliche Evolution ein guter und ziemlich alter probabilistischer Algorithmus :-)

Marzio De Biasi
quelle
1
+1 obwohl die Beschreibung des Prozesses als probabilistisch uns viel jünger ist. ;-)
Konrad Rudolph
7
"Algorithmus" legt nahe, dass es ein Problem gibt, das es zu lösen versucht; aber es ist nicht. Es geht nicht einmal darum, Tiere zu "bauen", die besser überleben können. Die Schaffung von Tieren, die an ihre Umwelt angepasst sind, ist nur ein Nebenprodukt (eines, das nicht immer erreicht wird, wie Ereignisse des Aussterbens und Massenaussterbens deutlich machen). In dieser Hinsicht ist Evolution nicht mehr ein Algorithmus als die Schwerkraft; Es ist nur so, was passiert.
Niel de Beaudrap
MDB ist tot auf! evolution ist ein genetischer Algorithmus , der sich für die evolutionäre Fitness entscheidet, und die Wissenschaft holt immer noch alle Implikationen davon ein ... dh sie ist ein aktives Forschungsgebiet. Es wurde nicht viel darauf hingewiesen oder weithin anerkannt, aber der phänomenale Erfolg von GAs in CS ist tatsächlich ein starker mathematisch / wissenschaftlicher Beweis für die Realität der Theorie der biologischen Evolution. Zugegeben, es unterscheidet sich definitiv in einigen wichtigen Punkten von anderen "Algorithmen".
vzn
2
@vzn: Ein "genetischer Algorithmus" wählt zunächst eine Fitnessfunktion aus, die wir für einen bestimmten Zweck auferlegen. Wir benutzen die Evolution als Werkzeug, um etwas in diesem Fall zu tun. Das heißt aber nicht, dass die biologische Evolution ein Algorithmus ist, mit dem man etwas tun kann. Gibt es einen sinnvollen Sinn, bei dem alle Wasserfälle Algorithmen sind, nur weil wir manchmal Wasserfälle verwenden, um Elektrizität zu erzeugen?
Niel de Beaudrap
4
@vzn: Ich behaupte nur, dass "ein Algorithmus" genau definierte Parameter der Erfolgswahrscheinlichkeit beinhalten sollte, ganz zu schweigen davon, dass es einen Agenten geben sollte, der ihn ausführt . Der einzige "Agent", von dem man sagen könnte, dass er "Evolution" durchführt, wäre ein gesamtes Ökosystem. Was sollen wir sagen, dass das Ökosystem "versucht" zu erreichen? Ich würde genauso gerne sagen, dass Sie die Natur anthropomorphisieren . Ich fordere nur, dass "Anwenden eines Algorithmus" ein gewisses Maß an zielgerichteter Intentionalität beinhaltet, die von Menschen angewendet wird oder nicht. Inwiefern kann ein Prozess ohne Ziel einen "Algorithmus" darstellen?
Niel de Beaudrap
6

Es gibt eine Arbeit über randomisierte Algorithmen in "primitiven" Kulturen .

Die Verwendung von Orakeln (z. B. Hühnerknochen, Steine), um zu entscheiden, wo gejagt werden soll, kann als randomisierter Algorithmus angesehen werden. Man kann argumentieren, dass die Randomisierung des Jagdreviers eine Anpassung des Wildes und eine Überjagung verhindert.

adrianN
quelle
0

Eine der Einsteins 1905 erschienenen "Wunder" -Papiere befasste sich mit der Brownschen Bewegung , einem klassischen physikalischen Beispiel für einen zufälligen Gang, und liefert eine Formel (dh im Grunde genommen einen Algorithmus, wenn der physikalische Prozess der "Computer" ist) zum Schätzen / Berechnen von Partikeln (Molekülen). Durchmesser bei anderen bekannten physikalischen Konstanten und der Beobachtung / Messung der (zufälligen) Partikelverschiebung über die Zeit. Dieses Papier diente auch als früher theoretischer / experimenteller / grundlegender Beweis für die Atomtheorie der Materie.

vzn
quelle
4
Wieder wie bei der Evolution: Obwohl die Bewegung zufällig sein und durch einen zufälligen Gang modelliert werden kann, welchen Algorithmus repräsentiert dies? Während einige Algorithmen zufällige Spaziergänge verwenden, bedeutet dies nicht, dass alle zufälligen Spaziergänge Algorithmen darstellen (mehr als jede Wortfolge in Englisch steht für Prosa, nur weil alle englischen Prosa aus Wörtern in Englisch besteht).
Niel de Beaudrap
-4

nini

Die Maschine hat auch eine gewisse Ähnlichkeit mit dem Babbage-Differentialmotor (~ 1830er Jahre). Es ist nicht völlig unvorstellbar, dass Babbage oder Lovelace sich etwas ähnliches wie probabilistische Algorithmen vorgestellt haben. Die Maschine (n) kann (können) sicherlich verwendet werden , um probabilistische Algorithmen zu implementieren, die die moderne Theorie entlehnen und sie der Vergangenheit überlagern.

[1] Lehmer Factoring-Maschine

[2] Babbage-Motor


Lehmer Mod & Factoring Maschine

vzn
quelle
1
Können Sie beschreiben, in welchem ​​Sinne es probabilistische Antworten für große Zahlen berechnet hat? Bei einer schnellen Suche kann ich anscheinend online keine Verweise darauf finden.
Niel de Beaudrap
Meines Wissens wurde es [unter anderem] verwendet, um kleinere Faktoren mit großen Testzahlen zu finden, ähnlich wie beim Sieben von Eratosthenen. Wenn die große Zahl bestanden wird, handelt es sich um "wahrscheinlich nicht zusammengesetzt" oder "möglicherweise um eine Primzahl" oder einen "Primkandidaten". Leider ist das Internet nicht sehr gut mit historischen Referenzen und Ursprüngen [sogar Wikipedia], Bücher sind besser. Weitere Details am Ende dieser Seite , "Arten von Problemen, die Lehmer zu lösen versuchte ", von Dr. mike williams, Chefkurator des Computer History Museum von CA
vzn
1
Die Maschine (n) können sicherlich zur Implementierung probabilistischer Algorithmen verwendet werden - also? Im Gegensatz zu anderen Maschinen, die das nicht können?
Jeffs
2
Obwohl sich die damalige Terminologie möglicherweise nicht auf "probabilistische Algorithmen" bezog, wurde sie in einigen Fällen möglicherweise auf diese Weise verwendet - [Zitieren erforderlich] Wenn Sie Beweise dafür haben , dass "möglicherweise prim" eine formale Aussage über die Wahrscheinlichkeit ist und nicht einfach ein heuristische Beschreibung, bitte zitieren. Ansonsten hören Sie bitte auf zu spekulieren.
Jeffs
n1∗n2∗n3∗nxx
-6

Hier sind einige Fälle der frühen und sogar alten / vorgeschichtlichen Anfänge von Konzepten im Zusammenhang mit randomisierten Algorithmen.

  • n/2

  • Glücksspiele und Glücksspiele sind sehr alt. Aus der modernen Theorie haben Spiele starke Ähnlichkeiten, wenn nicht direkte Verbindungen zu Algorithmen. Glücksspiel / Gaming - Würfel sind dafür bekannt , zumindest zu fünf millenia alt.

  • Die Griechen und Römer hatten auch das Konzept , Strohhalme zu ziehen, bei denen die Person, die den kürzesten Strohhalm zog, verlor. Ähnlich wie bei Würfeln ist dies in gewisser Hinsicht der einfachste Algorithmus, um eine einzelne Zufallsauswahl zu treffen.

  • Vollständige Offenlegung, es gibt einen Hauch von blutiger Geschichte und Verbindung. in einer anderen Antwort erwähnt MDB die Evolution . Ein Teil der Evolution ist die natürliche Auslese, die auch Parallelen zur menschlichen Kriegsführung aufweist - anscheinend ein wesentlicher Teil der Evolution menschlicher Städte / Gesellschaften. In gewisser Hinsicht ist ein Krieg ein grobes Zufallsverfahren für "etwas", über das Soziologen und Historiker immer noch über genaue Ursachen streiten. Diebstahl / Plünderung? Zuweisung von Ressourcen? Gebiet? politische Macht? Sklaven? (usw.) Die Römer hatten auch eine grausige Praxis namens Dezimierung(Das moderne Wort leitet sich in der Etymologie von dem alten ab!), in dem jeder 10. Soldat, der nach dem Zufallsprinzip ausgewählt wurde, als Strafe für Meuterei oder Feigheit von verbleibenden Soldaten hingerichtet wurde. es scheint eine vergessene und atavistische Praxis zu sein, aber es scheint eine Parallele zum modernen russischen Roulette zu haben , einem "modernen" randomisierten Quasi-Selbstmordspiel.

vzn
quelle
1
Darum frage ich nicht; Ich frage, ob sie in der von Ihnen beschriebenen Weise über die relative Häufigkeit von zusammengesetzten Zahlen argumentiert haben.
Niel de Beaudrap
1
Ich fürchte, ich interessiere mich nicht für vage Allgemeingültigkeiten, und es scheint ziemlich offensichtlich, dass wir uns im Grunde nicht darüber einig sind, was ein "Algorithmus" ist. Ich interessiere mich nicht nur für "Phänomene". Ansonsten können wir auch alle quantenmechanischen Ereignisse nach dem Urknall als Beispiele für "randomisierte Algorithmen" anführen, was das ganze Thema trivial macht.
Niel de Beaudrap
1
"weiche Frage" bedeutet keine Frage mit unendlich flexiblen Grenzen; "historischer Überblick" ist nicht dasselbe wie historischer Revisionismus.
Niel de Beaudrap
2
Ihr "Hinweis" auf die Evolution oder Ihre Absicht, Zeit mit einer Frage zu verschwenden, die ich nicht mag, oder Ihre Umgehung meiner früheren Frage waren respektvoll. Und tatsächlich ist Ihre Spekulation, dass die Griechen wahrscheinlich wussten, wovon Sie sprechen, sich aber nicht die Mühe gemacht haben, darüber zu schreiben, genau eines der Dinge, auf die sich der "historische Revisionismus" beziehen kann. (Vielleicht hat Archimedes die Dezimalschreibweise erfunden, hat sich aber nicht die Mühe gemacht, Aufzeichnungen zu machen. Schließlich ist die Sand-Reckoner-Schreibweise der Ortsschreibweise ziemlich nahe, und die Griechen haben ein Basis-10-ähnliches System verwendet. Aber sollten wir die Idee ernst nehmen? ? Nein.)
Niel de Beaudrap
1
Ich bin damit einverstanden, dass es möglich ist und dass es nicht einmal sehr weit hergeholt ist - abgesehen von der Tatsache, dass wir offenbar keine Aufzeichnungen darüber haben, dass die Griechen über die Wahrscheinlichkeit per se sprechen. Aber wenn es tatsächlich Aufzeichnungen gibt, sollten Sie in der Lage sein, darauf hinzuweisen. Ansonsten ist es Spekulation, nicht Geschichte.
Niel de Beaudrap
-7

JS erwähnt die Zahlentheorie. Fermat wird der Fermat-Primalitätstest zugeschrieben , ein probabilistischer Algorithmus aus dem 17. Jahrhundert, der als Vorläufer für modernere Primalitätstests wie Solovay-Strassen und Miller-Rabin dient. [Es würde einen Historiker brauchen, der sich auf Mathematik und Zahlentheorie spezialisiert hat, um genau zu bestimmen, was Fermat darüber wusste, im Gegensatz zu modernem Wissen, das viel vollständiger ist über die Struktur seiner Pseudoprimes (False Positives) usw.]

vzn
quelle
2
Können Sie Fermat zitieren, der seinen Test dazu verwendet hat, zufällig ausgewählte ganze Zahlen als Nicht-Primzahlen herauszufiltern (im Gegensatz zu einer interessanten Eigenschaft, die Primzahlen haben)? Oder vielleicht einen frühen Autor zitieren, der dies vorschlägt?
Niel de Beaudrap
Wie bereits erwähnt, sollten die genauen Details einem professionellen Historiker überlassen werden. Beachten Sie jedoch [Nachtrag; hätte dies erwähnen sollen] die einfache historische Tatsache, dass Fermat als Mitbegründer der Wahrscheinlichkeitstheorie zusammen mit Pascal anerkannt wird und die Grundlage für eine Reihe von Briefen Mitte des 17. Jahrhunderts legt.
VZN
2
Es ist nicht wirklich angemessen, Antworten auf der Grundlage dessen vorzuschlagen, was Ihrer Meinung nach jemand anderes zeigen kann. Auch das ist Spekulation.
Niel de Beaudrap
3
@vzn: Wenn Fermat erkannt hätte, dass Fermats kleiner Satz ein guter Primalitätstest ist, hätte er berechnet, dass die 5. Fermat-Zahl keine Primzahl ist . Dies geschah erst, als Euler es mehr als 60 Jahre nach Fermats Tod berücksichtigte.
Peter Shor
2
@vzn: [Zitieren benötigt]
Jeffs