- Donald Knuth behandelte im Stanford-Weihnachtsvortrag 2024 die strong components und weak components gerichteter Graphen und bezeichnete Tarjans Strong-Components-Algorithmus als seinen Lieblingsalgorithmus
- Fasst man eine strong component zu einem einzigen Knoten zusammen, entsteht ein zyklusfreier DAG, und der Algorithmus arbeitet, indem er eine sink strong component findet und entfernt
- Die weak component ist hier nicht die Zusammenhangskomponente bei ignorierter Richtung, sondern eine allgemeinere Partition, die strong components erneut so zusammenfasst, dass eine lineare Ordnung entsteht
- Der Tarjan-Algorithmus unterscheidet während der DFS zwischen tree arc, back arc, loop, forward arc und cross arc und liefert sowohl strong components als auch ihre topologische Sortierung
- Knuth betont, dass der Reiz nicht nur im Verfahren liegt, sondern in der tiefen Datenstruktur, die die benötigten Entscheidungsinformationen genau im richtigen Moment zugänglich macht
Ausgangspunkt des Vortrags und Knuths neues Buch
- Der einleitende Teil des Vortrags drehte sich um das neue Buch Constraint Satisfaction
- Das interne Manuskript wurde am Vortag an den Verlag geschickt, und Vorbestellungen sind nun möglich
- Ein Druck noch vor Weihnachten könnte schwierig werden, und als offizielles Erscheinungsdatum gilt offenbar der 3. Februar
- Im Buch selbst ist Januar als Druckdatum angegeben, und es war in den vergangenen fünf Jahren Knuths Hauptprojekt
- Ausführlichere Inhalte zum Thema Strong Components and Weak Components finden sich im Pre-Fascicle 12A
- Derzeit liegt das Buch bei Volume 4 Fascicle 7, frühere Fascicles wurden als Volume 4A und 4B in Hardcover-Form veröffentlicht
- Dieser Inhalt soll später das erste Drittel von Volume 4C bilden
- Der Untertitel des Vortrags lautet sinngemäß „Which algorithm do you love the most?”
- Knuth mag die Frage nach dem „Lieblingsalgorithmus“ normalerweise nicht, sagt aber, dass in diesem Fall Tarjans Strong-Components-Algorithmus die klare Antwort sei
- Als er dieses Verfahren 1973 kennenlernte, verstand er zum ersten Mal, dass auch Datenstrukturen ebenso „tief“ sein können wie Sätze oder Algorithmen
Der Unterschied zwischen strong component und weak component
- Ein gerichteter Graph besteht aus Knoten und gerichteten Pfeilen
- Wenn zwei Knoten u und v einander gegenseitig erreichen können, gehören sie zur selben strong component
- Knoten in einem Zyklus gehören alle zur selben strong component
- Selbst wenn es eingehende Pfade von mehreren Stellen gibt, kann ein Knoten, der nicht mehr nach außen gelangen kann, für sich allein eine strong component bilden
- Die von Knuth verwendete weak component ist nicht dasselbe wie eine ungerichtete Komponente bei ignorierter Richtung
- Wenn man die Richtung ignoriert und nur die Verbindung betrachtet, sollte man das laut ihm „undirected component“ nennen
- Eine weak component entsteht, indem man den DAG, der nach dem Zusammenziehen der strong components entsteht, erneut partitioniert, sodass insgesamt eine lineare Ordnung entsteht
- Zieht man jede strong component zu einem „super vertex“ zusammen, entsteht ein azyklischer Graph
- Dies kann als partielle Ordnung aufgefasst werden
- Reduziert man weiter zu weak components, erhält man eine totale oder lineare Ordnung
- Das steht auch in direktem Zusammenhang mit topologischer Sortierung
- Wenn ein x in jeder topologischen Sortierung stets vor y steht, liegen beide in verschiedenen weak components
- Wenn es eine Sortierung gibt, in der x vor y steht, und eine andere, in der y vor x steht, gehören beide zur selben weak component
- Knuth verknüpft dies mit mutual incomparability
Geschichte des Konzepts und der Algorithmen
- Das Konzept der weak component entstand in einem Briefwechsel zwischen Knuth, Ron Graham und einem als Mazkin bezeichneten Professor über ein anderes Problem
- In einem Brief vom 28. Februar 1970 von Mazkin an Graham ging es bereits um eine Partition, die eine totale Ordnung erzeugt
- Im Dezember 1970 schrieb Knuth an Graham, dass alle drei mit jeweils unterschiedlichen Ansätzen ein allgemeineres Resultat bewiesen hätten
- Knuth entschied, Mazkin als Mitautor aufzunehmen, erhielt aber kurz darauf die Nachricht, dass Mazkin unerwartet an einem Herzinfarkt gestorben war
- Die zugehörige Arbeit erschien 1972 in Discrete Mathematics volume 2 number 1
- Discrete Mathematics war damals gerade erst als Journal gestartet, und niemand ahnte, wie viele hervorragende Arbeiten dort später erscheinen würden
- Tarjans Strong-Components-Algorithmus erschien 1972 im SIAM Journal on Computing volume 1 number 2
- Tarjan war damals Doktorand, und der betreffende Artikel war der sechste Eintrag in seiner Publikationsliste
- Knuth las die Arbeit im Januar 1973 und begann den Algorithmus zu lieben
- Auch im Algorithmus-Lehrbuch von Aho, Hopcroft und Ullman ist Tarjans Algorithmus gut dargestellt
- Hopcroft teilte sich während eines Stanford-Sabbaticals ein Büro mit Tarjan und entwickelte mit ihm mehrere Algorithmen
- Hopcroft hatte bereits die Idee für einen Algorithmus zu biconnected components in ungerichteten Graphen, und Tarjan übertrug eine ähnliche Idee auf strong components in gerichteten Graphen
- Shimon Evens Buch behandelt den low point im Tarjan-Algorithmus
- Um eine Komponente zu finden, scheint man den low point zu brauchen, und um den low point zu berechnen, scheint man die Komponente bereits kennen zu müssen — dieses zirkuläre Problem löste Tarjan
Wie strong components mit DFS gefunden werden
- Knuth vergleicht die Graphsuche mit einer Höhlenerkundung
- Jeder room ist ein Knoten, und die Liste anderer rooms, die man von dort aus erreichen kann, sind die outgoing arcs
- Der Computer sieht keine Zeichnung, sondern arbeitet nur mit Knotenliste und Arc-Liste
- Das grundlegende Suchverfahren ist depth-first search
- Man folgt einem noch nicht betrachteten outgoing arc immer tiefer
- Wenn es nicht weitergeht, kehrt man zur vorherigen Position zurück
- Trifft man auf einen bereits besuchten Knoten, bestimmt man den Typ dieses arc
- In der DFS werden arcs in fünf Arten unterteilt
- tree arc: ein arc des DFS-Baums, durch den ein neuer Knoten erstmals entdeckt wird
- back arc: ein arc zurück zu einem Vorfahren
- loop: ein arc auf sich selbst, der die strong components nicht beeinflusst
- forward arc: ein arc zu einem Nachfahren
- cross arc: ein arc zu einem Knoten, der weder Vorfahr noch Nachfahr ist
- Jedes Mal, wenn der Algorithmus eine strong component entdeckt, findet er eine sink component im noch verbleibenden Graphen
- In jedem endlichen DAG gibt es immer einen sink
- Man entfernt die sink strong component und sucht dann im restlichen Graphen weiter
- Dabei erhält man gleichzeitig die strong components und ihre topologische Sortierung
- Die Leistung wird als sehr hoch dargestellt
- Für M arcs und N Knoten liegen die Speicherzugriffe im schlechtesten Fall bei etwa 5M + 17N
- Darin sind auch Arbeiten wie das Prüfen des Endes einer Arc-Liste und Pointer-Aktualisierungen enthalten
Weak components, Verbesserungen und Implementierung
- Der Algorithmus für weak components kann zusammen mit dem Auffinden der strong components ausgeführt werden
- Dabei wird genutzt, dass strong components von rechts nach links, also beginnend bei den sinks, entdeckt werden
- Wenn links eine neue strong component hinzukommt, wird entschieden, wie sie mit vorhandenen weak components zusammengeführt wird
- Für die Bestimmung von weak components sind source und sink innerhalb jeder Komponente wichtig
- Jeder sink einer weak component muss einen arc zu jeder source der nächsten weak component besitzen
- Diese Bedingung ist notwendig und hinreichend dafür, dass weak components vorliegen
- Für die Programmierung reicht es aus, nur die sources zu verfolgen, um Updates durchführen zu können
- Tarjan veröffentlichte 1974 in Information Processing Letters volume 3 number 1 einen dreiseitigen Algorithmusartikel zum Auffinden von weak components
- Knuth fasst diesen Inhalt in seinem Pre-Fascicle 12A zusammen
- Es ist nicht trivial, genügend Datenstrukturen zu pflegen, um linear time im Worst Case zu garantieren
- Auch Dijkstra behandelte das Problem der strong components
- Kapitel 25 von Dijkstras Buch behandelt „Finding the maximal strong components in a directed graph“
- Dijkstra verwendete ebenfalls die Struktur des fortlaufenden Entfernens von sink strong components, erreichte aber nicht Tarjans Vereinfachung über den low point
- Dijkstras Lösung führt vier neue Arrays zur Nachverfolgung der Struktur ein
- Knuth und Tarjan haben kürzlich die bestehenden Algorithmen erneut betrachtet und bessere Definitionen sowie eine verbesserte Fassung entwickelt
- Sie überarbeiteten sie auf Grundlage von Ideen aus den 1970er Jahren von Kurki-Suonio, wobei der ursprüngliche Artikel einen Fehlschluss enthielt
- Im bisherigen Verfahren wurde der Aufwand von etwa 7 Zugriffen pro arc auf etwa 5 reduziert
- Durch das Zusammenlegen einiger Felder entstand eine kompliziertere, aber schnellere Form, die Knuth scherzhaft nicht als „premature optimization“, sondern als „post-mature optimization“ bezeichnet
- Die Implementierung wird als CWEB-Programm bereitgestellt
- Als Programmnamen werden Tarjan strong and weak und Tarjan strong genannt
- Die Eingabe ist ein Graph im Stanford-GraphBase-Format
- Knuth sagt, er wolle die Programme auf seiner Website leichter auffindbar machen und den Umstand beheben, dass sie seit 2022 nicht mehr aktualisiert wurden
- In der Stanford GraphBase gibt es als Beispiel einen gerichteten Graphen mit etwa 1.000 Kategorien aus Rogets Thesaurus als Knoten und synonymen oder antonymen Beziehungen als arcs
1 Kommentare
Meinungen auf Hacker News
Als ich 2022 San Francisco besuchte, lief ich über den Stanford-Campus und wollte gerade durch einen ruhigen, leeren Gebäudeflur im Sommer wieder hinausgehen, als ich zufällig Knuths Büro sah.
Im Verhältnis zu seinem Ruhm war es überraschend klein, sodass ich noch einmal hinsah; gleichzeitig wirkte der Raum gerade deshalb passend zu seiner bescheidenen Art.
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
Ich habe auch nicht nur einen, sondern zwei Belohnungsschecks von ihm. Es waren nur kleine Tippfehler, aber diese beiden Dokumente zu besitzen, ist wirklich großartig.
Niemand wird es missbrauchen, aber ich fände es ziemlich unheimlich, wenn ich herausfinden würde, dass ein Foto meines Büros ohne mein Wissen online steht.
Ich lese in meiner Freizeit TAOCP 4A und 4B und sie sind wirklich hervorragend; ich kann sie sehr empfehlen.
Für die meisten Programmierer ist das nicht praktisch anwendbar, aber die Art, wie Knuth Algorithmen entwirft und erklärt, ist erstaunlich und einzigartig.
Besonders die Implementierung von Dancing Links in 4B wurde seit dem berühmten Paper deutlich überarbeitet; sie ist eine ausgefeilte und schöne Datenstruktur und zugleich sehr schnell. Selbst in seinen 80ern ist er immer noch beeindruckend.
Als wir die Kosten für unsere benötigte Größenordnung berechneten, kamen zig Millionen Dollar heraus, während das gesamte Infrastruktur-Budget von Route 53 im Bereich von Zehntausenden Dollar lag. Am Edge verwendeten wir CloudFront-Server mit ausgefallenen Festplatten als Nameserver wieder, die API-Server waren ebenfalls bescheiden, und das Team bestand aus etwa sechs Personen. „Scrappy“ im AWS-Stil bedeutete, fast kein Geld auszugeben, Downside-Risiken zu verringern und schnell zu liefern.
Also konnten wir nicht um zig Millionen Dollar für Packet Scrubber bitten; außerdem hätten sie lange Lieferzeiten gehabt und uns womöglich zu stark von einem bestimmten Anbieter abhängig gemacht.
Anfangs entschieden wir uns, die Route-53-Nameserver in einem dedizierten IP-Bereich zu betreiben, um sie bis zu einem gewissen Grad zu isolieren, und konnten mit dedizierten Netzwerk-Links verhindern, dass andere Amazon-Infrastruktur betroffen war. Das löste jedoch nicht das Problem, dass Route-53-Kunden untereinander ihr Schicksal teilten; der eigentliche Plan war im Grunde: „Wenn Probleme auftreten, filtern wir mit den vorhandenen Netzwerk- und System-Tools besonders gut.“
Im Frühsommer jenes Jahres las ich den neuesten Faszikel zu Knuths 4A und war tief in kombinatorische Algorithmen versunken. Eines Nachts hatte ich plötzlich den Gedanken, dass man, wenn man viele virtuelle Nameserver erstellt, jedem Kunden eindeutig eine Kombination aus vier virtuellen Nameservern zuweisen könnte. Auch den Grad der Überschneidung konnte man steuern, und ich rechnete schnell aus, dass bei ungefähr 2.000 Nameservern garantiert werden konnte, dass keine zwei Kunden mehr als zwei davon gemeinsam nutzen. In Experimenten lassen sich Domains noch gut auflösen, wenn zwei Nameserver nicht erreichbar sind, aber darüber hinaus wird es problematisch; deshalb war diese Zahl wichtig.
Der rekursive Suchalgorithmus zur IP-Zuweisung war direkt von einem Algorithmus aus 4A inspiriert und bot zwei weitere, von den Kundendomains unabhängige Isolationsdimensionen. Kunden erhalten vier Nameserver aus vier unabhängigen „Stripes“, was den unterschiedlichen Top-Level-Domains entspricht, die wir in den Nameserver-Namen verwenden (co.uk, com, net, org). Wenn also in einer dieser Top-Level-Domains ein Problem wie ein DNSSEC-Fehler auftritt, ist nur ein Nameserver betroffen.
Außerdem kamen sie aus vier unabhängigen „Braids“, sodass garantiert werden konnte, dass keine zwei Nameserver einen bestimmten Netzwerkpfad oder physische Hardware teilen. Obwohl ich durch meinen Statistik- und Kryptografie-Hintergrund Kombinatorik kannte, hätte ich dieses Design nicht entwickeln können, wenn ich 4A nicht gelesen hätte.
Nie zuvor war ich von einer Lösung so begeistert. Denn sie bot praktisch ohne zusätzliche Infrastrukturkosten eine nachweisbare Isolation auf Netzwerk-IP-Ebene zwischen Kundendomains. Es war Mathematik. Ganz kostenlos war es nicht: Wir mussten 2.000 Anycast-IP-Adressen verwenden, und wegen der Art, wie viele Top-Level-Domains Nameserver-Registrierungen und Glue Records verlangen, mussten wir außerdem 512 Domains registrieren. Der Prozess mit den Registraren war ziemlich unterhaltsam, aber am Ende haben wir es geschafft.
Wir nannten diese Methode Shuffle Sharding, und sie fühlte sich eher wie eine Entdeckung als wie eine Erfindung an. Viele Multi-Tenant-Systeme mit zufälliger Platzierung erhalten eine Art Shuffle Sharding, und Netzwerk-Filtering-Techniken wie Stochastic Fair Blue erzielen durch zeitbasiertes Hashing einen ähnlichen Effekt. Aber ich hatte noch nie genau diese Methode mit dem Grad an Kontrolle gesehen, den wir anwenden konnten; und wir konnten sie sogar zu rekursiv verschachteltem Shuffle Sharding erweitern, das nicht nur Aufrufer isoliert, sondern in „Aufruf im Namen von“-Mustern auch die Aufrufer der Aufrufer über weitere Ebenen hinweg.
Einige Jahre später ging ich aus Dankbarkeit persönlich zu Knuths Weihnachtsvorlesung und saß in der ersten Reihe. Da man nie weiß, was einen inspiriert, lese ich auch heute noch alles, was Knuth veröffentlicht. Einschließlich seiner Orgelstücke.
Deshalb halte ich Knuths Bücher für Programmierer für überraschend praktisch. Sie erweitern das Denken und vertiefen das Verständnis – was will man mehr?
Das ursprüngliche Dancing-Links-Paper ist eines meiner Lieblingspaper. In Sätzen wie „Dieser Prozess lässt die Zeigervariablen in der globalen Datenstruktur einen sorgfältig choreografierten Tanz aufführen“ sieht man Knuths Liebe zu Algorithmen unmittelbar.
Ich verwende das für die Kreuzworträtsel-Erzeugung, indem horizontale und vertikale Wörter eine exakte Überdeckung (exact cover) des Gitters bilden.
Ich frage mich, ob der aktualisierte Algorithmus weniger Speicher benötigt.
Für dieses große Problem schätze ich, dass es etwa 100 Millionen Lösungen gibt; selbst wenn man 100 pro Sekunde findet, dauert es rund zehn Tage, bis man fertig ist.
Das Problem, an dem ich arbeite, besteht darin, bei „Fancy Tetris Houten Puzzel“ die Anzahl der Fälle zu zählen, in denen gleichfarbige Teile alle verbunden sind, indem sie mindestens eine Kante gemeinsam haben.
Ich denke auch über andere Algorithmen nach, die weniger speicherempfindlich sind, um dieses Exact-Cover-Problem zu lösen.
Ich frage, weil ich erst vor Kurzem begonnen habe, Literatur zur Informatik zu lesen.
Als ich vor ein paar Jahren in San Francisco war, war ich überrascht zu erfahren, dass Donald Knuth nicht nur noch lebt, sondern weiterhin jedes Jahr in Stanford Vorlesungen hält.
Die Nacht, in der ich auf dem Campus das Gebäude suchte und ihn persönlich über ein Thema sprechen sah, dem ich kaum folgen konnte, wird mir lange in Erinnerung bleiben. Donald Knuth ist wirklich eine Legende.
Ein Teammitglied fand letzten Monat einen Fehler in Seminumerical Algorithms und erhielt einen Belohnungsscheck über 1 hexadecimal dollar; dazu kam ein Ausdruck der ursprünglichen E-Mail mit handschriftlichen Anmerkungen.
Was mich an Donald Knuth am meisten inspiriert, sind seine über Jahrzehnte anhaltende Hingabe und Disziplin.
Da ich selbst ständig Projekte, Sprachen und Distributionen wechsle, kann ich wirklich viel von ihm lernen.
Die Kleidung ist sehr kräftig und lebendig, sie wirkt wie eine Welt- bzw. Volkstracht, wie man sie früher in Dörfern getragen hat; ich bin mir aber nicht sicher, ob sie iranisch, slawisch oder irgendwo dazwischen ist.
Kann das jemand besser einschätzen?
Meine Erinnerung ist verschwommen, und es könnte auch mit seiner Frau zu tun gehabt haben. Seit Mitte der 2010er scheint er es bei Vorträgen häufig zu tragen, und irgendwo müsste es eine Erklärung dazu geben.
2012 stand ich einmal neben Knuth, als er auf einen Fensterrahmen klettern wollte, um zu sehen, wie die olympische Fackel auf den Platz vor der Manchester Town Hall kam. Ich sprach ihn an und streckte für einen Moment die Hand aus, weil ich befürchtete, er könnte aus dem Fenster fallen, aber es war alles in Ordnung. Er wirkte auf mich wie jemand voller Neugier, mit leuchtenden Fragen und Intelligenz, und jünger, als sein Alter vermuten ließ.
Wir nahmen beide an einer Veranstaltung zum 100. Geburtstag von Alan Turing teil, und es war erstaunlich, im selben Raum Größen der Informatik wie Knuth, Gary Kasparov, Fred Brooks, Vint Cerf und andere zu sehen. In der Mittagspause kam draußen auf dem Platz die olympische Fackel an, und er konnte nicht widerstehen, sie sich anzusehen. Er schien der Einzige zu sein, der sich darüber richtig freute.
Beim Bankett an diesem Abend hielt er einen Vortrag, und als ich ihn später wieder in Manchester traf, kurz nachdem 4B erschienen war, bat ich ihn, das Buch zu signieren; da erkannte er mich vage von der früheren Veranstaltung wieder.
Ich erzähle das, weil ich finde, dass sein Hemd auf einen viel eklektischeren und neugierigeren Geist hindeutet. An anderer Stelle habe ich dafür ebenfalls deutliche Belege gesehen.
Vielleicht stammt daher seine Zuneigung zu traditioneller Sami-Kleidung.
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Ich habe nachgesehen: Er ist 87 Jahre alt. Donald Knuth wurde am 10. Januar 1938 geboren.
Wow.
Knuth ist immer noch verblüffend.
Allerdings ist es sehr überraschend und enttäuschend, dass bei Stanford niemand eine Tonaufnahme hinbekommen hat, die diesem Material angemessen wäre. Es klingt, als hätte jemand mit einem Recorder in der Tasche aufgenommen.
Ich meine nicht Knuths Stimme im Alter; man muss nur hören, wie schlecht die Tonqualität ist, wenn er innehält und Fragen aus dem Publikum annimmt.
Solche Videos erinnern mich daran, warum ich Computer überhaupt lieben gelernt habe.
Es ist ziemlich erstaunlich, dass er immer noch so scharfsinnig ist. Leider hielt er schon keine Vorlesungen mehr, als ich vor gut 20 Jahren Undergraduate war.
Mir gefällt, wie er mit Fragen umgeht: https://youtu.be/Hi8r_63LGyg?t=827
Er nimmt sich Zeit, zu verstehen, was gefragt wird, und antwortet sehr klar.