Edsger W. Dijkstra - Edsger W. Dijkstra

Edsger W. Dijkstraße
Dijkstra im Jahr 2002
Geboren	( 1930-05-11 )11. Mai 1930 Rotterdam , Niederlande
Ist gestorben	6. August 2002 (2002-08-06)(72 Jahre) Nuenen , Niederlande
Staatsbürgerschaft	Niederlande
Ausbildung	Universität Leiden (BS, MS) Universität Amsterdam (Ph.D.)
Bekannt für	Siehe unten
Ehepartner	Maria (Ria) C. Debets
Auszeichnungen
Wissenschaftlicher Werdegang
Felder
Institutionen
These	Kommunikation mit einem automatischen Computer  (1959)
Doktoratsberater	Adriaan van Wijngaarden
Doktoranden
Einflüsse
Beeinflusst

Edsger Wybe Dijkstra ( / d aɪ k s t r ə / DYKE -strə ; Niederländisch:  [ɛtsxər ʋibə dɛikstra] ( hören ) , 11. Mai 1930 - 6. August 2002) war ein niederländischer Informatiker , Programmierer , Software - Ingenieur , Systemwissenschaftler , Wissenschafts - Essayist und Pionier der Informatik . Als theoretischer Physiker arbeitete er von 1952 bis 1962 als Programmierer am Mathematisch Centrum (Amsterdam). Ab 1984 war Dijkstra Universitätsprofessor und hatte den Schlumberger Centennial Chair in Computer Sciences an der University of Texas in Austin inne bis zu seiner Pensionierung 1999. Er war Professor für Mathematik an der Technischen Universität Eindhoven (1962–1984) und Forschungsstipendiat der Burroughs Corporation (1973–1984). 1972 gewann er als erster Mensch, der weder Amerikaner noch Brite war, den Turing Award .

Als eine der einflussreichsten Persönlichkeiten der Gründergeneration der Informatik hat Dijkstra die neue Disziplin sowohl als Ingenieur als auch als Theoretiker mitgestaltet . Seine grundlegenden Beiträge decken verschiedene Bereiche der Informatik ab, darunter Compilerkonstruktion , Betriebssysteme , verteilte Systeme , sequentielle und gleichzeitige Programmierung, Programmierparadigma und -methodik, Programmiersprachenforschung , Programmdesign, Programmentwicklung, Programmverifikation, Prinzipien der Softwareentwicklung, Graphalgorithmen, und philosophische Grundlagen der Computerprogrammierung und Informatik. Viele seiner Arbeiten sind die Quelle neuer Forschungsgebiete. Mehrere Konzepte und Probleme, die heute Standard in der Informatik sind, wurden zuerst von Dijkstra identifiziert oder tragen von ihm geprägte Namen.

Bis Mitte der 1960er Jahre galt die Computerprogrammierung eher als Kunst (oder Handwerk) denn als wissenschaftliche Disziplin. In Harlan Mills ' Worten (1986) wurde "Programmieren [vor den 1970er Jahren] als eine private, Rätsel lösende Aktivität angesehen, bei der Computeranweisungen geschrieben werden, um als Programm zu funktionieren". Ende der 1960er Jahre befand sich die Computerprogrammierung in einer Krise . Dijkstra gehörte zu einer kleinen Gruppe von Akademikern und industriellen Programmierern, die einen neuen Programmierstil befürworteten, um die Qualität der Programme zu verbessern . Dijkstra, der einen Hintergrund in Mathematik und Physik hatte, war eine der treibenden Kräfte hinter der Akzeptanz der Computerprogrammierung als wissenschaftliche Disziplin. Er prägte den Begriff „ strukturierte Programmierung “ und in den 1970er Jahren wurde dies zur neuen Programmier-Orthodoxie. Als Begründer der strukturierten Programmierungsbewegung (der ersten bemerkenswerten Bewegung in der Geschichte der Computerprogrammierung) trugen seine Ideen zur Programmiermethodik dazu bei, den Grundstein für die Geburt und Entwicklung der Berufsdisziplin Software Engineering zu legen , die es Programmierern ermöglichte, zunehmend zu organisieren und zu verwalten komplexe Softwareprojekte. Wie Bertrand Meyer (2009) feststellte: „Die Revolution der Programmieransichten, die durch Dijkstras Bildersturm ausgelöst wurde, führte zu einer Bewegung, die als strukturierte Programmierung bekannt ist und einen systematischen, rationalen Ansatz bei der Programmkonstruktion befürwortet. Strukturierte Programmierung ist die Grundlage für alles, was bisher getan wurde da in der Programmiermethodik , einschließlich der objektorientierten Programmierung ."

Die akademische Studie des Concurrent Computing begann in den 1960er Jahren, wobei Dijkstra (1965) als die erste Arbeit auf diesem Gebiet zugeschrieben wurde, die das Problem der gegenseitigen Ausgrenzung identifiziert und gelöst hat. Er war auch einer der frühen Pioniere der Erforschung der Prinzipien des verteilten Rechnens . Seine grundlegende Arbeit zu Nebenläufigkeit , Semaphoren , gegenseitigem Ausschluss, Deadlock (tödliche Umarmung), Finden der kürzesten Pfade in Graphen , Fehlertoleranz , Selbststabilisierung und vielen anderen Beiträgen umfasst viele der Säulen, auf denen das Gebiet des verteilten Rechnens aufbaut. Kurz vor seinem Tod im Jahr 2002 erhielt er für seine Arbeiten zur Selbststabilisierung von Programmberechnungen den ACM PODC Influential-Paper Award in Distributed Computing. Diese jährliche Auszeichnung wurde im folgenden Jahr in Dijkstra Prize (Edsger W. Dijkstra Prize in Distributed Computing) umbenannt. Als Preis, der gemeinsam vom Association for Computing Machinery (ACM) Symposium on Principles of Distributed Computing (PODC) und dem European Association for Theoretical Computer Science (EATCS) International Symposium on Distributed Computing (DISC) gesponsert wird , wird anerkannt, dass "keine andere Person" einen größeren Einfluss auf die Forschung zu Prinzipien des verteilten Rechnens hatte".

Biografie

Frühe Jahre

Edsger W. Dijkstra wurde in Rotterdam geboren . Sein Vater war Chemiker, der Präsident der Niederländischen Chemischen Gesellschaft war ; er unterrichtete Chemie an einer weiterführenden Schule und war später deren Schulleiter. Seine Mutter war Mathematikerin, hatte aber nie einen formellen Job.

Dijkstra hatte eine Karriere als Jurist in Erwägung gezogen und gehofft, die Niederlande bei den Vereinten Nationen zu vertreten . Nach dem Abitur 1948 studierte er jedoch auf Anregung seiner Eltern Mathematik und Physik und anschließend Theoretische Physik an der Universität Leiden .

In den frühen 1950er Jahren waren elektronische Computer ein Novum. Dijkstra stolperte durch Zufall über seine Karriere, und durch seinen Betreuer, Professor A. Haantjes, lernte er Adriaan van Wijngaarden , den Direktor der Computerabteilung am Mathematischen Zentrum in Amsterdam , kennen, der Dijkstra eine Stelle anbot; im März 1952 wurde er offiziell der erste "Programmierer" der Niederlande.

Für einige Zeit blieb Dijkstra der Physik verpflichtet und arbeitete an drei Tagen pro Woche in Leiden daran . Mit zunehmender Beschäftigung mit Computern begann sich jedoch sein Fokus zu verlagern. Wie er sich erinnerte:

Nachdem ich etwa drei Jahre lang programmiert hatte, hatte ich ein Gespräch mit A. van Wijngaarden , meinem damaligen Chef am Mathematischen Zentrum in Amsterdam , für das ich ihm mein Leben lang dankbar sein werde. Der Punkt war, dass ich gleichzeitig theoretische Physik an der Universität Leiden studieren sollte, und da es mir immer schwerer fiel, die beiden Aktivitäten zu kombinieren, musste ich mich entscheiden, entweder mit dem Programmieren aufzuhören und ein echter, respektabler Theoretiker zu werden Physiker , oder mein Studium der Physik mit minimalem Aufwand nur zu einem formalen Abschluss zu führen und zu werden....., ja was? Ein Programmierer ? Aber war das ein respektabler Beruf? Denn was war Programmieren ? Wo war das solide Wissen, das sie als intellektuell respektables Fach stützen konnte? Ich erinnere mich noch sehr gut daran, wie ich meine Hardware-Kollegen beneidete, die auf ihre fachliche Kompetenz zumindest darauf hinweisen konnten, dass sie alles über Röhren, Verstärker und Co. wussten, während ich bei dieser Frage das Gefühl hatte, würde mit leeren Händen dastehen. Voller Besorgnis klopfte ich an Van Wijngaardens Bürotür und fragte ihn, ob ich „einen Moment mit ihm sprechen“ könnte; als ich einige Stunden später sein Büro verließ, war ich ein anderer Mensch. Denn nachdem er sich meine Probleme geduldig angehört hatte, stimmte er zu, dass es bis zu diesem Zeitpunkt keine große Programmierdisziplin gab, erklärte dann aber leise, dass automatische Computer hier bleiben würden, dass wir erst am Anfang standen und es könnten gehöre ich nicht zu den Personen, die berufen sind, das Programmieren in den kommenden Jahren zu einer respektablen Disziplin zu machen? Dies war ein Wendepunkt in meinem Leben und ich schloss mein Physikstudium so schnell wie möglich formal ab.

—  Edsger Dijkstra, The Humble Programmer (EWD340), Kommunikation des ACM

Als Dijkstra 1957 Maria (Ria) C. Debets heiratete, musste er im Rahmen der Hochzeitsriten seinen Beruf angeben. Er gab an, Programmierer zu sein, was für die Behörden inakzeptabel war, da es einen solchen Beruf in den Niederlanden damals noch nicht gab.

1959 promovierte er an der Universität Amsterdam mit einer Dissertation mit dem Titel "Kommunikation mit einem automatischen Computer", die sich mit einer Beschreibung der Assemblersprache befasste, die für den ersten in den Niederlanden entwickelten kommerziellen Computer, den Electrologica X1 , entwickelt wurde . Der Betreuer seiner Dissertation war Van Wijngaarden.

Mathematisch Centrum, Amsterdam

