Silicon Valley Yoda

Donald Knuth, ein Meister der Algorithmen, denkt über 50 Jahre Arbeit an seiner Hauptkreation nach, dem Buch „The Art of Programming“, das er weiterhin ergänzt

Donald Knut in seinem Haus in Stanford, Kalifornien. Ein gruseliger Perfektionist hat eine Belohnung dafür vergeben, dass er Fehler in seinen Büchern gefunden hat.

Seit einem halben Jahrhundert nimmt der Stanford-Informatiker Donald Knuth, ein bisschen wie Yoda - obwohl er 193 cm groß ist und eine Brille trägt - eine dominierende Stellung als spiritueller Lehrer auf dem Gebiet der Algorithmen ein.

Er ist Autor von The Art of Programming, einer Monographie, die er bis heute mit 4 Bänden schreibt und die das Werk seines Lebens ist. Der erste Band wurde 1968 veröffentlicht, und alle Bände zusammen (im Set für 250 USD verkauft) wurden 2013 in die Liste der Bücher aufgenommen, die das letzte Jahrhundert der Wissenschaft bildeten und von American Scientist zusammengestellt wurden. Es enthält auch die Sonderausgabe von Charles Darwins Autobiographie, Tom Wolfs Buch " Guys What You Need! ", Rachel Carsons Buch " Silent Spring " und die Monographien von Albert Einstein, John von Neumann und Richard Feynman.

Die "Kunst des Programmierens", die in über einer Million Exemplaren gedruckt wurde, ist eine Bibel auf ihrem Gebiet. „Es sieht aus wie eine echte Bibel - sie ist sehr lang und umfassend; Es gibt keine anderen so umfassenden Bücher “, sagt Peter Norvig, Forschungsdirektor bei Google. Nach 652 Seiten schließt der Band mit einem Zitat auf der Rückseite eines Buches von Bill Gates: „Wenn Sie das ganze Buch lesen können, senden Sie mir Ihren Lebenslauf.“

Es beginnt mit einer Passage aus der McCall Recipe Collection:

Hier ist ein Buch, das Sie in Tausenden Ihrer Briefe veröffentlichen möchten. Wir haben Jahre gebraucht, um unzählige Rezepte zu testen und zu überprüfen, um Ihnen nur das Beste, Interessante, Ideale zu bieten.

Das Buch listet die Algorithmen auf, Rezepte, die das digitale Zeitalter speisen - obwohl, wie Dr. Knut gerne betont, Algorithmen auch auf babylonischen Tablets zu finden sind, die 3800 Jahre alt sind. Er ist ein hoch angesehener Algorithmusist; Einige der wichtigsten Muster sind nach ihm benannt, beispielsweise der Knut-Morris-Pratt-Algorithmus zum Auffinden eines Teilstrings in einem String. Es wurde 1970 erfunden und findet alle Vorkommen einer bestimmten Buchstabenfolge im Text - zum Beispiel, wenn Sie Strg-F drücken, um nach einem Wort in einem Dokument zu suchen.

Dr. Knut ist jetzt 80 und kleidet sich normalerweise so, wie er es war, als er noch ein junger Geek war, als er gerade mit dieser Odyssee begann: Ein langärmeliges T-Shirt hakt unter einem kurzärmeligen T-Shirt und Jeans - zumindest zu dieser Jahreszeit. In jenen Tagen schrieb er Programme in Maschinencode, gespielt mit Nullen und Einsen.

"Knut hat deutlich gemacht, dass das System bis auf die Ebene der Maschinencodes verstanden werden kann", sagte Dr. Norvig. Wenn Algorithmen heute unser Leben steuern (und stören), hat der durchschnittliche Programmierer keine Zeit, sich mit dem binären Durcheinander zu befassen. Er arbeitet mit Abstraktionshierarchien, mit Codeebenen - und oft mit Codeketten, die aus Bibliotheken entlehnt wurden. Aber die Elite der Programmierer fällt manchmal auf die niedrigsten Ebenen.

"Bei Google sammeln wir manchmal nur Code von dem, was wir haben", sagte Norvig während eines Treffens des Google Trips-Teams in Mountain View. „Und manchmal, wenn Sie Milliarden von Benutzern bedienen müssen, müssen Sie dies effizient tun. Eine Effizienzsteigerung von 10% kann zu Milliarden von Dollar führen. Um diese letzte Effizienzstufe zu erreichen, müssen Sie verstehen, was ganz unten passiert.


Dr. Knut an der California Tech, wo er 1963 promovierte.

Oder wie Andrei Broder, ein berühmter Google-Wissenschaftler und einer von Knuths ehemaligen Studenten, während des Treffens erklärte: „Wir brauchen eine theoretische Grundlage für unsere Arbeit. Wir brauchen keine leichtfertigen, umständlichen, zweitklassigen Algorithmen. Wir wollen nicht, dass andere Algorithmuswissenschaftler sagen: "Ja, ihr seid Idioten."

