Edsger Wybe Dijkstra


Quick Info

Born
11 May 1930
Rotterdam, The Netherlands
Died
6 August 2002
Nuenen, The Netherlands

Summary
Edsger Wybe Dijkstra was a Dutch mathematician and computer scientist best known for his shortest-path algorithm in graph theory.

Biography

Edsger Dijkstra's parents were Douwe Wybe Dijkstra and Brechtje Cornelia Kluijver (or Kluyver); he was the third of their four children. His father taught chemistry at the high school in Rotterdam while his mother was trained as a mathematician although she never had a formal position. Dijkstra wrote later of his mother's mathematical influence on him [9]:-
... she had a great agility in manipulating formulae and a wonderful gift for finding very elegant solutions.
He attended High School in Rotterdam and in his final years at school he decided he wanted to study law. His ambition was to represent the Netherlands at the United Nations and felt that a law degree was the first step towards this. He took his final school examinations in 1948, scoring the highest possible marks in mathematics, physics, chemistry, and biology. At this point his parents and his teachers all tried to persuade him to follow a career in science, given his outstanding performance in science subjects. He then decided to study theoretical physics and as a first step towards this he went to the University of Leyden to take courses in mathematics and physics. His intention was, after getting a good grounding in these topics, he would move towards theoretical physics.

In 1951 Dijkstra's father saw an advertisement for a three-week course in computer programming to be given at the University of Cambridge in England in September of that year. Feeling that being able to programme a computer was a good skill for a theoretical physicist to have so he registered for the course [5]:-
It was a frightening experience: it was the first time that I left the Netherlands, the first time I ever had to understand people speaking English and immediately I was all by myself, trying to follow a course on a totally new topic. But I liked it very much.
Aad van Wijngaarden, who was the director of the Computation Department of the Mathematical Centre in Amsterdam, had taken the same course in Cambridge in the previous year and when he learnt that Dijkstra had completed it, he offered him a position as a programmer of the Mathematical Centre. Dijkstra accepted the position from March 1952 but it only as a part-time position for he was still registered as a student of theoretical physics at the University of Leyden. He said [5]:-
... in '55 after three years of programming, while I was still a student, I concluded that the intellectual challenge of programming was greater than the intellectual challenge of theoretical physics, and as a result I chose programming ... I spoke with van Wijngaarden ..., and explained my dilemma that I had to take leave from science if I became a programmer. ... he said he agreed that there was no such thing as a clear scientific component in computer programming, but that I might very well be one of the people called to make it a science.
Having taken the decision, Dijkstra completed his studies in theoretical physics at the university, graduating in 1956. Also in 1956 the Mathematical Centre competed building a new computer and wanted to give a public demonstration [5]:-
... for a demonstration for non-computing people you have to have a problem statement that non-mathematicians can understand, even they have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced roadmap of the Netherlands, on which I had selected, 64 cities (so that in the coding, 6 bits would suffice to identify a city).
He published this shortest distance algorithm, together with his very efficient algorithm for the shortest spanning tree, were published in the two page paper A Note on Two Problems in Connexion with Graphs (1959). Also in 1959 he was awarded his Ph.D. from the University of Amsterdam for his thesis Communication with an Automatic Computer.

In 1957 he had married Maria C Debets; they had two sons and a daughter. However, he had a problem at his wedding for the Justice of the Peace would not accept 'programmer' as profession for the records, so he had to give 'theoretical physicist' on the form.

The computer language ALGOL-60 was designed by an international team which began work in December 1958. Dijkstra, who was a member of the team, made several major contributions: due to him was the explicit introduction of recursion and in handling recursion he introduced the notion of a 'stack', a word due to Dijkstra which is now totally standard terminology. Dijkstra, together with one of his colleagues at the Mathematical Centre, wrote the first compiler for ALGOL-60 which was completed by August 1960. Dijkstra, in retrospect, regarded ALGOL-60 [5]:-
... as the beginning of computing science; if we wish to mark a discontinuity in the way in which we thought about computing, then that is the emergence of ALGOL 60. ... it has made, for instance, the topic academically respectable.
In 1962 Dijkstra was appointed Professor of Mathematics at the Eindhoven University of Technology. At this time Eindhoven had no Computer Science Department, nor of course did other universities. He built a team of computer scientist within the Mathematics department which he managed to do despite reservations by some colleagues. It was at this time that he developed the 'THE' operating system. It was named after Technische Hogeschool te Eindhoven, the name by which the Eindhoven University of Technology was known at this time. Many features of this operating system have become standard features in all future operating systems.

In 1972 Dijkstra won the ACM Turing Award which is considered the most prestigious award in Computer Science. In accepting the award he gave the address The humble programmer which contains a remarkable collection of thoughts on the future of the subject which now, with the advantage of hindsight, we can now see were absolutely correct. In August 1973 Dijkstra joined Burroughs Corporation as a Research Fellow and was made Professor Extraordinarius at Eindhoven [9]:-
His duties [at Burroughs] consisted of visiting some of the company's research centers a few times a year and carrying on his own research, which he did in the smallest Burroughs research facility, namely, his study on the second floor of his house in Nuenen. He was already very famous by that time, and he received a large number of invitations to lecture throughout the world. He used these visits to interact with other computer scientists, mentor younger scientists, and sharpen his skills as an English speaker.
Dijkstra visited the Burroughs Research Center in Austin, Texas, from the late 1970s and while on these visits he came to know well the Computer Science Department at the University of Texas. In 1984 he was offered the Schlumberger Centennial Chair in Computer Science at Austin and happily accepted. He remained at Austin until he retired in 1999.