Von 1952 bis 1962 arbeitete Dijkstra am Mathematisch Centrum in Amsterdam, wo er eng mit Bram Jan Loopstra und Carel S. Scholten zusammenarbeitete , die mit dem Bau eines Computers beauftragt worden waren. Ihre Art der Interaktion war diszipliniert: Sie legten zunächst die Schnittstelle zwischen Hardware und Software fest, indem sie ein Programmierhandbuch verfassten. Dann müssten die Hardware-Designer ihrem Teil des Auftrags treu bleiben, während Dijkstra, der Programmierer, die Software für die nicht vorhandene Maschine schreiben würde. Zwei der Lektionen, die er aus dieser Erfahrung gelernt hat, waren die Bedeutung einer klaren Dokumentation und dass Programm-Debugging durch sorgfältiges Design weitgehend vermieden werden kann. Dijkstra formulierte und löste das Kürzeste-Weg-Problem für eine Demonstration bei der offiziellen Einweihung des ARMAC-Computers im Jahr 1956. Da es keine Zeitschriften für automatisches Rechnen gab, veröffentlichte er das Ergebnis erst 1959.

Am Mathematical Center entwickelten Dijkstra und sein Kollege Jaap Zonneveld  [ nl ] bis August 1960 den ersten Compiler für die Programmiersprache ALGOL 60 , mehr als ein Jahr bevor ein Compiler von einer anderen Gruppe produziert wurde. Es hatte einen tiefgreifenden Einfluss auf sein späteres Denken über das Programmieren als wissenschaftliche Tätigkeit.

Technische Universität Eindhoven

Die Technische Universität Eindhoven in Eindhoven im Süden der Niederlande, an der Dijkstra von 1962 bis 1984 Professor für Mathematik war.

1962 zog Dijkstra nach Eindhoven und später nach Nuenen im Süden der Niederlande, wo er Professor an der Fakultät für Mathematik der Technischen Universität Eindhoven wurde . Die Universität hatte keinen eigenen Informatik-Fachbereich und die Kultur des Mathematik-Fachbereichs lag ihm nicht sonderlich. Dijkstra versuchte, eine Gruppe von Informatikern aufzubauen, die bei der Lösung von Problemen zusammenarbeiten konnten. Dies war ein ungewöhnliches Forschungsmodell für die Fakultät für Mathematik. In den späten 1960er Jahren baute er das THE-Betriebssystem (benannt nach der Universität, damals bekannt als Technische Hogeschool Eindhoven ), das durch seine Verwendung von softwarebasiertem ausgelagerten virtuellen Speicher die Designs nachfolgender Betriebssysteme beeinflusst hat .

Burroughs Corporation

Dijkstra trat im August 1973 als Forschungsstipendiat in die Burroughs Corporation ein, die damals für die Herstellung von Computern auf der Grundlage einer innovativen Hardware-Architektur bekannt war. was er in der kleinsten Burroughs-Forschungseinrichtung tat, nämlich seinem Arbeitszimmer im zweiten Stock seines Hauses in Nuenen. Tatsächlich war Dijkstra der einzige Forschungsstipendiat von Burroughs und arbeitete von zu Hause aus für das Unternehmen und reiste gelegentlich zu seinen Niederlassungen in den Vereinigten Staaten. Daraufhin reduzierte er seinen Termin an der Universität auf einen Tag in der Woche. Dieser Tag, Dienstag, wurde bald als Tag des berühmten 'Tuesday Afternoon Club' bekannt, einem Seminar, bei dem er mit seinen Kollegen wissenschaftliche Artikel diskutierte und alle Aspekte betrachtete: Notation, Organisation, Präsentation, Sprache, Inhalt usw. In Kürze nachdem er 1984 an die University of Texas at Austin (USA) wechselte, entstand in Austin, Texas , ein neuer „Zweig“ des Tuesday Afternoon Club .

Die Burroughs-Jahre brachten ihn zu seinen produktivsten Forschungsartikeln. Er schrieb fast 500 Dokumente der EWD-Reihe (siehe unten), die meisten davon technische Berichte, für den privaten Umlauf innerhalb einer ausgewählten Gruppe.

Die University of Texas in Austin

Die University of Texas at Austin , wo Dijkstra von 1984 bis 1999 den Schlumberger Centennial Chair in Computer Sciences innehatte.

Dijkstra nahm 1984 den Schlumberger Centennial Chair am Computer Science Department der University of Texas in Austin an.

Letzten Jahren

Dijkstra arbeitete in Austin bis zu seiner Pensionierung im November 1999 die Gelegenheit zu markieren und seine vierzig-plus zu feiern Jahren bahnbrechenden Beiträge zur Informatik , der Fakultät für Informatik organisiert ein Symposium, das im Mai 2000 an seinem 70. Geburtstag nahm.

Dijkstra und seine Frau kehrten von Austin in sein ursprüngliches Haus in Nuenen (Niederlande) zurück, wo er feststellte, dass er nur noch wenige Monate zu leben hatte. Er sagte, er wolle in Austin, Texas , in Rente gehen , aber in den Niederlanden sterben. Dijkstra starb am 6. August 2002 nach langem Kampf an Krebs. Er und seine Frau Maria (Ria) Debets hinterließen ihre drei Kinder: Marcus, Femke und der Informatiker Rutger M. Dijkstra.

Wegweisende Beiträge und Auswirkungen auf die Informatik

Obwohl er theoretischer Physiker war, wurde Dijkstra zu einer der einflussreichsten Persönlichkeiten der Gründergeneration der Informatik. Als früher Pionier in vielen Forschungsgebieten der Informatik hat er die neue Disziplin sowohl aus ingenieurwissenschaftlicher als auch aus wissenschaftlicher Sicht mitgestaltet . Viele seiner Arbeiten sind die Quelle neuer Forschungsgebiete. Viele Konzepte, die heute Standard in der Informatik sind, wurden zuerst von Dijkstra identifiziert oder tragen von ihm geprägte Namen. Auch einige wichtige Probleme wurden von ihm zunächst formuliert und gelöst. 1994 wurde eine Umfrage unter über tausend Professoren der Informatik durchgeführt, um eine Liste der 38 einflussreichsten wissenschaftlichen Arbeiten auf diesem Gebiet zu erhalten, und Dijkstra ist Autor von fünf Arbeiten. Im Alter von 42 Jahren wurde er der erste nicht-amerikanische, nicht-britische und kontinentaleuropäische Gewinner des Turing-Preises .

Während seiner mehr als vierzig Jahre als Informatiker, die Positionen sowohl in der Wissenschaft als auch in der Industrie umfassten, leistete Dijkstra zahlreiche bahnbrechende Beiträge zu vielen Bereichen der Informatik , darunter Compilerbau , Betriebssysteme , Concurrent Computing ( Concurrent Programming ), Distributed Computing , Programmierung Paradigma und Methodik , Programmiersprachenforschung , Programmdesign , Programmentwicklung , Programmverifikation , Prinzipien der Softwareentwicklung , Algorithmusdesign und philosophische Grundlagen der Computerprogrammierung und Informatik . Darüber hinaus interessierte sich Dijkstra intensiv für den Informatikunterricht und die Beziehungen zwischen der akademischen Informatik und der Softwareindustrie .

Zu seinen wichtigsten bahnbrechenden Beiträgen (einschließlich Ideen, Erfindungen und Innovationen) gehören:

• Konzepte, Methoden, Prinzipien und Theorien : Dijkstra–Zonneveld ALGOL 60 Compiler (erster vollständig funktionierender ALGOL 60 Compiler), Aufrufliste , Nebenläufigkeit , gleichzeitige Programmierung , kooperierende sequentielle Prozesse , kritischer Abschnitt , tödliche Umarmung ( Deadlock ), Dining Philosophers Problem , Niederländische National Flag-Problem , fehlertolerante Systeme , Goto-less-Programmierung , geschützte Befehlssprache ( Guarded Commands ), Schichtstruktur in der Softwarearchitektur , Abstraktionsebenen , Multithreaded-Programmierung , gegenseitiger Ausschluss ( Mutex oder Lock ), Producer-Consumer-Problem ( Bounded Buffer Problem ), Programmfamilien , Prädikatstransformator-Semantik , Prozesssynchronisation , Selbststabilisierende verteilte Systeme ( Selbststabilisierung ), Semaphor , Trennung von Belangen , Schlafendes Barberproblem , Strukturierte Analyse , Strukturierte Programmierung , DAS Multiprogramming-System , Unbegrenzter Nichtdeterminismus , Kalkül der schwächsten Voraussetzung
• Algorithmen : Dijkstra-Algorithmus , DJP - Algorithmus , Dijkstra-Scholten Algorithmus , Dekker-Algorithmus (Generalisierung), Bankier-Algorithmus , Smoothsort , Rangier-Yard - Algorithmus , dreifarbige Markierungsalgorithmus , gleichzeitige Algorithmen , verteilte Algorithmen , Deadlock Prävention Algorithmen , mutual exclusion Algorithmen , Selbst -stabilisierende Algorithmen

Algorithmische Arbeit

Der Algorithmus von Dijkstra. Es wählt den nicht besuchten Scheitelpunkt mit der geringsten Entfernung aus, berechnet die Entfernung zu jedem nicht besuchten Nachbarn und aktualisiert die Entfernung des Nachbarn, wenn er kleiner ist. Besucht markieren (auf rot gesetzt), wenn die Nachbarn fertig sind.

Dijkstras algorithmische Arbeit (insbesondere Graphalgorithmen , nebenläufige Algorithmen und verteilte Algorithmen ) spielt in vielen Bereichen der Informatik eine wichtige Rolle. Laut Leslie Lamport (2002) begann Dijkstra " mit seinem CACM-Papier "Solution of a Problem in Concurrent Programming Control" aus dem Jahr 1965 das Gebiet der gleichzeitigen und verteilten Algorithmen , in dem er erstmals das Problem des gegenseitigen Ausschlusses formulierte und löste. Wie Lamport erklärt, "ist dieses Papier wahrscheinlich der Grund für die Existenz von PODC (...). Es bleibt bis heute das einflussreichste Papier auf diesem Gebiet. Dass es keinen PODC Influential Paper Award gewonnen hat, spiegelt eine künstliche Trennung zwischen gleichzeitigen und verteilten Algorithmen wider." – eine Trennung, die es in Dijkstras Werk noch nie gegeben hat."

