Dijkstra
Dijkstra nació el 11 de mayo de 1930 en una familia intelectual en Rotterdam, Países Bajos. Era el tercero de cuatro hermanos y hermanas. Su padre era un químico e inventor que se desempeñó como presidente de la Sociedad Química Holandesa. Su madre es matemática. Diseñó e implementó con éxito un algoritmo eficiente para encontrar el camino más corto entre dos ubicaciones con obstáculos. Este algoritmo se denominó "algoritmo de Dijkstra" y resolvió un problema muy crítico en robótica, es decir, el problema de planificación de la ruta de movimiento. Se utiliza ampliamente en la actualidad y se considera un ejemplo exitoso del uso del "método codicioso" (método codicioso, también conocido como algoritmo codicioso) para diseñar algoritmos.
Nombre chino: Edsgar Dijkstra
Nombre extranjero: Edsger Wybe Dijkstra
Nacionalidad: Países Bajos
Lugar de nacimiento: Rotterdam, Países Bajos
Fecha de nacimiento: 11 de mayo de 1930
Fecha de muerte: 6 de agosto de 2002
Ocupación: Informático
Institución de graduación: Leiden Universidad, Universidad de Cambridge
Principales logros: Diseño del algoritmo de Dijkstra
Trabajos representativos: "Introducción a la programación Algol60" y "Métodos de programación" 》
Introducción
Edsgar Dijkstra
——El maestro en informática que fue el primero en darse cuenta de que "goto es dañino"
Uno de los ganadores del primer premio Computer Pioneer Award fue Edsgar Wybe Dijkstra, un informático holandés. Dijkstra es famoso por ser el primero en señalar que "goto es perjudicial" y por ser pionero en la programación estructurada. De hecho, sus aportaciones a la informática no se limitaron a técnicas de programación. Dijkstra ha realizado muchas creaciones y ha realizado contribuciones destacadas en muchos aspectos de los algoritmos y la teoría de algoritmos, compiladores y sistemas operativos. En 1983, para conmemorar el 25º aniversario de Comunicaciones de ACM, ACM seleccionó 25 artículos emblemáticos publicados en la revista en el cuarto de siglo comprendido entre 1958 y 1982, uno por cada año, y Dijkstra fue uno de ellos. Se seleccionaron dos artículos, y él es uno de los dos únicos académicos (el otro es el académico británico C.A.R. Hoare, que también es el ganador del premio Computer Pioneer Award).
Logros de la vida
Dijkstra nació el 11 de mayo de 1930 en una familia intelectual en Rotterdam, Países Bajos. Era el tercero entre cuatro hermanos y hermanas. Su padre era un químico e inventor que se desempeñó como presidente de la Sociedad Química Holandesa. Su madre es matemática.
La infancia de Dijkstra transcurrió bajo el talón de hierro de las fuerzas de ocupación fascistas alemanas. Debido a la escasez de alimentos, lo enviaron a vivir con un amigo de su padre en el campo. Después de la rendición de la Alemania nazi, una Dijkstra muy débil se reunió con su familia en julio de 1945. Dijkstra originalmente planeó estudiar derecho y trabajar en las Naciones Unidas para mantener la paz mundial después de graduarse. Pero cuando se graduó de la escuela secundaria, sus calificaciones en matemáticas, física y química fueron particularmente buenas, por lo que su padre lo convenció de ingresar a la Universidad de Leiden en 1948 para estudiar matemáticas y física. Mientras estudiaba física teórica, Dijkstra descubrió que muchos problemas en este campo requerían una gran cantidad de cálculos complejos, por lo que decidió aprender programación informática. En 1951, viajó por su cuenta al Reino Unido para asistir a una clase de formación en programación organizada por la Universidad de Cambridge, donde estudió EDSAC (Electronic Delay Storage Automatic Calculator), el primer ordenador del mundo diseñado y desarrollado por Wilkes, otro ganador del primer Premio Computer Pioneer (Método de programación en una computadora electrónica con programa almacenado), que lo convirtió en uno de los primeros programadores del mundo. Al año siguiente, el Centro de Matemáticas de Ámsterdam se enteró de esta situación y le propuso contratarlo como programador a tiempo parcial. Al principio, Dijkstra dudaba, porque en aquella época no existía en el mundo el concepto de "programador".
A. van Wijingaarden (1916-1987), director del Departamento de Computación del Centro de Matemáticas, uno de los diseñadores del lenguaje Algol y pionero de la tecnología informática holandesa, lo propuso para resolver el problema de la dependencia del contexto al diseñar Algol68 Inventó una nueva gramática con una gran capacidad descriptiva, llamada gramática de dos niveles, también conocida como gramática W. Fue uno de los ganadores del premio Computer Pioneer en 1986 y también enseñó a N, otro ganador del primer Computer Pioneer. Award. (La investigación de Wirth ha tenido un impacto) le dijo que aunque la programación aún no se ha convertido en una disciplina y no se toma en serio, dado que las computadoras ya existen y se encuentran en una etapa pionera, es posible que en el futuro la programación sea una disciplina respetada. . Estas palabras conmovieron a Dijkstra y le hicieron aceptar el puesto. Cuanto más trabajaba, más interesado se volvía. De esta manera, terminó sus estudios en la Universidad de Leiden en el segundo año y se convirtió en miembro del personal de tiempo completo del Centro de Matemáticas. Desde entonces, ha entrado en el campo de las computadoras y, como predijo Viking Gerten, se ha convertido gradualmente en un conocido experto en el campo, creando muchas "primicias".
En 1956, diseñó e implementó con éxito un algoritmo eficiente para encontrar el camino más corto entre dos ubicaciones con obstáculos. Este algoritmo fue denominado "algoritmo de Dijkstra". Resuelve un problema muy crítico en robótica. El problema de planificación de la trayectoria del movimiento todavía se utiliza ampliamente en la actualidad y se considera un ejemplo exitoso del uso del "método codicioso" para diseñar algoritmos.
En 1959, cuando el Centro de Matemáticas estaba actualizando su computadora ARMAC original, Dijkstra diseñó un programa de procesamiento que resolvió con éxito la cuestión de la "interrupción en tiempo real". La tesis doctoral de Dijkstra se completó sobre este tema y se doctoró defendiendo su tesis en la Universidad de Ámsterdam.
En agosto de 1960, poco más de medio año después del lanzamiento del texto Algol60, Dijkstra y su colega J.A Zonneveld en el Centro de Matemáticas tomaron la iniciativa en la realización del primer compilador Algol60 del mundo. un año antes que académicos de otros países europeos y americanos implementaran Algol60. Este logro despertó el asombro de los estudiosos de la informática de todo el mundo y, por tanto, estableció la posición de Dijkstra en la comunidad científica como un estudioso de la informática de clase mundial.
En 1962, Dijkstra dejó el Centro de Matemáticas y entró en la Universidad Técnica de Eindhoven, en el sur de los Países Bajos, como profesor de matemáticas. Aquí se desarrolló, diseñó e implementó la computadora X86 con un sistema de multiprogramación: THEMultiprogrammingSystem. THE es la abreviatura de Technische Hoogeschool Eindhoven en holandés. La serie de métodos y tecnologías propuestos por Dijkstra en THE system sentó las bases para los sistemas operativos informáticos, ideas y conceptos especialmente importantes como la arquitectura multicapa y los mecanismos de exclusión mutua entre procesos secuenciales. Fue propuesto por primera vez por Dijkstra en THE y adoptado por. sistemas operativos posteriores como UNIX. Para determinar si un proceso puede ocupar el procesador en el caso de un solo procesador, Dijkstra dividió cada proceso en "listo", "en ejecución" y "bloqueando" tres estados de trabajo. Dado que como máximo un proceso puede utilizar el procesador a la vez, el proceso que ocupa el procesador se denomina proceso "en ejecución". Cuando un proceso tiene las condiciones para usar un procesador, pero actualmente no hay ningún procesador para usar, el proceso se coloca en el estado "listo". Cuando el proceso en ejecución no puede continuar ejecutándose por algún motivo, se detiene su procesamiento de ocupación. .
En cuanto a la sincronización mutuamente restrictiva (sincronización, lo que significa que para evitar errores, cuando un proceso accede a datos compartidos, otro proceso no accede a los datos) y exclusión mutua (mutuamente) entre todos los procesos que se ejecutan simultáneamente en el sistema -exclusiva. , lo que significa que dos procesos no pueden usar el mismo recurso reutilizable en una sección crítica al mismo tiempo, como los buffers de lectura y escritura. Dijkstra usa inteligentemente el "semáforo" en el sistema de control de operación del tren. ) concepto para resolverlo. El llamado semáforo es en realidad una unidad de almacenamiento que representa un determinado recurso que se utiliza para controlar el estado del proceso. Por ejemplo, P1 y P2 son dos procesos que envían datos al búfer B y leen datos del búfer B respectivamente. Para evitar que se produzcan errores cuando estos dos procesos son concurrentes, Dijkstra diseñó un mecanismo de sincronización llamado "Operación PV", P. operación y operación V son dos primitivas del sistema operativo que no se interrumpen durante la ejecución. Cuando se ejecuta la operación P P(S), el valor del semáforo S se reduce en 1. Si el resultado no es negativo, se completa la ejecución de P(S). De lo contrario, el proceso que ejecuta la operación P se suspende. espera la liberación. Al ejecutar la operación V V(S), el valor de S se incrementa en 1. Si el resultado no es mayor que 0, se libera un proceso que espera la ejecución de P(S). Para P1 y cóncavo, se pueden definir dos semáforos S1 y S2, siendo los valores iniciales 1 y 0 respectivamente. El proceso P1 realiza la operación P P (S1) antes de enviar datos al búfer B y realiza la operación V V (S2) después de enviar datos. El proceso P2 primero realiza la operación P P (S2) antes de leer los datos del búfer B, y realiza la operación V V (S1) después de leer los datos. Cuando P1 envía datos al búfer B, el valor del semáforo S1 se convierte en 0 y el valor de S1 se convierte en 1 solo después de leer los datos. Por lo tanto, el número siguiente no se enviará antes de que se lea el número anterior, por lo que se sincronizará. entre P1 y P2 está garantizado. Los lectores chinos a menudo no entienden por qué este mecanismo de sincronización se llama operación PV. Resulta que Dijkstra lo definió en holandés, porque en holandés, pasar se llama passeren y liberar se llama VRIJGEVEN, por lo que la operación PV recibió su nombre. Este es uno de los pocos ejemplos de terminología informática que no está expresada en inglés.
Uno de los casos
Al proponer un método para evaluar rápidamente la capacidad de producción dinámica del taller basado en el algoritmo de Dijkstra, este método puede garantizar de manera efectiva y razonable que los pedidos no se retrasen. Organizar el proceso de producción. Al establecer un modelo matemático del proceso del taller, aplicar un algoritmo mejorado para evaluar todos los pedidos y determinar el tiempo de finalización más temprano y el tiempo de ocurrencia más reciente de cada proceso para todos los pedidos, se puede lograr una evaluación dinámica de la capacidad de producción. Este algoritmo es adecuado para empresas que organizan estrictamente la producción según los pedidos. Las empresas pueden utilizar este algoritmo para evaluar los pedidos y determinar si pueden aceptarlos.
Teoremas y trabajos
El concepto de precondición más débil y el correspondiente cálculo de programación propuesto por Dijkstra permiten que el diseño del programa y la verificación del programa se realicen al mismo tiempo. tiempo, Tiene una importancia teórica y un valor práctico muy importantes y ha promovido en gran medida el proceso de programación como ciencia.
Dijkstra terminó su vida como investigador independiente en Polaris en 1984 y fue invitado a desempeñarse como director honorario del Departamento de Ciencias de la Computación de la Universidad de Texas en Austin.
Dijkstra ha escrito numerosos trabajos, entre los que se incluyen principalmente:
"A Primer of Algol60 Programming, Academic Pr., 1962"
"Programming Training Methods" (ADiscipline of Programming, Prentice-Hall, 1976)
"La enseñanza de la programación es la enseñanza de métodos de pensamiento" (La enseñanza de la programación, es decir, la enseñanza del pensamiento, Springer, 1976)
"Escritos seleccionados sobre informática: una perspectiva personal, Springer, 1982.
Este libro se compila seleccionando más de 60 de los materiales de comunicación más importantes y significativos de la gran cantidad de comunicaciones que envió a Bora Company, que reflejan sus puntos de vista y resultados de investigación de ese período)
"Un método de Programación" (Addison-Wesley, 1988)
"Desarrollo formal de programas y pruebas" (Addison-Wesley, 1990)
"Cálculo de predicados y "Semántica de programas" (Cálculo de predicados y Program Semantics, Springer, 1990)
Además de ganar el premio Turing, Dijkstra también ganó el premio AFIPS Harry Goode en 1974.
Dijkstra recibió el Premio Turing en la Reunión Anual de la ACM celebrada en Boston el 14 de agosto de 1972. Pronunció un discurso del Premio Turing titulado "El humilde programador", publicado en Communications of ACM, octubre de 1973, páginas 859-866. Véase también "Conferencias ACMTuringAward - Los primeros 20 años: 1966-1985, ACMPr.", páginas 17-32. En su discurso afirmó Fortran, Algol, LISP y otros lenguajes, pero para PL/I lo consideró un fracaso. El tema central del discurso fue cómo construir software fiable y cómo evitar errores durante la programación en lugar de eliminarlos más tarde. Esto no sólo es importante desde el punto de vista técnico, sino también desde el punto de vista económico. Las opiniones de Dijkstra antes mencionadas se han ganado la comprensión y el apoyo de cada vez más personas.
En 1989, para celebrar el 60 cumpleaños de Dijkstra, W.H.J. Feijin, un famoso estudioso de la informática y colaborador de Dijkstra desde hace mucho tiempo, compilaron conjuntamente una antología conmemorativa. El título del libro cita otro dicho famoso de Dijkstra: "La belleza es nuestro negocio" (Springer, 1990). El libro incluye 53 artículos escritos por sus colegas, amigos y estudiantes, incluidos 4 ganadores del Premio Turing, a saber, C.A.R Hoare (1980), D. Knuth (1974) y Worth (N. Wirth, 1984) y Bernoulli (A. Pnueli). , 1996). Curiosamente, Knut criticó la solución propuesta en la "Solución a un problema en el control de programas concurrentes" de Dijkstra en 1966, creyendo que esta solución podría "matar de hambre" a un proceso específico, es decir, quedar bloqueado para siempre para obtener los recursos que necesita. Propuso un plan que “no moriría de hambre”. Sin embargo, algunos críticos señalaron que el plan de Knut era más complicado que el plan de Dijkstra y no necesariamente más fiable. Evidentemente, las disputas académicas no impidieron que estos dos maestros informáticos se hicieran buenos amigos.
Después de una batalla de años contra el cáncer, Dijkstra murió en su casa de Nuenen, Países Bajos, el 6 de agosto de 2002.