Edsger W. Dijkstra

Edsger DijkstraDijkstraE. W. DijkstraE.W. DijkstraEdsger Wybe DijkstraDijkstra, E. W.Dijkstra, EdsgerDijkstra, Edsger W.Edsgar DijkstraEWDs
Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002) was a Dutch systems scientist, programmer, software engineer, science essayist, and pioneer in computing science.wikipedia
319 Related Articles

Structured programming

structuredProgram structurestructured program
He coined the phrase "structured programming" and during the 1970s this became the new programming orthodoxy.
Contributing factors to its popularity and widespread acceptance, at first in academia and later among practitioners, include the discovery of what is now known as the structured program theorem in 1966, and the publication of the influential "Go To Statement Considered Harmful" open letter in 1968 by Dutch computer scientist Edsger W. Dijkstra, who coined the term "structured programming".

List of pioneers in computer science

computer pioneerfather of the computerList of prominent pioneers in computer science
Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002) was a Dutch systems scientist, programmer, software engineer, science essayist, and pioneer in computing science.

Concurrency (computer science)

concurrencyconcurrentconcurrently
His foundational work on concurrency, semaphores, mutual exclusion, deadlock (deadly embrace), finding shortest paths in graphs, fault-tolerance, self-stabilization, among many other contributions comprises many of the pillars upon which the field of distributed computing is built.
As Leslie Lamport (2015) notes, "While concurrent program execution had been considered for years, the computer science of concurrency began with Edsger Dijkstra's seminal 1965 paper that introduced the mutual exclusion problem. ... The ensuing decades have seen a huge growth of interest in concurrency—particularly in distributed systems. Looking back at the origins of the field, what stands out is the fundamental role played by Edsger Dijkstra".

Mutual exclusion

mutexesmutexmutex locks
The academic study of concurrent computing started in the 1960s, with Dijkstra (1965) credited with being the first paper in this field, identifying and solving the mutual exclusion problem. In 1962 or 1963 Dijkstra proposed the semaphore mechanism for mutual exclusion algorithm for n processes (a generalization of Dekker's algorithm), which was probably the first published concurrent algorithm and which introduced a new area of algorithmic research.
The requirement of mutual exclusion was first identified and solved by Edsger W. Dijkstra in his seminal 1965 paper "Solution of a problem in concurrent programming control", which is credited as the first topic in the study of concurrent algorithms.

Software crisis

state of crisis
In the late 1960s, computer programming was in a state of crisis.
Edsger Dijkstra's 1972 ACM Turing Award Lecture makes reference to this same problem:

THE multiprogramming system

THETHE operating system
In the late 1960s he built the THE operating system (named for the university, then known as Technische Hogeschool Eindhoven), which has influenced the designs of subsequent operating systems through its use of software based paged virtual memory.
The THE multiprogramming system or THE OS was a computer operating system designed by a team led by Edsger W. Dijkstra, described in monographs in 1965-66 and published in 1968.

Centrum Wiskunde & Informatica

CWIMathematisch CentrumMathematical Centre
A theoretical physicist by training, he worked as a programmer at the Mathematisch Centrum (Amsterdam) from 1952 to 1962. Dijkstra stumbled on his career quite by accident, and through his supervisor, Professor A. Haantjes, he met Adriaan van Wijngaarden, the director of the Computation Department at the Mathematical Center in Amsterdam, who offered Dijkstra a job; he officially became the Netherlands' first "programmer" in March 1952. In 1961 Dijkstra first described the shunting-yard algorithm, a method for parsing mathematical expressions specified in infix notation, in the Mathematisch Centrum report. From 1952 until 1962 Dijkstra worked at the Mathematisch Centrum in Amsterdam, where he worked closely with Bram Jan Loopstra and Carel S. Scholten, who had been hired to build a computer.
Edsger Dijkstra did most of his early influential work on algorithms and formal methods at CWI.

Semaphore (programming)

semaphoressemaphorecounting semaphore
His foundational work on concurrency, semaphores, mutual exclusion, deadlock (deadly embrace), finding shortest paths in graphs, fault-tolerance, self-stabilization, among many other contributions comprises many of the pillars upon which the field of distributed computing is built. In 1962 or 1963 Dijkstra proposed the semaphore mechanism for mutual exclusion algorithm for n processes (a generalization of Dekker's algorithm), which was probably the first published concurrent algorithm and which introduced a new area of algorithmic research.
The semaphore concept was invented by Dutch computer scientist Edsger Dijkstra in 1962 or 1963, when Dijkstra and his team were developing an operating system for the Electrologica X8.

Dijkstra's algorithm

Dijkstra algorithmDijkstraShortest Path First
In 1959 Dijkstra published in a 3-page article 'A note on two problems in connexion with graphs' the algorithm to find the shortest path in a graph between any two given nodes, now called Dijkstra's algorithm.
It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Self-stabilization

self-stabilisationself-stabilizingself-stabilizing algorithm
His foundational work on concurrency, semaphores, mutual exclusion, deadlock (deadly embrace), finding shortest paths in graphs, fault-tolerance, self-stabilization, among many other contributions comprises many of the pillars upon which the field of distributed computing is built.
Many years after the seminal paper of Edsger Dijkstra in 1974, this concept remains important as it presents an important foundation for self-managing computer systems and fault-tolerant systems.

Harlan Mills

Harlan D. Mills AwardH.D. MillsHarlan B. Mills
In Harlan Mills's words (1986), "programming [before the 1970s] was regarded as a private, puzzle-solving activity of writing computer instructions to work as a program".
These included automata theory, the structured programming theory of Edsger Dijkstra, Robert W. Floyd, and others, and Markov chain-driven software testing.

A* search algorithm

A*A* algorithmA* search
One of the most used heuristic algorithms is the A* search algorithm (first described by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute in 1968), the main goal is to reduce the run time by reducing the search space.
It can be seen as an extension of Edsger Dijkstra's 1959 algorithm.

ALGOL 60

ALGOLALGOL 60 programming languageAlgol 60 Report
At the Mathematical Center, Dijkstra and his colleague developed a compiler for the programming language ALGOL 60; it had a profound influence on his later thinking on programming as a scientific activity.

Reverse Polish notation

RPNpostfix notationpostfix
It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST).
The reverse Polish scheme was proposed in 1954 by Arthur Burks, Don Warren, and Jesse Wright and was independently reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s to reduce computer memory access and utilize the stack to evaluate expressions.

Dijkstra–Scholten algorithm

Dijkstra-Scholten algorithm
In the early 1980s Dijkstra and Carel S. Scholten proposed the Dijkstra–Scholten algorithm for detecting termination in distributed systems.
The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and Carel S. Scholten) is an algorithm for detecting termination in a distributed system.

