Edsger Wybe Dijkstra ( / ˈ d aɪ k s t r ə / DYKE -strə , holandés: [ˈɛtsxər ˈʋibə ˈdɛikstraː] ; 11 de mayo de 1930 – 6 de agosto de 2002) fue uninformático,programador,ingeniero de software, matemático yensayista.[1][2]
Nacido en Róterdam , Países Bajos , Dijkstra estudió matemáticas y física y luego física teórica en la Universidad de Leiden . Adriaan van Wijngaarden le ofreció un trabajo como el primer programador de computadoras en los Países Bajos en el Centro de Matemáticas de Ámsterdam , donde trabajó desde 1952 hasta 1962. Formuló y resolvió el problema del camino más corto en 1956, y en 1960 desarrolló el primer compilador para el lenguaje de programación ALGOL 60 junto con su colega Jaap A. Zonneveld . En 1962 se mudó a Eindhoven , y más tarde a Nuenen , donde se convirtió en profesor en el Departamento de Matemáticas de la Technische Hogeschool Eindhoven . A fines de la década de 1960 construyó el sistema de multiprogramación THE , que influyó en los diseños de sistemas posteriores mediante el uso de memoria virtual paginada basada en software. Dijkstra se incorporó a Burroughs Corporation como su único investigador en agosto de 1973. Durante sus años en Burroughs, alcanzó su máximo rendimiento en cuanto a la producción de artículos de investigación. Escribió casi 500 documentos de la serie "EWD", la mayoría de ellos informes técnicos, para su distribución privada dentro de un grupo selecto.
Dijkstra aceptó la Cátedra Centenario de Schlumberger en el Departamento de Ciencias de la Computación de la Universidad de Texas en Austin en 1984, trabajando en Austin, Texas , hasta su jubilación en noviembre de 1999. Él y su esposa regresaron de Austin a su casa original en Nuenen, donde murió el 6 de agosto de 2002 después de una larga lucha contra el cáncer. [3]
Recibió el premio Turing en 1972 por sus contribuciones fundamentales al desarrollo de lenguajes de programación estructurados . Poco antes de su muerte, recibió el premio ACM PODC Influential Paper Award en computación distribuida por su trabajo sobre la autoestabilización de la computación de programas. Este premio anual pasó a llamarse premio Dijkstra al año siguiente, en su honor.
Edsger W. Dijkstra nació en Róterdam . Su padre era químico y presidente de la Sociedad Química Holandesa ; enseñó química en una escuela secundaria y más tarde fue su superintendente. Su madre era matemática, pero nunca tuvo un trabajo formal. [4] [5]
Dijkstra había considerado una carrera en derecho 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 . [6]
A principios de los años 50, las computadoras electrónicas eran una novedad. Dijkstra se topó con su carrera por casualidad y, a través de su supervisor, el profesor Johannes Haantjes , conoció a Adriaan van Wijngaarden , el director del Departamento de Computación del Centro de Matemáticas de Ámsterdam , quien le ofreció un trabajo; Dijkstra se convirtió oficialmente en el primer "programador" de los Países Bajos en marzo de 1952. [6]
Dijkstra siguió comprometido con la física durante algún tiempo, trabajando en ella en Leiden tres días a la semana. Sin embargo, a medida que fue aumentando su exposición a la informática, su enfoque comenzó a cambiar. Como él mismo recuerda: [7]
Después de haber programado durante unos tres años, tuve una discusión con A. van Wijngaarden, que entonces era mi jefe en el Centro de Matemáticas de Ámsterdam, una discusión por la que le estaré agradecido mientras viva. La cuestión era que se suponía que debía estudiar física teórica en la Universidad de Leiden simultáneamente, y como me resultaba cada vez más difícil combinar las dos actividades, tuve que decidirme: o bien dejar de programar y convertirme en un físico teórico respetable, o bien continuar mis estudios de física hasta su finalización formal, con un mínimo de esfuerzo, y convertirme en... ¿qué? ¿Un programador? Pero ¿era ésa una profesión respetable? Después de todo, ¿qué era la programación? ¿Dónde estaba el sólido cuerpo de conocimientos que pudiera sustentarla como una disciplina intelectualmente respetable? Recuerdo con toda claridad cómo envidiaba a mis colegas del sector del hardware, que, cuando les preguntaban por su competencia profesional, al menos podían señalar que sabían todo sobre válvulas, amplificadores y demás, mientras que yo pensaba que, al ser interrogado, me quedaría con las manos vacías. Lleno de dudas, llamé a la puerta del despacho de Van Wijngaarden y le pregunté si podía "hablar con él un momento"; cuando salí de su despacho varias horas más tarde, yo era otra persona. Después de haber escuchado pacientemente mis problemas, estuvo de acuerdo en que hasta ese momento no había mucha disciplina de programación, pero luego continuó explicando tranquilamente que los ordenadores automáticos habían llegado para quedarse, que estábamos sólo en el comienzo y que no podía ser yo una de las personas llamadas a hacer de la programación una disciplina respetable en los años venideros. Este fue un punto de inflexión en mi vida y completé mis estudios de física formalmente lo más rápido que pude.
— Edsger Dijkstra, El humilde programador (EWD340), Comunicaciones de la ACM
Cuando Dijkstra se casó con Maria "Ria" C. Debets en 1957, se le exigió, como parte de los ritos nupciales, que declarara su profesión. Declaró que era programador, lo cual era inaceptable para las autoridades, ya que en aquel entonces no existía esa profesión en los Países Bajos. [7] [8]
En 1959, recibió su doctorado de la Universidad de Ámsterdam con una tesis titulada 'Comunicación con una computadora automática', [9] dedicada a una descripción del lenguaje ensamblador diseñado para la primera computadora comercial desarrollada en los Países Bajos, la Electrologica X1 . Su supervisor de tesis fue Van Wijngaarden. [10]
Desde 1952 hasta 1962, Dijkstra trabajó en el Mathematisch Centrum de Ámsterdam, [10] donde colaboró estrechamente con Bram Jan Loopstra y Carel S. Scholten , que habían sido contratados para construir un ordenador. Su modo de interacción era disciplinado: primero decidían la interfaz entre el hardware y el software, escribiendo un manual de programación. Luego, los diseñadores de hardware tenían que ser fieles a su parte del contrato, mientras que Dijkstra, el programador, escribía el 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 de programas se puede evitar en gran medida mediante un diseño cuidadoso. [6] Dijkstra formuló y resolvió el problema del camino más corto para una demostración en la inauguración oficial del ordenador ARMAC en 1956. Debido a la ausencia de revistas dedicadas a la computación automática, no publicó el resultado hasta 1959.
En el Centro Matemático, Dijkstra y su colega Jaap Zonneveld desarrollaron el primer compilador para el lenguaje de programación ALGOL 60 en agosto de 1960, más de un año antes de que otro grupo produjera un compilador. [6] ALGOL 60 es conocido como un avance clave en el surgimiento de la programación estructurada.
En 1962, Dijkstra se trasladó 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 Tecnológica de Eindhoven . [10] La universidad no tenía un departamento de informática independiente y la cultura del departamento de matemáticas no le convenía especialmente. Dijkstra intentó formar un grupo de científicos informáticos que pudieran colaborar en la resolución de problemas. Este era un modelo de investigación inusual para el Departamento de Matemáticas. [6] A finales de la década de 1960, construyó el sistema operativo THE (nombrado por la universidad, entonces conocida como Technische Hogeschool Eindhoven ), que ha influido en los diseños de sistemas operativos posteriores a través de su uso de memoria virtual paginada basada en software. [11]
Dijkstra se incorporó a la Burroughs Corporation —una empresa conocida entonces por producir ordenadores basados en una innovadora arquitectura de hardware— como investigador en agosto de 1973. Sus funciones consistían en visitar algunos de los centros de investigación de la firma unas cuantas veces al año y llevar a cabo su propia investigación, que realizaba en la instalación de investigación más pequeña de Burroughs, es decir, su estudio en el segundo piso de su casa en Nuenen. De hecho, Dijkstra era el único investigador de Burroughs y trabajaba para ella desde casa, viajando ocasionalmente a sus sucursales en Estados Unidos. Como resultado, redujo su cita en la universidad a un día a la semana. Ese día, el martes, pronto se hizo conocido como el día del famoso 'Club de los Martes por la Tarde', un seminario durante el cual discutía con sus colegas artículos científicos, analizando todos los aspectos: notación, organización, presentación, lenguaje, contenido, etc. Poco después de mudarse en 1984 a la Universidad de Texas en Austin (EE. UU.), surgió una nueva 'rama' del Club de los Martes por la Tarde en Austin, Texas . [10]
Los años de Burroughs fueron los más prolíficos en cuanto a la producción de artículos de investigación. Escribió casi 500 documentos de la serie EWD (descrita más adelante), la mayoría de ellos informes técnicos, para su distribución privada dentro de un grupo selecto. [6]
Dijkstra aceptó la Cátedra Centenario de Schlumberger en el Departamento de Ciencias de la Computación de la Universidad de Texas en Austin en 1984.
Dijkstra trabajó en Austin hasta su jubilación en noviembre de 1999. Para conmemorar la ocasión y celebrar sus más de cuarenta años de contribuciones fundamentales a la ciencia 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. [6]
Dijkstra y su esposa regresaron de Austin a su casa original en Nuenen, Países Bajos, donde descubrió que solo le quedaban unos meses de vida. 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. [3] [12] [13] [14] A él y a su esposa les sobrevivieron sus tres hijos: Marcus, Femke y el científico informático Rutger M. Dijkstra. [15]
Difícilmente se puede culpar al MIT por no tomar nota de un oscuro científico informático de un pequeño pueblo de los Países Bajos.
—Dijkstra , dijo sobre sí mismo en Nuenen a mediados de la década de 1960. [17]
En el mundo de la informática, Dijkstra es conocido como un "personaje". En el prefacio de su libro A Discipline of Programming (1976) afirmaba lo siguiente: "No ofrezco explicación ni disculpa por la ausencia de bibliografía". De hecho, la mayoría de sus artículos y libros no tienen referencias en absoluto. [10] Dijkstra eligió esta forma de trabajar para preservar su autosuficiencia. [18]
Como profesor universitario durante gran parte de su vida, Dijkstra vio la enseñanza no solo como una actividad obligatoria sino como un esfuerzo de investigación serio. [6] Su enfoque de la enseñanza era poco convencional. [19] Su estilo de dar clases ha sido descrito como idiosincrásico. Cuando daba clases, las largas pausas entre oraciones a menudo se han atribuido al hecho de que el inglés no es la primera lengua de Dijkstra. Sin embargo, las pausas también le sirvieron como una forma de pensar con rapidez y se lo consideraba un pensador rápido y profundo mientras impartía clases. Sus cursos para estudiantes en Austin tenían poco que ver con la informática, pero trataban sobre la presentación de pruebas matemáticas. [10] Al comienzo de cada semestre, tomaba una foto de cada uno de sus estudiantes para memorizar sus nombres. Nunca seguía un libro de texto , con la posible excepción del suyo mientras lo estaba preparando. Cuando daba clases, escribía pruebas con tiza en una pizarra en lugar de usar transparencias. Invitaba a los estudiantes a sugerir ideas, que luego él exploraba o se negaba a explorar porque violaban algunos de sus principios. Asignaba problemas desafiantes para hacer en casa y estudiaba a fondo las soluciones de sus estudiantes. Realizaba sus exámenes finales de forma oral, durante toda una semana. Cada estudiante era examinado en la oficina o en su casa, y cada examen duraba varias horas. [6]
Dijkstra también fue muy original en su forma de evaluar la capacidad de las personas para un trabajo. Cuando Vladimir Lifschitz llegó a Austin en 1990 para una entrevista de trabajo, Dijkstra le dio un rompecabezas. Lifschitz lo resolvió y ha estado trabajando en Austin desde entonces. [10]
Durante muchas décadas evitó el uso de computadoras en su propio trabajo. Incluso después de sucumbir al estímulo de sus colegas de la UT y adquirir una computadora Macintosh , la utilizó solo para el correo electrónico y para navegar por la World Wide Web. [20] Dijkstra nunca escribió sus artículos utilizando una computadora. Prefirió confiar en su máquina de escribir y más tarde en su pluma Montblanc . [10] El instrumento de escritura favorito de Dijkstra era la pluma estilográfica Montblanc Meisterstück .
No le hacían ningún favor los procesadores de textos , pues creía que uno debería poder escribir una carta o un artículo sin borradores, reescrituras ni ninguna edición significativa. Lo trabajaba todo en su cabeza antes de ponerlo en papel y una vez mencionó que cuando era estudiante de física resolvía sus problemas de tarea en su cabeza mientras caminaba por las calles de Leiden . [6] La mayoría de las publicaciones de Dijkstra fueron escritas por él solo. Nunca tuvo una secretaria y se ocupó de toda su correspondencia solo. [10] Cuando sus colegas prepararon un Festschrift para su sexagésimo cumpleaños, publicado por Springer-Verlag , se tomó la molestia de agradecer a cada uno de los 61 colaboradores por separado, en una carta escrita a mano. [10]
En El humilde programador (1972), Dijkstra escribió: "No debemos olvidar que no es nuestro negocio [el de los informáticos] crear programas, es nuestro negocio diseñar clases de cálculos que muestren un comportamiento deseado".
Dijkstra también se opuso a la inclusión de la ingeniería de software bajo el paraguas de la informática académica. Escribió que, "Así como la economía es conocida como 'La Ciencia Miserable', la ingeniería de software debería ser conocida como 'La Disciplina Condenada', condenada porque ni siquiera puede acercarse a su objetivo, ya que su objetivo es contradictorio en sí mismo". Y "la ingeniería de software ha aceptado como su carta fundacional 'Cómo programar si no puedes'". [21]
Dijkstra llevó una vida modesta, hasta el punto de ser espartana. [10] La casa que él y su esposa tenían en Nuenen era sencilla, pequeña y sin pretensiones. No tenía televisión, reproductor de vídeo ni teléfono móvil y no iba al cine. [10] Tocaba el piano y, mientras estaba en Austin, le gustaba ir a conciertos. Oyente entusiasta de la música clásica , el compositor favorito de Dijkstra era Mozart . [6]
A lo largo de la carrera de Dijkstra, su obra se caracterizó por la elegancia y la economía. [10] Dijkstra, un escritor prolífico (especialmente como ensayista), escribió más de 1.300 artículos, muchos de ellos escritos a mano con su caligrafía precisa. Eran ensayos y parábolas; cuentos de hadas y advertencias; explicaciones exhaustivas y pretextos pedagógicos. La mayoría trataban sobre matemáticas y ciencias de la computación; otros eran informes de viajes que revelaban más sobre su autor que sobre las personas y los lugares visitados. Tenía la costumbre de copiar cada artículo y hacerlo circular entre un pequeño grupo de colegas que, a su vez, los copiaban y los enviaban a otro grupo limitado de científicos. [22]
Dijkstra era conocido por su hábito de componer cuidadosamente manuscritos con su pluma estilográfica . Los manuscritos se llaman EWD, ya que Dijkstra los numeró con EWD , sus iniciales, como prefijo. Según el propio Dijkstra, los EWD comenzaron cuando se mudó del Centro de Matemáticas de Ámsterdam a la Universidad Tecnológica de Eindhoven (entonces Technische Hogeschool Eindhoven). Después de ir a Eindhoven , Dijkstra experimentó un bloqueo de escritor durante más de un año. Distribuyó fotocopias de un nuevo EWD entre sus colegas. Muchos destinatarios fotocopiaron y reenviaron sus copias, por lo que los EWD se difundieron por toda la comunidad informática internacional. Los temas eran informática y matemáticas, e incluían informes de viajes, cartas y discursos. Estos breves artículos abarcan un período de 40 años. Casi todos los EWD que aparecieron después de 1972 fueron escritos a mano. Rara vez tienen más de 15 páginas y están numerados consecutivamente. El último, el número 1318, es del 14 de abril de 2002. En informática se conocen como informes EWD o, simplemente, EWD. Se han escaneado más de 1300 EWD y se ha transcrito un número cada vez mayor para facilitar la búsqueda. Están disponibles en línea en el archivo Dijkstra de la Universidad de Texas. [23]
Su interés por la simplicidad surgió a temprana edad y bajo la guía de su madre. En cierta ocasión dijo que le había preguntado a su madre si la trigonometría era un tema difícil. Ella le respondió que debía aprender todas las fórmulas y que, además, si necesitaba más de cinco líneas para demostrar algo, estaba en el camino equivocado. [24]
Dijkstra era famoso por su ingenio, elocuencia, rudeza, brusquedad y a menudo crueldad con sus colegas profesionales, y por su habilidad con las palabras, como en su observación: "La cuestión de si las máquinas pueden pensar (...) es tan relevante como la cuestión de si los submarinos pueden nadar". [25] Su consejo a un investigador prometedor, que le preguntó cómo seleccionar un tema de investigación, fue la frase: "Haz sólo lo que sólo tú puedes hacer". [6] Dijkstra también era conocido por su crítica vocal y su ausencia de habilidades sociales al interactuar con colegas. Como visionario abierto y crítico, se opuso firmemente a la enseñanza de BASIC . [26]
En muchos de sus ensayos más ingeniosos, Dijkstra describió una empresa ficticia de la que era presidente. La empresa se llamaba Mathematics, Inc., una empresa que él imaginaba que comercializaba la producción de teoremas matemáticos de la misma manera que las empresas de software habían comercializado la producción de programas informáticos. Inventó una serie de actividades y desafíos de Mathematics Inc. y los documentó en varios artículos de la serie EWD. La empresa imaginaria había producido una prueba de la hipótesis de Riemann , pero luego tuvo grandes dificultades para cobrar regalías a los matemáticos que habían demostrado resultados asumiendo la hipótesis de Riemann. La prueba en sí era un secreto comercial . [27] Muchas de las pruebas de la empresa se lanzaron a toda prisa y luego gran parte del esfuerzo de la empresa tuvo que dedicarse al mantenimiento . [28] Un esfuerzo más exitoso fue la prueba estándar para el teorema de Pitágoras , que reemplazó las más de 100 pruebas incompatibles existentes. [29] Dijkstra describió a Mathematics Inc. como "el negocio más emocionante y más miserable jamás concebido". [27] EWD 443 (1974) describe su empresa ficticia como poseedora de más del 75% de la participación de mercado mundial. [30] [31]
Dijkstra ganó el premio Turing en 1972 por su defensa de la programación estructurada, un paradigma de programación que hace uso del flujo de control estructurado en lugar de saltos no estructurados a diferentes secciones de un programa mediante instrucciones Goto . Su carta de 1968 al editor de Communications of ACM, " La instrucción Go To se considera dañina " , provocó un gran debate. Los programadores modernos generalmente se adhieren al paradigma de la programación estructurada. [32]
Entre sus contribuciones más famosas a la informática se encuentra el algoritmo del camino más corto , conocido como algoritmo de Dijkstra , ampliamente enseñado en los cursos de informática de grado modernos. Sus otras contribuciones incluyen el algoritmo de la yarda de maniobras ; el sistema de multiprogramación THE , un importante ejemplo temprano de estructuración de un sistema como un conjunto de capas; el algoritmo del banquero ; y la construcción del semáforo para coordinar múltiples procesadores y programas. Otro concepto formulado por Dijkstra en el campo de la computación distribuida es el de autoestabilización , una forma alternativa de garantizar la confiabilidad del sistema. El algoritmo de Dijkstra se utiliza en SPF, Shortest Path First , que se utiliza en los protocolos de enrutamiento OSPF e IS-IS . [33] [34]
Entre los premios y honores que recibió Dijkstra se encuentran: [20]
En 1969, la British Computer Society (BCS) recibió la aprobación para un premio y una beca, Distinguished Fellow of the British Computer Society (DFBCS), que se otorgaría según el artículo 7 de su carta real . En 1971, se realizó la primera elección, y Dijkstra fue elegido. [39]
En 1990, con motivo del 60º cumpleaños de Dijkstra, el Departamento de Ciencias Informáticas (UTCS) de la Universidad de Texas en Austin organizó un seminario de dos días en su honor. Los conferenciantes vinieron de todos los Estados Unidos y Europa, y un grupo de científicos informáticos contribuyó con artículos de investigación que se editaron en un libro. [40]
En 2002, la Fundación C&C de Japón reconoció a Dijkstra "por sus contribuciones pioneras al establecimiento de la base científica para el software informático a través de la investigación creativa en teoría básica del software, teoría de algoritmos, programación estructurada y semáforos". Dijkstra estaba vivo para recibir la noticia del premio, pero su familia lo aceptó en una ceremonia de entrega de premios después de su muerte.
Poco antes de su muerte en 2002, Dijkstra recibió el premio ACM PODC Influential-Paper Award en computación distribuida por su trabajo sobre la autoestabilización de la computación de programas. Este premio anual pasó a llamarse Premio Dijkstra ( Premio Edsger W. Dijkstra en Computación Distribuida ) al año siguiente en su honor.
El premio Dijkstra por logros académicos sobresalientes en informática ( Universidad Loyola de Chicago , Departamento de Informática) lleva el nombre de Edsger W. Dijkstra. A partir de 2005, este premio reconoce el mejor desempeño académico de un estudiante de informática que se gradúa. La selección se basa en el promedio de calificaciones de todos los cursos principales y la elección por parte de la facultad del departamento. [41]
El Departamento de Ciencias de la Computación (UTCS) de la Universidad de Texas en Austin fue el anfitrión de la conferencia inaugural Edsger W. Dijkstra Memorial el 12 de octubre de 2010. Tony Hoare , profesor emérito de Oxford e investigador principal de Microsoft Research, fue el orador del evento. Esta serie de conferencias fue posible gracias a una generosa subvención de Schlumberger para honrar la memoria de Dijkstra.
Alan M. Turing pensó en criterios para resolver la cuestión de si las máquinas pueden pensar, una cuestión de la que ahora sabemos que es tan relevante como la cuestión de si los submarinos pueden nadar.(transcripción), 1984