1959 veröffentlichte Dijkstra in einem dreiseitigen Artikel 'A note on two problems in connexion with graphs' den Algorithmus , um den kürzesten Weg in einem Graphen zwischen zwei beliebigen Knoten zu finden, der heute als Dijkstra-Algorithmus bezeichnet wird . Seine Auswirkungen in den nächsten 40 Jahren werden aus dem Artikel von Mikkel Thorup , 'Undirected Single Source Shortest Paths with Positive Integer Weights in Linear Time' (1999): "Seit 1959, all theoretische Entwicklungen in SSSP [Single-Source Shortest Paths] für allgemeine gerichtete und ungerichtete Graphen basieren auf dem Algorithmus von Dijkstra." Der Algorithmus von Dijkstra wird in SPF verwendet, Shortest Path First , das in den Routing-Protokollen OSPF und IS-IS verwendet wird . Verschiedene Modifikationen des Dijkstra-Algorithmus wurden von vielen Autoren vorgeschlagen, die Heuristiken verwenden , um die Laufzeit der Suche nach dem kürzesten Weg zu reduzieren . Einer der am häufigsten verwendeten heuristischen Algorithmen ist der A*-Suchalgorithmus (erstmals 1968 von Peter Hart , Nils Nilsson und Bertram Raphael vom Stanford Research Institute beschrieben ), dessen Hauptziel darin besteht, die Laufzeit durch Reduzierung des Suchraums zu reduzieren. Dijkstra dachte über das Kürzeste-Weg-Problem nach, als er 1956 am Mathematischen Zentrum in Amsterdam als Programmierer arbeitete , um die Fähigkeiten eines neuen Computers namens ARMAC zu demonstrieren . Sein Ziel war es, sowohl ein Problem als auch eine Antwort (die von einem Computer erzeugt werden würde) auszuwählen, die Nicht-Computer-Leute verstehen konnten. Er entwarf den Shortest Path Algorithmus in etwa 20 Minuten ohne Papier und Stift und implementierte ihn später für ARMAC für eine leicht vereinfachte Verkehrskarte von 64 Städten in den Niederlanden (so dass 6 Bit ausreichen würden, um die Stadt im Algorithmus darzustellen). Wie er sich in einem 2001 veröffentlichten Interview erinnerte:

Was ist die kürzeste Verbindung von Rotterdam nach Groningen , im Allgemeinen: von einer bestimmten Stadt zu einer bestimmten Stadt? Es ist der Algorithmus für den kürzesten Weg , den ich in etwa zwanzig Minuten entworfen habe. Eines Morgens war ich mit meiner jungen Verlobten in Amsterdam shoppen, und müde setzten wir uns auf die Café-Terrasse, um eine Tasse Kaffee zu trinken und ich habe gerade überlegt, ob ich das kann, und habe dann den Algorithmus für den kürzesten Weg entworfen . Wie gesagt, es war eine zwanzigminütige Erfindung. Tatsächlich wurde es '59 mit drei Jahren Verspätung veröffentlicht. Die Veröffentlichung ist noch lesbar, sie ist sogar ganz nett. Einer der Gründe, warum es so schön ist, war, dass ich es ohne Bleistift und Papier entworfen habe. Später erfuhr ich, dass einer der Vorteile des Entwerfens ohne Bleistift und Papier darin besteht, dass man fast gezwungen ist, alle vermeidbaren Komplexitäten zu vermeiden. Schließlich wurde dieser Algorithmus zu meinem großen Erstaunen einer der Eckpfeiler meines Ruhms.

—  Edsger Dijkstra, in einem Interview mit Philip L. Frana, Communications of the ACM 53 (8), 2001.

Ein Jahr später stieß er bei Hardware-Ingenieuren, die am nächsten Computer des Instituts arbeiteten, auf ein weiteres Problem: Minimieren Sie den Kabelaufwand für die Verbindung der Pins auf der Rückseite der Maschine. Als Lösung entdeckte er den als Minimal Spanning Tree Algorithmus von Prim bekannten Algorithmus wieder . Der Algorithmus von Prim wurde ursprünglich 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt . und später von Robert C. Prim 1957 und Dijkstra 1959 unabhängig wiederentdeckt und neu veröffentlicht . Daher wird er manchmal auch als DJP-Algorithmus bezeichnet .

1961 beschrieb Dijkstra im Bericht des Mathematisch Centrum erstmals den Rangierbahnhof-Algorithmus , eine Methode zum Parsen von mathematischen Ausdrücken, die in Infix-Notation angegeben sind . Es kann verwendet werden, um eine Ausgabe in umgekehrter polnischer Notation (RPN) oder als abstrakter Syntaxbaum (AST) zu erzeugen . Der Algorithmus wurde als Rangierbahnhof- Algorithmus bezeichnet, weil seine Funktionsweise der eines Eisenbahn-Rangierbahnhofs ähnelt . Der Rangier-Yard-Algorithmus wird häufig verwendet, um Operator-Präzedenz-Parser zu implementieren .

1962 oder 1963 schlug Dijkstra den Semaphor- Mechanismus für den Mutual-Exclusion- Algorithmus für n Prozesse (eine Verallgemeinerung des Dekker-Algorithmus ) vor, der wahrscheinlich der erste veröffentlichte gleichzeitige Algorithmus war und ein neues Gebiet der algorithmischen Forschung einführte. Er identifizierte auch das Deadlock- Problem und schlug den Banker-Algorithmus vor , der Deadlocks verhindert .

1974 stellte Dijkstra drei Selbststabilisierungsalgorithmen zum gegenseitigen Ausschluss auf einem Ring vor. Diese Arbeit gilt als die erste, die das Konzept der Selbststabilisierung einführt und demonstriert.

Mitte der 1970er Jahre führte Dijkstra (zusammen mit anderen Autoren) zwei nützliche Abstraktionen (Mutator und Collector) in das Studium der Garbage Collection ein . Der Mutator abstrahiert den Prozess, der die Berechnung durchführt, einschließlich der Zuweisung einer neuen Speicherzelle. Der Collector ist der Prozess, der automatisch Datenmüll zurückfordert. Darüber hinaus gibt dieses Papier eine Formalisierung der dreifarbigen Markierung , die für die inkrementelle Garbage Collection grundlegend ist.

In den frühen 1980er Jahren schlugen Dijkstra und Carel S. Scholten den Dijkstra-Scholten-Algorithmus zur Erkennung von Terminierungen in verteilten Systemen vor .

1981 entwickelte Dijkstra smoothsort , einen vergleichsbasierten Sortieralgorithmus und eine Variation von heapsort .

Compilerbau und Programmiersprachenforschung

ALGOL 60 entstand als Ergebnis der ALGOL- Konferenz im Januar 1960 in Paris. Im August 1960 nahmen Dijkstra und sein Kollege Jaap Zonneveld den ersten vollständig funktionierenden ALGOL 60- Compiler (für den Electrologica X1- Computer) der Welt in Betrieb. Der Dijkstra-Zonneveld-Compiler ist mehr als ein Jahr älter als der zweite ALGOL 60-Compiler (von einer anderen Gruppe).

Dijkstra war als Fan der Programmiersprache ALGOL bekannt und arbeitete in dem Team mit, das den ersten Compiler für ALGOL 60 implementierte , an dessen Entwicklung, Realisierung und Popularisierung er eng beteiligt war. Wie von Peter Naur im Artikel 'The European side of the last phase of the development of ALGOL 60' in den Proceedings of the First ACM SIGPLAN Conference on History of Programming Languages , Januar 1978, diskutiert, nahm Dijkstra im Zeitraum 1958– 1959 in einer Reihe von Treffen, die in der Veröffentlichung des Berichts zur Definition der Sprache ALGOL 60 gipfelten. Dijkstras Name erscheint nicht in der Liste der 13 Autoren des Abschlussberichts, aber er war offizielles Mitglied der IFIP Working Group 2.1 on Algorithmic Languages ​​and Calculi der International Federation for Information Processing (IFIP) , die ALGOL . spezifiziert, unterstützt und pflegt 60 und ALGOL 68 . Schließlich verließ er den Ausschuss, offenbar weil er den Mehrheitsmeinungen nicht zustimmen konnte. Dennoch schrieb er während seiner Zeit am Mathematisch Centrum (Amsterdam) gemeinsam mit Jaap Zonneveld den ersten ALGOL 60-Compiler . Im August 1960 nahmen er und Zonneveld den ersten vollständig funktionierenden ALGOL 60- Compiler (für den Electrologica X1- Computer) in Betrieb, mehr als ein Jahr bevor ein Compiler von einer anderen Gruppe produziert wurde. Dijkstra und Zonneveld, die am Compiler mitgearbeitet haben, vereinbarten, sich nicht zu rasieren, bis das Projekt abgeschlossen war. Zonneveld rasierte sich kurz darauf, aber Dijkstra behielt seinen Bart für den Rest seines Lebens.

ALGOL ist das Ergebnis einer Zusammenarbeit amerikanischer und europäischer Komitees. ALGOL 60 (kurz für ALGOrithmic Language 1960) ist ein Mitglied der ALGOL-Familie von Computerprogrammiersprachen. Es folgte auf ALGOL 58 und inspirierte viele darauf folgende Sprachen. Es führte zu vielen anderen Sprachen, darunter BCPL , B , Pascal , Simula und C . Algol 60 war eine hochentwickelte Computersprache und bot eine Vielzahl von bisher unbekannten Herausforderungen bei der Implementierung . Wie Bjarne Stroustrup anmerkt: "Ein Problem bei Algol60 war, dass niemand wusste, wie man es umsetzt." Eine große neue Herausforderung bei der Implementierung von Algol 60 war die Laufzeitzuweisung und -verwaltung von Daten. Im Jahr 1960 Dijkstra und Zonneveld gezeigt , wie man rekursive Prozeduren ausgeführt werden, um eine Laufzeit unter Verwendung von Stapeln von Aktivierungsaufzeichnungen, und wie effizient Zugriffskennungen von statisch umschließenden Bereichen der sogenannte Verwendung Anzeige . Der ALGOL 60-Compiler war einer der ersten, der Rekursion mit einer neuartigen Methode unterstützte. Dijkstras Kurzbuch Primer of Algol 60 Programming , das ursprünglich 1962 veröffentlicht wurde, war mehrere Jahre lang die Standardreferenz für die Sprache.

Die Rolle der Programmiermethodik und die Geburtsstunde der Bewegung der strukturierten Programmierung

