Donald Knuth, maestro de algoritmos, reflexiona sobre los 50 años de su obra en progreso, «El arte de la programación de computadoras».
Durante medio siglo, el científico informático de Stanford Donald Knuth, que se parece un poco a Yoda, a pesar de que mide mas de 1.90m y usa lentes, ha reinado como la guía espiritual del reino algorítmico.
Es el autor de «El arte de la programación por computadora«, una obra continua de cuatro volúmenes que es el trabajo de su vida. El primer volumen debutó en 1968, y los volúmenes recogidos (vendidos como un conjunto en caja por aproximadamente $ 250) fueron incluidos por American Scientist en 2013 en su lista de libros que dieron forma al último siglo de la ciencia, junto con una edición especial de “La autobiografía de Charles Darwin, » The Right Stuff » de Tom Wolfe, «Silent Spring» de Rachel Carson y monografías de Albert Einstein, John von Neumann y Richard Feynman.
Con más de un millón de copias impresas, «El arte de la programación de computadoras » es la Biblia de su campo. “Como una biblia real, es larga y completa; ningún otro libro es tan completo «, dijo Peter Norvig, director de investigación de Google. Después de 652 páginas, el volumen uno se cierra con una nota en la contraportada de Bill Gates: «Definitivamente, deberías enviarme un currículum si puedes leer todo el artículo».
El volumen se abre con un extracto de » McCall’s Cookbook «:
Aquí está su libro, el que sus miles de cartas nos han pedido que publiquemos. Nos ha llevado años hacerlo, verificando y volviendo a controlar innumerables recetas para ofrecerle solo lo mejor, lo interesante, lo perfecto.
En el interior se encuentran los algoritmos, las recetas que alimentan la era digital, aunque, como el Dr. Knuth le gusta señalar, los algoritmos también se pueden encontrar en tabletas babilónicas desde hace 3.800 años. Él es un algoritmo estimado; su nombre está adjunto a algunos de los especímenes más importantes del campo, como el algoritmo de búsqueda de cadenas Knuth-Morris-Pratt. Diseñado en 1970, encuentra todas las apariciones de una palabra o patrón de letras en un texto, por ejemplo, cuando presiona Comando + F para buscar una palabra clave en un documento.
Ahora con 80 años, el Dr. Knuth usualmente se viste como el friki juvenil que era cuando se embarcó en esta odisea: una camiseta de manga larga debajo de una camiseta de manga corta, con jeans, al menos en esta época del año. En aquellos primeros días, trabajó cerca de la máquina, escribiendo «en bruto», jugando con los ceros y los unos.
«Knuth dejó en claro que el sistema podría entenderse hasta el nivel del código de la máquina», dijo el Dr. Norvig. Hoy en día, por supuesto, con los algoritmos que dominan (y socavan) nuestra propia existencia, el programador promedio ya no tiene tiempo para manipular la basura binaria, y trabaja en su lugar con jerarquías de abstracción, capas sobre capas de código, y con frecuencia con cadenas de código prestadas. de las bibliotecas de código. Pero una clase de ingenieros de élite en ocasiones todavía hace la inmersión profunda.
«Aquí, en Google, a veces simplemente lanzamos cosas juntos», dijo el Dr. Norvig, durante una reunión del equipo de Google Trips, en Mountain View, California. «Pero otras veces, si está sirviendo a miles de millones de usuarios, es importante hacerlo de manera eficiente. «Una mejora del 10 por ciento en eficiencia puede resultar en miles de millones de dólares, y para obtener ese último nivel de eficiencia, tienes que entender lo que está pasando».
O, como lo explicó Andrei Broder, un científico distinguido de Google y uno de los antiguos graduados del Dr. Knuth, durante la reunión: “Queremos tener alguna base teórica para lo que estamos haciendo. No queremos un algoritmo frívolo o descuidado o de segunda clase. No queremos que otros algoritmos digan: ‘Ustedes son idiotas’ ”.
La aplicación Google Trips , creada en 2016, es un «algoritmo de orientación» que mapea las actividades turísticas recomendadas para un día. El equipo estaba trabajando en » maximizar la calidad del peor día » , por ejemplo, evitando enviar al usuario al mismo vecindario para ver diferentes sitios. Se inspiraron en un algoritmo de 300 años de antigüedad del matemático suizo Leonhard Euler, que quería trazar una ruta a través de la ciudad prusiana de Königsberg que cruzaría cada uno de sus siete puentes solo una vez. El Dr. Knuth aborda el problema clásico de Euler en el primer volumen de su tratado. (Una vez aplicó el método de Euler para codificar una máquina de coser controlada por computadora )
Seguir la doctrina del Dr. Knuth ayuda a alejar la moronería. Se le conoce por introducir la noción de «programación alfabetizada», enfatizando la importancia de escribir código que sea legible tanto por los humanos como por las computadoras, una noción que hoy en día parece casi una imitación. El Dr. Knuth ha llegado al extremo de argumentar que algunos programas de computadora son, como los poemas de Elizabeth Bishop y la «Pastoral estadounidense» de Philip Roth, obras de literatura dignas de un Pulitzer.
También es un perfeccionista notorio. Randall Munroe, el dibujante xkcd y autor de «Explicación de cosas», aprendió por primera vez sobre el Dr. Knuth a través de personas de ciencias de la computación que mencionaron el dinero de la recompensa que el Dr. Knuth paga a cualquiera que encuentre un error en cualquiera de sus libros. Como recordó el Sr. Munroe, «la gente habló de obtener uno de esos cheques como si fuera el Premio Nobel de informática».
Los exigentes estándares del Dr. Knuth, literarios y de cualquier otra índole, pueden explicar por qué el trabajo de su vida está lejos de terminarse. Tiene una apuesta con Sergey Brin, cofundador de Google y ex alumno (para usar el término a la ligera), sobre si el Sr. Brin terminará su Ph.D. Antes de que el Dr. Knuth concluya su obra.
El amanecer del algoritmo.
A la edad de 19 años, el Dr. Knuth publicó su primer artículo técnico, «El Sistema Potrzebie de Pesos y Medidas», en la revista Mad. Se convirtió en un científico informático antes de que existiera la disciplina, estudiando matemáticas en lo que hoy es la Universidad Case Western Reserve en Cleveland. Miró los programas de muestra para el mainframe IBM 650 de la escuela, una computadora decimal, y, notando algunas deficiencias, reescribió el software, así como el libro de texto utilizado en la clase. Como proyecto paralelo, dirigió las estadísticas para el equipo de baloncesto, escribiendo un programa de computadora que les ayudó a ganar su liga, y obtuvo un segmento de Walter Cronkite llamado » El entrenador electrónico «.
Durante las vacaciones de verano, el Dr. Knuth ganó más dinero del que ganaban los profesores en un año escribiendo compiladores. Un compilador es como un traductor, que convierte un lenguaje de programación de alto nivel (parecido al álgebra) a uno de nivel inferior (a veces binario arcano) y, idealmente, lo mejora en el proceso. En informática, la «optimización» es verdaderamente un arte, y esto se articula en otro proverbio de Knuthian: «La optimización prematura es la raíz de todo mal».
Registrarse en Science Times
Te traemos historias que capturan las maravillas del cuerpo humano, la naturaleza y el cosmos.
REGÍSTRATE
Finalmente, el Dr. Knuth se convirtió en un compilador, y descubrió inadvertidamente un nuevo campo al que llamó «análisis de algoritmos». Un editor lo contrató para escribir un libro sobre compiladores, pero se convirtió en un libro que recopilaba todo lo que sabía sobre cómo hacerlo. escribir para computadoras – un libro sobre algoritmos.
«En el momento del Renacimiento, el origen de esta palabra estaba en duda», comenzó. «Y los primeros lingüistas intentaron adivinar su derivación haciendo combinaciones como algiros [doloroso] + arithmos [número]». De hecho, el Dr. Knuth continuó, el homónimo es el autor del libro de texto persa del siglo IX Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī, latinizado como Algorithmi. El Dr. Knuth, que nunca fue uno de los medianos, realizó una peregrinación en 1979 a la patria ancestral de al-Khwārizmī en Uzbekistán.
Cuando el Dr. Knuth comenzó, tenía la intención de escribir un solo trabajo. Poco después, la informática se sometió a su Big Bang, por lo que volvió a imaginar y reformuló el proyecto en siete volúmenes. Ahora él distribuye sub-volúmenes, llamados fascículos. La siguiente instalación, «Volumen 4, Fascículo 5», que abarca, entre otras cosas, el «retroceso» y «enlaces de baile», debía publicarse a tiempo para Navidad. Se retrasa hasta el próximo abril porque sigue encontrando cada vez más problemas irresistibles que quiere presentar.
Con el fin de optimizar sus posibilidades de llegar al final, el Dr. Knuth siempre ha guardado su tiempo. Se retiró a los 55 años, restringió sus compromisos públicos y abandonó el correo electrónico (oficialmente, al menos). Andrei Broder recordó que la gestión del tiempo era la característica definitoria de su profesor incluso a principios de los años ochenta.
El Dr. Knuth solía tener citas con los estudiantes los viernes por la mañana, hasta que comenzó a pasar las noches en el laboratorio de John McCarthy, un fundador de la inteligencia artificial, para acceder a las computadoras cuando estaban libres. Horrorizado por el aspecto de su amado libro en la página con el advenimiento de la publicación digital, el Dr. Knuth tuvo la misión de crear el sistema de composición de computadora T e X , que sigue siendo el estándar de oro para todas las formas de comunicación y publicación científica. Algunos lo consideran la mayor contribución del Dr. Knuth al mundo y la mayor contribución a la tipografía desde Gutenberg.
Este desvío de una década tuvo lugar en la época en que las computadoras se compartían entre los usuarios y corrían más rápido por la noche mientras la mayoría de los humanos dormían. Así que el Dr. Knuth cambió el día a la noche, cambió su horario de trabajo por 12 horas y asignó las citas de sus estudiantes a los viernes de 8 pm a medianoche. El Dr. Broder recordó: «Cuando le dije a mi novia que no podemos hacer nada el viernes por la noche porque el viernes por la noche a las 10 tengo que reunirme con mi asesor, ella pensó: ‘Esto es algo tan estúpido que debe ser cierto’. ”
Sin embargo, cuando Knuth elige estar físicamente presente, en ese momento está al cien por cien. «Simplemente te hace feliz estar cerca de él», dijo Jennifer Chayes, directora general de Microsoft Research. “Es un máximo en la comunidad. Si tuvieras una función de optimización que fuera de alguna manera una combinación de calidez y profundidad, Don sería «.
Domingo con el algorithmist
El Dr. Knuth vive en Stanford y permitió una visita de domingo. El hecho de que perdonara un día entero fue excepcional; por lo general, su disponibilidad es la «hora de la siesta «, un ritual sagrado diario de la 1 a las 4 p. M. Comenzó temprano, en la Primera Iglesia Luterana de Palo Alto, donde impartió una lección de la escuela dominical a un alto nivel. Sólo para la sala. Conduciendo a casa, se puso filosófico sobre las matemáticas.
«Nunca lo sabré todo», dijo. «Mi vida sería mucho peor si no hubiera nada de lo que supiera las respuestas, y si no hubiera nada de lo que nosabía las respuestas». Luego ofreció un recorrido por su casa «moderna de California», que él y su Esposa, Jill, construida en 1970. Su oficina está llena de pilas de memorias USB y adornada con el arte del corazón de San Valentín de Jill, una diseñadora gráfica. Lo más impresionante es la sala de música, construida alrededor de su órgano de tubos de 812 tubos a medida. El día terminó con una cerveza en una fiesta de rompecabezas.
Rompecabezas y juegos, y escribir una novela sobre números surrealistas , y componer un sueño musical multimedia de 90 minutos, » Fantasia apocalíptica «, son el tipo de cosas que realmente le hacen cosquillas . Una sección de su libro se titula “Puzzles contra el mundo real”. Envió un extracto al equipo de padre e hijo de Martin Demaine, un artista, y Erik Demaine, científico informático, ambos en el Instituto de Tecnología de Massachusetts, porque El Dr. Knuth había incluido sus » fuentes de rompecabezas algorítmico «.
«Me emocioné», dijo Erik Demaine. «Es un honor estar en el libro». Mencionó otra cita de Knuth, que sirve como lema inspirador para la conferencia bianual de » DIVERSIÓN con algoritmos «: «El placer probablemente ha sido el objetivo principal todo el tiempo».
Pero entonces, dijo el Dr. Demaine, el campo se fue y se volvió práctico. Ingenieros, científicos y artistas se están uniendo para resolver problemas del mundo real (plegamiento de proteínas, robótica, airbags) utilizando los diseños de origami matemático de los Demaines para plegar el papel y los enlaces en diferentes formas.
Por supuesto, todo el rigmarole algorítmico también está causando problemas del mundo real. Los algoritmos escritos por humanos, que abordan cada vez más problemas, pero que producen código incrustado con errores y sesgos, son lo suficientemente problemáticos. Más preocupantes, tal vez, son los algoritmos que no están escritos por humanos, algoritmos escritos por la máquina, como aprende.
Los programadores siguen entrenando la máquina y, de manera crucial, alimentan datos. (Los datos son el nuevo dominio de sesgos y errores, y aquí los errores y sesgos son más difíciles de encontrar y solucionar). Sin embargo, como dijo Kevin Slavin, un afiliado de investigación en el Laboratorio de Medios del MIT, “ahora estamos escribiendo algoritmos que no podemos leer. Eso hace de este un momento único en la historia, en la que estamos sujetos a las ideas y las acciones y los esfuerzos de un conjunto de la física que tienen orígenes humanos sin la comprensión humana.”Como se ha señalado con frecuencia Slavin,“ Es un futuro brillante, si estás un algoritmo ”
Tanto más si eres un algoritmo versado en Knuth. «Hoy en día, los programadores usan cosas que Knuth y otros han hecho como componentes de sus algoritmos, y luego combinan eso con todas las otras cosas que necesitan», dijo el Dr. Norvig de Google.
“Con la IA, tenemos lo mismo. Es solo que la combinación de partes se realizará automáticamente, en función de los datos, en lugar de basarse en el trabajo de un programador. Desea que AI pueda combinar componentes para obtener una buena respuesta basada en los datos. Pero tienes que decidir cuáles son esos componentes. Podría ocurrir que cada componente sea una página o un capítulo fuera de Knuth, porque esa es la mejor manera posible de hacer alguna tarea «.
Suerte, entonces, el Dr. Knuth lo sigue haciendo. Él cree que tomará otros 25 años para terminar «El arte de la programación de computadoras», aunque ese período de tiempo ha sido una constante desde 1980. ¿Podrían los algoritmos de escritura de algoritmos obtener su propio capítulo, o tal vez una página en el epílogo? «Definitivamente no», dijo el Dr. Knuth.
«Me preocupa que los algoritmos se estén volviendo demasiado prominentes en el mundo», agregó. “Comenzó que los informáticos estaban preocupados de que nadie nos escuchara. Ahora me preocupa que mucha gente esté escuchando «.
Fuente original: The Yoda of Silicon Valley.
