Edsger Dijkstra
Dutch computer scientist (1930-2002). He is most widely known as the inventor of "Dijkstra's algorithm" for finding shortest paths, but his achievements go well beyond it: he advocated structured programming, devised the semaphore as a synchronization mechanism for concurrent processes, and established the idea of proving a program's correctness mathematically, leaving a broad influence on the foundations of computer science. He received the Turing Award in 1972. He recast programming from "something made to work by debugging" into "something that should be constructed correctly from the start", and he is also known for his sharp, categorical prose.
Life
He was born on May 11, 1930, in Rotterdam, the Netherlands. He grew up in a household where his father was a chemist and his mother a mathematician, studied mathematics and theoretical physics at Leiden University, and then obtained his doctorate at the University of Amsterdam. In March 1952 he took a job as a programmer at the Mathematical Centre (Mathematisch Centrum) in Amsterdam, where he stayed until 1962. Programming was not yet established as a profession at the time, and Dijkstra is said to be the first programmer in the Netherlands.
From November 1959 to August 1960, together with Jaap A. Zonneveld, he implemented the world's first ALGOL 60 compiler, for the Electrologica X1. He then went to the Eindhoven University of Technology (1963-1973) and was a research fellow at the Burroughs Corporation in the United States (1973-1984), before holding the Schlumberger Centennial Chair at the University of Texas at Austin from 1984 and retiring as professor emeritus in 1999※1. He died on August 6, 2002, in Nuenen, the Netherlands.
Dijkstra's algorithm
An algorithm for finding the shortest path between two points on a graph. It is a representative example of a greedy method: starting from the source, it expands the set of settled vertices one at a time, at each step choosing the unsettled vertex with the smallest distance and settling it. It was devised in 1956 and published as a paper in 1959. It remains in wide practical use today, in car navigation route search, network routing, flight planning and more.
The story of its conception is itself well known: Dijkstra himself related that he thought of it in about twenty minutes on a café terrace in Amsterdam, while out shopping with his fiancée, Maria Debets.
Structured programming and concurrency
In March 1968, in a letter published in Communications of the ACM under the title "Go To Statement Considered Harmful", he criticized the overuse of the goto statement for making a program's structure impossible to follow, and the letter settled the spread of structured programming. The polemical title was not Dijkstra's own: the original title was "A Case Against the Goto Statement", and the editor Niklaus Wirth, who had decided to treat it as a letter to speed up publication, replaced it. Thereafter "X considered harmful" became a stock phrase in computer science.
He also left many foundational concepts in the field of concurrency. He devised the semaphore (with P and V operations) for controlling situations in which multiple processes compete for resources, and gave formulations that still appear in textbooks: mutual exclusion, deadlock (which he himself called the deadly embrace), the banker's algorithm and the "dining philosophers problem". The hierarchically structured operating system "THE multiprogramming system" (1968), self-stabilization in distributed systems (1974), and guarded commands for deriving program correctness from weakest preconditions (1975) are also his work.
The EWDs and the man
Dijkstra numbered his manuscripts in sequence after the prefix "EWD" and kept circulating them by photocopying the handwritten pages, written with a Montblanc fountain pen, and mailing them to acquaintances. The EWDs, which exceed 1,300 over his lifetime, include not only technical essays but book reviews, travel reports and scathing criticism of education and the industry, and they are now made public in the archive at the University of Texas at Austin as a record of his thinking before it reached formal papers.
He left many categorical aphorisms, such as "testing can show the presence of bugs, but never their absence", and he criticized without reserve the languages and methods that were gaining ground at the time. His position that one should derive the proof of correctness and the program together, rather than write a program and then fix it until it works, is still debated, but it became the starting point for the idea of treating software as a mathematical object.
To verify
- The year of his doctorate at the University of Amsterdam and details of his dissertation
- The aphorism "computer science is no more about computers than astronomy is about telescopes" is widely quoted as Dijkstra's, but its source in primary material could not be confirmed
References
- Edsger W. Dijkstra - Wikipedia (English)
- Edsger Dijkstra | Biography, Algorithm, & Facts | Britannica
- Edsger W. Dijkstra - A.M. Turing Award Laureate | ACM
- E.W. Dijkstra Archive: Obituary | UT Austin Computer Science
- Edsger W. Dijkstra: Brilliant, colourful, and opinionated | CWI
- The Man Who Carried Computer Science on His Shoulders | Krzysztof Apt, Inference
- The Dijkstra-Zonneveld ALGOL 60 compiler for the Electrologica X1 | CWI
- Letters to the editor: go to statement considered harmful | Communications of the ACM
- Considered harmful - Wikipedia
- Computer Pioneers - Edsger W. Dijkstra | IEEE Computer Society
- Mentioned in
- none
- Similar