Die 2016 eingeführte Google Trips-App ist ein Reisealgorithmus für die ganztägige touristische Unterhaltung. Das Team arbeitete daran, " die Qualität der schlimmsten Tage zu maximieren " - der Algorithmus sollte beispielsweise vermeiden, dass der Benutzer mehrmals an dieselben Orte geschickt werden muss, um verschiedene Attraktionen zu erkunden. Sie wurden von einem 300 Jahre alten Algorithmus inspiriert, der vom Schweizer (sowie deutschen und russischen) Mathematiker Leonhard Euler erfunden wurde, der einen Weg durch die preußische Stadt Königsberg (heute Kaliningrad) zeichnen wollte und alle sieben Brücken nur einmal überquerte. Knut geht im ersten Band seiner Abhandlung auf das klassische Euler-Problem ein. Er hat einmal die Euler-Methode angewendet, um eine computergesteuerte Nähmaschine zu programmieren.


Das Befolgen von Knuts Doktrin hilft, Idiotie zu vermeiden. Er ist dafür bekannt, das Konzept der „literarischen Programmierung“ einzuführen und die Bedeutung des Schreibens von Code hervorzuheben, den nicht nur Computer, sondern auch Menschen lesen können - ein Konzept, das heute wie etwas Altmodisches erscheint. Knut behauptete sogar, dass einige Computerprogramme als literarische Werke angesehen werden können, zusammen mit den Gedichten von Elizabeth Bishop und dem Roman American Pastoral von Philip Roth, der den Pulitzer-Preis verdient.

Er ist auch bekannt für seinen Perfektionismus. Randal Munroe, der Autor der Cartoons xkcd und Thing Explainer, erfuhr zuerst von Programmierern von Knut, die die Auszeichnung erwähnten, die er versprach, an jeden zu zahlen, der in einem seiner Bücher einen Fehler gefunden hatte. Monroe erinnert sich: "Die Leute sprachen davon, einen solchen Scheck zu erhalten, als wäre es ein Nobelpreis für Informatik."

Die anspruchsvollen Standards von Knut, sowohl literarisch als auch im Rest, können erklären, warum das Werk seines ganzen Lebens bei weitem nicht vollständig ist. Er diskutierte mit Sergey Brin, Mitbegründer von Google und seinem ehemaligen Studenten, ob Brin seine Promotion beenden würde, bevor Knut seine Monographie fertigstellte.

Dawn-Algorithmus

Im Alter von 19 Jahren veröffentlichte Knut seine erste technische Arbeit „Das potentiologische System der Gewichte und Maße “ in der Zeitschrift Mad [Es war eine humorvolle Zeitschrift, und Potrebibi ist das polnische Wort, das im Englischen für Absurdität verwendet wird. Zum Beispiel führte Knut in seiner Arbeit ein neues Längenmaß von einem Potrecybi ein, das der Dicke der 26. Ausgabe der Zeitschrift entspricht. übersetzt.]. Schon vor dem Aufkommen der Informatik wurde er Spezialist für Informatik und studierte Mathematik an der Bildungseinrichtung, die heute als Keyes University der Western Reserve Region bezeichnet wird. Er studierte ausgewählte Programme, die für den IBM 650-Schul-Mainframe, einen Dezimalcomputer, geschrieben wurden, und schrieb sie und das im Klassenzimmer verwendete Lehrbuch neu, um Ungenauigkeiten zu erkennen. Als Hobby berechnete er Statistiken für eine Basketballmannschaft und schrieb ein Programm, das ihnen half, seine Liga zu gewinnen. Dank dessen drehte der renommierte Fernsehjournalist Walter Cronkite sogar eine Fernsehgeschichte über ihn mit dem Titel „Electronic Trainer“.


Während der Sommerferien verdiente Knut mehr Geld als seine Lehrer im Jahr, indem er Compiler erstellte. Der Compiler ist wie ein Übersetzer, verwandelt eine Programmiersprache auf hoher Ebene (die an Algebra erinnert) in eine Sprache auf niedriger Ebene (manchmal ist es ein mysteriöser Binärcode) und verbessert im Idealfall das Programm. In der Informatik ist Optimierung eine Kunst, die sich in einem weiteren Knuth-Sprichwort widerspiegelt: "Vorzeitige Optimierung ist die Wurzel aller Übel."

Infolgedessen wurde Knut selbst zum Compiler und entdeckte versehentlich einen neuen Bereich, den er später "Analyse von Algorithmen" nannte. Der Verlag beauftragte ihn, ein Buch über Compiler zu schreiben, aber aus dem Projekt wurde ein Buch, in dem alles gesammelt wurde, was er über das Schreiben von Programmen für Computer wusste - ein Buch über Algorithmen.


