Edsger Dijkstra

From Wikipedia, the free encyclopedia

You have new messages (last change).
Edsger Wybe Dijkstra

Born May 11, 1930
Rotterdam, Netherlands
Died August 6, 2002
Nuenen, Netherlands
Field Computer Science
Institution Mathematisch Centrum
The University of Texas at Austin
Known for Dijkstra's algorithm
THE multiprogramming system
Semaphore
Notable prizes Turing Award
Association for Computing Machinery

Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ˈɛtˌsxər ˈwɛɪbə ˈdɛɪkˌstra) 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 his death in 2002. Shortly before his death, he received the ACM (Association for Computing Machinery) PODC Influential paper award in distributed computing for his paper that started the subarea of self-stabilization. This annual award was renamed the ACM Edsger W. Dijkstra award shortly after Dijkstra's death.

Contents

[edit] Life

Born in Rotterdam, Dijkstra studied theoretical physics at the University of Leiden, but he quickly realized he was more interested in programming.

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, the THE multiprogramming system, 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, 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 paper's more famous title, "Go To Statement Considered Harmful", 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. Zonneveld eventually shaved off his beard; Dijkstra kept his until his death.

He also wrote two important papers in 1968, devoted to the structure of the multiprogramming systems and to cooperating of sequential processes.

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, 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 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. He was also 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 are mainly computer science and mathematics, but also include 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[1].

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 also noted for owning only one computer (late in life) and rarely actually using them[2], in keeping with his conviction that computer science was more abstract than mere programming, expressed in a number of famous sayings such as "Computer Science is no more about computers than astronomy is about telescopes."[3]

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.

Andrzej Sapkowski, Polish fantasy writer, used Dijkstra's name for one of the main characters in the five book "Saga" about The Hexer.

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.

[edit] See also

[edit] References

[edit] Writings by E.W. Dijkstra

  1. ^ University of Texas online Texas archive: ww.cs.utexas.edu/users/EWD/
  2. ^ "Almost all articles in this series appearing after 1972 are hand-written. Having invented much of the technology of software, Dijkstra eschewed the use of computers in his own work for many decades. 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." "IN MEMORIAM EDSGER WYBE DIJKSTRA"
  3. ^ "IN MEMORIAM EDSGER WYBE DIJKSTRA"

[edit] Others about Dijkstra, eulogies

[edit] External links

Wikiquote has a collection of quotations related to:
Persondata
NAME Dijkstra, Edsger
ALTERNATIVE NAMES
SHORT DESCRIPTION Danish mathematician
DATE OF BIRTH May 11, 1930
PLACE OF BIRTH Rotterdam
DATE OF DEATH August 6, 2002
PLACE OF DEATH Nuenen, The Netherlands
v • d • e
Turing award laureates

1966: Perlis • 67: Wilkes • 68: Hamming • 69: Minsky
1970: Wilkinson • 71: McCarthy • 72: Dijkstra • 73: Bachman • 74: Knuth • 75: Newell, Simon • 76: Rabin, Scott • 77: Backus • 78: Floyd • 79: Iverson
1980: Hoare • 81: Codd • 82: Cook • 83: Thompson, Ritchie • 84: Wirth • 85: Karp • 86: Hopcroft, Tarjan • 87: Cocke • 88: Sutherland • 89: Kahan
1990: Corbató • 91: Milner • 92: Lampson • 93: Hartmanis, Stearns • 94: Feigenbaum, Reddy • 95: Blum • 96: Pnueli • 97: Engelbart • 98: Gray • 99: Brooks
2000: Yao • 01: Dahl, Nygaard • 02: Rivest, Shamir, Adleman • 03: Kay • 04: Cerf, Kahn • 05: Naur • 06: Allen

Retrieved from "http://en.wikipedia.org../../../e/d/s/Edsger_Dijkstra_26c0.html"