1965 schrieb Dijkstra seine berühmten Notes on Structured Programming und erklärte Programmieren zu einer Disziplin im Gegensatz zu einem Handwerk . Ebenfalls 1965 veröffentlichte Hoare eine wichtige Arbeit über Datenstrukturierung. Diese Ideen hatten einen tiefgreifenden Einfluss auf neue Programmiersprachen , insbesondere Pascal . Sprachen sind die Vehikel, in denen diese Ideen ausgedrückt werden sollten. Die strukturierte Programmierung wurde durch eine strukturierte Programmiersprache unterstützt .

—  Niklaus Wirth , IEEE Annals of the History of Computing (2008)

Die durch Dijkstras Bildersturm ausgelöste Revolution der Programmieransichten führte zu einer Bewegung, die als strukturierte Programmierung bekannt ist und einen systematischen, rationalen Ansatz bei der Programmkonstruktion befürwortet. Strukturierte Programmierung ist die Grundlage für alles, was seitdem in der Programmiermethodik gemacht wurde , einschließlich der objektorientierten Programmierung .

—  Bertrand Meyer , Touch of Class: Mit Objekten und Verträgen gut programmieren lernen (2009)

Die Computerprogrammierung in den 1950er bis 1960er Jahren wurde nicht als akademische Disziplin anerkannt und im Gegensatz zu den ausgereiften Wissenschaften gab es keine theoretischen Konzepte oder Kodierungssysteme. Programmieren als berufliche Tätigkeit wurde in diesen Jahren kaum verstanden. In den späten 1960er Jahren befand sich die Computerprogrammierung in einer Krise. Softwarekrise ist ein Begriff, der in den Anfängen der Informatik für die Schwierigkeit verwendet wurde, nützliche und effiziente Computerprogramme in der erforderlichen Zeit zu schreiben . Die Softwarekrise war auf die rapide Zunahme der Computerleistung und die Komplexität der Probleme zurückzuführen, die angegangen werden konnten. Mit zunehmender Komplexität der Software entstanden viele Softwareprobleme, weil die vorhandenen Methoden nicht ausreichten. Der Begriff "Softwarekrise" wurde von einigen Teilnehmern der ersten NATO Software Engineering Conference 1968 in Garmisch , Deutschland, geprägt. Seine ACM Turing Award Lecture 1972 nimmt auf dasselbe Problem Bezug: „Die Hauptursache für die Softwarekrise ist, dass die Maschinen um mehrere Größenordnungen leistungsfähiger geworden sind! überhaupt kein Problem; als wir ein paar schwache Computer hatten, wurde die Programmierung zu einem leichten Problem, und jetzt haben wir riesige Computer, die Programmierung ist zu einem ebenso riesigen Problem geworden."

Während Dijkstra in den 1950er Jahren ausgiebig in Maschinencode programmiert hatte, kam er zu dem Schluss, dass die häufige Verwendung der GOTO- Anweisung in Hochsprachen meist ein Symptom für eine schlechte Struktur war. 1968 verfasste er eine private Zeitung "A Case against the GO TO Statement", die dann als Brief in CACM veröffentlicht wurde. Herausgeber Niklaus Wirth gab diesem Brief die Überschrift „ Go To Statement Considered Harmful “, wodurch der Begriff „ als schädlich “ in die Informatik eingeführt wurde.

Dijkstra argumentierte, dass die Programmieranweisung GOTO, die in vielen höheren Programmiersprachen zu finden ist, eine Hauptfehlerquelle darstellt und daher beseitigt werden sollte. Dieser Brief löste eine große Debatte in der Programmiergemeinschaft aus. Einige gingen so weit, gute Programmierung mit der Eliminierung von GO TO gleichzusetzen . Dijkstra weigerte sich, die Debatte oder sogar die GO TO-Erklärung in seinem Artikel "Notes on Structured Programming" zu erwähnen. Die Debatte ist längst verstummt; Programmiersprachen bieten Alternativen zum GO TO, nur wenige Programmierer verwenden es heute großzügig und die meisten verwenden es überhaupt nie.

Dijkstras These war, dass Abweichungen vom linearen Kontrollfluss deutlicher sind, wenn sie nur in disziplinierten übergeordneten Strukturen wie der if-then-else- Anweisung und der while-Schleife zulässig sind . Diese Methodik wurde zu einer Bewegung der strukturierten Programmierung weiterentwickelt , dem Titel seines Buches von 1972, das er gemeinsam mit Tony Hoare und Ole-Johan Dahl verfasst hat . Von vielen als die erste bedeutende Bewegung in der Geschichte der Computerprogrammierung angesehen, wurde die strukturierte Programmierung in den 1970er Jahren zur neuen Programmierorthodoxie.

Strukturierte Programmierung wird oft als "Goto-less-Programmierung" bezeichnet. Aber wie Bertrand Meyer stellt fest : „Als das erste Buch zum Thema [ Strukturierte Programmierung von Dijkstra, Dahl und Hoare] zeigt, strukturierte Programmierung geht es um viel mehr als Kontrollstrukturen und die goto . Seine Hauptaussage ist , sollte die Programmierung eines in Betracht gezogen werden wissenschaftliche Disziplin, die auf mathematischer Strenge basiert." Als Programmierparadigma hat die strukturierte Programmierung – insbesondere in den 1970er und 1980er Jahren – die Geburt vieler moderner Programmiersprachen wie Pascal , C , Modula-2 und Ada maßgeblich beeinflusst . Die Fortran 77- Version, die die Konzepte der strukturierten Programmierung beinhaltet, wurde 1978 veröffentlicht. Die Sprache C++ war eine erheblich erweiterte und verbesserte Version der beliebten strukturierten Programmiersprache C (siehe auch: Liste der C-basierten Programmiersprachen ). Da C++ aus einer traditionelleren strukturierten Sprache entwickelt wurde , ist es eher eine „ Hybridsprache “ als eine reine objektorientierte Programmiersprache .

In seinem Artikel Strukturierte Programmierung: Rückblick und Ausblick (1986), Harlan Mills schreibt : „Edsger W. Dijkstra 1969 Strukturierte Programmierung Artikel gefällte ein Jahrzehnt der intensiven Fokus auf Programmiertechniken , die menschlichen Erwartungen und Leistungen in grundlegend verändert hat Software - Entwicklung Vor diesem Jahrzehnt. Von intensiver Bedeutung wurde Programmieren als private, rätsellösende Aktivität betrachtet, bei der Computeranweisungen geschrieben wurden, um als Programm zu funktionieren Die Herausforderung bestand darin, Programme überhaupt zum Laufen zu bringen und sie dann weiter zu debuggen, um die richtigen Dinge zu tun. Danach konnte man von Programmen erwarten, dass sie sowohl laufen als auch die richtigen Dinge mit wenig oder gar keinem Debugging tun. Früher war es allgemein üblich, dass kein größeres Programm könnte fehlerfrei sein. Danach sind viele umfangreiche Programme ein Jahr oder länger gelaufen, ohne dass Fehler festgestellt wurden. Diese Erwartungen und Errungenschaften sind aufgrund der Trägheit industrieller Praktiken nicht universell. Aber sie sind gut genug etabliert, um einen grundlegenden Wandel in der Softwareentwicklung einzuläuten."

Das Buch Concise Encyclopedia of Computer Science (2004), herausgegeben von Edwin D. Reilly, stellt fest, dass "die Hauptbeiträge der strukturierten Programmierung zweierlei waren - die Erhebung der Programmiertechnik zu etwas weniger Kunst und mehr zu einer Wissenschaft, und die Demonstration, dass sorgfältig strukturierte Programme kreative Werke mit ausreichend literarischem Wert sein können, um von Menschen und nicht nur von Computern gelesen zu werden."

Forschung zu Programmdesign und -entwicklung zu Beginn der Softwareentwicklung

Dijkstras Ideen zur Programmiermethodik (insbesondere der Bewegung der strukturierten Programmierung) trugen dazu bei, den Grundstein für die Geburt und Entwicklung der Berufsdisziplin des Software-Engineerings (insbesondere des Software-Designs und -Entwicklung ) zu legen , die es Programmierern ermöglichte, immer komplexere Softwareprojekte zu organisieren und zu verwalten. In den späten 1960er Jahren diskutierte Dijkstra das Konzept der Programmfamilien. Mitte der 1970er Jahre klärten David Parnas und andere die Idee und zeigten, wie man sie in Software-Engineering-Prinzipien anwendet.

Der Aufstieg der strukturierten Programmierungsbewegung führte zu vielen anderen strukturierten Ansätzen, die auf das Softwaredesign angewendet wurden . Die Techniken der strukturierten Analyse und des strukturierten Designs sind Auswüchse strukturierter Programmierkonzepte und -techniken sowie der frühen Ideen zum modularen Design. Die Prinzipien der Modularität wurden durch Larry Constantines Konzepte der Kopplung (zu minimieren zwischen Modulen) und Kohäsion (zu maximieren innerhalb von Modulen), durch David Parnass Techniken des Verbergens von Informationen und durch abstrakte Datentypen gestärkt . Es wurden eine Reihe von Werkzeugen und Methoden entwickelt, die strukturierte Konzepte verwenden , wie beispielsweise Structured Design , Jacksons Structured Programming , Ross ' Structured Analysis and Design Technique (SADT), Yourdons Structured Method , Structured Systems Analysis and Design Method (SSADM) und James Martins Informationen technik ingenieurwesen . Der Bereich der Softwaremetriken wird oft als direkter Einfluss der strukturierten Programmierungsbewegung auf das Software Engineering in den 1970er Jahren angesehen.

Separation of Concerns (SoC), eines der Grundprinzipien in der Softwareentwicklung , ist ein Entwurfsprinzip zur Unterteilung eines Computerprogramms in verschiedene Abschnitte, sodass jeder Abschnitt ein separates Anliegen behandelt . Der Begriff Trennung von Interessen wurde von Dijkstra in seinem 1974 erschienenen Aufsatz "Über die Rolle des wissenschaftlichen Denkens" geprägt.

Betriebssystemforschung

