
Donald Knuth
Informático y matemático estadounidense, padre del análisis de algoritmos y autor de El arte de programar ordenadores · 1938
- Nacimiento
- 10 de enero de 1938
- País
- Estados Unidos
- Sección
- Informática
- Premios
- Premio Turing
Biografía ampliada
Infancia y formación temprana
Donald Ervin Knuth nació el 10 de enero de 1938 en Milwaukee, Wisconsin, en el medio oeste de Estados Unidos. Era hijo de Ervin Henry Knuth y Louise Marie Bohning. Él mismo describe su herencia como «alemana luterana del Medio Oeste», una identidad religiosa y cultural que marcaría buena parte de sus intereses posteriores. Su padre tenía una pequeña imprenta y enseñaba contabilidad, de modo que el niño creció rodeado de papel, tipos de imprenta y números.
Durante sus años en el Milwaukee Lutheran High School, Knuth destacó por buscar caminos ingeniosos para resolver problemas, más que por seguir el método que proponía el profesor. Un episodio que se repite en casi todas sus biografías ilustra bien esa forma de pensar. En octavo curso participó en un concurso que pedía encontrar cuántas palabras podían formarse reordenando las letras de la frase «Ziegler's Giant Bar». Los jueces habían identificado 2.500 palabras. Knuth, que aprovechó parte del tiempo libre que consiguió fingiendo un dolor de estómago, planteó el problema al revés: en lugar de generar combinaciones de letras, recorrió un diccionario completo y comprobó, palabra por palabra, si cada entrada podía escribirse con las letras disponibles. Con ese procedimiento encontró más de 4.500 palabras y ganó el concurso. El premio fue un televisor nuevo para el colegio y suficientes chocolatinas para que todos sus compañeros pudieran comer.
El episodio es valioso porque anticipa una idea central de su trabajo posterior: un mismo problema puede resolverse de muchas maneras, y el método que se elige determina cuánto trabajo cuesta llegar a la respuesta. Esa preocupación por la eficiencia de los procedimientos, que en informática se llama algoritmo, sería el núcleo de su carrera.
Los primeros contactos con los ordenadores
En 1956 Knuth obtuvo una beca para estudiar física en el Case Institute of Technology, hoy parte de la Case Western Reserve University, en Cleveland, Ohio. Allí se integró también en la fraternidad Theta Chi. Su primer contacto serio con la informática llegó a través del IBM 650, un ordenador comercial de los primeros que se vendían fuera de los grandes laboratorios. Tras leer el manual de la máquina, Knuth consideró que el código ensamblador y el compilador que utilizaba la escuela podían mejorarse, y decidió reescribirlos. Un ensamblador es un programa que traduce instrucciones escritas en un lenguaje casi humano a los códigos numéricos que entiende el procesador; un compilador hace algo parecido con lenguajes de programación más abstractos.
En 1958 creó un programa para ayudar al equipo de baloncesto del colegio. Asignó valores numéricos a cada jugador para estimar su probabilidad de anotar puntos, un enfoque poco habitual en aquella época que más tarde mereció la atención de medios como Newsweek y del programa CBS Evening News. Conviene tomar esta anécdota como lo que es: una muestra temprana de su interés por convertir situaciones cotidianas en problemas que puedan tratarse con cálculo.
Knuth también participó en la fundación de la revista Engineering and Science Review del Instituto Case, que en 1959 obtuvo un premio nacional como mejor revista técnica. Ese mismo año empezó a sentirse atraído por las matemáticas, y en 1960 recibió dos títulos de la universidad: la licenciatura en ciencias y, al mismo tiempo, un máster en ciencias concedido por un premio especial de la facultad, que consideró que su trabajo era excepcionalmente destacado.
En 1960, al final de su último curso, propuso a la empresa Burroughs Corporation escribir un compilador del lenguaje ALGOL para su ordenador B205 por 5.500 dólares. La propuesta fue aceptada, y Knuth trabajó en ese compilador entre su graduación en Case y su llegada al Caltech. Esta etapa le dio una experiencia práctica muy amplia, que luego se reflejaría en la forma en que analiza los programas.
El doctorado y los primeros años como profesional
En 1963 se doctoró en matemáticas en el California Institute of Technology, con el matemático Marshall Hall como director de tesis. La tesis llevaba por título Finite Semifields and Projective Planes, un trabajo de álgebra abstracta alejado, en apariencia, de la programación. Ese mismo año se incorporó como profesor asistente a la plantilla del Caltech.
Al mismo tiempo mantuvo una relación de consultoría con Burroughs, donde trabajó en el área de planificación de productos. Knuth se consideraba matemático en el Caltech y programador en Burroughs, y en la empresa colaboró con quienes, según su propio juicio, escribían el mejor software de la época. Hubo además decisiones que muestran su manera de administrar el tiempo: rechazó un contrato de 100.000 dólares para escribir compiladores en la empresa Green Tree Corporation, y también renunció a dos becas, la de la National Science Foundation y la de la Woodrow Wilson Foundation, porque exigían dedicarse exclusivamente a estudiar como estudiante de posgrado, lo que le habría impedido seguir con Burroughs.
En esos años escribió también un compilador de FORTRAN para la empresa Univac durante el verano de 1962. Knuth comentó con humor que, al escribirlo, sentía que había «vendido su alma al diablo», una forma de expresar lo tedioso que le resultó ese trabajo frente a otros más creativos.
Un detalle que demuestra su gusto por las ideas de diseño es su aportación al compilador ALGOL de Burroughs. Propuso ampliar la tabla de símbolos para que un solo símbolo pudiera representar una cadena de símbolos. De esa propuesta surgió la instrucción DEFINE del lenguaje ALGOL de Burroughs, un mecanismo que después adoptaron otros lenguajes. La idea no fue bien recibida al principio, y algunos querían eliminarla. Según la ficha que se conserva del episodio, el último en opinar que era una pésima idea fue Edsger Dijkstra, durante una visita a Burroughs.
El encargo de un libro que se convirtió en seis y luego en siete volúmenes
En 1962 la editorial Addison-Wesley le encargó un libro sobre compiladores de lenguajes de programación. Knuth empezó a trabajar en él y pronto comprobó que no podía tratar bien el tema sin antes construir una teoría fundamental de la programación de ordenadores. Un compilador, en efecto, depende de muchas decisiones previas sobre cómo representar datos, cómo recorrer instrucciones y cómo medir el coste de cada operación. Lo que había empezado como un manual técnico se transformó en un proyecto mucho más ambicioso, que acabaría titulándose The Art of Computer Programming, es decir, El arte de programar ordenadores.
Inicialmente pensaba publicarlo en un solo libro. Al desarrollar el esquema, llegó a la conclusión de que necesitaba seis volúmenes y, más tarde, siete para cubrir el tema por completo. El primer volumen apareció en 1968. Justo antes de su publicación, Knuth dejó el Caltech para trabajar en el Institute for Defense Analyses, en su división de investigación en comunicaciones, que por entonces estaba situada en el campus de la Universidad de Princeton. Allí se hacían investigaciones matemáticas en criptografía para apoyar a la National Security Agency.
En 1969 abandonó ese puesto para incorporarse a la Universidad de Stanford, donde en 1977 pasó a ser profesor Fletcher Jones de Ciencias de la Computación. En 1990 recibió el título singular de Professor of The Art of Computer Programming, que más tarde se revisó a profesor emérito de ese mismo título. Se jubiló de la docencia y de la investigación regular en 1992 para terminar la obra, y desde 1993 es profesor emérito.
La historia del proyecto ilustra una característica de Knuth: la disposición a retrasar la publicación para hacerla bien. En los años setenta describió la informática como un campo nuevo, sin una identidad clara, y observó que muchas publicaciones de la época eran sencillamente incorrectas. Su intención al escribir la serie fue ordenar ese caos y contar la historia de forma rigurosa. Hacia 2011 había publicado el volumen 4A, y en 2022 apareció el 4B. La serie sigue incompleta, lo que él mismo ha reconocido al anunciar nuevas partes del cuarto volumen.
El análisis de algoritmos y una nueva disciplina
En 1967 Knuth asistió a una conferencia de la Society for Industrial and Applied Mathematics. Alguien le preguntó a qué se dedicaba. En aquella época la informática se dividía, en la práctica, en tres grandes áreas: el análisis numérico, la inteligencia artificial y los lenguajes de programación. Knuth, basándose en su estudio y en el trabajo que estaba haciendo para su libro, decidió que la próxima vez que alguien le preguntara respondería «análisis de algoritmos». La frase resultó clave: dio nombre a un campo que hasta entonces no estaba bien delimitado.
El análisis de algoritmos consiste en estudiar cuánto tiempo y cuánta memoria necesita un procedimiento para resolver un problema cuando el tamaño de los datos crece. Un ejemplo sencillo ayuda a entenderlo. Buscar un nombre en una lista desordenada exige, en el peor caso, revisar todos los elementos; si la lista se ordena previamente, puede bastar con un número de comparaciones mucho menor. El análisis permite saber de antemano qué opción escala mejor, sin depender de la potencia de una máquina concreta.
Para expresar estas comparaciones Knuth contribuyó a sistematizar la notación asintótica, que describe cómo crece el coste de un algoritmo cuando los datos se hacen muy grandes, y la popularizó entre los informáticos. Así, en lugar de ofrecer una cifra exacta de operaciones, se indica la forma general del crecimiento. Su trabajo en este terreno le valió el apodo de «padre del análisis de algoritmos».
Su aportación no se limitó a esa área. Ha realizado contribuciones en varias ramas teóricas de la informática, y también ha trabajado sobre el problema del emparejamiento estable, que consiste en asignar pares de elementos, por ejemplo estudiantes y plazas, de forma que no haya dos participantes que prefieran romper sus asignaciones para formar otra pareja. Como resumen de su enfoque, propuso el nombre «algorítmica» como mejor denominación para la disciplina de la informática. Knuth defendía que el centro del campo son los procedimientos y su eficiencia, más que los aparatos.
Tipografía digital: TeX y METAFONT
En los años setenta, los editores de The Art of Computer Programming abandonaron el sistema de composición de textos con tipos de metal Monotype y se pasaron a la fotocomposición. Knuth quedó muy insatisfecho, porque el nuevo sistema no lograba la calidad tipográfica de los volúmenes anteriores, que se habían compuesto con el método antiguo. Esa frustración lo llevó a dedicar tiempo a la composición digital, es decir, a diseñar un programa que pudiera colocar letras, fórmulas y espacios con la precisión de un buen impresor.
El resultado fue TeX, un sistema de composición de textos pensado especialmente para escribir matemáticas. Las fórmulas complejas, con subíndices, fracciones y símbolos apilados, son difíciles de colocar a mano en un ordenador, y TeX permite describirlas con un lenguaje de órdenes en lugar de dibujarlas. El texto de entrada es un documento escrito en código, y el programa lo transforma en una página lista para imprimir o publicar.
Para completar el sistema creó METAFONT, un lenguaje para definir tipos de letra mediante fórmulas matemáticas. En lugar de guardar el dibujo de cada carácter, se describe cómo se construye cada trazo a partir de parámetros, de modo que una misma familia tipográfica puede generar variantes de peso o tamaño. De esta labor surgió la familia de tipos Computer Modern, muy utilizada en publicaciones científicas.
Knuth conecta estas herramientas con una idea más general: los sistemas que diseña son también objetos de estudio. Por eso en el número de versión de TeX se fueron acercando al número π, y en el de METAFONT, al número e. Cada nueva edición se numera con más cifras decimales, de manera que el programa tiende hacia un límite conocido, aunque nunca llegue a él. Es una broma técnica, pero también un modo de decir que el software puede terminarse sin perder la voluntad de mejorarlo.
La programación literaria
Mientras desarrollaba TeX, Knuth ideó un método al que llamó programación literaria. La idea parte de una convicción sencilla: un programa debe escribirse pensando en que otra persona lo va a leer y comprender, no solo en que la máquina lo ejecute. Un programa convencional mezcla instrucciones y comentarios de forma poco ordenada, y su explicación suele quedar fuera del código, en documentos que se desactualizan. La programación literaria propone lo contrario: el texto explicativo y el código se escriben juntos, como un documento que puede leerse de corrido.
El sistema concreto que desarrolló se llama WEB. A partir de un mismo archivo fuente, WEB genera dos productos: un documento legible, preparado con TeX, que describe el programa, y el código ejecutable, en lenguaje Pascal. Los dos salen del mismo origen, lo que evita que la explicación y el programa se separen. Más tarde apareció CWEB, una versión que sustituye Pascal por C, C++ y Java.
Knuth empleó WEB para escribir TeX y METAFONT, y publicó ambos programas como libros. Las dos obras aparecieron en 1986, el mismo año en que se publicaron. Sobre la misma época, Leslie Lamport desarrolló LaTeX, un conjunto de macros basado en TeX que se adoptó muy ampliamente y que, en 1986, tuvo su primer manual de usuario.
La programación literaria no se impuso como práctica general en la industria, y el propio Knuth reconoce que es un método exigente. Sin embargo, su insistencia en la claridad y en la explicación cuidadosa del razonamiento forma parte de su legado, y se refleja en el estilo de sus libros, en los que cada ejemplo se acompaña de comentarios extensos y de ejercicios graduados.
Humor, errores y polémicas
Knuth es conocido por un sentido del humor técnico. Durante años ofreció una recompensa a quien encontrara errores conceptuales o tipográficos en sus libros. La cifra era de 2,56 dólares, y la explicación que dio es que «256 centavos son 1 dólar hexadecimal», una broma para quien conoce el sistema de numeración en base 16. También ofrecía un premio por errores en su libro 3:16 Bible Texts Illuminated, cuya cantidad, según la ficha de referencia, era de 3,16 dólares. Los cheques de recompensa se consideraban en algunos círculos un trofeo muy apreciado. Según se recoge, dejó de enviar cheques reales en 2008 debido a un fraude bancario, y desde entonces entrega a quien encuentra un error un certificado de depósito de un banco ficticio, el «Bank of San Serriffe».
También hay bromas dentro de sus textos. Para ilustrar la recursión, dejó que las entradas «Circular definition» y «Definition, circular» remitieran una a otra en el índice del primer volumen de su obra. Cuando el lector busca una, encuentra la otra, y así sucesivamente. La recursión es el procedimiento por el que una definición o un programa se invoca a sí mismo sobre una parte más pequeña del problema.
En cuanto a su trabajo técnico, Knuth se ha mostrado muy crítico con la concesión de patentes de software. Considera que soluciones triviales, que deberían resultar evidentes para cualquier especialista, no deberían protegerse con patentes. Ha matizado su postura en el caso de soluciones no triviales, como el método de punto interior para programación lineal, y ha expresado su desacuerdo directamente ante la Oficina de Patentes y Marcas de Estados Unidos y ante la Organización Europea de Patentes.
Knuth tampoco ha rehuido los temas religiosos. Como luterano, escribió 3:16 Bible Texts Illuminated, un libro en el que examina la Biblia mediante una especie de muestreo sistemático: analiza el capítulo 3, versículo 16 de cada libro. Cada versículo aparece acompañado de una ilustración caligráfica realizada por un grupo de calígrafos dirigido por Hermann Zapf. Después fue invitado a dar unas conferencias en el MIT sobre sus ideas acerca de la religión y la informática, que dieron lugar a otro libro, Things a Computer Scientist Rarely Talks About.
Vida personal, música y los últimos años
Knuth se casó con Nancy Jill Carter el 24 de junio de 1961, mientras era estudiante de posgrado en el Caltech. Tienen dos hijos, John Martin Knuth y Jennifer Sierra Knuth. Su vida familiar ha estado siempre ligada a la música. Es organista y compositor, y él y su padre trabajaron como organistas en congregaciones luteranas. Inicialmente pensó en estudiar música en la Valparaiso University, luterana, antes de decidirse por Case. En su casa tiene un órgano de 16 registros.
En 2016 completó una pieza para órgano titulada Fantasia Apocalyptica, que describe como una «traducción» del texto griego del Apocalipsis de san Juan a música. Se estrenó en Suecia el 10 de enero de 2018, coincidiendo con su cumpleaños.
La relación de Knuth con China también es singular. Su nombre chino es Gao Dena, que le puso en 1977 Frances Yao poco antes de un viaje de tres semanas a ese país. En la traducción china del primer volumen de su obra, publicada en 1980, explicó que adoptó ese nombre porque quería ser conocido por el creciente número de programadores chinos. En 1989 su nombre chino se incluyó en la cabecera de la Journal of Computer Science and Technology, algo que, según sus palabras, le hace sentirse cercano a todos los chinos, aunque no hable su idioma.
Su actividad pública continúa. Ofrece charlas informales unas pocas veces al año en Stanford, a las que llama «Computer Musings». Fue profesor visitante en el Departamento de Ciencias de la Computación de la Universidad de Oxford hasta 2017, y es miembro honorario del Magdalen College. Ha aparecido en vídeos de Numberphile y Computerphile, donde habla de temas como sus números surrealistas o por qué no utiliza el correo electrónico.
Sus intereses matemáticos recreativos también son amplios. Contribuyó con artículos al Journal of Recreational Mathematics desde la década de 1960 y fue reconocido como uno de los principales colaboradores del libro de Joseph Madachy Mathematics on Vacation. Escribió la novela matemática Números surrealistas, sobre la construcción que hizo John Horton Conway de un sistema alternativo de números a partir de la teoría de conjuntos, con el objetivo de mostrar cómo se desarrolla realmente una teoría matemática y de preparar a los estudiantes para investigar de forma original.
Reconocimientos y legado
Knuth ha recibido numerosos premios. En 1971 obtuvo el primer premio Grace Murray Hopper de la ACM. En 1974 recibió el Premio Turing, que la propia ACM considera informalmente el Nobel de la informática. Otros reconocimientos incluyen la Medalla Nacional de Ciencia de Estados Unidos (1979), la medalla John von Neumann (1995), el Premio Kyoto (1996) y el Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la información y la comunicación (2010). También fue elegido miembro de la Academia Nacional de Ciencias en 1975 y de la Academia Nacional de Ingeniería en 1981, por organizar amplias áreas de la informática de forma accesible para toda la comunidad. Además, ha recibido más de treinta doctorados honoris causa en distintos países.
El legado de Knuth tiene varias caras. La primera es The Art of Computer Programming, una referencia que muchos programadores y académicos consultan para comprender a fondo algoritmos y estructuras de datos. La segunda es TeX, que sigue siendo el estándar de composición de textos matemáticos en buena parte de la comunidad científica, y sobre el que se han construido herramientas como LaTeX. La tercera es la programación literaria, que influyó en la forma de documentar el código y en la idea de que el software debe poder leerse.
La cita más conocida de Knuth resume su actitud ante la verificación de programas. Al enviar comentarios a un colega autor de un algoritmo, escribió: «Cuidado con los errores en el código anterior; solo he demostrado que es correcto, no lo he probado». La frase distingue entre demostrar un resultado con razonamiento matemático y comprobarlo mediante pruebas, que solo cubren los casos examinados. Su vida profesional ilustra esa diferencia: prefirió dedicar años a razonar con rigor antes que publicar deprisa.
Knuth es, en definitiva, un científico que unió matemáticas, programación, tipografía y música en una sola preocupación: que las ideas complejas se expliquen con claridad y que los procedimientos sean correctos y eficientes. Su nombre aparece hoy en asteroides, en premios y en los manuales que siguen usando los estudiantes de informática, y su obra continúa en curso.
Citas
«Deberíamos esforzarnos continuamente por transformar cada arte en una ciencia: en el proceso, avanzamos el arte.»
«La ciencia es el conocimiento que entendemos tan bien que podemos enseñárselo a una computadora; y si no entendemos del todo algo, es un arte tratar con ello.»
«Un algoritmo debe verse para ser creído.»
«Cambiemos nuestra actitud tradicional hacia la construcción de programas: en lugar de imaginar que nuestra tarea principal es indicarle a una computadora qué hacer, concentrémonos más bien en explicarle a los seres humanos lo que queremos que una computadora haga.»
Aportaciones principales
- 1967Análisis de algoritmos como disciplina, nombre que dio a la estimación rigurosa del coste de los procedimientos de cálculo.
- 1968Primer volumen de El arte de la programación de ordenadores, obra de referencia sobre algoritmos y programación que terminó ocupando varios tomos.
- 1974Premio Turing, considerado informalmente el Nobel de la informática.
- 1986Publicación de TeX: The Program y METAFONT: The Program, en los que expuso el código completo de ambos programas.
- TeX, sistema de composición tipográfica digital pensado para textos científicos, sobre todo con fórmulas matemáticas.
- METAFONT, lenguaje para describir y diseñar tipos de letra mediante instrucciones matemáticas.
- Programación literaria, método en el que el programa se escribe como un texto pensado para ser leído por personas, con el sistema WEB.
Maestros y alumnos
Aprendió de:
Formó a:
Curiosidades y anécdotas
Recompensa por errores
Durante años pagó 2,56 dólares a quien encontrara errores en sus libros, porque 256 centavos equivalen a un dólar hexadecimal. Desde 2008 entrega certificados en lugar de cheques.
Números de versión con π
Las versiones de TeX se van acercando al número π (3, 3.1, 3.14...), y las de METAFONT se aproximan al número e.
Primer artículo científico
Según se cuenta, publicó en 1957 en una revista escolar un artículo titulado The Potrzebie System of Weights and Measures, que se publicó después en la revista Mad.
Descubrimientos e inventos relacionados
- 1970Algoritmo Knuth-Morris-PrattAlgoritmo que busca rápidamente un patrón dentro de un texto aprovechando lo que ya se comprobó antes de cada fallo, sin volver a leer caracteres.
Sus contemporáneos
Mientras vivía Donald Knuth (1938–)…
Vivieron a la vez
Se descubrió o inventó en esos años
- 1945ComputadoraMáquina programable que recibe datos, los procesa siguiendo instrucciones y entrega resultados, con una arquitectura de hardware y software que puede cambiar de tarea sin cambiar de cuerpo.
- 1957Satélite artificialUn satélite artificial es un objeto construido por personas y puesto en órbita alrededor de un cuerpo celeste, normalmente la Tierra, para recoger información, transmitirla o cumplir una función concreta.
- 1969InternetRed mundial de redes de ordenadores interconectadas que se comunican mediante el conjunto de protocolos TCP/IP.
- 1971Correo electrónicoServicio de red que permite enviar y recibir mensajes digitales entre usuarios mediante una cuenta con dirección propia, como el correo postal pero electrónico.
- 1973Teléfono móvilDispositivo electrónico portátil que permite hacer llamadas por radiofrecuencia mientras el usuario se desplaza dentro de la zona de cobertura de una red.
- 1989World Wide WebSistema de documentos y recursos interconectados por enlaces (hipervínculos) y accesibles a través de Internet mediante navegadores web.
Ivan Sutherland1938 · Informática
Bob Kahn1938 · Informática
Manuel Blum1938 · Informática
Barbara Liskov1939 · Informática
Stephen Cook1939 · Informática
Alan Kay1940 · Informática