Adriaan van Wijngaarden

Van Wijngaarden AwardAad van WijngaardenAad van Wijngarden
Dijkstra stumbled on his career quite by accident, and through his supervisor, Professor A. Haantjes, he met Adriaan van Wijngaarden, the director of the Computation Department at the Mathematical Center in Amsterdam, who offered Dijkstra a job; he officially became the Netherlands' first "programmer" in March 1952.
In that same year, Van Wijngaarden hired Edsger Dijkstra, and they worked on software for the ARRA.

Dekker's algorithm

Dekker
In 1962 or 1963 Dijkstra proposed the semaphore mechanism for mutual exclusion algorithm for n processes (a generalization of Dekker's algorithm), which was probably the first published concurrent algorithm and which introduced a new area of algorithmic research.
The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions and his manuscript on cooperating sequential processes.

Shunting-yard algorithm

Shunting yard algorithmshunting-yard
In 1961 Dijkstra first described the shunting-yard algorithm, a method for parsing mathematical expressions specified in infix notation, in the Mathematisch Centrum report.
The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard.

Software engineer

computer science engineerConsulting software engineerEngineer
Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002) was a Dutch systems scientist, programmer, software engineer, science essayist, and pioneer in computing science.
In 1978, computer scientist E. W. Dijkstra wrote in a paper that the coining of the term software engineer was not useful since it was an inappropriate analogy: "The existence of the mere term has been the base of a number of extremely shallow—and false—analogies, which just confuse the issue... Computers are such exceptional gadgets that there is good reason to assume that most analogies with other disciplines are too shallow to be of any positive value, are even so shallow that they are only confusing."

Carel S. Scholten

C.S. ScholtenCarel Scholten
In the early 1980s Dijkstra and Carel S. Scholten proposed the Dijkstra–Scholten algorithm for detecting termination in distributed systems. From 1952 until 1962 Dijkstra worked at the Mathematisch Centrum in Amsterdam, where he worked closely with Bram Jan Loopstra and Carel S. Scholten, who had been hired to build a computer.
In 1954 work started on the ARMAC, which he built together with Loopstra and Edsger Dijkstra, who was responsible for the software and collaborated with Scholten for more than 30 years.

Operator-precedence parser

Operator Precedence Parseroperator precedenceoperator-precedence parsing
The shunting-yard algorithm is commonly used to implement operator-precedence parsers.
Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator precedence parsers.

Prim's algorithm

PrimDJP algorithmJarnik's algorithm
As a solution, he re-discovered the algorithm known as Prim's minimal spanning tree algorithm.
The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959.

Smoothsort

Leonardo Heap
In 1981 Dijkstra developed smoothsort, a comparison-based sorting algorithm and a variation of heapsort.
A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981.

Banker's algorithm

He also identified the deadlock problem and proposed the banker's algorithm that prevents deadlock.
The Banker algorithm, sometimes referred to as the detection algorithm, is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

Goto

GO TOGo To Statement Considered Harmfulcomputed goto
While Dijkstra had programmed extensively in machine code in the 1950s, he came to the conclusion that in high-level languages frequent use of the GOTO statement was usually symptomatic of poor structure.
At the pre-ALGOL meeting held in 1959 Heinz Zemanek explicitly threw doubt on the necessity for GOTO statements; at the time no one paid attention to his remark, including Edsger W. Dijkstra, who later became the iconic opponent of GOTO.