In den 1960er Jahren entwarfen und implementierten Dijkstra und seine Kollegen in Eindhoven DAS (für ' Technische Hogeschool Eindhoven ') Betriebssystem , das in klar identifizierte Abstraktionsschichten organisiert war . Sein Artikel von 1968 zu diesem Thema bildete die Grundlage für die späteren Entwürfe der Betriebssysteme. David Alan Grier von der IEEE Computer Society schreibt: „Wir führen die Idee, Computersysteme in Schichten zu bauen, im Allgemeinen auf ein Papier von 1967 zurück, das der niederländische Informatiker Edsger Dijkstra auf einer gemeinsamen Konferenz der IEEE Computer Society/ACM hielt hatte mit dem Problem gekämpft, Software zu organisieren. Wenn Sie sich frühe Beispiele von Programmen ansehen, von denen Sie viele in der elektronischen Bibliothek der Computer Society finden, werden Sie feststellen, dass der meiste Code dieser Ära kompliziert und schwer zu lesen ist, schwer zu modifizieren und schwer wiederzuverwenden. In seinem Aufsatz von 1967 beschrieb Dijkstra, wie Software in Schichten aufgebaut werden kann, und gab ein Beispiel für ein einfaches Betriebssystem mit fünf Schichten. Er räumte ein, dass dieses System möglicherweise kein realistischer Test für ihn ist Ideen, aber er argumentierte, dass „je größer das Projekt, desto wesentlicher die Strukturierung!“ Die Idee, Komplexität durch Schichten zu kontrollieren, ist zu einer tragenden Säule der Softwarearchitektur geworden Wende es auf viele Probleme an. Wir sehen es in der Hierarchie der Klassen in der objektorientierten Programmierung und in der Struktur der serviceorientierten Architektur (SOA). SOA ist eine relativ neue Anwendung von Layering in der Informatik. Es wurde 2007 als Mittel zur Steuerung der Komplexität in Geschäftssystemen formuliert, insbesondere in verteilten Systemen, die das Internet stark nutzen. Wie Dijkstras Plan für die Systementwicklung wird das Schichtsystem als SOA Solution Stack oder S3 bezeichnet. Die neun Schichten von S3 sind: 1) Betriebssysteme, 2) Servicekomponenten, 3) Services, 4) Geschäftsprozesse, 5) Verbraucheraktionen, 6) Systemintegration, 7) Qualitätskontrolle und -sicherung, 8) Informationsarchitektur und 9) System-Governance und -Richtlinien."

Dijkstra organisierte das Design des Systems in Schichten, um die Gesamtkomplexität der Software zu reduzieren. Obwohl der Begriff „Architektur“ noch nicht zur Beschreibung von Softwaredesign verwendet wurde , galt dies sicherlich als der erste Einblick in die Softwarearchitektur . Sie führte eine Reihe von Gestaltungsprinzipien ein, die zum Arbeitsvokabular eines jeden professionellen Programmierers gehören: Abstraktionsebenen, Programmierung in Schichten, die Semaphore und kooperierende sequentielle Prozesse . Sein Originalartikel über das THE-Betriebssystem wurde im Januar 1983 in der Ausgabe zum 25 Architektur – eine Linie, die bis heute andauert, weil hierarchische Modularität ein leistungsstarker Ansatz zur Organisation großer Systeme ist."

Concurrent Computing (gleichzeitige Programmierung)

Während seit Jahren die gleichzeitige Programmausführung in Betracht gezogen wurde, begann die Informatik der Nebenläufigkeit mit Edsger Dijkstras bahnbrechender Arbeit von 1965, die das Problem des gegenseitigen Ausschlusses einführte . (...) Das zweite grundlegende Problem der gleichzeitigen Programmierung, das untersucht werden sollte, war die Produzenten-Konsumenten-Synchronisation. Diese Form der Synchronisation auf Hardware - Ebene in den frühesten Computern verwendet wurde, aber es wurde zum ersten Mal als Concurrency Problem von Dijkstra im Jahr 1965 identifiziert, wenn auch nicht in dieser Formulierung bis 1968 (...) Nach veröffentlicht verteilten Systemen , die nächste großen Schritt bei gleichzeitigen Algorithmen war die Untersuchung der Fehlertoleranz . Die erste wissenschaftliche Untersuchung der Fehlertoleranz war Dijkstras bahnbrechendes Papier von 1974 zur Selbststabilisierung . Doch wie es manchmal bei Arbeiten vorkommt, die ihrer Zeit voraus sind, wurde dieses Papier wenig beachtet und für ein Jahrzehnt im Wesentlichen vergessen. (...) In den folgenden Jahrzehnten ist das Interesse an Nebenläufigkeit insbesondere in verteilten Systemen enorm gewachsen. Rückblickend auf die Ursprünge des Feldes fällt die grundlegende Rolle von Edsger Dijkstra auf, dem diese Geschichte gewidmet ist.

—  Leslie Lamport , Turing-Vortrag: The Computer Science of Concurrency: The Early Years (Juni 2015)

Ein Semaphor ( niederländisch : seinpaal ), der Begriff, der in Dijkstras Originalarbeit verwendet wird. In den frühen 1960er Jahren schlug Dijkstra den ersten Synchronisationsmechanismus für nebenläufige Prozesse vor, den Semaphor mit seinen beiden Operationen P und V.

In einem einseitigen Papier von 1965 stellte Dijkstra das ' Mutual-Exclusion- Problem' für n Prozesse vor und diskutierte eine Lösung dafür. Es war wahrscheinlich der erste veröffentlichte gleichzeitige Algorithmus . Auch der inzwischen übliche Begriff eines „ kritischen Abschnitts “ wurde in diesem Aufsatz eingeführt. Per Brinch Hansen , ein Pionier auf dem Gebiet des Concurrent Computing , betrachtet Dijkstras Cooperating Sequential Processes (1965) als den ersten Klassiker in der parallelen Programmierung. Wie Brinch Hansen feststellt, legt Dijkstra mit diesem Papier die konzeptionelle Grundlage für abstrakte gleichzeitige Programmierung.

Ein einfaches Beispiel für zwei Prozesse, die gleichzeitig eine verknüpfte Liste ändern und einen Konflikt verursachen. Das Erfordernis des gegenseitigen Ausschlusses wurde erstmals von Dijkstra in seiner bahnbrechenden Arbeit von 1965 mit dem Titel Solution of a problem in Concurrent Programming Control identifiziert und gelöst und wird als das erste Thema in der Erforschung nebenläufiger Algorithmen genannt .

1968 veröffentlichte Dijkstra seine bahnbrechende Arbeit ' Cooperating Sequential Processes ', einen 70-seitigen Essay, der das Gebiet der gleichzeitigen Programmierung begründete . Er erörterte darin den Begriff des gegenseitigen Ausschlusses ( Mutex ) und die Kriterien, die eine zufriedenstellende Lösung erfüllen sollte. Er korrigierte auch die historische Perspektive, die in seiner Arbeit von 1965 ausgelassen wurde, indem er die erste bekannte richtige Lösung des Problems des gegenseitigen Ausschlusses für zwei Prozesse von Theodorus Dekker aufnahm . Dijkstra verallgemeinerte anschließend die Lösung von Dekker auf n Prozesse. Außerdem schlug er den ersten Synchronisationsmechanismus für nebenläufige Prozesse vor, den Semaphor mit seinen beiden Operationen P und V. Er identifizierte auch das ' Deadlock- Problem' (dort 'das Problem der tödlichen Umarmung ' genannt) und schlug einen eleganten ' Banker's Algorithmus' vor ' das verhindert Deadlocks . Das Erkennen und Verhindern von Blockaden wurde zu mehrjährigen Forschungsproblemen im Bereich der gleichzeitigen Programmierung.

Illustration des Problems der Speisephilosophen

Das Diner-Philosophen-Problem ist ein Beispielproblem, das häufig beim Design von gleichzeitigen Algorithmen verwendet wird, um Synchronisationsprobleme und Techniken zu ihrer Lösung zu veranschaulichen . Es wurde ursprünglich 1965 von Dijkstra als Prüfungsübung für Studenten formuliert und in Form von Computern präsentiert, die um den Zugang zu Peripheriegeräten für Bandlaufwerke konkurrieren . Kurz darauf gab Tony Hoare dem Problem seine gegenwärtige Formulierung. Das Problem des schlafenden Friseurs wird auch Dijkstra zugeschrieben.

Michel Raynal (2012) schreibt: "Seit den frühen Arbeiten von EW Dijkstra (1965), der das Problem des gegenseitigen Ausschlusses, das Konzept eines Prozesses, das Semaphor-Objekt, die Vorstellung einer schwächsten Vorbedingung und bewachte Befehle (unter vielen anderen) Beiträge) ist die Synchronisation kein Trickkatalog mehr, sondern eine Domäne der Informatik mit eigenen Konzepten, Mechanismen und Techniken, deren Ergebnisse in vielen Bereichen angewendet werden können Lehrplan."

John W. McCormicket al. (2011) stellt fest: „Der Begriff des nebenläufigen Programms als Mittel zum Schreiben paralleler Programme ohne Rücksicht auf die zugrunde liegende Hardware wurde erstmals von Edsger Dijkstra (1968) eingeführt. Moti Ben-Ari (1982) fasste Dijkstras Idee elegant in drei Sätzen zusammen : "Concurrent Programming ist die Bezeichnung für Programmiernotationen und Techniken, um potenzielle Parallelität auszudrücken und die resultierenden Synchronisations- und Kommunikationsprobleme zu lösen. Die Implementierung von Parallelität ist ein Thema in Computersystemen (Hardware und Software), das im Wesentlichen unabhängig von der gleichzeitigen Programmierung ist ist wichtig, weil es einen abstrakten Rahmen bietet, um Parallelität zu studieren, ohne sich in den Implementierungsdetails zu verzetteln.'"

Verteiltes Rechnen (verteilte Programmierung)

Dijkstra war einer der ganz frühen Pioniere der Erforschung der Prinzipien des verteilten Rechnens . Die Sponsoren des Dijkstra-Preises erkennen an, dass "kein anderer Mensch einen größeren Einfluss auf die Forschung zu Prinzipien des verteilten Rechnens hatte". Einige seiner Arbeiten gelten sogar als solche, die das Feld begründeten. Dijkstras Aufsatz aus dem Jahr 1965, Lösung eines Problems bei gleichzeitiger Programmsteuerung, war der erste, der die richtige Lösung für das Problem des gegenseitigen Ausschlusses präsentierte . Leslie Lamport schreibt, dass diese Arbeit "wahrscheinlich der Grund ist, warum PODC existiert" und "das Gebiet der gleichzeitigen und verteilten Algorithmen begann ".