Let us now look at some of the books which Dijkstra published. First we look at Structured programming, a book which contains three monographs, the one written by Dijkstra being Notes on structured programming (1973). C A Ellis and James Reid write in a review of the book:-
This book is based upon and supports the premise that programming is an intellectual activity requiring a high level of knowledge and creativity. This attitude is in contrast to that of many current practitioners.
Of the monograph by Dijkstra they write:-
Written in the form of letters to himself, Dijkstra's 'Notes on structured programming' make eloquent and forceful arguments for structured programming.
The book by Dijkstra A discipline of programming (1976) contains a Preface by C A R Hoare who writes:-
The book expounds, in its author's usual cultured style, his radical new insights into the nature of computer programming. From these insights, he had developed a new range of programming methods and notational tools, which are displayed and tested in a host of elegant and efficient examples. This will surely be recognized as one of the outstanding achievements in the development of the intellectual discipline of computer programming.
H Kilov writes in a review:-
You look at this latest Dijkstra book with great interest. You know about his enormous influence on programming, and therefore you are very interested to see a monograph (or may I call it a textbook?) presenting general programming concepts. You are not disappointed in your expectations.
In 1982 Selected writings on computing: a personal perspective by Dijkstra was published which collected together 66 of his papers written between 1968 and 1979, most of which had not previously been published. A joint work with Carel S Scholten, Predicate calculus and program semantics, was published in 1990. John C Mitchell writes:-
As stated clearly in the introduction, this book has two main concerns. One is programming language semantics via the well-known method of predicate transformers. The second is a particular formal style of presentation and proof development.
Van Vlissingen's personal reflection [11] contains the following which says much about Dijkstra character:-
Dijkstra's life in the deeper sense was spent in the pursuit of making people think. Making people think through a problem before they put pen to paper. He was popular, but his students sometimes disliked him as much as they - grudgingly one would think - respected him, because he insisted on handwritten papers and would not accept output from a word processor. His reasoning: by the number of corrections he could see if the person was thinking before they wrote, something he considered an essential skill in programming. So he lived what he taught, and made his students do the same.
Finally let us look at some of the many honours which have been given to Dijkstra in recognition to his outstanding contributions. We have mentioned above the ACM Turing Award made in 1972. Part of the citation reads:-
The precious gift that this Turing Award acknowledges is Dijkstra's style: his approach to programming as a high, intellectual challenge; his eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; and his illuminating perception of problems at the foundations of program design.
Other awards and honours to Dijkstra include his election to the Royal Netherlands Academy of Arts and Sciences (1971); elected Distinguished Fellow of the British Computer Society (1971), received the AFIPS Harry Goode Memorial Award (1974), made a Foreign Honorary member of the American Academy of Arts and Sciences (1975); awarded an honorary Doctorate of Science by Queen's University of Belfast (1976); given the Computer Pioneer Award from the IEEE Computer Society (1982); given the ACM/SIGCSE Award for outstanding contributions to computer science education (1989); elected an ACM Fellow(1994), awarded an honorary doctorate by Athens University, Greece (2001); given the ACM Influential Paper Award for his paper Self-stabilizing systems in spite of distributed control (2002). His final award was in 2002 from the C&C Foundation of Japan:-
... for his pioneering contributions to the establishment of the scientific basis for computer software through creative research in basic software theory, algorithm theory, structured programming, and semaphores.


References (show)

  1. F L Bauer and M Broy, Edsger W Dijkstra - Acta Informatica and Marktoberdorf, Acta Inform. 39 (3) (2003), 141-142.
  2. Edsger Wybe Dijkstra : 11 May 1930 - 6 August 2002, UT Computer Sciences Department's Obituary http://www.cs.utexas.edu/users/EWD/CSobit.html
  3. E W Dijkstra, EWD1166: from my life. People & ideas in theoretical computer science (Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, Singapore, 1999), 86-92.
  4. E W Dijkstra, The humble programmer, Communications of the ACM 15 10 (1972), 859-866.
  5. P L Frana, Oral history interview with Edsger W Dijkstra, Charles Babbage Institute, University of Minnesota, Minneapolis http://www.cbi.umn.edu/oh/display.phtml?id=320
  6. A Orlowski, Edsger Dijkstra : RIP, The Register (8th August 2002) (http://www.theregister.co.uk/2002/08/08/edsger_dijkstra_rip/)
  7. A van den Brandhof, Edsger Wybe Dijkstra (1930-2002), The Biographical Dictionary of Dutch Mathematicians http://www.bwnw.nl/index.html
  8. J van Lint, Levensbericht Edsger Wybe Dijkstra, Jaarboek Koninklijke Akademie van Wetenschappen (2004), 32-36.
  9. J Misra and H Richards, Memorial Resolution : Edsger Wybe Dijkstra (1930-2002), The University of Texas at Austin.
  10. R F van Vlissingen, Interview Prof Dr Edsger W Dijkstra, Austin, 04-03-1985 http://www.cs.utexas.edu/users/EWD/misc/vanVlissingenInterview.html
  11. R F van Vlissingen, EWD : A Personal Reflection : Dijkstra's sense of what computer science and programming are and what they aren't http://digitalundivide.blogspot.com/2005/12/ewd-personal-reflection.html

Additional Resources (show)


Written by J J O'Connor and E F Robertson
Last Update July 2008