Algorithmen aus dem Buch.

Paul Erdos sprach über das "Buch", in dem Gott den elegantesten Beweis für jeden mathematischen Satz aufbewahrt. Dies inspirierte sogar ein Buch (von dem ich glaube, dass es jetzt in der 4. Auflage vorliegt ): Proofs from the Book .

Wenn Gott ein ähnliches Buch für Algorithmen hätte, welche Algorithmen würden Sie für einen Kandidaten halten?

Wenn möglich, geben Sie bitte auch eine anklickbare Referenz und die wichtigsten Erkenntnisse an, die dafür sorgen, dass es funktioniert.

Bitte nur einen Algorithmus pro Antwort.

Union-find ist ein schönes Problem, dessen bester Algorithmus / Datenstruktur ( Disjoint Set Forest ) auf einem Spaghetti-Stack basiert. Es war zwar sehr einfach und intuitiv genug, um es einem intelligenten Kind zu erklären, aber es dauerte mehrere Jahre, um seine Laufzeit genau zu bestimmen. Letztendlich wurde entdeckt, dass sein Verhalten mit der inversen Ackermann-Funktion zusammenhängt, einer Funktion, deren Entdeckung einen Perspektivwechsel in Bezug auf die Berechnung kennzeichnete (und tatsächlich in Hilberts On the Infinite enthalten war ).

Wikipedia bietet eine gute Einführung in Disjoint Set Forests .

Knuth-Morris-Pratt- String-Matching. Die glattesten acht Codezeilen, die Sie jemals sehen werden.

Der Algorithmus von Blum, Floyd, Pratt, Rivest und Tarjan , um das k- te Element einer unsortierten Liste in linearer Zeit zu finden, ist ein schöner Algorithmus und funktioniert nur, weil die Zahlen genau richtig sind , um in den Hauptsatz zu passen. Es geht wie folgt:

1. Sortieren Sie jede Folge von fünf Elementen.
2. Wählen Sie jeweils den Median aus.
3. Wiederholen Sie diese Schritte, um den Median dieser Liste zu ermitteln.
4. Drehpunkt auf dem Median der Mediane (wie in Quicksort)
5. Wählen Sie die richtige Seite der Liste und die Position in dieser Liste aus und wiederholen Sie den Vorgang.

Die binäre Suche ist der einfachste, schönste und nützlichste Algorithmus, dem ich jemals begegnet bin.

Ich bin überrascht, den Floyd-Warshall-Algorithmus für die kürzesten Wege aller Paare hier nicht zu sehen :

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

$O(n^3)$$O(n^2)$

Euklidischer Algorithmus zur Berechnung des größten gemeinsamen Divisors (GCD)

Es mag etwas trivial erscheinen (besonders im Vergleich zu den anderen Antworten), aber ich finde, dass Quicksort wirklich elegant ist. Ich erinnere mich, als ich es das erste Mal sah, dachte ich, es sei wirklich kompliziert, aber jetzt scheint es mir alles zu einfach.

Huffman-Codierung für die Datenkomprimierung.

Der Miller-Rabin-Primalitätstest (und ähnliche Tests) sollte im Buch stehen. Die Idee ist, die Eigenschaften von Primzahlen zu nutzen (dh Fermats kleines Theorem zu verwenden), um probabilistisch nach einem Zeugen dafür zu suchen, dass die Zahl keine Primzahl ist. Wird nach genügend zufälligen Tests kein Zeuge gefunden, wird die Zahl als Primzahl klassifiziert.

In diesem Sinne sollte der AKS-Primalitätstest , bei dem PRIMES in P vorkommt, auf jeden Fall im Buch stehen!

Polynomidentitätstest mit dem Schwartz-Zippel-Lemma :

Wenn jemand Sie mitten in der Nacht aufweckte und Sie aufforderte, zwei univariate Polynomausdrücke auf Identität zu testen, würden Sie sie wahrscheinlich auf die normale Produktsummenform reduzieren und auf strukturelle Identität vergleichen. Leider kann die Reduzierung exponentielle Zeit in Anspruch nehmen. es ist analog zu booleschen Ausdrücken auf disjunktive Normalform zu reduzieren.

Angenommen, Sie sind der Typ, der randomisierte Algorithmen mag, besteht Ihr nächster Versuch wahrscheinlich darin, die Polynome an zufällig ausgewählten Punkten auf der Suche nach Gegenbeispielen auszuwerten und die Polynome für sehr wahrscheinlich identisch zu erklären, wenn sie genügend Tests bestehen. Das Schwartz-Zippel-Lemma zeigt, dass mit zunehmender Punktzahl die Wahrscheinlichkeit eines falschen Positivs sehr schnell abnimmt.

