miércoles, 26 de septiembre de 2012

Donald E. Knuth, guerra al correo electrónico

Donald E. Knuth
Cuando en 2010 la Fundación BBVA concedió el premio Fronteras del Conocimiento en su categoría de Tecnologías de la Información y la Comunicación a Donald Ervin Knuth, estaba reconociendo la ingente labor desarrollada por este hombre desde sus años de estudiante. Su actividad principal ha sido en el campo de la informática teórica y práctica, pero por razones personales y familiares también se ha adentrado en la tipografía, la física, las matemáticas, el estudio de la Biblia y la música.

La biografía de Donald Knuth (nacido el 10 de enero de 1938) está llena de desafíos y problemas resueltos. Cuando en junio de 1960 terminó su BS con la calificación summa cum laude en el Case Institute of Technology, el claustro de profesores le concedió el MS en ese momento por sus brillantes resultados. Es doctor honoris causa de unas 28 universidades de todo el mundo.

Su obra cumbre es el libro "The Art of Computer Programming" (TAOCP) como gran enciclopedia de los algoritmos, en el que sigue trabajando desde 1962 y por el que fue nombrado en 1990 Profesor y en 1993 Profesor Emérito de the Art of Computer Programming en la Universidad de Stanford. El proceso de trabajo incluye las siguientes fases, no necesariamente sucesivas: planificación de la obra, estudio de los próximos temas, redacción y prepublicación, mejoras y depuración de errores,...

La obra cumbre: TAOCP

The Art of Computer Programming
Después de una primera propuesta de 1962 que se limitaría a hablar de compiladores, se amplia el ámbito para tratar el análisis de los algoritmos y en 1965 se elabora un plan para escribir un libro de un volumen con 12 capítulos, que finalmente se convierte en siete volúmenes:
  • Volume 1 – Fundamental Algorithms (chapters 1 and 2)
  • Volume 2 – Seminumerical Algorithms (chapters 3 and 4)
  • Volume 3 – Sorting and Searching (chapters 5 and 6)
  • Volume 4 – Combinatorial Algorithms (chapters 7 and 8 released in several subvolumes)
  • Volume 5 – Syntactic Algorithms (as of 2011, estimated in 2020) (chapters 9 and 10)
  • Volume 6 – The Theory of Context-Free Languages (planned)
  • Volume 7 – Compiler Techniques (planned)
Actualmente están publicados los volúmenes 1, 2 y 3. El volumen 4 se ha dividido en subvolúmenes (4A, 4B, 4C,...), algunos ya prepublicados en forma de fascículos de aproximadamente 128 páginas cada uno, al ritmo de dos al año. El autor está también trabajando en el volumen 5, mientras que los volúmenes 6 y 7 quedarán pendientes de nueva definición, pues antes hay que revisar los volúmenes 1 a 5 para actualizar su contenido a los conocimientos actuales. En cualquier caso Knuth piensa que los cinco primeros volúmenes son el núcleo fundamental de la programación de las máquinas secuenciales.

En 1999, American Scientist consideró TAOCP como uno de los 100 libros más importantes del siglo XX, y uno de los 12 mejores en monografías sobre Física. Esto es sorprendente teniendo en cuenta el estado en que se encontraba su redacción y publicación.

Correo electrónico

Pues bien, en 1989 ya llevaba 27 años trabajando en TAOCP y se dio cuenta que a ese ritmo tardaría otros 20 años en terminar la obra (como se ha visto, era una estimación muy optimista). Decidió pisar el acelerador y eliminar la mayoría de los frenos: dejó de dar clase, de aconsejar a los alumnos y de leer el correo electrónico. Esto quiere decir que desde el 1 de enero de 1990 Knuth no tiene dirección de correo electrónico personal, sino que una secretaria lee los mensajes que le llegan, le pasa los realmente urgentes e importantes, y los restantes los lee una vez cada tres meses. Los fax los lee una vez cada seis meses.

Esto ocurría en los años 80, antes de la explosión del correo electrónico por Internet. Que el lector reflexione y compare con su propia disciplina de lectura de los mensajes que recibe diariamente. Muchas personas han limitado la lectura de su correo a sólo tres veces al día.

El cheque de $2.56

Cheque de $2.56 de Donald KnuthLa estrategia de publicación se basa en poner a disposición de los lectores en Internet las partes de TAOCP según llegan a un estado avanzado; lo que en software llamaríamos versión beta o RC (release candidate). El autor promete enviar un cheque personal de $2.56 a cada una de las personas que le informen por primera vez de un error tipográfico, técnico, histórico o político.

El valor $2.56 es un "dólar hexadecimal" (para los informáticos 0x$1.00). Hay recompensas de diferentes valores para otras obras del autor. Por ejemplo, $3.16 para su obra 3:16 Bible Texts Illuminated, que analiza el capítulo3, versículo 16 de cada uno de los libros de la Biblia. También ofrece 32 centavos (en hexadecimal 0x$0.20) por cada sugerencia de mejora significativa.

Este procedimiento proporciona una revisión rápida, detallada y profunda del material del libro por parte de los propios lectores, asegurando la máxima calidad del contenido. Sorprendentemente, no ha supuesto un perjuicio económico para el autor, porque la mayoría de los que conseguían el cheque no lo cobraban, sino que lo guardaban como un trofeo. Desde principios de 2006, sólo 9 de 275 cheques han sido cobrados.

Intelligence: Finding an error in a Knuth text.
Stupidity: Cashing that $2.56 check you got.

