Wissenschaft ist das, was wir gut genug verstehen, um es einem Computer zu erklären; Kunst ist alles andere.
Donald Ervin Knuth ist ein amerikanischer Informatiker, Mathematiker und Professor Emeritus an der Stanford University. Er ist der Empfänger des ACM Turing Award von 1974, informell als der Nobelpreis der Informatik bekannt. Knuth wird der „Vater der Algorithmenanalyse" genannt.
Er ist der Autor des mehrbändigen Werks The Art of Computer Programming. Er trug zur Entwicklung der rigorosen Analyse der Rechenkomplexität von Algorithmen bei und systematisierte formale mathematische Techniken dafür. In diesem Prozess verbreitete er auch die asymptotische Notation. Zusätzlich zu grundlegenden Beiträgen in mehreren Bereichen der theoretischen Informatik ist Knuth der Schöpfer des TeX-Computersatzsystems, der zugehörigen METAFONT-Schriftdefinitions- und Rendering-Sprache und der Computer Modern-Familie von Schriftarten.
Als Schriftsteller und Gelehrter schuf Knuth die WEB- und CWEB-Computerprogrammiersysteme, die dazu entwickelt wurden, literarisches Programmieren zu fördern und zu erleichtern, und entwarf die MIX/MMIX-Befehlssatzarchitekturen. Knuth lehnt die Vergabe von Softwarepatenten stark ab und hat seine Meinung gegenüber dem United States Patent and Trademark Office und der European Patent Organisation geäußert.
Biografie
Frühes Leben
Knuth wurde in Milwaukee, Wisconsin, als Sohn der Deutschamerikaner Ervin Henry Knuth und Louise Marie Bohning geboren. Sein Vater besaß ein kleines Druckunternehmen und unterrichtete Buchhaltung. Donald, ein Schüler der Milwaukee Lutheran High School, dachte sich geniale Wege aus, um Probleme zu lösen. Zum Beispiel trat er in der achten Klasse in einen Wettbewerb ein, um die Anzahl der Wörter zu finden, die aus den Buchstaben in „Ziegler's Giant Bar" neu angeordnet werden könnten; die Richter hatten 2.500 solcher Wörter identifiziert. Mit Zeit, die er sich durch eine vorgetäuschte Magenschmerzen vom Schulunterricht verschaffte, und indem er das Problem umgekehrt anging, nutzte Knuth ein umfassendes Wörterbuch und bestimmte, ob jeder Wörterbucheintrag mit den Buchstaben aus dem Ausdruck gebildet werden konnte. Mit diesem Algorithmus identifizierte er über 4.500 Wörter und gewann den Wettbewerb. Als Preise erhielt die Schule einen neuen Fernseher und genug Schokoriegel für alle seine Schulkameraden zum Essen.
Bildung
Knuth erhielt ein Stipendium in Physik für das Case Institute of Technology, das jetzt Teil der Case Western Reserve University in Cleveland, Ohio ist, und schrieb sich 1956 ein. Er trat auch der Beta Nu Chapter der Theta Chi-Bruderschaft bei. Während des Physikstudiums am Case wurde Knuth mit dem IBM 650, einem frühen kommerziellen Computer, bekannt gemacht. Nach dem Lesen des Handbuchs des Computers beschloss Knuth, den Assembly- und Compiler-Code für die an seiner Schule verwendete Maschine neu zu schreiben, da er glaubte, dies besser tun zu können.
1958 erstellte Knuth ein Programm, um der Basketballmannschaft seiner Schule zum Sieg zu verhelfen. Er wies Spielern „Werte" zu, um ihre Wahrscheinlichkeit zu bewerten, Punkte zu erzielen, einen neuartigen Ansatz, über den Newsweek und CBS Evening News später berichteten.
Knuth war einer der Gründungsredakteure der Engineering and Science Review des Case Institute, die 1959 als beste Fachzeitschrift einen nationalen Preis erhielt. Danach wechselte er von Physik zu Mathematik und erhielt 1960 zwei Abschlüsse vom Case: seinen Bachelor of Science-Abschluss und gleichzeitig einen Master of Science durch eine Sonderauszeichnung der Fakultät, die seine Arbeit als außergewöhnlich hervorragend betrachtete.
1963 erwarb er mit dem Mathematiker Marshall Hall als Berater einen PhD in Mathematik vom California Institute of Technology.
Frühe Arbeiten
Nach seiner Promotion trat Knuth als Assistenzprofessor der Fakultät von Caltech bei.
Er akzeptierte einen Auftrag, ein Buch über Computersprachen-Compiler zu schreiben. Während der Arbeit an diesem Projekt beschloss Knuth, dass er das Thema nicht angemessen behandeln konnte, ohne zuerst eine grundlegende Theorie der Computerprogrammierung zu entwickeln, die zu The Art of Computer Programming wurde. Er plante ursprünglich, dies als einzelnes Buch zu veröffentlichen. Als Knuth seine Gliederung für das Buch entwickelte, kam er zu dem Ergebnis, dass er sechs, dann sieben Bände benötigte, um das Thema gründlich zu behandeln. Er veröffentlichte den ersten Band 1968.
Kurz vor der Veröffentlichung des ersten Bandes von The Art of Computer Programming verließ Knuth Caltech, um eine Position beim Communications Research Division des Institute for Defense Analyses anzunehmen, das sich damals auf dem Campus der Princeton University befand und mathematische Forschung in Kryptografie zur Unterstützung der National Security Agency durchführte.
1967 besuchte Knuth eine Konferenz der Society for Industrial and Applied Mathematics und jemand fragte, was er tat. Zu dieser Zeit war Informatik in numerische Analyse, künstliche Intelligenz und Programmiersprachen unterteilt. Basierend auf seinem Studium und dem Buch The Art of Computer Programming beschloss Knuth, dass er das nächste Mal, wenn jemand fragte, sagen würde: „Analysis of algorithms".
Knuth verließ diese Position dann, um 1969 der Fakultät der Stanford University beizutreten, wo er jetzt Fletcher Jones Professor of Computer Science, Emeritus, ist.
Schriften
Knuth ist neben einem Informatiker auch ein Schriftsteller.
The Art of Computer Programming TAOCP
In den 1970er Jahren beschrieb Knuth Informatik als „ein völlig neues Gebiet ohne echte Identität. Und der Standard der verfügbaren Publikationen war nicht so hoch. Viele der veröffentlichten Arbeiten waren einfach falsch. ... So einer meiner Beweggründe war es, eine Geschichte, die sehr schlecht erzählt worden war, richtigzustellen." Bis 2011 waren die ersten drei Bände und der erste Teil des vierten Bandes seiner Serie veröffentlicht. Concrete Mathematics: A Foundation for Computer Science 2. Aufl., die mit einer Erweiterung des mathematischen Vorbemerkungsabschnitts von Volume 1 von TAoCP begann, wurde ebenfalls veröffentlicht. Im April 2020 sagte Knuth, er arbeite hart am Teil B von Band 4, und er erwartet, dass das Buch mindestens die Teile A bis F haben wird.
Andere Werke
Knuth ist auch der Autor von Surreal Numbers, einer mathematischen Novelle über John Conways Mengentheoretische Konstruktion eines alternativen Zahlensystems. Anstatt das Thema einfach zu erklären, versucht das Buch, die Entwicklung der Mathematik zu zeigen. Knuth wollte, dass das Buch Schüler auf die Durchführung ursprünglicher, kreativer Forschung vorbereitet.
1995 schrieb Knuth das Vorwort zum Buch A=B von Marko Petkovšek, Herbert Wilf und Doron Zeilberger. Knuth ist auch ein gelegentlicher Mitwirkender bei Sprachrätseln für Word Ways: The Journal of Recreational Linguistics.
Knuth hat sich auch in Freizeitmathematik vertieft. Er trug ab den 1960er Jahren Artikel zum Journal of Recreational Mathematics bei und wurde in Joseph Madachys Mathematics on Vacation als wichtiger Mitwirkender anerkannt.
Knuth ist auch in einer Reihe von Numberphile- und Computerphile-Videos auf YouTube aufgetreten, in denen er Themen von der Schreibweise von Surreal Numbers bis hin zu der Frage diskutiert hat, warum er keine E-Mails verwendet.
Werke bezüglich Knuths religiöser Überzeugungen
Zusätzlich zu seinen Schriften über Informatik ist Knuth, ein Lutheraner, auch der Autor von 3:16 Bible Texts Illuminated, in dem er die Bibel durch einen Prozess der systematischen Stichprobenziehung untersucht, nämlich eine Analyse von Kapitel 3, Vers 16 jedes Buches. Jedem Vers ist eine Wiedergabe in kalligraphischer Kunst beigefügt, beigesteuert von einer Gruppe von Kalligraphen unter der Leitung von Hermann Zapf. Anschließend wurde er eingeladen, eine Reihe von Vorlesungen am MIT über seine Ansichten zu Religion und Informatik hinter seinem 3:16-Projekt zu halten, was zu einem weiteren Buch führte, Things a Computer Scientist Rarely Talks About, in dem er die Vorlesungen „God and Computer Science" veröffentlichte.
Meinung zu Softwarepatenten
Als Mitglied der akademischen und wissenschaftlichen Gemeinschaft lehnt Knuth die Politik der Vergabe von Softwarepatenten für triviale Lösungen, die offensichtlich sein sollten, stark ab, hat aber differenzierte Ansichten für nicht-triviale Lösungen wie die Interior-Point-Methode der linearen Programmierung geäußert. Er hat seinen Widerspruch direkt sowohl dem United States Patent and Trademark Office als auch der European Patent Organisation ausgedrückt.
Computer Musings
Knuth hält mehrmals pro Jahr an der Stanford University informelle Vorlesungen, die er „Computer Musings" nannte. Er war bis 2017 Gastprofessor am Oxford University Department of Computer Science im Vereinigten Königreich und ein Ehrenmitglied des Magdalen College.
Programmierung
Digitale Drucklegung
In den 1970er Jahren gaben die Verleger von TAOCP die Monotype zugunsten des Fotosatzes auf. Knuth wurde so frustriert über die Unfähigkeit des letzteren Systems, sich der Qualität der früheren Bände zu nähern, die mit dem älteren System gesetzt wurden, dass er sich Zeit nahm, um an digitaler Drucklegung zu arbeiten und TeX und Metafont erstellte.
Literarische Programmierung
Während der Entwicklung von TeX schuf Knuth eine neue Programmierungsmethodik, die er literarische Programmierung nannte, weil er glaubte, dass Programmierer Programme als Literaturwerke betrachten sollten. „Anstatt uns vorzustellen, dass unsere Hauptaufgabe darin besteht, einen Computer anzuweisen, was er tun soll, konzentrieren wir uns lieber darauf, Menschen zu erklären, was wir einen Computer tun lassen möchten."
Knuth verkörperte die Idee der literarischen Programmierung im WEB-System. Die gleiche WEB-Quelle wird verwendet, um eine TeX-Datei zu weben und eine Pascal-Quelldatei zu verwickeln. Diese wiederum erzeugen eine lesbare Beschreibung des Programms und eine ausführbare Binärdatei. Eine spätere Iteration des Systems, CWEB, ersetzt Pascal durch C.
Knuth verwendete WEB, um TeX und METAFONT zu programmieren, und veröffentlichte beide Programme als Bücher: The TeXbook, das ursprünglich 1984 veröffentlicht wurde, und The METAFONTbook, das ursprünglich 1986 veröffentlicht wurde. Ungefähr zur gleichen Zeit wurde LaTeX, das heute weit verbreitete Makropaket basierend auf TeX, zuerst von Leslie Lamport entwickelt, der später sein erstes Benutzerhandbuch 1986 veröffentlichte.
Musik
Knuth ist Organist und Komponist. 2016 vollendete er ein Musikstück für Orgel mit dem Titel Fantasia Apocalyptica, das er als „Übersetzung des griechischen Textes der Offenbarung des heiligen Johannes in Musik" beschreibt. Es wurde am 10. Januar 2018 in Schweden uraufgeführt.
Privatleben
Donald Knuth heiratete Nancy Jill Carter am 24. Juni 1961, als er Doktorand am California Institute of Technology war. Sie haben zwei Kinder: John Martin Knuth und Jennifer Sierra Knuth.
Chinesischer Name
Knuths chinesischer Name ist Gao Dena. 1977 erhielt er diesen Namen von Frances Yao, kurz bevor er eine dreiw öchige Reise nach China machte. In seinem Band von 1980 von The Art of Computer Programming erklärt Knuth, dass er seinen chinesischen Namen annahm, weil er von der wachsenden Anzahl von Computerprogrammierern in China zu dieser Zeit bekannt sein wollte. 1989 wurde sein chinesischer Name oben auf der Kopfzeile des Journal of Computer Science and Technology platziert, wobei Knuth sagt: „macht mich mir fühlen mich allen chinesischen Menschen nah, obwohl ich deine Sprache nicht sprechen kann".
Gesundheitliche Bedenken
2006 wurde bei Knuth Prostatakrebs diagnostiziert. Er unterzog sich im Dezember dieses Jahres einer Operation und erklärte: „ein wenig Strahlentherapie ... zur Vorsicht, aber die Prognose sieht ziemlich gut aus", wie er in seiner Videoautobiografie berichtete.
Humor
Knuth zahlte früher eine Finderlohn von 2,56 US-Dollar für alle Tippfehler oder Fehler, die in seinen Büchern gefunden wurden, weil „256 Pfennige ein hexadezimaler Dollar sind", und 0,32 US-Dollar für „wertvolle Vorschläge". Nach einem Artikel in der Technology Review des Massachusetts Institute of Technology sind diese Knuth-Reward-Checks „unter Computerdoms gefragtesten Trophäen". Knuth musste 2008 aufhören, echte Schecks zu verschicken, weil es zu Bankbetrug kam, und gibt stattdessen jedem Fehler einen „Depositenzertifikat" aus einer öffentlich aufgelisteten Bilanz in seiner fiktiven „Bank of San Serriffe".
Er warnte einmal einen Korrespondenten: „Vorsicht vor Bugs im obigen Code; ich habe nur bewiesen, dass er korrekt ist, aber nicht ausprobiert."
Knuth veröffentlichte seinen ersten „wissenschaftlichen" Artikel 1957 in einer Schulzeitschrift unter dem Titel „The Potrzebie System of Weights and Measures". Darin definierte er die Grundeinheit der Länge als die Dicke von Mad Nr. 26 und nannte die Grundeinheit der Kraft „whatmeworry". Mad veröffentlichte den Artikel in Ausgabe Nr. 33 Juni 1957.
Um das Konzept der Rekursion zu demonstrieren, bezog Knuth absichtlich „Circular definition" und „Definition, circular" in dem Index von The Art of Computer Programming, Volume 1, aufeinander.
Das Vorwort von Concrete Mathematics hat den folgenden Absatz:
Als DEK Concrete Mathematics zum ersten Mal an der Stanford unterrichtete, erklärte er den etwas seltsamen Titel, indem er sagte, dass es sein Versuch war, einen Mathematikunterricht zu lehren, der hart statt weich war. Er kündigte an, dass er, entgegen den Erwartungen seiner Kollegen, weder die Theorie der Aggregate, noch Stone's Embedding Theorem, noch einmal die Stone–Čech-Kompaktifizierung unterrichten würde. (Mehrere Schüler aus der Bauingenieurabeilung standen auf und verließen stillschweigend den Raum.)
Auf der TUG 2010 Conference kündigte Knuth einen satirischen XML-basierten Nachfolger von TeX an, betitelt „iTeX" ausgesprochen, aufgeführt mit einer Glocke, die klingelt, die Funktionen wie willkürlich skalierte irrationale Einheiten, 3D-Druck, Eingabe von seis unterstützen würde
