Edsger Dijkstra
![]() ![]() | |
Biografia | |
---|---|
Naixement | (nl) Edsger Wybe Dijkstra ![]() 11 maig 1930 ![]() Rotterdam (Països Baixos) ![]() |
Mort | 6 agost 2002 ![]() Nuenen (Països Baixos) ![]() |
Causa de mort | càncer colorectal ![]() |
Formació | Universitat d'Amsterdam - ciències de la computació (1956–1959) Universitat de Cambridge (1951–1951) Gymnasium Erasmianum (–1948) Universitat de Leiden - física, matemàtiques (1948–1956) ![]() |
Tesi acadèmica | Communication with an Automatic Computer ![]() ![]() |
Director de tesi | Adriaan van Wijngaarden ![]() |
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 | Association for Computing Machinery (membre de l'Association for Computing Machinery) (1994–) Acadèmia Americana de les Arts i les Ciències Reial Acadèmia d'Arts i Ciències dels Països Baixos ![]() |
Obra | |
Obres destacables
| |
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 ![]() |
Pares | Douwe Wybe Dijkstra i Brechtje Cornelia Kluijver |
Premis
| |
![]() |
Edsger Dijkstra (neerlandès: Edsger Wybe Dijkstra) (pronunciació en : /ˈɛtsxər ˈwibə ˈdɛɪkstra/) (Rotterdam, 11 de maig de 1930 - Nuenen, 6 d'agost de 2002) va ser un científic de sistemes, programador, enginyer de software, assagista de ciències [1] i pioner en ciències de la computació. Físic teòric en formació, va treballar com a programador al Mathematisch Centrum (Amsterdam) entre 1952 i 1962. Catedràtic universitari durant la major part de la seva vida, Dijkstra va exercir la Càtedra Centenari Schlumberger en Ciències de la Computació a la Universitat de Texas a Austin des de 1984 fins a la seva jubilació el 1999. Va ser professor de matemàtiques a la Universitat de Tecnologia d'Eindhoven (1962–1984) i investigador de la Corporació Burroughs (1973–1984).
Una de les figures més influents de la generació fundadora de la ciència informàtica, Dijkstra va ajudar a donar forma a la nova disciplina tant des de la perspectiva de l'enginyeria com des de la teoria.[2] Les seves contribucions fonamentals cobreixen diverses àrees de la informàtica, incloent-hi la construcció de compiladors, sistemes operatius, sistemes distribuïts, programació seqüencial i concurrent, paradigma i metodologia de programació, recerca en llenguatges de programació, disseny de programes, desenvolupament de programes, principis d'enginyeria de software, algoritmes de gràfics, i fonaments filosòfics de la programació informàtica i de la informàtica. Molts dels seus papers són l'origen de noves àrees de recerca. Diversos conceptes i problemes que ara són estàndard en informàtica van ser identificats per primera vegada per Dijkstra o els noms dels ossos encunyats per ell.[3] Com a principal opositor de la visió mecanitzadora de la ciència informàtica, va refutar l'ús dels conceptes d'informàtica i d'enginyeria de programari com a paraules clau per a les disciplines acadèmiques.
Fins a la meitat dels anys seixanta, la programació informàtica es considerava més un art (o un ofici) que una disciplina científica. En les paraules de Harlan Mills (1986), "la programació [abans de la dècada de 1970] va ser considerada com una activitat privada per resoldre trencaclosques per escriure instruccions informàtiques per treballar com a programa". A finals dels anys seixanta, la programació informàtica estava en crisi. Dijkstra va ser un grup petit de acadèmics i programadors industrials que van defensar un nou estil de programació per millorar la qualitat dels programes. Dijkstra, que va tenir una formació en matemàtiques i física, va ser un dels motors de l'acceptació de la programació informàtica com a disciplina científica.[4][5] Va encunyar la frase "programació estructurada" i durant els anys setanta aquesta es va convertir en la nova programació ortodoxa.[6] Les seves idees sobre la programació estructurada van ajudar a establir les bases per al naixement i el desenvolupament de la disciplina professional de l'enginyeria de programari, permetent als programadors organitzar i gestionar projectes de programari cada vegada més complexos. Tal com va assenyalar Bertrand Meyer (2009), "la revolució en la visió de la programació iniciada per la iconoclàstia de Dijkstra va portar a un moviment conegut com a programació estructurada, que defensava un enfocament sistemàtic i racional de la construcció del programa. La programació estructurada és la base de tot el que s'ha fet, ja que en la metodologia de programació, inclosa la programació orientada a objectes.[7]
L'estudi acadèmic de la computació simultània va començar als anys seixanta, amb Dijkstra (1965) el primer article d'aquest camp, identificant i resolent el problema d'exclusió mútua.[8][9] També va ser un dels primers pioners de la investigació sobre els principis de la computació distribuïda. El seu treball fonamental sobre la concurrència, els semàfors, l'exclusió mútua, deadlock (abraçada mortal), la recerca de camins més curts en gràfics, tolerància a fallades, autoestabilització, entre moltes altres contribucions, inclou molts dels pilars sobre els quals es construeix el camp de la informàtica distribuïda. Poc abans de la seva mort el 2002, va rebre el premi ACM PODC Influential-Paper en informàtica distribuïda pel seu treball sobre l'auto-estabilització del càlcul del programa. Aquest premi anual es va canviar el nom de Premi Dijkstra (Premi Edsger W. Dijkstra en Informàtica distribuïda) l'any següent, en el seu honor.[10][11] Com el premi, patrocinat conjuntament pel simposi ACM sobre principis de computació distribuïda (PODC) i el simposi internacional EATCS sobre computació distribuïda (DISC), reconeix que "cap altre individu ha tingut una influència més gran en la investigació en els principis de la computació distribuïda".
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.[12]
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.[13]
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 Johannes 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.[13]
Durant un temps, Dijkstra es va mantenir compromesa amb la física, treballant-hi a Leiden tres dies després de cada setmana. Amb l'exposició creixent a la informàtica, però, el seu enfocament va començar a canviar. Com va recordar:[14]
« | Després d'haver programat durant tres anys, vaig tenir una discussió amb A. van Wijngaarden, que era llavors el meu cap al Centre de Matemàtiques d'Amsterdam, una discussió per la qual continuaré agraït mentre visc. La qüestió era que se suposava que havia d'estudiar física teòrica a la Universitat de Leiden simultàniament, i com vaig trobar ambdues activitats cada cop més difícils de combinar, vaig haver de decidir-me, ja sigui per deixar de programar i convertir-me en un veritable i respectable teòric físic, o per portar el meu estudi de la física a una finalització formal només, amb un mínim d'esforç, i per convertir-me en ....., sí què? Un programador? Però era una professió respectable? Perquè després de tot, què era la programació? On era el cos sòlid del coneixement que podia suportar-lo com una disciplina respectable intel·lectualment? Recordo amb molta claredat com envegava els meus companys de maquinari, que, quan se'ls preguntava sobre la seva competència professional, podrien almenys assenyalar que ho sabien tot sobre els tubs de buit, els amplificadors i la resta, mentre que sentia que, davant d'aquesta pregunta, jo es quedaria amb les mans buides. Ple de dubtes vaig trucar a la porta de l'oficina de Van Wijngaarden, preguntant-li si podia "parlar-li un moment"; Quan vaig deixar el seu despatx diverses hores més tard, era una altra persona. Després d'haver escoltat els meus problemes amb paciència, va estar d'acord que fins a aquell moment no hi havia molt d'una disciplina de programació, però després va explicar tranquil·lament que els ordinadors automàtics estaven aquí per quedar-se, que érem just al principi i podíem No ser jo una de les persones que es va cridar a fer la programació una disciplina respectable en els propers anys? Aquest va ser un moment decisiu en la meva vida i vaig completar el meu estudi de física formalment el més ràpid possible. | » |
— Edsger Dijkstra, The Humble Programmer (EWD340) |
Quan Dijkstra es va casar amb Maria (Ria) C. Debets el 1957, va ser requerit com a part dels ritus matrimonials per declarar la seva professió. Va afirmar que era un programador, cosa que era inacceptable per a les autoritats, i no hi havia cap professió en aquell moment als Països Baixos.[15][16]
Al 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.[17]
Aspectes Generals
Era conegut per que va alertar sobre els perills de la sentència GOTO en la programació, que va culminar el 1968 amb la carta a l'editor que va publicar amb el títol Go To Statement Considered Harmful (La sentència Goto considerada perjudicial), vist com un pas important cap a el rebuig de l'expressió GOTO i del seu eficaç reemplaçament per estructures de control com ara el bucle while.
Des dels anys 1970, el principal interès de Dijkstra va ser la verificació formal. L'opinió que prevalia llavors era que un ha de primer escriure un programa i seguidament proporcionar una prova matemàtica de la seva correcció. Dijkstra va objectar que les proves que resulten són llargues i incòmodes, i que la prova no dona cap comprensió de com es va desenvolupar el programa. Un mètode alternatiu és la derivació de programes, «desenvolupar prova i programa conjuntament». Un comença amb una especificació matemàtica del programa que se suposa va a fer i aplica transformacions matemàtiques a l'especificació fins que es transforma en un programa que pugui ser executat. El programa que resulta llavors és sabut correcte per la construcció. Molts dels últims treballs de Dijkstra tracten sobre les maneres de fer fluïda l'argumentació matemàtica.
Respecte al seu caràcter àrid i àcid, conegudes són la seva oposició a la instrucció GOTO i al llenguatge BASIC («mutila la ment més enllà de tota recuperació»). Alan Kay va exposar que en informàtica, l'arrogància es mesura en nanodijkstras.[18]
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 manera 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.[12]
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.[2]
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.[19]
Contribucions científiques
Com 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.[20][21]
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) té 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.[22] Com va recordar, en una entrevista publicada al 2001:[23]
« | Quin és el camí més curt per viatjar de Rotterdam a Groningen, en general: des d'una ciutat a una ciutat determinada. És l'algorisme del camí més curt, que he dissenyat en uns vint minuts. Un matí feia compres a Amsterdam amb la meva jove promesa, i cansada, ens vam asseure a la terrassa de la cafeteria per beure una tassa de cafè i només pensava si podia fer-ho i llavors vaig dissenyar l'algorisme per al camí més curt.. Com he dit, va ser un invent de vint minuts. De fet, es va publicar el '59, amb tres anys de retard. La publicació continua sent llegible, és, de fet, bastant agradable. Una de les raons per les quals és tan agradable va ser que el vaig dissenyar sense llapis i paper. Més endavant vaig aprendre que un dels avantatges de dissenyar sense llapis i paper és que està gairebé obligat a evitar totes les complexitats evitables. Finalment, aquest algorisme va esdevenir, per sorpresa meva, un dels pilars fonamentals de la meva fama. | » |
— Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM 53 (8), 2001 |
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.
Construcció de compiladors i recerca en llenguatge de programació
Dijkstra era conegut per ser fan d'ALGOL 60 i va treballar en l'equip que va implementar el primer compilador per a aquest idioma. Va estar molt involucrat en el desenvolupament, la realització i la popularització d'ALGOL 60. Tal com va discutir Peter Naur a l'article "El costat europeu de l'última fase del desenvolupament d'ALGOL 60", a les Actes de la primera conferència ACM SIGPLAN sobre història de les llengües de programació, gener de 1978, Dijkstra va participar en el període 1958– 1959 en diverses reunions que van culminar amb la publicació de l'informe que definia el llenguatge ALGOL 60. El nom de Dijkstra no apareix a la llista de 13 autors de l'informe final. Pel que sembla, finalment va deixar el comitè perquè no podia estar d'acord amb les opinions de la majoria. Tot i així, mentre que a Mathematisch Centrum (Amsterdam), va escriure conjuntament amb Jaap Zonneveld el primer compilador ALGOL 60. Dijkstra i Zonneveld, que van col·laborar en el compilador, van acordar no afaitar-se fins que es completés el projecte; mentre que Zonneveld es va afaitar poc després, Dijkstra va mantenir la barba durant la resta de la seva vida.[24]
ALGOL va ser el resultat de la col·laboració de comitès americans i europeus. ALGOL 60 (abreujat de ALGOrithmic Language 1960) és membre de la família de llenguatges de programació informàtica ALGOL. Va seguir d'Algol 58 i va inspirar molts idiomes que el van seguir. Va donar lloc a molts altres llenguatges de programació, incloent BCPL, B, Pascal, Simula i C.[25] Algol 60 era un llenguatge informàtic dissenyat sofisticadament i proporcionava un gran nombre de reptes fins ara desconeguts en la implementació. Com assenyala Bjarne Stroustrup, "un problema amb Algol60 era que ningú sabia com implementar-ho". Un nou repte important en la implementació d'Algol 60 va ser l'assignació i la gestió de les dades en temps d'execució. El 1960, Dijkstra i Zonneveld van mostrar com es podrien executar procediments recursius utilitzant una pila de temps d'execució de registres d'activació i com accedir de manera eficient als identificadors des dels àmbits tancats de forma estàtica utilitzant l'anomenat "display".[26] El compilador ALGOL 60 va ser un dels primers a donar suport a la recursió [27] que emprava un mètode nou per fer-ho. El llibre breu de Dijkstra, Primer of Algol 60 Programming, publicat originalment el 1962, va ser la referència estàndard per al llenguatge durant diversos anys.
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".
Investigació 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 d'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.[28]
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.[29] 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.
Referències
- ↑ «Storytelling About Lighthouses: Criticizing Professor Dijkstra Considered Harmless».
- ↑ 2,0 2,1 «The University of Texas at Austin».
- ↑ «Programming Methodology: A Collection of Articles by Members of IFIP WG2.3».
- ↑ «Edsger Dijkstra, 72, Physicist Who Shaped Computer Era».
- ↑ «The Guardian. Retrieved 19 April 2015.».
- ↑ «Software Pioneers: Contributions to Software Engineering, p19».
- ↑ «Bertrand Meyer: STOUCH OF CLASS. Learning to program well with objects and contracts». Arxivat de l'original el 2017-07-06. [Consulta: 25 maig 2019].
- ↑ «2002 PODC Influential Paper Award».
- ↑ «Turing Lecture: The Computer Science of Concurrency: The Early Years».
- ↑ «Edsger W. Dijkstra Prize in Distributed Computing (European Association for Theoretical Computer Science – EATCS)».
- ↑ «Dijkstra Prize».
- ↑ 12,0 12,1 ; Robertson, E F«Dijkstra biography», juliol 2008. Arxivat de l'original el 11 octubre 2013. [Consulta: 18 gener 2014].
- ↑ 13,0 13,1 ; Durbin, John R.«In Memoriam: Edsger Wybe Dijkstra». The University of Texas at Austin, 19-08-2013. [Consulta: 20 agost 2015].
- ↑ «[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD340.html The Humble Programmer by Edsger W. Dijkstra]».
- ↑ «The Humble Programmer by Edsger W. Dijkstra».
- ↑ «Edsger Dijkstra - The Poetry Of Programming».
- ↑ Gries, David. Programming Methodology: A Collection of Articles by Members of IFIP WG2.3. Springer, 1978, p. 7. ISBN 978-1-4612-6315-9.
- ↑ vermilyer. «Alan Kay on Dijkstra», 06-06-2011. [Consulta: 7 maig 2019].
- ↑ Goyeneche, Juan-Mariano de. «Juan-Mariano de Goyeneche - En la muerte de Dijkstra» (en espanyol europeu), 12-08-2002. [Consulta: 14 maig 2019].
- ↑ Chen, P.P. «From goto-less to structured programming: the legacy of Edger W. Dijkstra» (en anglès). IEEE Software, 19, 5, 2002-09, pàg. 21–21. DOI: 10.1109/ms.2002.1032847. ISSN: 0740-7459.
- ↑ Laplante, Phillip A. «Great Papers in Computer Science: A Retrospective» (PDF). Journal of Scientific and Practical Computing, 2, 1, Desembre 2008, pàg. 31-35. Arxivat de l'original el 2018-05-05 [Consulta: 2 maig 2018]. Arxivat 2018-05-05 a Wayback Machine.
- ↑ «Biografia de Dijkstra».
- ↑ «An Interview with Edsger W. Dijkstra (OH 330)».
- ↑ «Van Emden, Maarten (6 May 2008)| I remember Edsger Dijkstra (1930 – 2002)».
- ↑ «"Hints on Programming Language Design" | Hoare, C.A.R. (December 1973, p.27».
- ↑ Gram, Christian; Rasmussen, Per; Østergaard, Søren Duus (eds.) (2015). History of Nordic Computing 4 4th IFIP WG 9.7 Conference, HiNC 4, Copenhagen, Denmark, August 13–15, 2014, Revised Selected Papers. (Springer), p. 358
- ↑ «Dijkstra's Rallying Cry for Generalization: the Advent of the Recursive Procedure, late 1950s – early 1960s».
- ↑ «E.W.Dijkstra Archive: Home page» (en angles). [Consulta: 2 maig 2018].
- ↑ Dijkstra, Edsger Wybe. «How do we tell truths that might hurt?». (18 de Juny de 1975). «Enllaç». (anglès)
Vegeu també
- Semàfor (informàtica)
- El problema del sopar dels filòsofs
- Monitor (concurrència)
- Algorisme de Dijkstra
Enllaços externs
En altres projectes de Wikimedia: | |
![]() | Commons ![]() |
![]() | Viquidites |
- Fotografies de Dijkstra (rus)
- Escrits de Dijkstra (EWD) (anglès)
- O'Connor, John J.; Robertson, Edmund F. «Edsger Dijkstra» (en anglès). MacTutor History of Mathematics archive. School of Mathematics and Statistics, University of St Andrews, Scotland.