Edsger W. Dijkstra

Bedeutung und Grundidee

Edsger Wybe Dijkstra (* 11. Mai 1930 in Rotterdam; † 6. August 2002 in Nuenen) war ein niederländischer Informatiker. Er gilt als Wegbereiter der strukturierten Programmierung, also einer Art des Programmierens, bei der Programme klar gegliedert und logisch aufgebaut werden sollen. Für grundlegende Beiträge zur Entwicklung von Programmiersprachen erhielt er 1972 den Turing Award, eine der wichtigsten Auszeichnungen der Informatik.

Dijkstra ist besonders wichtig, weil viele seiner Arbeiten Grundbegriffe der Informatik betreffen: Algorithmen, Programmiersprachen, Betriebssysteme, Nebenläufigkeit und Programmiermethoden. Mehrere nach ihm benannte oder mit ihm verbundene Verfahren werden bis heute in der Informatik verwendet oder historisch als sehr einflussreich betrachtet.

Ausbildung und akademischer Weg

Dijkstra wurde als Sohn eines Chemikers und einer Mathematikerin geboren. Nach dem Besuch des Gymnasiums Erasmianum in Rotterdam studierte er ab 1948 Mathematik und theoretische Physik an der Universität Leiden. 1951 erreichte er den Bachelor-Grad. Danach besuchte er einen Programmierkurs bei Maurice V. Wilkes an der University of Cambridge.

Anschließend setzte Dijkstra sein Studium in Leiden fort und arbeitete nebenbei am Mathematisch Centrum in Amsterdam, dem heutigen Centrum Wiskunde & Informatica. Sein Betreuer war Adriaan van Wijngaarden, der ihn überzeugte, ganz zum Programmieren zu wechseln, statt sich hauptsächlich der theoretischen Physik zu widmen. 1956 erreichte Dijkstra den Master-Grad und wurde Vollzeitangestellter am Mathematisch Centrum. Er wird als erster Programmierer der Niederlande bezeichnet. 1959 schrieb er an der Universität von Amsterdam seine Doktorarbeit über die Electrologica X1, deren grundlegende Software er selbst schrieb.

1962 wurde Dijkstra Mathematikprofessor an der Technischen Hochschule Eindhoven. Er wollte zunächst keinen reinen Informatik-Lehrstuhl annehmen, weil er die wissenschaftliche Grundlage der Informatik noch nicht für ausreichend entwickelt hielt. Dennoch ermöglichte er Studierenden nach mindestens drei Jahren Mathematikstudium eine Spezialisierung auf Themen der Informatik. Er war der Ansicht, dass ein Informatikstudium stark mathematisch geprägt sein müsse und dass ein Einführungskurs in Programmierung formalmathematisch und frei von konkreten Programmiersprachen sein solle.

Ab 1973 beschränkte er seine Tätigkeit an der Universität auf eine außerordentliche Professur. Diese war eng mit dem von ihm gegründeten Eindhoven Tuesday Afternoon Club verbunden, in dem er dienstagnachmittags mit Kollegen wissenschaftliche Probleme und neue Veröffentlichungen besprach. Hauptamtlich wurde er Research Fellow der Burroughs Corporation. 1984 wechselte er auf den Schlumberger Centennial Chair in Computer Sciences an der University of Texas at Austin. 1999 wurde er emeritiert. Dijkstra starb 2002 an Krebs in seinem Haus in Nuenen. Er hinterließ seine Frau Ria, die er 1957 geheiratet hatte, und drei Kinder.

Algorithmen und Betriebssysteme

Zu Dijkstras wichtigsten Beiträgen gehört der Dijkstra-Algorithmus. Er dient zur Berechnung eines kürzesten Weges in einem Graphen. Ein Graph ist eine Struktur aus Knoten und Verbindungen, mit der zum Beispiel Netzwerke, Straßen oder Zustände modelliert werden können. Dijkstra veröffentlichte diesen Algorithmus 1959 in einem dreiseitigen Artikel.

Ein weiterer wichtiger Beitrag ist die erstmalige Einführung von Semaphoren zur Synchronisation zwischen Threads. Threads sind parallel oder nebenläufig ablaufende Ausführungseinheiten eines Programms. Eine Semaphore ist ein Steuerungsmittel, mit dem geregelt wird, wann ein Thread auf eine gemeinsame Ressource zugreifen darf. Damit verbunden ist das Philosophenproblem, ein klassisches Beispielproblem der Informatik zur Koordination nebenläufiger Prozesse. Ebenfalls von Dijkstra stammt der Bankieralgorithmus, der mit der sicheren Zuteilung von Ressourcen zusammenhängt.

