Donald Ervin Knuth (nacido el 10 de enero de 1938) es un informático y matemático estadounidense. Es profesor emérito en Stanford University y receptor del Premio Turing de la ACM en 1974, considerado informalmente el Premio Nobel de la informática. Knuth ha sido llamado el "padre del análisis de algoritmos" y es el autor de la obra en varios volúmenes El arte de programar ordenadores.
Knuth contribuyó al desarrollo del análisis riguroso de la complejidad computacional y sistematizó técnicas matemáticas formales para ello, popularizando la notación asintótica. También es el creador del sistema de composición tipográfica TeX, del lenguaje de definición de fuentes METAFONT y de las familias tipográficas Computer Modern. Como escritor y académico, creó los sistemas de programación WEB y CWEB para la programación literaria y diseñó las arquitecturas de conjuntos de instrucciones MIX y MMIX. Se opone firmemente a las patentes de software y ha expresado sus opiniones ante la Oficina de Patentes y Marcas de los Estados Unidos y la Organización Europea de Patentes.
Primeros años y educación
Knuth nació en Milwaukee, Wisconsin, hijo de Ervin Henry Knuth y Louise Marie Bohning. Describe su herencia como "luterana alemana del Medio Oeste". Su padre era propietario de una pequeña imprenta y enseñaba teneduría de libros. En la Milwaukee Lutheran High School, Knuth mostró una temprana capacidad para la resolución de problemas. En octavo grado, participó en un concurso para encontrar el número de palabras que podían formarse reordenando las letras de "Ziegler's Giant Bar". Los jueces habían identificado 2,500 palabras; Knuth, usando un diccionario no abreviado durante un día de baja fingida, encontró más de 4,500 y ganó. La escuela recibió un televisor y barras de caramelo para todos los estudiantes.
Knuth recibió una beca para estudiar física en el Case Institute of Technology (ahora parte de Case Western Reserve University) en 1956. Se unió a la fraternidad Beta Nu Chapter de Theta Chi. Al conocer la IBM 650, una de las primeras computadoras comerciales, leyó su manual y decidió reescribir el ensamblador y el compilador de la máquina, creyendo que podía hacerlo mejor. En 1958, creó un programa para ayudar al equipo de baloncesto a ganar, asignando "valores" a los jugadores para estimar la probabilidad de anotación, un enfoque novedoso que fue reportado por Newsweek y CBS Evening News.
Knuth fue editor fundador de la Engineering and Science Review, que ganó un premio nacional en 1959. Pasó de la física a las matemáticas y obtuvo tanto una licenciatura en ciencias como una maestría en 1960, esta última con mención especial de la facultad. Al final de su último año, propuso a Burroughs Corporation escribir un compilador de ALGOL para la B205 por $5,500; la propuesta fue aceptada y trabajó en ello entre Case y Caltech. En 1963, obtuvo un doctorado en matemáticas por el Instituto de Tecnología de California, con Marshall Hall como asesor, con la tesis Semifields and Projective Planes (Semifinitos y planos proyectivos).
Carrera temprana y El arte de programar ordenadores
Tras obtener su doctorado, Knuth se unió a la facultad de Caltech como profesor asistente en 1963. También se convirtió en consultor de Burroughs Corporation, trabajando en el compilador de ALGOL para la B220. Rechazó un contrato de $100,000 de Green Tree Corporation para continuar en Caltech y Burroughs. Declinó becas de la Fundación Nacional de la Ciencia y de Woodrow Wilson porque le habrían impedido realizar trabajo de consultoría. En el verano de 1962, escribió un compilador de FORTRAN para Univac, diciendo más tarde que "vendió su alma al diablo".
En Burroughs, Knuth sugirió una extensión a la tabla de símbolos que permitía que un símbolo representara una cadena de símbolos, lo que se convirtió en la base de la instrucción DEFINE en el ALGOL de Burroughs. Edsger Dijkstra inicialmente disliked la idea. Knuth también trabajó en lenguajes de simulación, produciendo SOL con J. McNeeley, e influyó en Burroughs para adoptar Simula después de asistir a una conferencia en Noruega en 1967. Su relación de consultoría con Burroughs duró de 1960 a 1968.
En 1962, Addison-Wesley encargó a Knuth escribir un libro sobre compiladores. Mientras trabajaba en él, se dio cuenta de que necesitaba una teoría fundamental de la programación de computadoras, que se convirtió en El arte de programar ordenadores. Originalmente planeado como un solo volumen, se expandió a seis o siete; el primer volumen se publicó en 1968. Justo antes de la publicación, Knuth dejó Caltech para trabajar en la División de Investigación de Comunicaciones del Instituto de Análisis de Defensa en Princeton, realizando investigación matemática en criptografía para la Agencia de Seguridad Nacional.
Contribuciones a la informática
El trabajo de Knuth en El arte de programar ordenadores estableció el análisis de algoritmos como una disciplina rigurosa. Introdujo y popularizó la notación asintótica (como la notación O grande) para describir la eficiencia de los algoritmos. Sus libros son conocidos por su precisión, sus notas históricas y sus ejercicios clasificados por dificultad. La serie se considera una referencia fundamental en la informática.
Knuth también desarrolló el sistema de composición tipográfica TeX (publicado en 1978) y METAFONT, que permiten la composición tipográfica matemática de alta calidad. TeX se convirtió en un estándar en la publicación académica. Creó los sistemas WEB y CWEB para la programación literaria, que combinan código y documentación en una sola fuente. Sus lenguajes ensambladores MIX y MMIX se utilizan en sus libros para ilustrar conceptos de programación de bajo nivel.
Carrera posterior y reconocimiento
Knuth se unió a la Universidad de Stanford en 1969, donde fue profesor y más tarde profesor emérito. Recibió el Premio Turing en 1974 por sus principales contribuciones al análisis de algoritmos y al diseño de lenguajes de programación. También ha recibido la Medalla Nacional de Ciencia (1979), la Medalla John von Neumann (1995) y el Premio Kyoto (1996). Knuth es conocido por su atención al detalle, incluida la oferta de recompensas monetarias por errores encontrados en sus libros.
Knuth ha sido un opositor declarado de las patentes de software, presentando escritos de amicus curiae y testificando ante oficinas de patentes. Se retiró de la investigación activa en la década de 1990 para centrarse en completar El arte de programar ordenadores, cuyos volúmenes 4A y 4B se publicaron en 2011 y 2022. Su trabajo ha influido en generaciones de informáticos, incluidos muchos en MIT y Carnegie Mellon University.
Legado
La influencia de Knuth se extiende a los algoritmos, la composición tipográfica y la metodología de programación. Sus libros de texto han sido traducidos a muchos idiomas y siguen siendo ampliamente utilizados. El sistema TeX y sus derivados (como LaTeX) son herramientas esenciales en la publicación científica. Su concepto de programación literaria ha influido en las prácticas modernas de documentación. Su insistencia en el rigor matemático en el análisis de algoritmos estableció un estándar para el campo, y sus contribuciones a la inteligencia artificial y áreas relacionadas son reconocidas a través de numerosos doctorados honoris causa y premios.
A pesar de su enfoque en la informática clásica, el trabajo de Knuth sustenta muchos desarrollos modernos, incluidos el aprendizaje automático y las redes neuronales, al proporcionar técnicas algorítmicas fundamentales. Su legado se celebra con el Premio Knuth anual, otorgado por contribuciones sobresalientes a los fundamentos de la informática.