Edsger Dijkstra

Edsger Dijkstra

Biografia
Naixement	(nl) Edsger Wybe Dijkstra 11 maig 1930 Rotterdam (Països Baixos)
Mort	6 agost 2002 (72 anys) Nuenen (Països Baixos)
Causa de mort	Causes naturals  (Càncer colorectal )
Dades personals
Formació	Universitat d'Amsterdam - ciències de la computació (1956–1959) Universitat de Cambridge (1951–1951) Universitat de Leiden - física, matemàtiques (1948–1956) Gymnasium Erasmianum (–1948)
Tesi acadèmica	Communication with an Automatic Computer  (1959 )
Director de tesi	Adriaan van Wijngaarden
Es coneix per	L'Algorisme de Dijkstra Oposició a la utilització del GOTO El Sistema Operatiu THE Semàfor (Informàtica)
Activitat
Camp de treball	Ciència computacional
Ocupació	matemàtic, enginyer, professor d'universitat, informàtic, físic, científic
Ocupador	Universitat de Texas a Austin (1984–1999) Burroughs Corporation (1973–1984) Universitat Radboud de Nimega, Professor extraordinari (1971–1972) Universitat Tècnica d'Eindhoven. Facultat de Matemàtiques i Ciències de la computació (1962–1984) Centre de Matemàtiques i Informàtica (1952–1962)
Membre de	Reial Acadèmia d'Arts i Ciències dels Països Baixos Acadèmia Americana de les Arts i les Ciències Association for Computing Machinery
Obra
Obres destacables Algorisme de Dijkstra Algorisme smoothsort Algorisme shunting-yard Algorisme del banquer (1968) Go To Statement Considered Harmful (1972) The humble programmer
Estudiant doctoral	Nico Habermann, Martin Rem, David Naumann, Jan L.A. van de Snepscheut, Antonetta van Gasteren, Jan Udding i Cornelis Hemerik
Família
Cònjuge	Maria C. Debets
Premis (2002)  Premi Dijkstra (2002)  Premi C&C (1994)  membre de l'Association for Computing Machinery (1982)  Premi Pioner d'Informàtica (1974)  Premi Memorial Harry H. Goode (1972)  Premi Turing (1971)  Fellow de la British Computer Society

