Dijkstra


Dijkstra

Edsger Dijkstra

Edsger Dijkstra

Edsger Wybe Dijkstra (prononciation: [ˈɛtsxər ˈwibə ˈdɛɪkstra][1]), né à Rotterdam le 11 mai 1930, et mort à Nuenen le 6 août 2002 est un mathématicien et informaticien néerlandais du XXe siècle.

Sommaire

Biographie

Après des études de physique théorique, il s'engage dès 1955 dans le domaine de l'informatique alors naissante, dont il est l'un des pionniers les plus éclairés. Parmi ses contributions se trouve un algorithme de calcul du plus court chemin dans les graphes, connu sous le nom d'algorithme de Dijkstra.

Enseignant à l'université technique d'Eindhoven, il commence à se faire connaître en matière de systèmes avec THE Operating system, un système construit en couches d'abstraction successives et idéal pour l'enseignement (« THE » est un jeu de mot sur l'acronyme de son université Technische Hogeschool Eindhoven, école polytechnique). Fort de l'expérience d'écriture de ce système, il formalise le concept, avant lui diffus, de sémaphore puis introduit le concept de section critique avec deux exemples devenus classiques : le problème des lecteurs et des rédacteurs et le dîner des philosophes.

Constatant les dégâts provoqués par l'usage incontrôlé de l'instruction goto en programmation, il rédige en 1968 pour les Communications of the ACM un article qu'il nomme A case against the GOTO statement (« Un procès contre l'instruction GOTO »). Voulant publier rapidement l'article sous la forme d'une lettre à l'éditeur, l'éditeur Niklaus Wirth le rebaptise Go To Statement Considered Harmful (« L'instruction Go To jugée nuisible »). Ce nouveau titre autant que le propos de l'article devient alors célèbre dans le milieu de l'informatique. Les titres de la forme X considered harmful se multiplient, jusqu'à un Dijkstra considered harmful.[2] L'instruction goto est rapidement marginalisée, et presque éliminée, par la programmation structurée (concept de Wirth et Dijkstra, présenté entre autres dans EWD 268). En programmation structurée, le goto est remplacé par des instructions comme if... then ... else ..., while ... do, repeat ... until comme elles furent introduites par Wirth dans Algol W : chacun contient une seule entrée et une seule sortie, ce qui rend enfin possible des tests systématiques exhaustifs impossibles avec le "code spaghetti". Des conditions peuvent aussi être imposées à l'entrée unique et des caractéristiques postulées à la sortie unique, ce qui ouvre la porte à des outils ajoutés à la syntaxe, comme assert (voir Logique de Hoare) et plus tard à la programmation par contrat du langage Eiffel.

Dijkstra avait joué un rôle important dans le développement du langage Algol à la fin des années 1950 et développé ensuite « la science et l'art des langages de programmation », contribuant grandement à notre compréhension de leur structure, de leur représentation et de leur implémentation »[3]. C'est aussi un adepte du bel algorithme, y compris pour des sujets difficiles à traiter en programmation structurée comme les perles de Dijkstra (disposer des perles de trois couleurs sur un fil de façon à ce qu'il n'y ait jamais deux séquences adjacentes identiques).

Le discours qu'il prononce en 1972 lorsqu'il reçoit le prix Turing, The Humble Programmer[4], est resté célèbre, lui aussi. Il s'agit également d'un exercice d'autodérision, le professeur Dijkstra s'étant toujours montré très conscient de la valeur de ses travaux

Anecdotes

  • Dijkstra avait une très belle écriture manuscrite et a toujours refusé d'utiliser un traitement de texte, préférant la lettre manuscrite photocopiée. Luca Cardelli a créé une fonte « Dijkstra » en son honneur, qui imite son écriture régulière. Dijkstra référençait toutes ses lettres par EWD suivi d'un nombre, la dernière étant la lettre EWD 1318.

Aphorismes

Dijkstra, connu pour son caractère difficile et son intransigeance, était réputé pour ses aphorismes qui résumaient sa vision de la science informatique.

  • « Tester un programme peut démontrer la présence de bugs, jamais leur absence ».
  • « Se demander si un ordinateur peut penser est aussi intéressant que de se demander si un sous-marin peut nager. »
  • « La programmation par objets est une idée exceptionnellement mauvaise qui ne pouvait naître qu'en Californie. »
  • « Les progrès ne seront possibles que si nous pouvons réfléchir sur les programmes sans les imaginer comme des morceaux de code exécutable. »
  • « Autrefois les physiciens répétaient les expériences de leurs collègues pour se rassurer. Aujourd'hui ils adhèrent à FORTRAN et s'échangent leurs programmes, bugs inclus. »
  • « À propos des langages : il est impossible de tailler un crayon avec une hache émoussée. Il est vain d'essayer, à la place, de le faire avec dix haches émoussées. »
  • « L'informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. »
  • « Le plus court chemin d'un graphe n'est jamais celui que l'on croit, il peut surgir de nulle part, et la plupart du temps il n'existe pas. »

Voir aussi

Articles connexes

Références

  1. Écouter Edsger Dijkstra sur forovo.com
  2. Phillip Laplante, Great Papers in Computer Science, West Pub.Co., U.S., 14 février 1996, (ISBN 0-314-06365-X), p. 420
  3. citation de l'ACM, Association for Computer Machinery
  4. Edsger Wybe Dijkstra, intitulé The Humble Programmer, lire en ligne la traduction française

Bibliographie

  • Krzysztof Apt : Edsger Wybe Dijkstra (1930-2002): A Portrait of a Genius in Formal Aspects of Computing(2002) 14:92-08 [pdf] [1]

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Edsger Dijkstra ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Dijkstra de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Dijkstra — (pronounced [ˈdɛikstrɑ]) is a Dutch family name that may refer to: Edsger W. Dijkstra (1930–2002), computer scientist Dijkstra s algorithm, conceived by Edsger Dijkstra is a graph search algorithm that solves the single source shortest path… …   Wikipedia

  • Dijkstra — ist der Familienname folgender Personen: Edsger Wybe Dijkstra (1930–2002), niederländischer Informatiker Jorrit Dijkstra (* 1966), niederländischer Jazz Saxophonist Peter Dijkstra (* 1978), niederländischer Dirigent Rineke Dijkstra (* 1959),… …   Deutsch Wikipedia

  • Dijkstra — Dijkstra, Waling, fruchtbarer friesischer Schriftsteller, geb. 14. Aug. 1821, lebt als Buchhändler in Holwerd, veröffentlichte seit 1848 eine große Zahl von Gedichtsammlungen, Erzählungen und Dramen, namentlich Lustspielen, in friesischer Mundart …   Meyers Großes Konversations-Lexikon

  • Dijkstra — (spr. deik ), Waling, fries. Dichter, geb. 14. Aug. 1821 zu Vrouwen Parochie, lebt als Buchhändler in Holwerd; veröffentlichte zahlreiche Gedichte, Erzählungen, Dramen und Übersetzungen, ferner »Uit Friesland s volksleven« (1892 fg.) …   Kleines Konversations-Lexikon

  • Dijkstra —   [niederländisch dɛjkstra, friesisch dikstra], Waling, westfriesischer Schriftsteller, * Vrouwen Parochie (Provinz Friesland) 14. 8. 1821, ✝ Holwerd (Provinz Friesland) 15. 1. 1914; war u. a. Buchhändler sowie Redakteur friesischsprachiger… …   Universal-Lexikon

  • Dijkstra — …   Википедия

  • Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Dijkstra Prize — The Edsger W. Dijkstra Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a …   Wikipedia

  • Dijkstra-Algorithmus — Animation des Dijkstra Algorithmus Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er… …   Deutsch Wikipedia

  • Dijkstra–Scholten algorithm — The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and C. S. Scholten) is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980. First, let us consider the case of …   Wikipedia