Insbesondere seine Arbeit "Self-stabilizing Systems in Spite of Distributed Control" (1974) hat das Teilgebiet der Selbststabilisierung eröffnet . Sie gilt auch als die erste wissenschaftliche Untersuchung fehlertoleranter Systeme . Dijkstra-Papier wurde nicht viel beachteten bis Leslie Lamport eingeladen Vortrag auf dem ACM Symposium on Principles of Distributed Computing ( PODC ) im Jahr 1983. In seinem Bericht über Dijkstra Arbeit selbststabilisierend verteilten Systeme , Lamport betrachtet es als ‚ein Meilenstein in der Arbeit auf Fehlertoleranz “ und „ein sehr fruchtbares Feld für die Forschung“.

Formale Spezifikation und Verifizierung

Ab den 1970er Jahren galt Dijkstras Hauptinteresse der formalen Überprüfung . 1976 veröffentlichte Dijkstra ein bahnbrechendes Buch, A Discipline of Programming , das seine Methode der systematischen Entwicklung von Programmen zusammen mit ihren Korrektheitsbeweisen vorstellte. In seiner Exposition benutzte er seine ' Bewachte Befehlssprache '. Die Sprache mit ihrem Vertrauen auf Nicht-Determinismus, der angenommenen Semantik der schwächsten Vorbedingung und der vorgeschlagenen Entwicklungsmethode hat das Feld bis heute erheblich beeinflusst. Der Verfeinerungskalkül , ursprünglich von Ralph-Johan Back vorgeschlagen und von Carroll Morgan entwickelt , ist eine Erweiterung des schwächsten Vorbedingungskalküls von Dijkstra , bei dem Programmanweisungen als Prädikatstransformatoren modelliert werden .

Um diesen Programmieransatz weiter zu unterstützen, veröffentlichte er 1984 gemeinsam mit Wim Feijen ein Einführungslehrbuch für Erstsemester der Informatik. Das zuerst auf Niederländisch erschienene Buch trug den Titel Een methode van programren . Die englische Ausgabe erschien 1988 als A Method of Programming .

Zum Wesen der Informatik und Computerprogrammierung

Viele von Dijkstras Meinungen zu Informatik und Programmierung sind weit verbreitet. Zum Beispiel wird ihm manchmal die Programmierphrase "zwei oder mehr, benutze ein for" (eine Faustregel für die Verwendung einer Schleife) zugeschrieben.

Er war der erste, der behauptete, dass Programmierung von Natur aus so komplex ist, dass Programmierer alle möglichen Tricks und Abstraktionen nutzen müssen, um sie erfolgreich zu verwalten.

Dijkstra war einer der bekanntesten Gegner der ingenieurwissenschaftlichen Sichtweise der Informatik. Wie Peter Naur und Kristen Nygaard mochte Dijkstra den Begriff „Informatik“ nicht. Informatik verdient, wie Dijkstra betonte, einen besseren Namen. Er schlägt vor, dass man es „Informatik“ nennen kann. Anstelle des Computers oder der Computertechnologie wollte Dijkstra die abstrakten Mechanismen hervorheben, mit denen die Informatik die Komplexität beherrscht. Als er die abstrakte Natur der Informatik zum Ausdruck brachte , schrieb er:

Eine noch längere Verwirrung entstand dadurch, dass zu den Unvorbereiteten auch die Elektroniker gehörten, die die Maschinen entwerfen, bauen und warten sollten. Der Job ging eigentlich über die damalige elektronische Technologie hinaus , und so wurde die Frage, wie man die physische Ausrüstung mehr oder weniger in einem funktionsfähigen Zustand bekommt und hält, in der Anfangszeit zum alles überragenden Anliegen. Dadurch wurde das Thema – vor allem in den USA – zu früh als „ Informatik “ bekannt – was eigentlich so viel ist, als würde man Chirurgie als „Messerwissenschaft“ bezeichnen – und es hat sich in den Köpfen der Menschen fest verankert, dass es in der Informatik um Maschinen geht und deren Peripheriegeräte. Quod non [lateinisch: "Was nicht wahr ist"]. Heute wissen wir, dass die elektronische Technologie nicht mehr zur Informatik beitragen kann als die physische Ausrüstung. Heute wissen wir, dass programmierbare Computer nicht mehr und nicht weniger als ein äußerst handliches Gerät sind, um jeden denkbaren Mechanismus zu realisieren, ohne einen einzigen Draht zu verändern, und dass die Kernherausforderung für die Informatik daher eine konzeptionelle ist, nämlich welche (abstrakten) Mechanismen wir können schwanger werden, ohne uns in der Komplexität unseres eigenen Schaffens zu verlieren.

In The Humble Programmer (1972) schrieb Dijkstra: "Wir dürfen nicht vergessen, dass es nicht unsere Aufgabe [Computerwissenschaftler] ist, Programme zu erstellen, sondern es ist unsere Aufgabe, Berechnungsklassen zu entwerfen, die ein gewünschtes Verhalten zeigen."

Dijkstra lehnte auch die Aufnahme des Software Engineerings unter das Dach der akademischen Informatik ab. Er schrieb: "Da die Wirtschaftswissenschaften als "Die miserable Wissenschaft" bekannt sind, sollte Software-Engineering als "The Doomed Discipline" bekannt sein, zum Scheitern verurteilt, weil sie ihr Ziel nicht einmal erreichen kann, da ihr Ziel in sich widersprüchlich ist." Und "Software-Engineering hat 'Wie man programmiert, wenn man es nicht kann' als seine Charta akzeptiert."

Persönlichkeit und Arbeitsstil

Dijkstra an der Tafel während einer Konferenz an der ETH Zürich 1994. Er sagte einmal: " Ein Bild sagt mehr als tausend Worte , eine Formel sagt mehr als tausend Bilder."

Einfachheit ist eine große Tugend, aber es erfordert harte Arbeit, um sie zu erreichen, und Bildung, um sie zu schätzen. Und zu allem Überfluss: Komplexität verkauft sich besser. Die Computerindustrie ist nicht die einzige, die diese wunde Wahrheit entdeckt hat, sondern auch die akademische Welt. Wenn Sie einen von Anfang bis Ende glasklaren Vortrag halten, fühlt sich Ihr Publikum betrogen und murmelt beim Verlassen des Hörsaals "Das war doch alles ziemlich trivial, oder?"

—  EW Dijkstra, "On the Nature of Computing Science" (EWD896), August 1984

Man kann es dem MIT kaum verdenken , einen obskuren Informatiker in einer Kleinstadt in den Niederlanden nicht wahrgenommen zu haben.

—  Dijkstra hat sich in Nuenen Mitte der 1960er Jahre witzig beschrieben .

In der Welt der Informatik ist Dijkstra als "Charakter" bekannt. Im Vorwort seines Buches A Discipline of Programming (1976) stellte er folgendes fest: "Für das Fehlen einer Bibliographie biete ich weder eine Erklärung noch eine Entschuldigung an." Tatsächlich haben die meisten seiner Artikel und Bücher überhaupt keine Referenzen. Diese Herangehensweise an Referenzen wurde von einigen Forschern beklagt. Aber Dijkstra wählte diese Arbeitsweise, um seine Eigenständigkeit zu bewahren.

Als Universitätsprofessor für einen Großteil seines Lebens betrachtete Dijkstra das Lehren nicht nur als eine obligatorische Tätigkeit, sondern als ernsthaftes Forschungsvorhaben. Sein Lehransatz war unkonventionell. Sein Vortragsstil wird als eigenwillig beschrieben. Bei Vorlesungen werden die langen Pausen zwischen den Sätzen oft darauf zurückgeführt, dass Englisch nicht Dijkstras Muttersprache ist. Die Pausen dienten ihm jedoch auch als Möglichkeit, auf den Beinen zu denken, und er galt als schneller und tiefgründiger Denker, während er Vorlesungen hielt. Seine Kurse für Studenten in Austin hatten wenig mit Informatik zu tun, sondern mit der Präsentation mathematischer Beweise. Zu Beginn jedes Semesters machte er von jedem Studenten ein Foto, um sich deren Namen einzuprägen. Er befolgte nie ein Lehrbuch , mit Ausnahme seines eigenen, während es in Vorbereitung war. Während seiner Vorlesungen schrieb er Korrekturabzüge mit Kreide auf eine Tafel, anstatt Überkopffolien zu verwenden. Er forderte die Schüler auf, Ideen vorzuschlagen, die er dann erforschte, oder weigerte sich, sie zu erforschen, weil sie gegen einige seiner Grundsätze verstießen. Er stellte schwierige Hausaufgaben auf und studierte die Lösungen seiner Schüler gründlich. Seine Abschlussprüfungen führte er eine Woche lang mündlich durch. Jeder Schüler wurde in Dijkstras Büro oder zu Hause untersucht, und eine Prüfung dauerte mehrere Stunden.

Aufgabe der Universität ist es nicht, das zu bieten, was die Gesellschaft verlangt, sondern zu geben, was die Gesellschaft braucht. [Die Dinge, die die Gesellschaft verlangt, werden allgemein verstanden, und dafür braucht man keine Universität; die Universität hat zu bieten, was sonst niemand bieten kann.]

—  EW Dijkstra, "Antworten auf Fragen von Studenten der Softwaretechnik" (EWD1305), November 2000

Dijkstra war auch sehr originell in seiner Art, die Fähigkeit der Menschen für einen Job einzuschätzen. Als Vladimir Lifschitz 1990 zu einem Vorstellungsgespräch nach Austin kam, gab ihm Dijkstra ein Rätsel. Vladimir hat es gelöst und arbeitet seitdem in Austin.

Obwohl er einen Großteil der Softwaretechnologie erfunden hatte, verzichtete er jahrzehntelang auf den Einsatz von Computern in seiner eigenen Arbeit. Selbst nachdem er der Ermutigung seiner UT-Kollegen nachgegeben und einen Macintosh- Computer erworben hatte , nutzte er ihn nur für E-Mails und zum Surfen im World Wide Web . Dijkstra schrieb seine Artikel nie mit einem Computer. Er verließ sich lieber auf seine Schreibmaschine und später auf seinen Montblanc- Kugelschreiber. Dijkstras Lieblingsschreibgerät war der Montblanc Meisterstück Füllfederhalter . Er probierte immer wieder andere Stifte aus, aber keiner verdrängte jemals den Montblanc.