Edsger Wybe Dijkstra (Rotterdam, 11 de maig de 1930 – Nuenen, 6 d'agost de 2002) fou un informàtic neerlandès. Va rebre el 1972 el Premi Turing per les contribucions fonamentals en l'àrea dels llenguatges de programació, i va ser el "Schlumberger Centennial Chair of Computer Sciences" a la Universitat de Texas a Austin des de 1984 fins a la seva mort el 2002.

Biografia

Primers Anys

Nascut a Rotterdam. El seu pare, que era químic, va ser president de la Societat Holandesa de Química; i havia après química durant la secundària i més tard va ser el seu superintendent. La seva mare era matemàtica però mai va tenir un treball formal.

Dijkstra sempre havia considerat emprendre una carrera jurídica i representar els Països Baixos en les Nacions Unides. Tanmateix, després de graduar-se a l'escola el 1948, sota el suggeriment dels seus pares va estudiar matemàtiques i física i després física teòrica en la Universitat de Leiden.

A principis dels anys cinquanta, els ordinadors eren una novetat. Dijkstra va ensopegar amb la seva carrera per casualitat, i a través del seu supervisor, el professor A. Haantjes, va conèixer a Adriaan van Wijngaarden, el director del Departament de Computació del Centre de Matemàtiques i Informàtica d'Amsterdam, el qual va oferir un treball a Dijkstra que va esdevenir el primer programador holandès el març de 1952.

El 1959 va rebre el doctorat de la Universitat d'Amsterdam per la tesi 'Communication with an Automatic Computer' dedicada a la descripció del llenguatge d'assemblador del primer ordinador comercial desenvolupat als Països Baixos, el X1. El seu director de tesis va ser Adriaan van Wijngaarden.

Mathematisch Centrum, Amsterdam

Des de 1952 fins al 1962, Dijkstra va treballar al Centre de Matemàtiques i Informàtica (CWI) d'Amsterdam conjuntament amb Bram Jan Loopstra i Carel S. Scholten que havien estat contractats per construir un ordinador. La seva forma d'interaccionar era disciplinada: En primer lloc, van escriure un manual de programació per decidir sobre la interfície entre el hardware i el software. A continuació, mentre els dissenyadors de hardware havien de ser fidels a la seva part del contracte, Dijkstra havia d'escriure un programari per una màquina inexistent. Dues de les lliçons que va aprendre d'aquella experiència van ser: la importància d'una documentació clara, i que la depuració d'un programa es pot evitar en gran mesura amb un disseny acurat.

Dijkstra va formular i resoldre el Problema del camí més curt per a una demostració en la inauguració oficial de l’ordinador AEMAC l’any 1956 però a causa de l’absència de mitjans dedicats a la computació informàtica no es van publicar els resultats fins al 1959.

Al CWI, Dijkstra i el seu company Jaap Zonneveld van desenvolupar un compilador per al llenguatge de programació ALGOL 60; aquest projecte va tenir una profunda influència en el seu pensament sobre la programació com activitat científica. Dijkstra i Zonneveld van completar la implementació del primer compilador per ALGOL 60 l’agost de 1960, més d’un any abans que un altre grup crees un compilador.

Eindhoven University of Technology

El 1962 Dijkstra es va traslladar a Eindhoven, i més tard a Nuenen, al sud dels Països Baixos on es va convertir en professor del Departament de Matemàtiques a la Universitat Tècnica d'Eindhoven. La universitat no tenia un departament d'informàtica independent al de matemàtiques i la forma de treballar d'aquest departament no l'entusiasmava. Dijkstra va intentar construir un grup de treball per científics de la computació per a poder resoldre problemes. A finals dels anys 60, va construir el Sistema Operatiu THE (anomenat per la universitat, conegut més tard com Technische Hogeschool Eindhoven), el qual va influenciar als sistemes operatius posteriors mitjançant l'ús de software basat en paginació de memòria virtual.

Burroughs Corporation

Dijkstar es va unir a Burroughs Corporation, una companyia coneguda per la producció d'ordinadors basats en arquitectures hardware innovadores, com a Research Fellow l'agost de 1973. Els seus deures com investigador consistien a visitar alguns dels centres d'investigació de la companyia unes quantes vegades a l'any i seguir amb la seva investigació. El qual va fer en la instal·lació de recerca més petita de Burroughs, l'estudi de la segona planta de la seva casa a Nuenen. De fet, Dijkstra era l'únic Research Fellow de l'empresa i a més treballava des de casa i ocasionalment es desplaçava a alguna de les sucursals als Estats Units. Com a resultat va disminuir l'assistència a la universitat a una a la setmana. Aquell dia, dijous, es va convertir en el famós dia 'Tuesday Afternoon Club', un seminari on ell juntament amb companys discutien sobre articles científics en tots els aspectes. Poc després que es traslladés a la Universitat de Texas a Austin l'any 1984, va sorgir una nova 'branca' del 'Tuesday Afternoon Club' a Austin.

Els anys a Burroughs Corporation van ser els més prolífics en la producció d'articles de recerca. Va escriure prop d'uns 500 documents a la sèrie EWD, la majoria informes tècnics, per a la circulació privada dins un grup selecte.

Universitat de Texas

Dijkstra va acceptar la Schlumberger Centennial Chair en el  Departament de Ciències de la Computació de la Universitat de Texas a Austin el 1984.

Últims Anys

Dijkstra va treballar a Austin fins que es va retirar el novembre de 1999. Per emmarcar l'ocasió i celebrar els seus quaranta anys de contribucions a la ciència de la computació, el Departament de Ciències de la Computació va organitzar un simpòsium que va tenir lloc en el seu setantè aniversari el maig del 2000.

Dijkstra va tornar d'Austin a la seva casa a Nuenen (Països Baixos) després de retirar-se. Ell havia dit que volia retirar-se a Austin però morir als Països Baixos. Dijkstra va morir el 6 d'agost de 2002 després d'una llarga lluita contra el càncer.

Contribucions científiques

Coma a primer teòric pioner en diverses àrees d'investigació de la ciència de la computació, Dijkstra va ajudar a donar forma a la nova disciplina des d'una perspectiva acadèmica com d'enginyeria. Molts dels seus treballs han esdevingut la font en noves àrees de recerca. Un gran nombre de conceptes que avui en dia es consideren estàndards en la ciència de la computació van ser identificats per primera vegada per Dijkstra i persones lligades al seu entorn. Al 1994 es va dur a terme una enquesta entre més de mil professors de les Ciències de la Computació per obtenir una llista dels 38 documents acadèmics més influents en el camp, i Dijkstra era l'autor de cinc articles en la llista.

Durant els més de 40 anys com a científic de la computació, incloses posicions acadèmiques i en la indústria, Dijkstra va fer nombroses contribucions en moltes de les àrees de la ciència de la computació. Va realitzar contribucions en l'àrea dels sistemes operatius, programació concurrent, programació distribuïda, paradigmes de programació i metodologia entre moles d'altres.

A més Dijkstra estava molt interessat en l'ensenyança d'aquesta ciència i en la relació entre la ciència de la computació i la indústria del software.

Treball en algorismes

El treball en algorismes de Dijkstra (especialment algorismes de grafs, algorismes concurrents, i algorismes distribuïts) juga un paper important en moltes àrees de la ciència de la computació.

El 1959 Dijkstra va publicar en un article de 3 pàgines l'algorisme per trobar el camí més curt entre dos nodes d'un graf, avui en dia nomenat Algorisme de Dijkstra. L'impacte de l'algorisme durant els següents 40 anys després de la seva publicació es troba resumit en l'article de Mikkel Thorup, 'Undirected Single Source Shortest Paths with Positive Integer Weights in Linear Time' (1999): "Des del 1959, tot el desenvolupament teòric en SSSP [Single-Source Shortest Paths] per grafs generals dirigits i no dirigits s'han basat en l'algorisme de Dijkstra.". L'algorisme de Dijkstra, s'aplica als protocols d'encaminament OSPF i IS-IS. Diverses modificacions per l'algorisme de Dijkstra han estat proposades per diferents autors que utilitzen heurístiques per reduir el temps de cerca del camí més curt. Una de les implementacions més utilitzades és l'Algorisme de cerca A*, descrit per primera vegada per Peter Hart, Nils Nilsson i Berttram Raphael de l'Institut de Recerca de Stanford el 1968. L'objectiu principal és reduir el temps d'execució reduint l'espai de cerca. Dijkstra va pensar sobre el problema del camí més curt quan estava treballant al Centre de Matemàtiques i Informàtica (CWI) d'Amsterdam el 1956 com a programador per demostrar les capacitats del nou computador ARMAC. El seu objectiu era triar un problema i a la vegada la resposta, que seria proporcionada pel computador, que la gent no relacionada amb la computació pogués entendre. Va dissenyar l'Algorisme de Dijkstra en 20 minuts sense paper ni llapis i el després el va implementar pel computador ARMAC per obtenir un mapa de transport lleugerament simplificat de 64 ciutats dels Països Baixos.

Un any més tard es va trobar amb un altre problema amb els enginyers de hardware que treballaven en el següent computador de l'institut: minimitzar el conjunt de cables necessaris per connectar els pins del panell posterior de la màquina. Coma solució va redescobrir l'algorisme conegut com a Algorisme de Prim per trobar un arbre generador minimal. L'Algorisme de Prim va ser desenvolupat l'any 1930 pel matemàtic txec Vojtěch Jarník i posteriorment descobert de forma independent i tornar a publicar per Robert C. Prim l'any 1957. Dijkstra va publicar el seu redescobriment l'any 1959. A causa dels diferents redescobriments i republicacions l'algorisme es coneix també com Algorisme DJP'.

L'any 1961 Dijkstra va descriure per primera vegada l'Algorisme shunting yard, un mètode per persejar expressions matemàtiques especificades en la notació infix, a l'informe del CWI. Es pot utilitzar per produir resultats en Notació Polonesa Inversa (RPN) o com un arbre de sintaxi abstracte (AST). L'algorisme shunting yard s'utilitza per implementar 'operator-precedence parsers'.

Entre 1962 i 1963 Dijkstra va proposar el mecanisme dels semàfors per l'algorisme d'exclusió mútua per n processos que probablement va ser la primera publicació sobre algorismes concurrents i que va introduir una nova àrea de recerca. També va identificar el problema del deadlock i va proposar l'algorisme del banquer per prevenir el deadlock.

Dijkstra va presentar el 1964 tres algorismes d'auto estabilització per a l'exclusió mútua en un anell. El treball de Dijkstra és considerat el primer en la introducció i demostració del concepte d'auto estabilització.

A mitjans dels anys 70 Dijkstra, juntament amb altres autors van introduir dues abstraccions útils (mutator i collector) en l'estudi sobre la recollida de memòria brossa. El mutator és una abstracció del procés que realitza la computació, incloent-hi l'assignació d'una nova cel·la d'emmagatzematge. El collector és el procés que automàticament recupera memòria brossa.

A principis dels anys 80 Carel S. Scholten i Dijkstra van proposar l'algoritme Dijkstra-Scholten per detectar la finalització d'un sistema distribuït.

El 1981 Dijkstra va desenvolupar l'algorisme smoothsort, un algorisme de cerca basat en comparacions, variació de l'algorisme heapsort.

Disseny i desenvolupament de programes (investigació d'enginyeria del software)

Les idees de Dijkstra sobre la metodologia de programació (especialment el moviment de programació estructurada) van ajudar a establir els fonaments per al naixement i desenvolupament de la disciplina professional de l'enginyeria del software (en particular, el disseny i desenvolupament de programari), que permetrà als programadors organitzar i gestionar projectes de software cada vegada més complexos. A finals de la dècada de 1960 Dijkstra va debatre sobre el concepte de famílies de programes. I a mitjan anys setanta David Parnas i altres van aclarir la idea i van mostrar com aplicar-la en els principis d'enginyeria del software.

L'augment del moviment de programació estructurada va donar lloc a molts altres enfocaments estructurats aplicats al disseny de software. Les tècniques d'anàlisi estructurada i disseny estructurat són conseqüències de conceptes i tècniques de programació estructurada i de les primeres idees sobre disseny modular. Els principis de modularitat es van veure reforçats pels conceptes d'acoblament (minimitzar-se entre mòduls) i la cohesió (maximitzar-se en els mòduls) de Larry Constantine, per les tècniques d'ocultació d'informació de David Parnas i per tipus de dades abstractes. Es van desenvolupar diverses eines i mètodes que utilitzen conceptes estructurats, com ara el disseny estructurat, la programació estructurada de Jackson, l'anàlisi estructurada i la tècnica de disseny (SADT) de Ross, el mètode estructurat de Yourdon, l'anàlisi de sistemes estructurats i el mètode de disseny (SSADM) i Enginyeria de la informació de James Martin. El camp de les mètriques del software sovint es considera com una influència directa del moviment estructurat de programació en l'enginyeria del software en els anys 70.

La separació d'inquietuds (SoC), un dels principis bàsics de l'enginyeria del software, és un principi de disseny per separar un programa informàtic en diferents seccions, de manera que cada secció tracta d'una preocupació diferent. El terme "separació de preocupacions" va ser encunyat per Dijkstra en el seu article de 1974 "Sobre el paper del pensament científic".

Investigacio de sistemes operatius

A la dècada dels seixanta, Dijkstra i els seus companys d'Eindhoven van dissenyar i implementar el sistema operatiu "The Technische Hogeschool Eindhoven", que estava organitzat en capes clarament identificades. El seu article de 1968 sobre aquest tema va proporcionar la base per als posteriors dissenys dels sistemes operatius. David Alan Grier, de l'equip informàtic de l'IEEE, escriu: "En general, seguim la idea de construir sistemes informàtics en capes com explica el document de 1967 que el científic informàtic holandès Edsger Dijkstra va donar a la conferència conjunta d'IEEE Computer Society / ACM. Abans d'aquest article, els enginyers havien lluitat amb el problema de com organitzar el software. Si observeu els primers exemples de programes, i podeu trobar molts a la biblioteca electrònica de la Societat de la Computació, trobareu que la majoria del codi d'aquesta era és complicat, difícil de llegir, difícil de modificar i difícil de reutilitzar. En el document de 1967, Dijkstra va descriure com el software es podia construir en capes i va donar un exemple d'un sistema operatiu senzill que usava cinc capes. Va admetre que aquest sistema podria no ser una prova realista de les seves idees però va argumentar que "com més gran és el projecte, més important és l'estructuració". La idea d'utilitzar capes per controlar la complexitat s'ha convertit en un element fonamental de l'arquitectura de software. Ho veiem en moltes formes i l'apliquem a molts problemes. Ho veiem a la jerarquia de classes en programació orientada a objectes i en l'estructura de l'Arquitectura orientada a serveis (SOA). SOA és una aplicació relativament recent de capes en informàtica. Es va articular el 2007 com un mitjà per controlar la complexitat dels sistemes empresarials, especialment els sistemes distribuïts que fan un ús substancial d'Internet. Igual que el pla de Dijkstra per al desenvolupament del sistema, el seu sistema de capes es diu SOA Solution Stack o S3. Les noves capes del S3 són: 1) sistemes operatius, 2) components del servei, 3) serveis, 4) processos empresarials, 5) accions del consumidor, 6) integració del sistema, 7) control i garantia de qualitat, 8) arquitectura d'informació i 9) governança i polítiques del sistema".

Dijkstra va organitzar el disseny del sistema en capes per reduir la complexitat global del software. Encara que el terme "arquitectura" encara no s'havia utilitzat per descriure el disseny de software, aquest va ser sens dubte el primer cop d'ull de l'arquitectura del software. Va introduir una sèrie de principis de disseny que s'han convertit en part del vocabulari de treball de cada programador professional: nivells d'abstracció, programació en capes, semàfor i processos seqüencials que cooperen. El seu article original sobre el sistema operatiu THE va ser reimprès en el número 25 de l'aniversari de Communications of the ACM, el gener de 1983. Com a introducció, el redactor en cap diu: "Aquest projecte va iniciar una llarga línia de recerca en l'arquitectura de sistemes multinivell - una línia que continua fins als nostres dies perquè la modularitat jeràrquica és un enfocament potent per organitzar grans sistemes".

Manuscrits de EWD

Dijkstra era coneguda pel seu costum de compondre curosament els manuscrits amb la seva ploma estilogràfica. Els manuscrits es diuen EWDs, ja que Dijkstra els va numerar amb EWD, les seves inicials, com a prefix. Segons el mateix Dijkstra, els EWD començar quan es va traslladar del Centre de Matemàtiques d'Amsterdam a la Universitat de Tecnologia d'Eindhoven (llavors Technische Hogeschool Eindhoven). Després d'anar a Eindhoven, Dijkstra va experimentar un bloqueig durant més d'un any on va ser incapaç de crear nou material. Dijkstra va distribuir fotocòpies d'un nou EWD entre els seus companys. Molts destinataris van fotocopiar i reenviar les còpies, de manera que els EWD es van estendre per tota la comunitat informàtica internacional. Els temes eren la informàtica i les matemàtiques, incloent-hi informes de viatges, cartes i intervencions. Aquests articles breus abasten un període de 40 anys. Gairebé tots els EWD que apareixen després de 1972 van ser escrits a mà. Rarament són més de 15 pàgines i es numeren consecutivament. L'últim, núm. 1318, és del 14 d'abril de 2002. Dins de la informàtica es coneixen com a informes EWD, o simplement els EWD. S'han escanejat més de 1.300 EWD, amb un nombre creixent transcrit per facilitar la cerca, i estan disponibles en línia a l'arxiu Dijkstra de la Universitat de Texas.

Les veritats de Dijkstra

El 1975 va escriure How do we tell truths that might hurt?, en el qual Dijkstra planteja diverses "veritats" per a l'època. Entre elles s'hi pot trobar:

• Fortran –"el desordre infantil"–, ja proper als 20 anys, és desesperadament inadequat per a qualsevol aplicació de computació que tinguis al cap : és massa matusser, massa rigorós i massa costós d'usar.
• PL1 –"la malaltia fatal"– pertany més al conjunt del problema que al conjunt de la solució.
• És pràcticament impossible ensenyar bona programació a estudiants que han estat exposats prèviament a la programació en BASIC: com a programadors potencials han estat mutilats mentalment més enllà de qualsevol esperança de regeneració.
• L'ús del Cobol atrofia la ment; la seva ensenyança hauria, aleshores, ser considerada com un crim.

La simplicitat és un prerequisit per la fiabilitat. (anotació feta a mà)

Premis i Honors

• Membre de l'Acadèmia Reial d'Arts i Ciències dels Països Baixos (1971).
• Membre distingit de la British Computer Society (1971).
• ACM A.M. Turing Award (1972).
• Harry H. Goode Memorial Award de la IEEE Computer Society (1974).
• Membre honorari de l'Acadèmia Americana d'Arts i Ciències (1975).
• Doctor en Ciències Honoris Causa de la Queen's University Belfast (1976).
• Computer Pioneer Charter Receptor de la Societat d'Informàtica de l'IEEE (1982).
• Premi ACM / SIGCSE per contribucions destacades a l'educació en informàtica (1989).
• Membre de l'Association for Computing Machinery (1994).
• Doctorat honorífic de la Universitat d'Economia i Empresa d'Atenes, Grècia (2001).

La Beca Distingida de la Societat Britànica d'Informàtica (BCS) es concedeix segons l'ordenança 7 de la Carta Reial de BCS. El premi va ser aprovat per primera vegada el 1969 i la primera elecció va ser el 1971 per a Dijkstra.

Amb motiu del 60è aniversari de Dijkstra el 1990, el Departament de Ciències de la Computació (UTCS) de la Universitat de Texas a Austin va organitzar un seminari de dos dies en el seu honor. Els ponents provenien de tots els Estats Units i Europa, i un grup de científics informàtics van aportar articles d'investigació que es van editar en un llibre.

El 2002, la Fundació C & C del Japó va reconèixer a Dijkstra "per les seves contribucions pioneres a l'establiment de la base científica del programari informàtic a través de la recerca creativa en la teoria de programari bàsica, la teoria d'algorismes, la programació estructurada i els semàfors". Dijkstra era viu quan va rebre l'avís del premi, però va ser acceptat per la seva família en una cerimònia de lliurament després de la seva mort.

Poc abans de la seva mort l'any 2002, Dijkstra va rebre el premi PODC Influential-Paper de ACM en informàtica distribuïda pel seu treball d'auto estabilització de la computació del programa. Aquest premi anual fou anomenat premi Dijkstra (Premi Edsger W. Dijkstra en Informàtica Distribuïda) l'any següent, en el seu honor.

El Premi Dijkstra per al Millor Acompliment Acadèmic en Informàtica (Loyola University Chicago, Departament d'Informàtica) és nomenat per Edger W. Dijkstra. A partir de 2005, aquest guardó reconeix el millor rendiment acadèmic d'un graduat en informàtica. La selecció es basa en l'expedient acadèmic en tots els cursos principals i en les eleccions dels professors del departament.

El Departament d'Informàtica (UTCS) de la Universitat de Texas a Austin va acollir la conferència inaugural Edsger W. Dijkstra Memorial el 12 d'octubre de 2010. Tony Hoare, professor emèrit d'Oxford i investigador principal de Microsoft Research, va ser el ponent de l'esdeveniment. Aquesta sèrie de conferències va ser possible gràcies a una generosa subvenció de Schlumberger per honrar la memòria de Dijkstra.

Bibliografia

{cite journal |first=Krzysztof R. |last=Apt |title=Edsger Wybe Dijkstra (1930–2002): A Portrait of a Genius |journal=Formal Aspects of Computing |volume=14 |issue=2 |pages=92–98 |year=2002 |doi=10.1007/s001650200029 |url=https://link.springer.com/article/10.1007/s001650200029 |arxiv=cs/0210001 |ref=harv}} Vegeu també Semàfor (informàtica) El problema del sopar dels filòsofs Monitor (concurrència) Algorisme de Dijkstra Enllaços externs Fotografies de Dijkstra (rus) Escrits de Dijkstra (EWD) (anglès) La Història dels Filosofs Comensals