Dijkstra entwickelte außerdem den Shunting-yard-Algorithmus. Dieser Algorithmus überführt mathematische Terme von der Infixnotation in die umgekehrte polnische Notation oder in einen abstrakten Syntaxbaum. Infixnotation bedeutet, dass ein Operator zwischen den Operanden steht, wie etwa bei üblichen Rechenausdrücken. Ein abstrakter Syntaxbaum ist eine Baumdarstellung der logischen Struktur eines Ausdrucks.

Auf Grundlage seiner Erfahrungen entwarf Dijkstra das Multitasking-Betriebssystem THE, benannt nach der Technischen Hogeschool Eindhoven. Dieses Betriebssystem wurde vor allem für seine Schichtenstruktur bekannt. Niklaus Wirth berichtete, Dijkstra habe im Rahmen dieser Arbeit erkannt, dass er nicht für Teamarbeit geeignet sei, und danach nur noch allein gearbeitet.

Weitere Beiträge betreffen Programmiersprachen und Sortierverfahren. Ende der 1950er Jahre war Dijkstra am Entwurf von Algol 60 beteiligt. 1960 stellte er den ersten Compiler dafür fertig. Ein Compiler ist ein Programm, das Quellcode in eine ausführbare oder maschinennahe Form übersetzt. Außerdem entwarf Dijkstra den Sortieralgorithmus Smoothsort und entdeckte den Algorithmus von Prim wieder, der auch Prim-Dijkstra-Algorithmus oder Algorithmus von Jarnik, Prim und Dijkstra genannt wird.

Strukturierte Programmierung und Texte

Dijkstra führte den Begriff der strukturierten Programmierung in die Informatik ein. Damit meinte er eine Programmierweise, die Programme übersichtlich, logisch kontrollierbar und mathematisch besser begründbar machen sollte. Besonders bekannt wurde seine Abhandlung Go To Statement Considered Harmful über den Goto-Befehl. Darin argumentierte er, warum dieser Befehl nicht benutzt werden sollte. Der Goto-Befehl springt an eine andere Stelle im Programm und kann dadurch die Programmstruktur unübersichtlich machen.

In seiner Turing-Lecture The Humble Programmer popularisierte Dijkstra auch den Begriff der Softwarekrise. Diesen Begriff hatte er als regelmäßiger Redner an Friedrich L. Bauers International Summer School Marktoberdorf aufgenommen. Mit Softwarekrise ist hier die Schwierigkeit gemeint, große und zuverlässige Software systematisch zu entwickeln.

Dijkstra schrieb über 1300 Manuskripte fachlicher und privater Natur. Er kopierte sie und verschickte sie per Post an zahlreiche Kollegen, veröffentlichte sie jedoch meist nicht offiziell. Viele dieser Texte werden EWD-Manuskripte genannt, nach seinen Initialen, und sind heute in einem Online-Archiv gesammelt. Für die Burroughs Corporation schrieb er außerdem über 500 wissenschaftliche Berichte.

Auszeichnungen und wichtige Veröffentlichungen

Dijkstra erhielt zahlreiche Auszeichnungen. 1971 wurde er Mitglied der Königlich-Niederländischen Akademie der Wissenschaften und Distinguished Fellow der British Computer Society. 1972 erhielt er den Turing Award. 1975 wurde er Auslands-Ehrenmitglied der American Academy of Arts and Sciences. Weitere Ehrungen waren ein Ehrendoktortitel der Queen’s University of Belfast 1976, der Computer Pioneer Award der IEEE 1982, ein Ehrendoktortitel der Wirtschaftsuniversität Athen 2001 und der C&C-Preis der NEC Corporation 2002. Ebenfalls 2002 wurde der PODC Influential Paper Award nach seinem Tod ihm zu Ehren als Dijkstra-Preis benannt.

Zu seinen ausgewählten Schriften gehören A Note on Two Problems in Connexion with Graphs von 1959, Go To Statement Considered Harmful von 1968 und Cooperating sequential processes von 1968. Zusammen mit Ole-Johan Dahl und Tony Hoare veröffentlichte er 1972 Structured Programming, das auch die 1970 geschriebenen und zuvor unveröffentlichten Notes on Structured Programming enthält. Weitere wichtige Werke sind Selected Writings on Computing: A Personal Perspective von 1982 sowie Predicate Calculus and Program Semantics von 1990, das er mit Carel S. Scholten schrieb.