Zufällige Algorithmen (intro)

Sprecher: Ich habe Neuigkeiten. Die NASA hat angekündigt, dass es einen Hardware-Zufallszahlengenerator auf dem Rover geben wird, auf den wir Zugriff haben. Danach haben sie noch einen weiteren Kommentar abgegeben und mich daran erinnert, dass unser Algorithmus in der Praxis funktionieren muss. Damit etwas in der Praxis funktioniert, bedeutet das, dass es immer eine gewisse Fehlermöglichkeit gibt, aber vielleicht ist die Möglichkeit so gering, dass wir sie in der Praxis ignorieren. Und wenn das verrückt klingt, mach dir einfach klar, dass in der physischen Welt nichts jemals sicher ist, es gibt immer Fehlerchancen. Zum Beispiel enthalten Chipgehäuse geringe Mengen an radioaktiven Verunreinigungen, und wenn diese zerfallen, setzen sie Alpha-Teilchen frei, die tatsächlich Bits im Speicher umkippen und möglicherweise eine Zahl unerwartet ändern können. Noch interessanter ist, dass auch kosmische Strahlen weiche Fehler verursachen können, wir können die Fehlerchance nie vollständig eliminieren. Ich habe die NASA gefragt, welche Fehlerwahrscheinlichkeit akzeptabel ist. Sie sagten: "Wir müssen nur sicherstellen, dass die Fehlerwahrscheinlichkeit bei einem gegebenen Versuch geringer ist als die Chance, zweimal hintereinander im Lotto zu gewinnen." Die Chance, zweimal hintereinander im Lotto zu gewinnen, beispielsweise im 6/49, liegt bei sechs mal zehn hoch minus vierzehn, also lasst uns sicherheitshalber abrunden und sagen, dass unsere Fehlerwahrscheinlichkeit zehn hoch minus fünfzehn beträgt. Sicher genug; wir erwarten keinen Fehler und es könnte hunderte oder tausende Male laufen. Jetzt ist meine Frage, ob der Zugang zur Zufälligkeit uns helfen könnte, einen Entscheidungsalgorithmus, wie beispielsweise diesen Primzahltest, zu beschleunigen? Das ist eine tiefgehende Frage, also treten wir einen Schritt zurück und betrachten das große Ganze. Angenommen, wir haben eine Sammlung von Ganzzahlen von eins bis zu einer bestimmten Grenze N, sagen wir, betrachten wir es als unser Universum der Ganzzahlen. Wir können immer eine Sammlung in zwei Mengen aufteilen. Ein Entscheidungsproblem kann tatsächlich als Aufteilung in zwei Mengen betrachtet werden. Zum Beispiel wird, wenn ein N gegeben ist, N kleiner als 100, für alle Ganzzahlen kleiner als 100 ein Ja ausgegeben. Hier ist eine Sammlung und für alle anderen ein "Nein", was eine andere Sammlung ist. Okay, lassen Sie uns uns jetzt darauf konzentrieren, Primzahlen mit der Entscheidung zu erkennen. Im Idealfall würden wir gerne einige einfach berechnete Kriterien haben, die alle Primzahlen erfüllen und keine zusammengesetzten Zahlen erfüllen. Wenn wir nun ein einfaches Muster kennen würden, das die Position aller Primzahlen beschreibt, und nur Primzahlen, dann könnten wir bei einer gegebenen Zahl N einfach überprüfen, ob N diesem Muster folgt. Das Problem ist, dass bisher kein erschöpfendes und einfach berechenbares Muster für alle Primzahlen und keine zusammengesetzten Zahlen oder alle zusammengesetzten Zahlen und keine Primzahlen gefunden wurde. Aber wir kennen schnelle Tests für die meisten zusammengesetzten Zahlen. Ein Beispiel für ein einfach berechenbares Kriterium wäre ein Test auf Gleichheit, und alle geraden Zahlen sind durch zwei teilbar. Es ist schnell, weil wir erkennen können, ob etwas gerade ist, indem wir uns nur die letzte Ziffer ansehen, und selbst wenn N wächst, wird das Problem nicht schwieriger, wir sehen uns einfach diese letzte Ziffer an, die auch als niedrigste Stelle bekannt ist. Jetzt wird klar, dass wir diesen Gleichheitstest als einen niedrigqualitativen zusammengesetzten Test verwenden können. Damit könnten wir einen Algorithmus haben, der unsere Ganzzahl N akzeptiert und alles, was unser Algorithmus tut, ist zu prüfen, ob sie gerade ist. Wenn sie gerade ist und größer als zwei, dann wissen wir mit hundertprozentiger Sicherheit, dass sie zusammengesetzt ist, weil wir einen Beweis haben. Denke an zwei von den zusammengesetzte Zahlen, als unseren Zeugen. Aber wenn nicht, dann sind wir uns nicht ganz sicher. Wenn es ungerade ist, könnte es eine Primzahl sein, da alle Primzahlen ungerade sind, oder es könnte eine von vielen zusammengesetzten Zahlen sein, die ungerade sind, wie neun oder fünfzehn. Dieser massive Bereich ungerader zusammengesetzter Zahlen macht einen Test unakzeptabel. Um das klarzustellen, lass es uns aufzeichnen. Angenommen, wir haben eine Zahl N, diese kann entweder eine Primzahl oder zusammengesetzt sein. Wenn N eine Primzahl ist, wird unser Algorithmus 100 Prozent der Zeit Primzahlen sagen, da keine Primzahlen gerade sind, die größer als zwei sind. Er wird nie zusammengesetzt sagen, wenn eine Primzahl gegeben ist. Wenn N jedoch zusammengesetzt ist, wird unser Algorithmus etwa 50 Prozent der Zeit zusammengesetzt und 50 Prozent der Zeit Primzahl sagen. Das bedeutet, dass, wenn unser Algorithmus zusammengesetzt ausgibt, er einen Beweis für eine zusammengesetzten Zeugen gefunden hat. Wenn unser Algorithmus jedoch Primzahl ausgibt, wissen wir, dass es eine unannehmbar große Fehlerchance gibt. Bisher haben wir diesen großen, unannehmbaren Fehler durch Wiederholung behandelt und den Fluss unserer Maschine gezeichnet. Angenommen, wir haben eine Zahl N, unsere Maschine führt eine Reihe von Teilbarkeitstests durch, beginnend bei A gleich zwei. Sie fragt, ob A durch N teilbar ist. Wenn A nicht durch N teilbar ist, dann können wir diesen gesamten Bereich streichen. Dann wird die nächste Frage gestellt, Ist N durch drei teilbar? Wenn nicht, dann streichen wir diesen ganzen Abschnitt. Ist N durch fünf, sieben, und so weiter teilbar? Beachte, dass dies disjunkte Mengen sind, die allmählich alle möglichen zusammengesetzten Zahlen füllen. Wenn wir irgendwo auf dem Weg ja sagen, dann haben wir den Beweis, dass N zusammengesetzt ist. A, was auch immer es zu diesem Zeitpunkt ist, ist unser Zeuge. Wir stoppen N und geben zusammengesetzt aus unserem Algorithmus aus. Andernfalls versuchen wir weiter, bis wir alle möglichen zusammengesetzten Zahlen erschöpft haben. Bis wir die Quadratwurzel von N erreichen, da wir wissen, dass jede zusammengesetzte Zahl N einen Faktor haben muss, der kleiner oder gleich der Quadratwurzel von N ist. Dies führt uns wirklich zur letzten Frage in unserem Algorithmus. Wenn keine Zeugen gefunden werden und A größer ist als die Quadratwurzel von N, dann haben wir plötzlich einen Beweis und wir stoppen und geben Primzahl aus. Beachten Sie, dass wir zwei Auswege durch unseren Algorithmus haben. Beide Wege stellen einen Beweis der Gewissheit dar, dass N entweder Primzahl oder zusammengesetzt ist. Wenn N prim ist, versuchen wir alle möglichen Teiler und schließen sie im Grunde alle aus, und das ist unser Beweis, dass N eine Primzahl ist. Das Problem mit dieser Strategie ist, dass unser Testwert A uns mindestens dazu zwingt, alle Primzahlen von zwei bis zur Quadratwurzel von N zu durchlaufen. Wenn N wächst, wächst die Anzahl der Primzahlen mit ihm. Dies führt zu vielen Iterationen im schlimmsten Fall, zum Beispiel, wenn wir eine Primzahl zu unserem Algorithmus hinzufügen. Wenn wir uns jetzt das große Ganze anschauen, stellt es den Beweis dar, wenn N eine Primzahl ist. Was wir jetzt wissen, dass wir nicht unbedingt brauchen. Niemand hat gesagt, dass wir es beweisen müssen. Wir müssen nur zu 99,9999999999999999999 % sicher sein. Hmm, also müssen wir eigentlich über den zusammengesetzten Test nachdenken, der in unserem Algorithmus verwendet wird. Denke wie wir mit unseren bisher schnellsten Teilungstests für Primzahlen versucht haben, Primzahlmuster wie 6K oder alle Primzahlen sind der Form 6K plus oder minus eins zu verwenden, um nur die Primzahlen zu durchlaufen und viele der zusammengesetzten Zahlen auszuschließen, um Zeit zu sparen. Denke daran, das ein Test wie dieser in einen zusammengesetzten Test umgewandelt werden kann. Das heißt, wenn eine gegebene Zahl N der Form 6K plus oder minus eins ist, dann können wir sagen, dass sie wahrscheinlich eine Primzahl ist, aber es gibt noch viele zusammengesetzte Zahlen, die diesem Muster folgen. Es beinhaltet nicht nur Primzahlen, sondern alle Primzahlen und einige zusammengesetzte Zahlen, und wir können diese zusätzlichen zusammengesetzten Zahlen als Leck betrachten, und dieses Leck ist unsere Fehlerquelle. Jetzt, wenn wir es umkehren und fragen, ob N nicht der Form 6K plus oder minus eins ist, dann können wir mit 100 Prozent Sicherheit sagen, dass es zusammengesetzt ist, also ist das Leck unsere Fehlerquelle auf der Primzahlen-Seite, aber in diesem Fall ist es unannehmbar, es ist kein vernachlässigbarer Fehler. Es besteht eine viel größere Wahrscheinlichkeit. Wir müssen ein neues Verfahren zur zusammengesetzten Prüfung definieren, das in der Lage ist, diesen Raum zu verkleinern und die Fehlerchance vernachlässigbar zu machen. Das bedeutet, dass wir überprüfen müssen, wie wir Fehler tatsächlich durch Iterationen reduzieren können. Ich denke, wir sollten jetzt unsere Ideen unten posten, welche Art von Tests wir durchführen möchten und vor allem, wie könnte uns ein Zufallsgenerator wirklich helfen?