Es ist kein deterministischer Algorithmus für das Problem bekannt, der in Polynomialzeit abläuft.

Tiefe erste Suche . Es ist die Basis vieler anderer Algorithmen. Es ist auch täuschend einfach: Wenn Sie beispielsweise die Warteschlange in einer BFS-Implementierung durch einen Stapel ersetzen, erhalten Sie DFS?

Dijkstra-Algorithmus : das Single-Source-Problem mit dem kürzesten Pfad für einen Graphen mit nichtnegativen Kantenpfadkosten. Es wird überall verwendet und ist einer der schönsten Algorithmen auf dem Markt. Das Internet könnte ohne es nicht geroutet werden - es ist ein Kernbestandteil der Routing-Protokolle IS-IS und OSPF (Open Shortest Path First).

1. Weisen Sie jedem Knoten einen Abstandswert zu. Setzen Sie es für unseren Anfangsknoten auf Null und für alle anderen Knoten auf Unendlich.
2. Markieren Sie alle Knoten als nicht besucht. Setzt den Anfangsknoten als aktuell.
3. Berücksichtigen Sie für den aktuellen Knoten alle nicht besuchten Nachbarn und berechnen Sie deren vorläufigen Abstand (vom ursprünglichen Knoten). Wenn beispielsweise der aktuelle Knoten (A) einen Abstand von 6 hat und eine Kante, die ihn mit einem anderen Knoten (B) verbindet, 2 ist, beträgt der Abstand von B bis A 6 + 2 = 8. Wenn dieser Abstand geringer ist als der zuvor aufgezeichnete Abstand (Unendlich am Anfang, Null für den Anfangsknoten), überschreiben Sie den Abstand.
4. Wenn wir alle Nachbarn des aktuellen Knotens berücksichtigt haben, markieren Sie ihn als besucht. Ein besuchter Knoten wird nie wieder überprüft. Die jetzt aufgezeichnete Distanz ist endgültig und minimal.
5. Wenn alle Knoten besucht wurden, beenden Sie den Vorgang. Andernfalls legen Sie den nicht besuchten Knoten mit der geringsten Entfernung (vom Anfangsknoten) als nächsten "aktuellen Knoten" fest und fahren Sie mit Schritt 3 fort.

Das Sieb des Eratosthenes , einfach und intuitiv.

Ich mag auch die Schönheit von Horners Algorithmus .

Gentrys vollständig homomorphes Verschlüsselungsschema (entweder über idealen Gittern oder über ganzen Zahlen) ist schrecklich schön. Damit kann ein Dritter beliebige Berechnungen für verschlüsselte Daten durchführen, ohne auf einen privaten Schlüssel zugreifen zu müssen.

Das Verschlüsselungsschema beruht auf mehreren genauen Beobachtungen.

• Um ein vollständig homomorphes Verschlüsselungsschema zu erhalten, muss man nur ein Schema haben, das über Addition und Multiplikation homomorph ist. Dies liegt daran, dass Addition und Multiplikation (Mod 2) ausreichen, um UND-, ODER- und NICHT-Gatter zu erhalten (und damit die Vollständigkeit zu bestimmen).
• Wenn ein solches Schema vorhanden wäre, aber aufgrund einiger Einschränkungen nur für Schaltkreise mit einer begrenzten Tiefe ausgeführt werden könnte, dann kann man das Entschlüsselungs- und Wiederaufnahmeverfahren homomorph auswerten, um die Begrenzung der Schaltkreistiefe zurückzusetzen, ohne die Privatsphäre des Schlüssels zu beeinträchtigen.
• Dass durch "Quetschen" der Tiefe der Schaltungsversion der Entschlüsselungsfunktion für das Schema ein Schema ermöglicht werden könnte, das ursprünglich auf endliche, flache Schaltungen mit einer willkürlichen Anzahl von Berechnungen beschränkt war.

Craig Gentry hat in seiner Dissertation ein langjähriges (und großartiges) offenes Problem in der Kryptographie gelöst. Die Tatsache, dass ein vollständig homomorphes Schema existiert, erfordert, dass wir erkennen, dass die Berechenbarkeit eine gewisse Struktur aufweist, die wir sonst möglicherweise ignoriert haben.

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

Der Cooley-Tukey-FFT-Algorithmus .

Strassens Algorithmus zur Matrixmultiplikation.

Der stabile Heiratsalgorithmus von Gale-Shapley . Dieser Algorithmus ist gierig und sehr einfach, es ist zunächst nicht klar, warum er funktionieren würde, aber dann ist der Beweis der Korrektheit wieder leicht zu verstehen.