Er hatte keine Verwendung für Textverarbeitungsprogramme , da er glaubte, dass man in der Lage sein sollte, einen Brief oder Artikel ohne grobe Entwürfe, Umschreibungen oder wesentliche Bearbeitungen zu schreiben. Er arbeitete alles in seinem Kopf durch, bevor er den Stift zu Papier brachte, und erwähnte einmal, dass er als Physikstudent seine Hausaufgaben im Kopf lösen würde, während er durch die Straßen von Leiden ging . Die meisten Veröffentlichungen von Dijkstra wurden von ihm allein verfasst. Er hatte nie eine Sekretärin und kümmerte sich allein um seine Korrespondenz. Als Kollegen zu seinem sechzigsten Geburtstag eine Festschrift verfassten , die im Springer-Verlag erschienen ist , hat er sich die Mühe gemacht, jedem der 61 Mitwirkenden einzeln in einem handgeschriebenen Brief zu danken.

Während seiner gesamten Karriere war seine Arbeit von Eleganz und Sparsamkeit geprägt. Als produktiver Schriftsteller (insbesondere als Essayist) verfasste Dijkstra mehr als 1.300 Aufsätze, von denen viele handschriftlich in seinem präzisen Skript verfasst wurden. Es waren Aufsätze und Gleichnisse; Märchen und Warnungen; umfassende Erklärung und pädagogischer Vorwand. Die meisten beschäftigten sich mit Mathematik und Informatik; andere waren Reiseberichte, die mehr über ihren Autor als über die besuchten Personen und Orte aussagen. Es war seine Gewohnheit, jeden Artikel zu kopieren und an eine kleine Gruppe von Kollegen zu verteilen, die die Artikel kopierten und an eine andere begrenzte Gruppe von Wissenschaftlern weiterleiteten. Seine Liebesaffäre mit der Einfachheit kam in jungen Jahren und unter der Anleitung seiner Mutter. Er sagte einmal, er habe seine Mutter gefragt, ob Trigonometrie ein schwieriges Thema sei. Sie antwortete, er müsse alle Formeln lernen, und wenn er mehr als fünf Zeilen brauche, um etwas zu beweisen, sei er auf dem falschen Weg.

Dijkstra war berühmt für seinen Witz, seine Beredsamkeit, seine Grobheit, seine Schroffheit und oft Grausamkeit gegenüber Berufskollegen und seine Art mit Worten, wie in seiner Bemerkung: "Die Frage, ob Maschinen denken können (…) ist ungefähr so ​​relevant wie die Frage, ob" U-Boote können schwimmen." Sein Rat an einen vielversprechenden Forscher, der nach der Auswahl eines Forschungsthemas fragte, waren die weisen Worte: "Tue nur, was nur du tun kannst". Dijkstra war auch für seine lautstarke Kritik und seinen Mangel an sozialen Fähigkeiten im Umgang mit Kollegen bekannt. Als ausgesprochener und kritischer Visionär war er entschieden gegen die BASIC- Lehre .

In vielen seiner witzigeren Essays beschrieb Dijkstra eine fiktive Firma, deren Vorsitzender er war. Das Unternehmen wurde Mathematik, Inc. genannt, ein Unternehmen , das er sich vorgestellt hat , vermarktet die Produktion von mathematischen Theoremen in der gleichen Art und Weise , dass Software - Unternehmen , die Produktion von Computerprogrammen vermarktet hatte. Er erfand eine Reihe von Aktivitäten und Herausforderungen von Mathematics Inc. und dokumentierte sie in mehreren Artikeln der EWD-Reihe. Das imaginäre Unternehmen hatte einen Beweis für die Riemann-Hypothese erbracht , hatte dann aber große Schwierigkeiten, Lizenzgebühren von Mathematikern einzutreiben , die Ergebnisse unter der Annahme der Riemann-Hypothese nachgewiesen hatten. Der Beweis selbst war ein Geschäftsgeheimnis . Viele der Beweise des Unternehmens wurden vor die Tür geworfen und dann musste ein Großteil der Bemühungen des Unternehmens für die Wartung aufgewendet werden . Ein erfolgreicherer Versuch war der Standardbeweis für den Satz des Pythagoras , der die mehr als 100 inkompatiblen existierenden Beweise ersetzte. Dijkstra beschrieb Mathematics Inc. als "das aufregendste und miserabelste Geschäft, das je konzipiert wurde". EWD 443 (1974) beschreibt sein fiktives Unternehmen mit über 75 Prozent des Weltmarktanteils.

EWD-Manuskripte

Dijkstra war bekannt für seine Angewohnheit, Manuskripte sorgfältig mit seinem Füllfederhalter zu verfassen . Die Manuskripte werden EWDs genannt, da Dijkstra sie mit EWD , seinen Initialen, als Präfix nummeriert hat . Laut Dijkstra selbst begannen die EWDs, als er vom Mathematischen Zentrum in Amsterdam an die Technische Universität Eindhoven (damals Technische Hogeschool Eindhoven) wechselte. Nach dem Gehen Eindhoven , erfuhr Dijkstra einen Block des Schriftstellers für mehr als ein Jahr. Dijkstra verteilte Fotokopien eines neuen EWD an seine Kollegen. Viele Empfänger haben ihre Kopien fotokopiert und weitergeleitet, sodass sich die EWDs in der internationalen Informatik-Community verbreitet haben. Die Themen waren Informatik und Mathematik und umfassten Reiseberichte, Briefe und Reden. Diese kurzen Artikel umfassen einen Zeitraum von 40 Jahren. Fast alle EWDs, die nach 1972 erschienen, waren handschriftlich. Sie sind selten länger als 15 Seiten und werden fortlaufend nummeriert. Der letzte, Nr. 1318, ist vom 14. April 2002. In der Informatik werden sie als EWD-Berichte oder einfach als EWDs bezeichnet. Mehr als 1300 EWDs wurden gescannt, wobei eine wachsende Zahl transkribiert wurde, um die Suche zu erleichtern, und sind online im Dijkstra-Archiv der University of Texas verfügbar.

Persönliches Leben und Sterben

Dijkstra führte einen bescheidenen Lebensstil , bis hin zu spartanisch. Das Haus von ihm und seiner Frau in Nuenen war einfach, klein und bescheiden. Er besaß keinen Fernseher, keinen Videorekorder oder ein Mobiltelefon und ging nicht ins Kino. Er spielte Klavier und ging in Austin gerne auf Konzerte . Als begeisterter Hörer klassischer Musik war Dijkstras Lieblingskomponist Mozart .

Dijkstra starb am 6. August 2002. Laut Beamten der University of Texas war Krebs die Todesursache.

Einfluss und Anerkennung

Der Unterschied zwischen einem Computerprogrammierer und einem Informatiker liegt in der Berufsbezeichnung. Edsger Dijkstra möchte stolz "Computerprogrammierer" genannt werden, obwohl er seit einigen Jahren keinen Computer mehr angerührt hat. (...) Seine große Stärke ist, dass er kompromisslos ist. Es würde ihn körperlich krank machen, wenn er daran denkt, in C++ zu programmieren.

—  Donald Knuth (1996), ein Interview mit Donald Knuth von Jack Woehr von Dr. Dobb's Journal .

1972 würdigte die Association for Computing Machinery (ACM) Dijkstras wegweisende Beiträge auf diesem Gebiet mit der Verleihung des renommierten Turing-Preises. Das Zitat zur Auszeichnung lautet:

Edsger Dijkstra war in den späten 1950er Jahren maßgeblich an der Entwicklung von ALGOL beteiligt , einer höheren Programmiersprache, die zu einem Modell für Klarheit und mathematische Strenge geworden ist. Er ist einer der Hauptvertreter der Wissenschaft und Kunst von Programmiersprachen im Allgemeinen und hat viel zu unserem Verständnis ihrer Struktur, Repräsentation und Implementierung beigetragen. Seine fünfzehnjährigen Veröffentlichungen reichen von theoretischen Artikeln zur Graphentheorie bis hin zu grundlegenden Handbüchern, erläuternden Texten und philosophischen Betrachtungen im Bereich der Programmiersprachen.

Die Einführung bei der Preisverleihung ist eine Hommage an Dijkstra:

Das Arbeitsvokabular von Programmierern überall ist mit Wörtern übersät, die von EW Dijkstra stammen oder mit Nachdruck verbreitet wurden – Anzeige, tödliche Umarmung , Semaphor, Go-to-less-Programmierung, strukturierte Programmierung . Aber sein Einfluss auf die Programmierung ist weitreichender, als irgendein Glossar möglicherweise andeuten kann. Das kostbare Geschenk, das dieser Turing Award anerkennt, ist Dijkstras Stil: seine Herangehensweise an das Programmieren als hohe intellektuelle Herausforderung; seine beredte Beharrlichkeit und praktische Demonstration, dass Programme richtig komponiert und nicht nur auf Korrektheit ausgetestet werden sollten ; und seine einleuchtende Wahrnehmung von Problemen an den Grundlagen der Programmgestaltung . (…) Wir schätzen gute Programme genauso wie gute Literatur. Und im Zentrum dieser Bewegung, die nicht weniger schöne als nützliche Muster schafft und reflektiert, steht EW Dijkstra.

Mit den Worten von Sir Tony Hoare , FRS , die er bei Dijkstras Beerdigung überbrachte:

Edsger ist weithin als ein Mann anerkannt, der tief über viele tiefe Fragen nachgedacht hat; und zu den tiefsten Fragen gehört die der traditionellen Moralphilosophie: Wie soll ein Mensch sein Leben leben? Edsger fand seine Antwort auf diese Frage schon früh in seinem Leben: Er beschloss, als akademischer Wissenschaftler zu leben und an einem neuen Wissenschaftszweig zu forschen, der Wissenschaft der Informatik. Er würde die Grundlagen legen, die die Informatik als eine strenge wissenschaftliche Disziplin etablieren würden; und in seiner Forschung, in seiner Lehre und in seinem Schreiben strebte er nach Perfektion unter Ausschluss aller anderen Anliegen. Von diesen Verpflichtungen ist er nie abgewichen, und so hat er zu seinem gewählten Studienfach den größten Beitrag geleistet, den ein Mensch in einem Leben leisten kann.

Im März 2003 wurde die folgende E-Mail an die Distributed Computing- Community gesendet :

