Edsger Dijkstra, 1930 - 2002

http://www.nytimes.com/2002/08/10/obituaries/10DIJK.html

http://www.cs.utexas.edu/users/UTCS/notices/dijkstra/ewdobit.html


Edsger Dijkstra, 72, Physicist Who Shaped Computer Era, Dies
By JOHN MARKOFF


Edsger Wybe Dijkstra, whose contributions to the mathematical logic that
underlies computer programs and operating systems make him one of the
intellectual giants of the field, died on Monday at his home in Nuenen, the
Netherlands. He was 72.

The cause of death was cancer, said officials at the University of Texas,
where Dr. Dijkstra held the Schlumberger centennial chair in computer
sciences from 1984 to 1999, when he retired.

Dr. Dijkstra is best known for his shortest-path algorithm, a method for
finding the most direct route on a graph or map, and for his work as the
co-designer of the first version of Algol 60, a programming language that
represented one of the first compiler programs that translates human
instructions.

The shortest-path algorithm, which is now widely used in global positioning
systems and travel planning, came to him one morning in 1956 as he sat
sipping coffee on the terrace of an Amsterdam cafe.

It took him three years to publish the method, which is now known simply as
Dijkstra's algorithm. At the time, he said, algorithms were hardly
considered a scientific topic.

Of even greater importance was his solution to what he originally called the
dining quintuple problem, but which later became known as the dining
philosophers' problem.

He conceived of the problem faced by five philosophers sitting around a
table, each with a bowl of rice and a single chopstick. Because eating
requires two chopsticks, the challenge was to find an equitable method that
would permit all of those at the table to eat without having anyone starve
or having the entire table face deadlock. Dijkstra's original solution
ensured that each diner took turns using a pair of chopsticks.

The problem has applicability to both computer operating systems and to
network design.

Several years after Dr. Dijkstra solved the problem, he was surprised to
learn that the Massachusetts Institute of Technology designers of the
pioneering Multics operating system had not grappled successfully with the
issue of deadlock. The consequence was that on occasion their system would
abruptly halt.

"You can hardly blame M.I.T. for not taking notice of an obscure computer
scientist in a small town in the Netherlands," he was quoted as saying in
"Out Of Their Minds: The Lives and Discoveries of 15 Great Computer
Scientists."

Dr. Dijkstra, an advocate of an approach known as structured programming,
wrote a short research note in the March 1968 edition of the journal
Communications of the ACM that became legendary. Titled "The GO TO
Considered Harmful," it argued against the complexity of a feature in
programming languages like Fortran and Basic that permitted programmers to
write convoluted programs that jump around haphazardly.

A theoretical physicist by training, early in his career he observed that
many problems required extensive calculation and so in the early 1950's he
taught himself how to program.

In March 1952 he took a part-time job at the Mathematical Center in
Amsterdam, immersing himself in the challenges of instructing the primitive
computers of the era.

When he married in 1957, the Dutch marriage rites required that he state his
profession and he attempted to say he was a programmer. The municipal
authorities in Amsterdam did not accept his answer on the ground that there
was no such profession. As a result, his marriage certificate described his
profession as "theoretical physicist."

He was born May 11, 1930, in Rotterdam, the Netherlands. His father was a
chemist and his mother was a mathematician. In 1942, at 12, Dr. Dijkstra
entered an elite high school where he studied classical Greek and Latin,
French, German, English, biology, mathematics, physics and chemistry. During
the German occupation his parents sent him away for a brief period to the
countryside. He earned degrees in mathematics and theoretical physics from
the University of Leyden and a Ph.D. in computing science from the
University of Amsterdam.

He worked as a programmer at the Mathematical Center from 1952 to 1962,
taught mathematics at Eindhoven University of Technology from 1962 to 1984
and was a research fellow at the Burroughs Corporation from 1973 to 1984.

Dr. Dijkstra was the recipient of many awards, notably the Association for
Computing Machinery's prestigious Turing Award in 1972.

He is survived by his wife of more than 40 years, Maria C. Debets Dijkstra,
who is known as Ria; three children, Marcus, Femke and the computer
scientist Rutger M. Dijkstra; and by two grandchildren.

Throughout Dr. Dijkstra's career, his work was characterized by elegance and
economy. His love affair with simplicity came at an early age and under his
mother's guidance. He once said he had asked his mother whether mathematics
was a difficult topic. She replied that he must learn all the formulas and
that furthermore if he required more than five lines to prove something, he
was on the wrong track.