Edsger Dijkstra Wybe ( / d aɪ k s t r ə / ; holandesa: [ɛtsxər ʋibə dɛikstra] ( escuchar )
; 11 mayo 1930 a 6 agosto 2002) era un holandés sistemas científico , programador , ingeniero de software , la ciencia ensayista , [9 ] y pionero en la informática . [10] Físico teórico de formación, trabajó como programador en el Mathematisch Centrum.(Ámsterdam) de 1952 a 1962. Profesor universitario durante gran parte de su vida, Dijkstra ocupó la Cátedra Centenaria de Schlumberger en Ciencias de la Computación en la Universidad de Texas en Austin desde 1984 hasta su jubilación en 1999. Fue profesor de matemáticas en Eindhoven. Universidad de Tecnología (1962–1984) y investigadora en la Corporación Burroughs (1973–1984).
; 11 mayo 1930 a 6 agosto 2002) era un holandés sistemas científico , programador , ingeniero de software , la ciencia ensayista , [9 ] y pionero en la informática . [10] Físico teórico de formación, trabajó como programador en el Mathematisch Centrum.(Ámsterdam) de 1952 a 1962. Profesor universitario durante gran parte de su vida, Dijkstra ocupó la Cátedra Centenaria de Schlumberger en Ciencias de la Computación en la Universidad de Texas en Austin desde 1984 hasta su jubilación en 1999. Fue profesor de matemáticas en Eindhoven. Universidad de Tecnología (1962–1984) y investigadora en la Corporación Burroughs (1973–1984).
Una de las figuras más influyentes de la generación fundadora de la ciencia de la computación, Dijkstra ayudó a dar forma a la nueva disciplina desde una perspectiva tanto de ingeniería como teórica . [11] [12] Sus contribuciones fundamentales cubren diversas áreas de la informática, que incluyen la construcción de compiladores , sistemas operativos, sistemas distribuidos , programación secuencial y concurrente, paradigma y metodología de programación, investigación de lenguaje de programación., diseño de programas, desarrollo de programas, verificación de programas, principios de ingeniería de software, algoritmos gráficos y fundamentos filosóficos de la programación de computadoras y ciencias de la computación. Muchos de sus trabajos son la fuente de nuevas áreas de investigación. Varios conceptos y problemas que ahora son estándar en informática se identificaron por primera vez por Dijkstra o nombres de oso acuñados por él. [13] [14] Como principal opositor de la visión mecanizadora de la informática, refutó el uso de los conceptos de "informática" y "ingeniería de software" como términos generales para las disciplinas académicas .
Hasta mediados de la década de los sesenta, la programación informática se consideraba más un arte (o un oficio) que una disciplina científica. En palabras de Harlan Mills (1986), "la programación [antes de la década de 1970] se consideraba como una actividad privada de resolución de rompecabezas al escribir instrucciones de computadora para funcionar como un programa". A fines de la década de 1960, la programación de computadoras estaba en un estado de crisis . Dijkstra fue uno de un pequeño grupo de académicos y programadores industriales que defendieron un nuevo estilo de programación para mejorar la calidad de los programas . Dijkstra, quien tenía experiencia en matemáticas y física, fue una de las fuerzas impulsoras detrás de la aceptación de la programación de computadoras como una disciplina científica. [15] [16] Él acuñó la frase "Programación estructurada "y durante la década de 1970 se convirtió en la nueva ortodoxia de programación. [17] [18] [19] Sus ideas sobre programación estructurada ayudaron a sentar las bases para el nacimiento y desarrollo de la disciplina profesional de la ingeniería de software , lo que permitió a los programadores organizar y administre proyectos de software cada vez más complejos. [20] [21] Como señaló Bertrand Meyer (2009), "La revolución en los puntos de vista de la programación iniciada por la iconoclasia de Dijkstra condujo a un movimiento conocido como programación estructurada, que abogó por un enfoque sistemático y racional para la construcción del programa. . La programación estructurada es la base de todo lo que se ha hecho desde la metodología de programación., incluida la programación orientada a objetos . " [22]
El estudio académico de la computación concurrente comenzó en la década de 1960, y Dijkstra (1965) fue reconocido como el primer artículo en este campo, identificando y resolviendo el problema de la exclusión mutua . [23] [24] También fue uno de los primeros pioneros de la investigación sobre los principios de la computación distribuida . Su trabajo fundamental sobre la concurrencia , los semáforos , la exclusión mutua, el punto muerto (abrazo mortal), la búsqueda de caminos más cortos en gráficos , tolerancia a fallos , autoestabilización.Entre otras muchas contribuciones se incluyen muchos de los pilares sobre los cuales se construye el campo de la computación distribuida. Poco antes de su muerte en 2002, recibió el premio ACM PODC Influent-Paper Award en computación distribuida por su trabajo sobre la autoestabilización de la computación del programa. Este premio anual pasó a llamarse Premio Dijkstra ( Premio Edsger W. Dijkstra en Computación Distribuida) al año siguiente, en su honor. [25] [26] [27] Como premio, patrocinado conjuntamente por el Simposio ACM sobre Principios de Computación Distribuida (PODC) y el Simposio Internacional EATCS sobre Computación Distribuida (DISC), reconoce que "Ningún otro individuo ha tenido una influencia mayor en la investigación de los principios de la computación distribuida".
Biografia [ editar ]
Primeros años [ editar ]
Edsger W. Dijkstra nació en Rotterdam . Su padre era un químico que era presidente de la Sociedad Química Holandesa; él enseñó química en una escuela secundaria y luego fue superintendente. Su madre era matemática, pero nunca tuvo un trabajo formal. [28] [29]
Dijkstra había considerado una carrera en la ley y esperaba representar a los Países Bajos en las Naciones Unidas . Sin embargo, después de graduarse de la escuela en 1948, por sugerencia de sus padres, estudió matemáticas y física y luego física teórica en la Universidad de Leiden . [11]
A principios de la década de 1950, las computadoras electrónicas eran una novedad. Dijkstra tropezó con su carrera por accidente y, a través de su supervisor, el profesor A. Haantjes, se reunió con Adriaan van Wijngaarden , el director del Departamento de Computación del Centro de Matemáticas de Ámsterdam , quien le ofreció un puesto a Dijkstra; se convirtió oficialmente en el primer "programador" de los Países Bajos en marzo de 1952. [11]
Durante algún tiempo, Dijkstra mantuvo su compromiso con la física, trabajando en ello en Leiden tres días de cada semana. Sin embargo, al aumentar la exposición a la informática, su enfoque comenzó a cambiar. Como recordó: [30]
Cuando Dijkstra se casó con María (Ria) C. Debets en 1957, fue requerido como parte de los ritos matrimoniales para declarar su profesión. Afirmó que era un programador, lo cual era inaceptable para las autoridades, ya que en ese momento no existía tal profesión en los Países Bajos. [31] [32]
En 1959 recibió su doctorado de la Universidad de Ámsterdam para una tesis titulada "Comunicación con una computadora automática", dedicada a una descripción del lenguaje ensamblador diseñado para la primera computadora comercial desarrollada en los Países Bajos, el X1. Su supervisor de tesis fue Van Wijngaarden. [13]
Mathematisch Centrum, Amsterdam [ editar ]
Desde 1952 hasta 1962, Dijkstra trabajó en el Mathematisch Centrum en Ámsterdam, [13] donde trabajó estrechamente con Bram Jan Loopstra y Carel S. Scholten , quien había sido contratado para construir una computadora. Su modo de interacción fue disciplinado: Primero decidirían sobre la interfaz entre el hardware y el software, escribiendo un manual de programación. Luego, los diseñadores de hardware tendrían que ser fieles a su parte del contrato, mientras que Dijkstra, el programador, escribiría software para la máquina inexistente. Dos de las lecciones que aprendió de esta experiencia fueron la importancia de una documentación clara, y que la depuración del programa se puede evitar en gran medida mediante un diseño cuidadoso. [11] Dijkstra formuló y resolvió el problema del camino más corto para una demostración en la inauguración oficial de la computadora ARMAC en 1956, pero, debido a la ausencia de revistas dedicadas a la computación automática, no publicó el resultado hasta 1959.
En el Centro de Matemáticas, Dijkstra y su colega Jaap Zonneveld desarrollaron un compilador para el lenguaje de programación ALGOL 60 ; tuvo una profunda influencia en su pensamiento posterior sobre la programación como una actividad científica. Él y Zonneveld habían completado la implementación del primer compilador ALGOL 60 en agosto de 1960, más de un año antes de que otro grupo produjera un compilador. [11]
Universidad Tecnológica de Eindhoven [ editar ]
En 1962, Dijkstra se mudó a Eindhoven , y más tarde a Nuenen , en el sur de los Países Bajos, donde se convirtió en profesor en el Departamento de Matemáticas de la Universidad de Tecnología de Eindhoven . [13] La universidad no tenía un departamento separado de informática y la cultura del departamento de matemáticas no le convenía particularmente. Dijkstra intentó construir un grupo de científicos informáticos que pudieran colaborar en la resolución de problemas. Este fue un modelo inusual de investigación para el Departamento de Matemáticas. [11] A finales de la década de 1960 construyó el sistema operativo THE (llamado así por la universidad, entonces conocido como Technische Hogeschool Eindhoven).), que ha influido en los diseños de los sistemas operativos posteriores a través del uso de la memoria virtual paginada basada en software. [33]
Burroughs Corporation [ editar ]
Dijkstra se unió a Burroughs Corporation, una empresa conocida en ese momento por la producción de computadoras basadas en una arquitectura de hardware innovadora, como su Investigadora en agosto de 1973. Sus funciones consistían en visitar algunos de los centros de investigación de la compañía varias veces al año y continuar su propia investigación. lo que hizo en el centro de investigación de Burroughs más pequeño, a saber, su estudio en el segundo piso de su casa en Nuenen. De hecho, Dijkstra fue el único investigador de Burroughs Corporation y trabajó para él desde su casa, viajando ocasionalmente a sus sucursales en los Estados Unidos. Como resultado, redujo su cita en la universidad a un día a la semana. Ese día, el martes, pronto se conoció como el día del famoso "Club de la tarde de los martes", un seminario durante el cual discutió con sus colegas artículos científicos, analizando todos los aspectos: notación, organización,La Universidad de Texas en Austin(EE. UU.), Una nueva 'sucursal' del Tuesday Afternoon Club surgió en Austin . [13]
Los años de Burroughs lo vieron en su momento más prolífico en la producción de artículos de investigación. Escribió casi 500 documentos en la serie EWD (descritos a continuación), la mayoría de ellos informes técnicos, para circulación privada dentro de un grupo selecto. [11]
La Universidad de Texas en Austin [ editar ]
Dijkstra aceptó la Cátedra del Centenario de Schlumberger en el Departamento de Ciencias de la Computación de la Universidad de Texas en Austin en 1984.
Últimos años [ editar ]
Dijkstra trabajó en Austin hasta su jubilación en noviembre de 1999. Para celebrar la ocasión y celebrar sus más de cuarenta años de contribuciones seminales a la informática , el Departamento de Ciencias de la Computación organizó un simposio, que tuvo lugar en su 70º cumpleaños en mayo de 2000. [11]
Dijkstra y su esposa regresaron de Austin a su casa original en Nuenen (Países Bajos), donde descubrieron que solo tenía meses para vivir. Dijo que quería retirarse en Austin, Texas , pero morir en los Países Bajos. Dijkstra murió el 6 de agosto de 2002 después de una larga lucha contra el cáncer. [34] Él y su esposa Maria (Ria) Debets fueron sobrevividos por sus tres hijos: Marcus, Femke y el informático Rutger M. Dijkstra.
Contribuciones científicas e impactos [ editar ]
Como pionero teórico temprano en muchas áreas de investigación de ciencias de la computación, Dijkstra ayudó a dar forma a la nueva disciplina desde una perspectiva tanto de ingeniería como académica . Muchos de sus trabajos son la fuente de nuevas áreas de investigación. Muchos conceptos que ahora son estándar en informática se identificaron por primera vez por Dijkstra y / o nombres de oso acuñados por él. Varios problemas importantes también fueron primero formulados y resueltos por él. Se realizó una encuesta en 1994 a más de mil profesores de ciencias de la computación para obtener una lista de los 38 trabajos académicos más influyentes en el campo, y Dijkstra es el autor de cinco artículos. [35] [36] [37]
Durante sus más de cuarenta años como científico informático, que incluyó posiciones tanto en el mundo académico como en la industria, Dijkstra realizó numerosas contribuciones fundamentales a muchas áreas de la informática, incluida la construcción de compiladores, sistemas operativos, programación concurrente (computación concurrente), programación distribuida (distribuida computación), paradigma y metodología de programación, investigación del lenguaje de programación, diseño de programas, desarrollo de programas, verificación de programas, principios de ingeniería de software, diseño de algoritmos y bases filosóficas de la programación de computadoras y ciencias de la computación. Además, Dijkstra estaba muy interesado en la enseñanza de ciencias de la computación y en las relaciones entre la ciencia de la computación académica y la industria del software.
Trabajo algorítmico [ editar ]
El trabajo algorítmico de Dijkstra (especialmente los algoritmos de grafos , algoritmos concurrentes y algoritmos distribuidos ) desempeña un papel importante en muchas áreas de la ciencia de la computación. De acuerdo con Leslie Lamport (2002), Dijkstra "inició el campo de los algoritmos concurrentes y distribuidos con su documento de 1965 MCC" Solución de un problema en el control de programación concurrente ", en el que primero declaró y resolvió el problema de exclusión mutua". Como explica Lamport, "ese papel es probablemente la razón por la que existe el PODC (...). Sigue siendo hasta hoy el papel más influyente en el campo. No ganó un Premio al Papel Influyente del PODCrefleja una separación artificial entre algoritmos concurrentes y distribuidos, una separación que nunca ha existido en el trabajo de Dijkstra ". [38]
En 1959, Dijkstra publicó en un artículo de 3 páginas 'Una nota sobre dos problemas relacionados con los gráficos' el algoritmopara encontrar la ruta más corta en un gráfico entre dos nodos dados, ahora llamado algoritmo de Dijkstra . Su impacto en los próximos 40 años se resume en el artículo de Mikkel Thorup , 'Rutas más cortas de una sola fuente no direccionadas con pesos enteros positivos en tiempo lineal' (1999): "Desde 1959, todos los desarrollos teóricos en SSSP [Rutas más cortas de una sola fuente] para gráficos generales dirigidos y no dirigidos se han basado en el algoritmo de Dijkstra ". El algoritmo de Dijkstra se usa en SPF, la ruta más corta primero , que se usa en los protocolos de enrutamiento OSPF e IS-IS.. Varios autores han propuesto varias modificaciones al algoritmo de Dijkstra utilizando heurística para reducir el tiempo de ejecución de la búsqueda de ruta más corta . Uno de los algoritmos heurísticos más utilizados es el algoritmo de búsqueda A * (descrito por primera vez por Peter Hart , Nils Nilsson y Bertram Raphael del Instituto de Investigación Stanford en 1968), [39] el objetivo principal es reducir el tiempo de ejecución al reducir el espacio de búsqueda . Dijkstra pensó en el problema de la ruta más corta cuando trabajaba en el Mathematical Center en Amsterdam en 1956 como programadorpara demostrar las capacidades de un nuevoordenador llamado ARMAC. Su objetivo era elegir tanto un problema como una respuesta (que sería producida por una computadora) que las personas no informáticas podrían entender. Diseñó el algoritmo de ruta más corta en unos 20 minutos sin ayuda de papel y bolígrafo, y más tarde lo implementó para ARMAC para un mapa de transporte ligeramente simplificado de 64 ciudades en los Países Bajos (de modo que 6 bits serían suficientes para representar la ciudad en el algoritmo). [40] Como recordó, en una entrevista publicada en 2001: [41]
Un año más tarde, se encontró con otro problema de los ingenieros de hardware que trabajan en la próxima computadora del instituto: minimizar la cantidad de cable necesario para conectar los pines en el panel posterior de la máquina. Como solución, volvió a descubrir el algoritmo conocido como algoritmo de árbol de expansión mínima de Prim . El algoritmo de Prim fue desarrollado originalmente en 1930 por el matemático checo Vojtěch Jarník [42] y luego redescubierto y publicado de forma independiente por Robert C. Prim en 1957 [43] y Dijkstra en 1959. [44] Por lo tanto, a veces también se lo denomina algoritmo DJP . [45]
En 1961, Dijkstra describió por primera vez el algoritmo de derivación , un método para analizar expresiones matemáticas especificadas en notación de infijo , en el informe Mathematisch Centrum . [46] Se puede utilizar para producir resultados en notación polaca inversa (RPN) o como un árbol de sintaxis abstracta (AST). El algoritmo se denominó algoritmo de "patio de maniobras" porque su operación se asemeja a la de un patio de maniobras del ferrocarril . El algoritmo de derivación se usa comúnmente para implementar analizadores de precedencia de operadores .
En 1962 o 1963, Dijkstra propuso el mecanismo de semáforo para el algoritmo de exclusión mutua para n procesos (una generalización del algoritmo de Dekker ), que fue probablemente el primer algoritmo concurrentepublicado y que introdujo una nueva área de investigación algorítmica. También identificó el problema del punto muerto y propuso el algoritmo bancario que evita el punto muerto .
En 1974, Dijkstra presentó tres algoritmos de autoestabilización para la exclusión mutua en un anillo. Se considera que el trabajo de Dijkstra es el primero en introducir y demostrar el concepto de autoestabilización . [47]
A mediados de la década de 1970, Dijkstra (junto con otros autores) introdujo dos abstracciones útiles (mutador y recolector) para el estudio de la recolección de basura . El mutador abstrae el proceso que realiza el cálculo, incluida la asignación de una nueva celda de almacenamiento. El recolector es el proceso que automáticamente reclama basura. Además, este documento proporciona una formalización de la " marca de tres colores " que es básica para la recolección incremental de basura. [48] [49]
A principios de la década de 1980, Dijkstra y Carel S. Scholten propusieron el algoritmo Dijkstra-Scholten para detectar la terminación en sistemas distribuidos .
En 1981, Dijkstra desarrolló smoothsort , un algoritmo de clasificación basado en comparación y una variación de heapsort .
Construcción de compiladores y lenguaje de programación de investigación [ editar ]
Dijkstra era conocido por ser un fan de ALGOL 60 , y trabajó en el equipo que implementó el primer compilador para ese idioma. Participó estrechamente en el desarrollo, realización y popularización de ALGOL 60. Como discutió Peter Naur en el artículo 'El lado europeo de la última fase del desarrollo de ALGOL 60', en las Actas de la Primera Conferencia ACM SIGPLAN sobre Historia de los Lenguajes de ProgramaciónEn enero de 1978, Dijkstra participó en el período 1958–1959 en varias reuniones que culminaron con la publicación del informe que define el lenguaje ALGOL 60. El nombre de Dijkstra no aparece en la lista de los 13 autores del informe final. Aparentemente, eventualmente dejó el comité porque no podía estar de acuerdo con las opiniones de la mayoría. Aún así, mientras estaba en el Mathematisch Centrum (Amsterdam), escribió conjuntamente con Jaap Zonneveld el primer compilador de ALGOL 60 . Dijkstra y Zonneveld, quienes colaboraron en el compilador, acordaron no afeitarse hasta que se completara el proyecto; mientras que Zonneveld se afeitó poco después, Dijkstra mantuvo su barba por el resto de su vida. [50]
ALGOL fue el resultado de una colaboración de comités americanos y europeos. ALGOL 60 (abreviatura de ALGOrithmic Language 1960) es miembro de la familia ALGOL de lenguajes de programación informática. Siguió de ALGOL 58 e inspiró muchos idiomas que lo siguieron. Que dio lugar a muchos otros lenguajes de programación, incluyendo BCPL , B , Pascal , Simula y C . [51] Algol 60 era un lenguaje informático diseñado sofisticadamente y brindaba una gran cantidad de desafíos de implementación hasta ahora desconocidos . Como Bjarne Stroustrupseñala, "un problema con Algol60 fue que nadie sabía cómo implementarlo". [52] Un nuevo desafío importante en la implementación de Algol 60 fue la asignación en tiempo de ejecución y la gestión de datos. En 1960, Dijkstra y Zonneveld mostraron cómo los procedimientos recursivos podrían ejecutarse usando una pila de registros de activación en tiempo de ejecución, y cómo acceder de manera eficiente a los identificadores de los ámbitos que contienen estáticamente utilizando la llamada "visualización". [53] El compilador ALGOL 60 fue uno de los primeros en apoyar la recursión [54] empleando un método novedoso para hacerlo. El libro corto de Dijkstra Primer of Algol 60 Programming , publicado originalmente en 1962, fue la referencia estándar para el idioma durante varios años.
No hay comentarios:
Publicar un comentario