Damit soll bekannt gegeben werden, dass der früher als „ PODC Influential-Paper Award “ bekannte Preis nach dem verstorbenen Edsger W. Dijkstra, einem Pionier auf dem Gebiet des verteilten Computings, in „ Edsger W. Dijkstra Prize in Distributed Computing “ umbenannt wurde . Seine grundlegende Arbeit zu Nebenläufigkeitsprimitiven (wie dem Semaphor), Nebenläufigkeitsproblemen (wie gegenseitigem Ausschluss und Deadlock ), Überlegungen zu nebenläufigen Systemen und Selbststabilisierung umfasst eine der wichtigsten Stützen, auf denen das Gebiet des verteilten Rechnens aufbaut. Kein anderer Mensch hat einen größeren Einfluss auf die Forschung zu Prinzipien des verteilten Rechnens gehabt.

Der ehemalige ACM- Präsident Peter J. Denning schrieb über Dijkstra:

Edsger Dijkstra, einer der Giganten auf unserem Gebiet und ein leidenschaftlicher Anhänger der mathematischen Sichtweise von Programmen und Programmierung (...) Im Laufe des letzten Vierteljahrhunderts hatte er viele der großen intellektuellen Herausforderungen auf diesem Gebiet als Programmierung formuliert – die goto-Anweisung, strukturierte Programmierung, nebenläufige Prozesse, Semaphoren, Deadlocks, rekursive Programmierung in Algol und Ableitung korrekter Programme.

Auszeichnungen und Ehrungen

Zu den Auszeichnungen und Ehrungen von Dijkstra gehören:

• Mitglied der Königlich Niederländischen Akademie der Künste und Wissenschaften (1971)
• Distinguished Fellow der British Computer Society (1971)
• Die Association for Computing Machinery ‚s AM Turing Award (1972)
• Harry H. Goode Memorial Award der IEEE Computer Society (1974).
• Ausländisches Ehrenmitglied der American Academy of Arts and Sciences (1975)
• Doktor der Wissenschaften Honoris Causa von der Queen's University Belfast (1976)
• Computer Pioneer Charter Empfänger der IEEE Computer Society (1982)
• ACM/ SIGCSE- Preis für herausragende Beiträge zur Informatikausbildung (1989)
• Fellow der Association for Computing Machinery (1994)
• Ehrendoktorwürde der Wirtschaftsuniversität Athen , Griechenland (2001).

Im Jahr 1969 erhielt die British Computer Society (BCS) die Genehmigung für eine Auszeichnung und ein Stipendium, Distinguished Fellow of the British Computer Society (DFBCS), die gemäß Satzung 7 ihrer königlichen Charta verliehen werden . 1971 fand die erste Wahl nach Dijkstra statt.

1990 veranstaltete das Department of Computer Science (UTCS) der University of Texas in Austin anlässlich Dijkstras 60. Geburtstag ein zweitägiges Seminar zu seinen Ehren. Referenten kamen aus den ganzen Vereinigten Staaten und Europa, und eine Gruppe von Informatikern steuerte Forschungsartikel bei, die in einem Buch bearbeitet wurden.

Im Jahr 2002 würdigte die C&C Foundation of Japan Dijkstra "für seine bahnbrechenden Beiträge zur Schaffung der wissenschaftlichen Grundlage für Computersoftware durch kreative Forschung in grundlegender Softwaretheorie, Algorithmustheorie, strukturierter Programmierung und Semaphoren". Dijkstra war noch am Leben, um die Auszeichnung zu erhalten, aber sie wurde nach seinem Tod von seiner Familie in einer Preisverleihung entgegengenommen.

Kurz vor seinem Tod im Jahr 2002 erhielt Dijkstra den ACM PODC Influential-Paper Award in Distributed Computing für seine Arbeiten zur Selbststabilisierung der Programmberechnung. Diese jährliche Auszeichnung wurde ihm zu Ehren im folgenden Jahr in Dijkstra-Preis ( Edsger W. Dijkstra Prize in Distributed Computing ) umbenannt.

Der Dijkstra Award for Outstanding Academic Achievement in Computer Science ( Loyola University Chicago , Department of Computer Science) ist nach Edsger W. Dijkstra benannt. Dieser Preis würdigt seit 2005 die akademischen Spitzenleistungen eines abgeschlossenen Informatik-Studiengangs. Die Auswahl basiert auf GPA in allen Hauptfächern und Wahl durch die Fakultät der Fakultät.

Das Institut für Informatik (UTCs) an der University of Texas in Austin Gastgeber der Eröffnungs Edsger W. Dijkstra Memorial Lecture am 12. Oktober 2010 Tony Hoare , emeritierter Professor in Oxford und Haupt Forscher bei Microsoft Research, der Sprecher für die Veranstaltung war. Diese Vortragsreihe wurde durch ein großzügiges Stipendium von Schlumberger zum Gedenken an Dijkstra ermöglicht.

Siehe auch

• Der Algorithmus von Dijkstra
• Das Problem der Speisephilosophen
• Bewachte Befehlssprache
• Prädikatstransformator-Semantik
• Kalkül der schwächsten Voraussetzung
• Semaphor
• Smoothsort
• Gehe zu Aussage, die als schädlich angesehen wird
• Über die Grausamkeit, Informatik wirklich zu lehren
• Liste der Pioniere der Informatik
• Liste wichtiger Veröffentlichungen in der Informatik
• Liste wichtiger Veröffentlichungen in der theoretischen Informatik
• Liste wichtiger Veröffentlichungen im Bereich Concurrent, Parallel und Distributed Computing

Ausgewählte Publikationen

Bücher

Ausgewählte Artikel

Verweise

Weiterlesen

• Altisen, Karine; Devismes, Stéphane; Dubois, Schwan; Petit, Franck; Raynal, Michel (2019). Einführung in verteilte selbststabilisierende Algorithmen . San Rafael, CA : Morgan & Claypool Publishers. ISBN 9781681735375.
• Apt, Krzysztof R. (2002). „Edsger Wybe Dijkstra (1930–2002): Ein Porträt eines Genies“. Formale Aspekte der Informatik . 14 (2): 92–98. arXiv : cs/0210001 . Bibcode : 2002cs.......10001A . doi : 10.1007/s001650200029 . S2CID  12482128 .
• Brinch Hansen, Per (2002). Der Ursprung der gleichzeitigen Programmierung: Von Semaphoren zu entfernten Prozeduraufrufen . Springer. ISBN 978-0-387-95401-1.
• Ben-Ari, M. (2006). Prinzipien der parallelen und verteilten Programmierung (2. Aufl.). Addison-Wesley. ISBN 978-0-321-31283-9.
• Broy, M.; Denert, Ernst, Hrsg. (2002). Software-Pioniere: Beiträge zum Software-Engineering . Springer. ISBN 978-3-540-43081-0.
• Chen, Peter P. (2002). „Von Goto-less zu strukturierter Programmierung: Das Vermächtnis von Edsger W. Dijkstra“. IEEE-Software . 19 (5): 21. doi : 10.1109/MS.2002.1032847 . S2CID  29320163 .
• Tageslicht, Edgar G. (2012). Die Anfänge der Softwareentwicklung: von Turing bis Dijkstra . Einsamer Gelehrter. ISBN 9789491386022.
• Tageslicht, Edgar G. (2011). „Dijkstras Rallying Cry for Generalization: The Advent of the Recursive Procedure, Ende der 1950er-Anfang der 1960er Jahre“. Das Computerjournal . 54 (11): 1756–72. doi : 10.1093/comjnl/bxr002 .
• Dolev, Schlomi (2000). Selbststabilisierung . MIT-Presse. ISBN 978-0-262-04178-2.
• Feijen, WHJ; Gries, David, Hrsg. (1990). Schönheit ist unser Geschäft: Ein Geburtstagsgruß an Edsger W. Dijkstra . Springer. ISBN 978-0-387-97299-2.
• Istrail, Sorin (Herbst–Winter 2008). "Geschichten über Leuchttürme: Kritik an Professor Dijkstra als harmlos " (PDF) . Leitung . vol. 17 Nr. 2. Fakultät für Informatik der Brown University. S. 10–17.
• Istrail, Sorin (Frühling–Sommer 2010). "Geschichten über Leuchttürme: Als Professor Dijkstra mich auf der Suche nach schönem Code schlug" (PDF) . Leitung . vol. 19 Nr. 1. Fakultät für Informatik der Brown University. S. 10–12.
• James, Mike (2013). „Edsger Dijkstra – Die Poesie der Programmierung“ . I-programmer.info .
• Lamport, Leslie (Juni 2015). "Turing Lecture: The Computer Science of Concurrency: The Early Years" . Komm. ACM . 58 (6): 71–76. doi : 10.1145/2771951 . S2CID  19164754 .
• Laplante, Phillip A. (1996). Tolle Arbeiten in Informatik . IEEE-Presse. ISBN 978-0-7803-1112-1.
• Laplante, Phillip A. (2008). "Great Papers in Computer Science: A Retrospective" (PDF) . Zeitschrift für wissenschaftliche und praktische Informatik . 2 (1): 31–35. CiteSeerX  10.1.1.559.2457 . Archiviert vom Original (PDF) am 5. Mai 2018.
• Lee, JAN (1991). „Frontiers of Computing: Eine Hommage an Edsger W. Dijkstra anlässlich seines 60. Geburtstags“. Ann. Hist. Komp . 13 (1): 91–96. doi : 10.1109/MAHC.1991.10000 .
• Markoff, John (2002). „Edsger Dijkstra, 72, Physiker, der die Computer-Ära prägte“ . Die New York Times .
• Milone, Lorenzo (2009). "EW Dijkstra, una vita da informatico [auf Italienisch]" (PDF) . Mondo Digital . 9 (2).
• O'Regan, Gerard (2013). Giants of Computing: Ein Kompendium ausgewählter, entscheidender Pioniere . Springer. ISBN 978-1-4471-5340-5.
• Payette, Sandy (2014). „Hopper und Dijkstra: Krise, Revolution und die Zukunft der Programmierung“. IEEE Annals of the History of Computing . 36 (4): 64–73. doi : 10.1109/MAHC.2014.54 . S2CID  9029390 .
• Schascha, Dennis; Lazere, Cathy (2. Juli 1998). Aus ihren Köpfen: Das Leben und die Entdeckungen von 15 großartigen Informatikern . Springer. ISBN 978-0-387-98269-4.

Externe Links

• "EW Dijkstra-Archiv" . Zentrum für amerikanische Geschichte, University of Texas at Austin .
• "Dijkstras Sammelruf nach Verallgemeinerung" . Eine Site, die Dijkstras Werken und Gedanken gewidmet ist und vom Computerhistoriker Edgar Graham Daylight erstellt und gepflegt wurde.