Knut studierte 1981 die Ausgabe des Mad Magazine von 1957, in der sein erster technischer Artikel veröffentlicht wurde.


Die Kunst des Programmierens, Bände 1-4.

„Zu Beginn der Renaissance gab es bereits Zweifel an der Herkunft dieses Wortes“, beginnt das Buch. "Frühe Linguisten versuchten, seinen Ursprung zu verstehen, indem sie Kombinationen wie Algiros [krankhaft] + Arithmos [Zahl] schufen." Knut fährt fort, dieser Name sei zu Ehren des persischen Autors des Lehrbuchs Abu Abdullah Muhammad ibn Musa al-Khwarizmi aus dem 9. Jahrhundert erschienen, dessen Name in der lateinischen Aufzeichnung wie „Algorithmus“ zu klingen begann. Knut, der sich nie mit halben Sachen zufrieden gab, pilgerte 1979 in die Heimat von al-Khwarizmi nach Usbekistan [ genauer gesagt, er nahm an einer Konferenz in Urgench teil. perev. ].

Knut wollte von Anfang an ein Buch schreiben. Bald geschah der Urknall in der Informatik, also überarbeitete er sein Projekt und teilte es in sieben Bände auf. Jetzt veröffentlicht er Teilbände oder Ausgaben. Der nächste „Band 4, Ausgabe 5“, der unter anderem „Backtracking“ und „Dance Links“ beschreibt, sollte bereits 2018 erscheinen. Er wurde jedoch bis April verschoben, da der Autor immer mehr neue Aufgaben findet, die er definitiv präsentieren möchte.

Um die Chancen zu optimieren, das Ende der Arbeit zu erreichen, hat Knut seine Zeit lange Zeit streng überwacht. Er ging im Alter von 55 Jahren in den Ruhestand, beschränkte das öffentliche Sprechen und lehnte E-Mails ab (zumindest offiziell). Andrei Broder erinnert sich, dass Zeitmanagement in den 1980er Jahren ein bestimmendes Merkmal seines Lehrers war.

Knut traf die Schüler normalerweise freitags am Morgen, bis er die Abende im Labor von John McCarthy, einem der Pioniere der künstlichen Intelligenz, verbrachte, um auf Computer zuzugreifen, wenn sie frei waren. Knut war erschrocken darüber, wie das Buch, das ihm am Herzen lag, nach dem Aufkommen digitaler Publishing-Systeme aussah, und setzte sich zum Ziel, ein Computersystem für das typografische TeX-Set zu entwickeln, das nach wie vor der Goldstandard für alle Formen wissenschaftlicher Kommunikation und Veröffentlichungen ist. Einige halten es für den größten Beitrag von Knut und den größten Beitrag zur Druckerei seit Gutenberg.

Diese Verzögerung von zehn Jahren trat zu einer Zeit auf, als verschiedene Menschen Computer benutzten und nachts schneller arbeiteten, wenn die meisten Menschen schliefen. Daher wechselte Knut zu einem nächtlichen Lebensstil, verschob den Zeitplan um 12 Stunden und änderte die Zeit für Treffen mit Studenten am Freitag von 8 auf 12 Uhr nachts. Broder erinnert sich: "Als ich meiner Freundin sagte, dass wir am Freitagabend nichts tun könnten, weil ich um 22 Uhr einen Termin mit meinem Vorgesetzten hatte, dachte sie:" Es klingt so dumm, dass es wahr zu sein scheint. " ".

Wenn Knut sich jedoch entscheidet, irgendwo persönlich teilzunehmen, widmet er diesem Ereignis seine ganze Aufmerksamkeit. "Es ist eine Freude, mit ihm zusammen zu sein", sagte Jennifer Chase, Geschäftsführerin von Microsoft Research. „Er ist maximal in der Gemeinde. Wenn Sie eine Optimierungsfunktion hätten, die Wärme und Tiefe repräsentiert, dann wäre das Don. “


Knut bespricht Schriften mit Hermann Zapf, einem Schriftentwickler.

Sonntag mit einem Algorithmus

Knut lebt in Stanford und trifft sich sonntags mit Menschen. Was er für den ganzen Tag beiseite legte, war außergewöhnlich - er ist normalerweise während seines Tagesschlafes nicht verfügbar, was ein heiliges Ritual ist, das von 13 bis 16 Stunden dauert. Er begann seinen Tag früh in der Ersten Lutherischen Kirche von Palo Alto, wo er vor einer Menschenmenge, die sich in einem Raum ohne Stühle versammelt hatte, Unterricht für die Sonntagsschule gab. Auf dem Heimweg beginnt er über Mathematik zu philosophieren.

