Edsger W. Dijkstra
From Wikipedia, the free encyclopedia
| Edsger Wybe Dijkstra | |
 |
|
| Born | May 11, 1930 Rotterdam, Netherlands |
|---|---|
| Died | August 6, 2002 (aged 72) Nuenen, Netherlands |
| Fields | Computer science |
| Institutions | Mathematisch Centrum Eindhoven University of Technology The University of Texas at Austin |
| Doctoral advisor | Adriaan van Wijngaarden |
| Doctoral students | Nico Habermann Martin Rem David Naumann Cornelis Hemerik Jan Tijmen Udding Johannes van de Snepscheut Antonetta van Gasteren |
| Known for | Dijkstra's algorithm Goto Considered Harmful[1] THE multiprogramming system Semaphore |
| Notable awards | Turing Award Association for Computing Machinery |
Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002; pronounced [ˈɛtsxər ˈwibə ˈdɛɪkstra]) was a Dutch computer scientist. He received the 1972 A. M. Turing Award for fundamental contributions in the area of programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.
Shortly before his death in 2002, he received the ACM PODC Influential Paper Award in distributed computing for his work in the subarea of self-stabilization. This annual award was renamed the Dijkstra Prize the following year, in his honour.
Contents |
[edit] Life and work
Born in Rotterdam, Dijkstra studied theoretical physics at Leiden University, but he quickly realized he was more interested in computer science. Originally employed by the Mathematisch Centrum in Amsterdam, he held a professorship at the Eindhoven University of Technology in the Netherlands, worked as a research fellow for Burroughs Corporation in the early 1970s, and later held the Schlumberger Centennial Chair in Computer Sciences at The University of Texas at Austin, in the United States. He retired in 2000.
Among his contributions to computer science is the shortest path-algorithm, also known as Dijkstra's algorithm; Reverse Polish Notation and related Shunting yard algorithm; the THE multiprogramming system; Banker's algorithm; the concept of operating system rings; and the semaphore construct for coordinating multiple processors and programs. Another concept due to Dijkstra in the field of distributed computing is that of self-stabilization – an alternative way to ensure the reliability of the system. Dijkstra's algorithm is used in SPF, Shortest Path First, which is used in the routing protocol OSPF, Open Shortest Path First.
He was also known for his low opinion of the GOTO statement in computer programming, writing a paper in 1965, and culminating in the 1968 article "A Case against the GO TO Statement" (EWD215), regarded as a major step towards the widespread deprecation of the GOTO statement and its effective replacement by structured control constructs, such as the while loop. This methodology was also called structured programming, the title of his 1972 book, coauthored with C.A.R. Hoare and Ole-Johan Dahl. The March 1968 ACM letter's famous title, "Go To Statement Considered Harmful", [1] was not the work of Dijkstra, but of Niklaus Wirth, then editor of Communications of the ACM.
Dijkstra was known to be a fan of ALGOL 60, and worked on the team that implemented the first compiler for that language. Dijkstra and Jaap Zonneveld, who collaborated on the compiler, agreed not to shave until the project was completed.
He also wrote two important papers in 1968, devoted to the structure of a multiprogramming operating system called THE, and to Co-operating Sequential Processes.
He is famed for coining the popular programming phrase "2 or more, use a for", alluding to the fact that when you find yourself processing more than one instance of a data structure, it is time to encapsulate that logic inside a loop.
From the 1970s, Dijkstra's chief interest was formal verification. The prevailing opinion at the time was that one should first write a program and then provide a mathematical proof of correctness. Dijkstra objected that the resulting proofs are long and cumbersome, and that the proof gives no insight as to how the program was developed. An alternative method is program derivation, to "develop proof and program hand in hand". One starts with a mathematical specification of what a program is supposed to do and applies mathematical transformations to the specification until it is turned into a program that can be executed. The resulting program is then known to be correct by construction. Much of Dijkstra's later work concerns ways to streamline mathematical argument. In a 2001 interview[citation needed], he stated a desire for "elegance", whereby the correct approach would be to process thoughts mentally, rather than attempt to render them until they are complete. The analogy he made was to contrast the compositional approaches of Mozart and Beethoven.
Dijkstra was one of the very early pioneers of the research on distributed computing. Some people even consider some of his papers to be those that established the field. In particular, his paper "Self-stabilizing Systems in Spite of Distributed Control" started the sub-field of self-stabilization.
Dijkstra was known for his essays on programming; he was the first to make the claim that programming is so inherently difficult and complex that programmers need to harness every trick and abstraction possible in hopes of managing the complexity of it successfully.
Dijkstra believed that computer science was more abstract than programming; he once said, "Computer Science is no more about computers than astronomy is about telescopes."
He died in Nuenen, The Netherlands on August 6, 2002 after a long struggle with cancer. The following year, the ACM (Association for Computing Machinery) PODC Influential Paper Award in distributed computing was renamed the Dijkstra Prize in his honour.
[edit] EWDs and writing by hand
Dijkstra was known for his habit of carefully composing manuscripts with his fountain pen. The manuscripts are called EWDs, since Dijkstra numbered them with EWD as prefix. Dijkstra would distribute photocopies of a new EWD among his colleagues; as many recipients photocopied and forwarded their copy, the EWDs spread throughout the international computer science community. The topics were mainly computer science and mathematics, but also included trip reports, letters, and speeches. More than 1300 EWDs have since been scanned, with a growing number also transcribed to facilitate search, and are available online at the Dijkstra archive of the University of Texas[2].
One of Dijkstra's sidelines was serving as Chairman of the Board of the fictional Mathematics Inc., a company that he imagined having commercialized the production of mathematical theorems in the same way that software companies had commercialized the production of computer programs. He invented a number of activities and challenges of Mathematics Inc. and documented them in several papers in the EWD series. The imaginary company had produced a proof of the Riemann Hypothesis but then had great difficulties collecting royalties from mathematicians who had proved results assuming the Riemann Hypothesis. The proof itself was a trade secret (EWD 475). Many of the company's proofs were rushed out the door and then much of the company's effort had to be spent on maintenance (EWD 539). A more successful effort was the Standard Proof for Pythagoras' Theorem, that replaced the more than 100 incompatible existing proofs (EWD427). Dijkstra described Mathematics Inc. as "the most exciting and most miserable business ever conceived" (EWD475). He claimed that by 1974 his fictional company was the world's leading mathematical industry with more than 75 percent of the world market (EWD443).[3]
Having invented much of the technology of software, Dijkstra eschewed the use of computers in his own work for many decades. Almost all EWDs appearing after 1972 were hand-written. When lecturing, he would write proofs in chalk on a blackboard rather than using overhead foils, let alone Powerpoint slides. Even after he succumbed to his UT colleagues’ encouragement and acquired a Macintosh computer, he used it only for e-mail and for browsing the World Wide Web.[4]
[edit] Awards and honors
Among Dijkstra's awards and honours are:[4]
- Member of the Royal Netherlands Academy of Arts and Sciences (1971)
- Distinguished Fellow of the British Computer Society (1971)
- The Association for Computing Machinery's A.M. Turing Award (1972)
- Foreign Honorary Member of the American Academy of Arts and Sciences (1975)
- Doctor of Science Honoris Causa from the Queen's University Belfast (1976)
- Computer Pioneer Charter Recipient from the IEEE Computer Society (1982)
- Honorary doctorate from the Athens University of Economics & Business, Greece (2001).
[edit] See also
- Dijkstra's algorithm
- Dining philosophers problem
- "The Cruelty of Really Teaching Computer Science"
- Shunting yard algorithm
[edit] Footnotes
- ^ a b "Go To Statement Considered Harmful", Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148.
- ^ University of Texas online EWD archive.
- ^ Dijkstra, Edsger W. (1982). Selected Writings on Computing: A Personal Perspective. Berlin: Springer-Verlag. ISBN 9780387906522.
- ^ a b University of Texas, "In Memoriam Edsger Wybe Dijkstra."
[edit] References
[edit] Writings by E.W. Dijkstra
- Dijkstra, E. W. (March 1968). "Letters to the editor: go to statement considered harmful". Communications of the ACM 11 (3): 147–148. doi:. ISSN 0001-0782. (EWD215)
- Dijkstra, E. W. (Aug 1972). "The Humble Programmer". Communications of the ACM 15 (10): 859–866. http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html. (EWD340) PDF, 1972 ACM Turing Award lecture
- Dijkstra, E. W. (May 1982). "How do we tell truths that might hurt?". SIGPLAN Notice 17 (5): 13–15. doi:. ISSN 0362-1340. http://www.cs.virginia.edu/~evans/cs655/readings/ewd498.html. (EWD498)
- From My Life (EWD1166)
- A Discipline of Programming, Prentice-Hall Series in Automatic Computation, 1976, ISBN 0-13-215871-X
- Selected Writings on Computing: A Personal Perspective, Texts and Monographs in Computer Science, Springer-Verlag, 1982, ISBN 0-387-90652-5
- A Method of Programming, E.W. Dijkstra, W.H.J. Feijen, J. Sterringa, Addison Wesley 1988, ISBN 0-201-17536-3
- O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3
- this volume includes an expanded version of the Notes on Structured Programming, including an extended example of using the structured approach to develop a backtracking algorithm to solve the 8 Queens problem.
- a pdf version of this book is available in the ACM Classic Books Series
[edit] Others about Dijkstra, eulogies
- Biography Digidome
- Edsger Wybe Dijkstra (1930–2002): A Portrait of a Genius (PDF) Obituary in Formal Aspects of Computing with a short biography
- How can we explain Edsger W. Dijkstra to those who didn't know him? by David Gries
- Dijkstra Eulogy by J Strother Moore
- In Memoriam Edsger Wybe Dijkstra by Mario Szegedy
- Photos of Edsger Dijkstra
[edit] External links
 |
Wikiquote has a collection of quotations related to: Edsger W. Dijkstra |
- Oral history interview with Edsger W. Dijkstra. Dijkstra recounts his early education and training as a theoretical physicist and as a 'programmer'. Dijkstra describes his work developing software, and his activities at several early information processing conferences. Dijkstra also discourses on the development of ALGOL 60 and the origins of computing science in Europe and America. Oral history interview 2001. Charles Babbage Institute University of Minnesota, Minneapolis.
- E. W. Dijkstra Archive
- Noorderlicht Interview Video, bandwidth options
|
|||||
|
||||||||||||||||||||
| Persondata | |
|---|---|
| NAME | Dijkstra, Edsger |
| ALTERNATIVE NAMES | |
| SHORT DESCRIPTION | Dutch mathematician |
| DATE OF BIRTH | May 11, 1930 |
| PLACE OF BIRTH | Rotterdam |
| DATE OF DEATH | August 6, 2002 |
| PLACE OF DEATH | Nuenen, The Netherlands |