Certificado de depósito de $2.56 de Donald Knuth
El riesgo de que los cheques en papel enviados internacionalmente permitan a los delincuentes atacar la cuenta bancaria del emisor, ha hecho que este premio haya sido substituido en octubre de 2008 por certificados personales de depósito en el Bank of San Serriffe (entidad ficticia cuyo nombre es un guiño a su interés por la tipografía). La página personal de Knuth incluye el estado de las cuentas en este banco, es decir los nombres de los depositantes y las cantidades ganadas.

Órgano de Donald KnuthEl órgano

El padre de Donald Knuth fue profesor en una escuela luterana y organista de iglesia. Donald estudió piano y órgano hasta su llegada a la high scholl. Posteriormente fue durante un tiempo organista suplente en la Faith Lutheran Church en Pasadena (California) y desde 1965 miembro de la American Guild of Organists.

Como resultado de esta afición encargó la construcción de un órgano con 812 tubos, que se instaló en la sala de música de su casa, inaugurándose en 1975.






Referencias

Los datos de este post están tomados de las siguientes fuentes:

miércoles, 19 de septiembre de 2012

Mi número favorito: el 142.857

Cuando introducía mi afición a los números en mi post Los números, ¿qué números?, ya anunciaba que mi favorito es el 142.857. No se trata de un número obtenido por el azar ni por la casualidad, sino que tiene su origen en otros números con propiedades interesantes sobre los que ya he hablado (o pienso hacerlo): el seis, el siete y el nueve.

Origen

Tomemos un número formado por seis nueves y dividámoslo por siete.

¡Quién nos iba a decir que 999.999 era divisible por 7!

Más sencillo todavía: hagamos la división 1 / 7.
El resultado es un número decimal periódico puro, en el que se se repiten las cifras 142857. Por el contrario no aparecen las cifras múltiplos de tres: 3, 6 y 9.

Esta forma decimal puede obtenerse sumando indefinidamente la serie cuyo primer elemento es  0,14, y cada nuevo elemento se obtiene a partir del anterior multiplicando por 2 y dividiendo por 100, para formar la suma que se ve a la izquierda.







 Lo que en notación matemática expresaríamos como
Lógicamente si dividimos la fracción y la suma por 14 tenmos que:



 Para empezar...

Su propiedad más sencilla nos lleva de nuevo al número nueve: si sumamos el número formado por sus tres primeras cifras (142) a las tres últimas (857) obtenemos 999, que nos recuerda su origen.

El 142.857 es un número cíclico

Este número comparte con algunos otros un comportamiento curioso cuando los multiplicamos por 1, 2, 3,... A estos números se les denomina cíclicos.

En nuestro caso, multiplicando por 1, ..., 7 tenemos:

Ignorando la última multiplicación, podemos ver que las cifras son las mismas que en el número original, pero su posición ha variado de una multiplicación a otra, pero siempre manteniendo circularmente la misma secuencia entre ellas.
Cada cifra ocupa todas y cada una de las seis posiciones. Por ejemplo, la cifra 4 ocupa sucesivamente las posiciones 2, 6, 1, 4, 3 y 5.
Recordando el origen del número 142857 no nos extraña el resultado de la última fila.

Si continuamos multiplicando por los números naturales siguientes 8,... y lo comparamos con el resultado anterior, vemos:


Cada resultado en la segunda columna es el mismo de la primera columna en el que la última cifra (la de las unidades) se ha descompuesto en 1, que pasa a la primera posición (la de las unidades de millón) y el resto, que permanece en su lugar. Por ejemplo, 142857 pasa a 1142856, pues 7 = 1 + 6.

Parecido ocurre en la tercera columna. Restando 2 a la última posición tenemos que 7 = 2 + 5 y que 142857 pasa a 2142855.

Dejo al lector que, con la ayuda de una sencilla hoja de cálculo, compruebe el comportamiento de este número cuando se multiplica por números enteros cada vez mayores.

Otros números cíclicos

Si definimos número cíclico como aquél entero que al multiplicarlo sucesivamente por 1, 2, 3... produce variaciones circulares del número original, como hemos visto en el 142.857, observamos dos propiedades curiosas:
142857 (6 cifras)
0588235294117647 (16 cifras)
052631578947368421 (18 cifras)
0434782608695652173913 (22 cifras)
0344827586206896551724137931 (28 cifras)
0212765957446808510638297872340425531914893617 (46 cifras)
0169491525423728813559322033898305084745762711864406779661 (58 cifras)
016393442622950819672131147540983606557377049180327868852459 (60 cifras)
  • Todos los números cíclicos, excepto el 142.857, empiezan por cero, por lo que si no permitimos que un número entero empiece por cero, entonces el 142.857 es el único número cíclico.
El tamaño de estos números nos impide jugar fácilmente con ellos. Nos contentamos con comprobar que partiendo cualquier número cíclico en dos mitades y sumándolas, se obtiene un número compuesto exclusivamente por la cifra nueve. Por ejemplo, con el número de 60 cifras:
Para terminar con una cuarta propiedad de los números cíclicos: de la propiedad anterior deducimos que todos son divisibles por 9. Como nos enseñaron en la escuela, un número es divisible por nueve si la suma de sus dígitos es divisible por nueve.

No son números cíclicos...

Por el contrario, no se consideran números cíclicos los que producen variaciones circulares del mismo número, pero multiplicándolo por enteros NO sucesivos, como en el caso del 076.923. Este número tiene esa propiedad cuando se multiplica por 1, 3, 4, 9, 10 y 12.