"Ich werde nie alles wissen", sagte er. "Mein Leben wäre viel schlimmer, wenn es keine Fragen gäbe, auf die ich die Antworten kennen würde, und wenn es keine Fragen gäbe, auf die ich die Antworten nicht kennen würde." Anschließend bot er eine Tour durch das „moderne Kalifornien“ an, das er und seine Frau 1970 errichteten. Sein Büro ist voller Stapel von Flash-Laufwerken und am Valentinstag mit Kunsthandwerk von Jill, einer Grafikdesignerin, dekoriert. Am eindrucksvollsten ist das Musikzimmer, das um eine maßgeschneiderte Orgel mit 812 Pfeifen herum gebaut wurde. Der Tag endete mit einer Party mit Bier und Rätseln.

Rätsel, Spiele, ein Roman über surreale Zahlen schreiben, eine 90-minütige multimediale Musikkomposition Fantasia Apocalyptica komponieren - solche Dinge fangen an . Ein Abschnitt seines Buches heißt Rätsel gegen die reale Welt. Er schickte einen Auszug aus dem Buch an ein Team aus Vater und Sohn, Martin Demein, einem Künstler, und Eric Demein, einem IT-Spezialisten, der am MIT arbeitet, als Knut ihre „ algorithmischen Puzzle-Schriften “ in das Buch aufnahm.

"Ich war angenehm überrascht", sagte Eric Demain. "Es ist eine Ehre, in dieses Buch einzusteigen." Er erwähnte ein weiteres Zitat von Knut, einer inspirierenden zweijährlichen Konferenz über Unterhaltung mit Algorithmen : „Das Hauptziel war wahrscheinlich immer das Vergnügen.“

Und dann, sagte Demane, wurde dieser Bereich zu einem praktischen. Ingenieure, Wissenschaftler, Künstler - alle kommen zusammen, um echte Probleme wie das Falten von Protein, Robotik und Airbags mithilfe der von den beiden Demane entwickelten Origami- Methoden zu lösen, Papier zu falten und in verschiedene Formen zu binden.

Natürlich verursacht all dieses algorithmische Durcheinander echte Probleme. Von Menschen geschriebene Algorithmen, die sich immer komplexeren Aufgaben nähern und mit Fehlern und Vorurteilen gefüllten Code ausgeben, sind bereits ziemlich unangenehm. Schlimmer noch, dies sind Algorithmen, die nicht von Menschen, sondern von Maschinen geschrieben wurden.

Programmierer trainieren immer noch Maschinen und geben ihnen Daten. Daten sind ein neuer Bereich für Fehler und Verzerrungen, und es ist schwieriger, sie zu erfassen und zu korrigieren. Kevin Slavin, Associate Professor am MIT Media Lab, sagte jedoch: „Jetzt schreiben wir Algorithmen, die nicht lesen können. Dies ist ein einzigartiger historischer Moment, in dem wir mit Ideen, Handlungen und Versuchen arbeiten, die von der Physik verursacht werden und von Menschen stammen, aber von Menschen nicht verstanden werden. “ Slavin bemerkt oft: "Sie haben eine glänzende Zukunft, wenn Sie ein Algorithmus sind."


Knut an seinem Schreibtisch zu Hause, 1999.


Anmerkungen

Und es wird umso schöner sein, wenn Sie ein in Knut versierter Algorithmus sind. "Heute verwenden Programmierer das, was Knut und andere als Komponenten ihrer Algorithmen verwendet haben, und kombinieren dies mit allen möglichen anderen Dingen, die sie benötigen", sagte Dr. Norvig von Google.

„Mit AI machen wir dasselbe. Es ist nur so, dass der Kombinationsschritt automatisch auf der Grundlage der Daten und nicht auf der Grundlage der Arbeit des Programmierers erfolgt. Wir brauchen die KI, um die Komponenten kombinieren zu können, um anhand der Daten die richtige Antwort zu erhalten. Sie müssen jedoch entscheiden, um welche Komponenten es sich handelt. Es kann vorkommen, dass jede der Komponenten eine Seite oder ein Kapitel von Knut ist, da dies der beste Weg ist, eine Aufgabe zu erfüllen. “

Wir haben Glück, dass Knut dies weiterhin tut. Er ist der Meinung, dass es weitere 25 Jahre dauern sollte, bis die „Art of Programming“ abgeschlossen ist, obwohl sich diese Einschätzung seit den 1980er Jahren nicht geändert hat. Werden die Algorithmen, die andere Algorithmen schreiben, ihr Kapitel im Buch oder die Seite im Epilog erhalten? "Auf keinen Fall", sagte Knut.

"Ich bin besorgt über die Auswirkungen, die Algorithmen auf die Welt haben", fügte er hinzu. - Alles begann mit der Tatsache, dass Informatiker besorgt waren, weil niemand ihnen zuhörte. Jetzt mache ich mir Sorgen, dass zu viele Leute uns zuhören. "

☃