Der lineare Zeitalgorithmus zum Erstellen von Suffix-Arrays ist wirklich wunderschön, obwohl er nicht die verdiente Anerkennung erhielt. Http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

Gaußsche Eliminierung. Es vervollständigt die Generalisierungssequenz vom euklidischen GCD-Algorithmus zu Knuth-Bendix.

Ich war beeindruckt, als ich zum ersten Mal den Algorithmus für die Probenahme von Behältern und seinen Beweis sah. Es ist das typische "Brain Teaser" -Puzzle mit einer extrem einfachen Lösung. Ich denke, es gehört definitiv zum Buch, sowohl für Algorithmen als auch für mathematische Theoreme.

In Bezug auf das Buch heißt es, dass Erdös, als er starb und in den Himmel kam, darum bat, sich mit Gott zu treffen. Dem Antrag wurde stattgegeben und für das Treffen hatte Erdös nur eine Frage. "Darf ich in das Buch schauen?" Gott hat ja gesagt und Erdös dorthin geführt. Natürlich sehr aufgeregt, öffnet Erdös das Buch nur um folgendes zu sehen.

Satz 1: ...
Beweis: Offensichtlich.

Satz 2: ...
Beweis: Offensichtlich.

Satz 3: ...
Beweis: Offensichtlich.

Der Schildkröten- und Hasen-Algorithmus . Ich mag es, weil ich mir sicher bin, dass ich auf keinen Fall auf eine solche Idee kommen würde, selbst wenn ich mein ganzes Leben damit verschwendet hätte, sie zu finden.

Ein so grundlegendes und "triviales" Beispiel wie Euklids Beweis für unendlich viele Primzahlen:

2-Approximation für MAX-CUT - Ordnen Sie sie für jeden Scheitelpunkt unabhängig mit gleicher Wahrscheinlichkeit einer der beiden Partitionen zu.

Ich war schon immer an Christofides 'Algorithmus interessiert , der eine (3/2) -Anäherung für metrische TSP liefert. Rufen Sie mich einfach bitte an, aber ich mochte sogar den 2-Approximations-Algorithmus, der davor war . Christofides 'Trick, durch Hinzufügen eines Matchings seiner Eckpunkte ungeraden Grades einen Euler-Baum mit minimalem Gewicht zu erstellen (anstatt alle Kanten zu duplizieren), ist einfach und elegant einer optimalen Tour.

Sortieren zusammenführen . Einfach, elegant, effizient.

$O(\sqrt N)$

Algorithmen für die lineare Programmierung : Simplex-, Ellipsoid- und Innenpunktmethoden.

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Robin Moser-Algorithmus zum Lösen einer bestimmten Klasse von SAT-Instanzen. Solche Fälle können von Lovasz Local Lemma gelöst werden. Moser-Algorithmus ist in der Tat eine De-Randomisierung der Aussage des Lemmas.

Ich denke, in einigen Jahren wird sein Algorithmus (und die Technik für seinen Korrektheitsnachweis) gut verdaut und verfeinert sein, bis er ein brauchbarer Kandidat für einen Algorithmus aus dem Buch ist .

Diese Version ist eine Erweiterung seines Originalpapiers, das mit Gábor Tardos geschrieben wurde.

Marcus Hutters schnellster und kürzester Algorithmus für alle genau definierten Probleme .

Dies widerspricht dem Geist der anderen Angebote in dieser Liste, da es nur von theoretischem und nicht von praktischem Interesse ist, aber der Titel sagt schon alles. Vielleicht sollte es als Vorsichtsmaßnahme für diejenigen aufgenommen werden, die sich nur mit dem asymptotischen Verhalten eines Algorithmus befassen.

Knuths Algorithmus X findet alle Lösungen für das genaue Deckungsproblem . Was daran so magisch ist, ist die von ihm vorgeschlagene Technik, um sie effizient umzusetzen: Dancing Links .

Ich denke, wir müssen Schieber-Vishkins einbeziehen , der die niedrigsten gemeinsamen Vorfahrenabfragen in konstanter Zeit beantwortet und den Wald in linearer Zeit vorverarbeitet.

Ich mag Knuths Darstellung in Band 4, Fascicle 1, und sein Nachdenken . Er sagte, er habe zwei Tage gebraucht, um es vollständig zu verstehen, und ich erinnere mich an seine Worte:

Ich finde es ziemlich schön, aber erstaunlicherweise hat es eine schlechte Presse in der Literatur (..) Es basiert auf Mathematik, die mich begeistert.