Donald Knuth

Donald Ervin Knuth
Donald Knuth en una recepción para el Open Content Alliance, 25 de octubre 2005
Nacido	(10/01/1938) 10 de enero 1938 Milwaukee, Wisconsin, EE.UU.
Residencia	EE.UU.
Nacionalidad	Americano
Campos	Matemáticas Ciencias de la Computación
Instituciones	Universidad Stanford
Alma máter	Case Institute of Technology Instituto de Tecnología de California
Doctoral consejero	Marshall Hall, Jr.
Los estudiantes de doctorado	Leonidas J. Guibas Michael Fredman Scott, Kim Vaughan Pratt Robert Sedgewick Jeffrey Vitter Andrei Broder
Conocido por	The Art of Computer Programming TeX , METAFONT Algoritmo de Knuth-Morris-Pratt Algoritmo de finalización Knuth-Bendix MMIX
Premios notables	Premio Turing (1974) John von Neumann Medalla (1995) Premio Harvey (1995) Premio Kyoto (1996)
Sitio web
Donald E. Knuth

Donald Ervin Knuth (pron .: / k ə n U θ / Nooth kə-; nació 10 de enero 1938) es un científico de la computación y Profesor Emérito de la Universidad Stanford.

Él es el autor de la obra de varios volúmenes seminal The Art of Computer Programming. Knuth ha sido llamado el "padre" de la análisis de algoritmos. Contribuyó al desarrollo del análisis riguroso de la complejidad computacional de los algoritmos y técnicas matemáticas formales sistematizados para ello. En el proceso, también se popularizó la notación asintótica.

Además de las contribuciones fundamentales en varias ramas de la informática teórica, Knuth es el creador de la TeX sistema de tratamiento informático, la relacionada METAFONT lenguaje de definición de la fuente y el sistema de representación, y la Computadora de la familia moderna de tipos de letra.

Como escritor y erudito, Knuth creó el WEB / Sistemas de programación de computadoras CWEB diseñado para fomentar y facilitar programación literaria, y diseñó el MIX / MMIX arquitecturas de conjuntos de instrucciones.

Primeros años de vida

Knuth nació en Milwaukee, Wisconsin, donde su padre era dueño de una pequeña empresa de impresión y enseñó en la contabilidad Milwaukee Lutheran High School, donde se matriculó, ganando premios por sus logros. Aplicó su inteligencia de manera poco convencional, ganar un concurso cuando estaba en octavo grado, encontrando más de 4.500 palabras que podrían formarse a partir de las letras de "Bar gigante de Ziegler"; los jueces tenían sólo unos 2.500 palabras en su lista principal. Esto le ganó un set de televisión para su escuela y una barra de chocolate para todo el mundo en su clase.

Educación

Knuth tenía un tiempo difícil elegir la física más de la música como su principal al Case Institute of Technology (ahora parte de Case Western Reserve Universidad). También se unió Beta Nu Capítulo de la Theta Chi fraternidad. Mientras estudiaba física en el Instituto de Tecnología del caso, Knuth fue introducido en el IBM 650, uno de los primeros mainframes. Después de leer el manual del ordenador, Knuth decidió reescribir la asamblea y el código del compilador para la máquina que se utiliza en su escuela, porque creía que podía hacerlo mejor. En 1958, Knuth construyó un programa basado en el valor de cada jugador que podría ayudar a su equipo de baloncesto de la escuela a ganar la liga. Esto era tan novedoso una proposición en el momento en que fue recogida y publicada por Newsweek y también cubierto por Walter Cronkite en el CBS Evening News. Knuth fue uno de los editores fundadores de la Ingeniería y Ciencias de la opinión, que ganó un premio nacional como mejor revista técnica en 1959. Luego pasó de la física a las matemáticas, y en 1960 recibió su licenciatura en ciencias, recibiendo al mismo tiempo su amo de grado de la ciencia por un premio especial de la facultad que consideraba su destacada labor.

En 1963, obtuvo un Ph.D. en matemáticas (asesor: Marshall Hall) de la Instituto de Tecnología de California, y comenzó a trabajar allí como profesor asociado y comenzó a trabajar en The Art of Computer Programming. Él había aceptado inicialmente una comisión para escribir un libro sobre los compiladores que más tarde sería el de varios volúmenes The Art of Computer Programming. Este trabajo fue planeado originalmente para ser un solo libro, y luego planeó como una continuación, serie de siete volúmenes de seis y. En 1968, justo antes de que él publicó el primer volumen, Knuth aceptó un trabajo sobre los problemas de la Agencia de Seguridad Nacional ( NSA) a través de su FFRDC el Instituto de Análisis de Defensa ( IDA) División de Investigación de Comunicaciones situado en el momento en el campus de Princeton en el edificio Von Neumann como se indica en su cumulae vitae. Parece probable Knuth dejó el cargo y se unió a la facultad de Universidad de Stanford debido a sus creencias políticas y el clima político volátil en el campus en el momento.

Escritos

The Art of Computer Programming (TAOCP)

A continuación, la informática daba sus primeros pasos vacilantes. "Fue un campo totalmente nuevo", Knuth recuerda, "sin identidad real. Y el estándar de las publicaciones disponibles no era tan alto. Una gran cantidad de los papeles que salen eran simplemente equivocado. (...) Así que una de mis motivaciones era poner directamente una historia que había sido muy mal dicho ".

Después de producir el tercer volumen de su serie en 1976, expresó esa frustración con el estado incipiente de las herramientas de publicación electrónica entonces desarrolladas recientemente (en especial los que hizo aportaciones a phototypesetters) que se tomó el tiempo para trabajar en la composición tipográfica y creó el TeX y Herramientas MetaFont.

A partir de 2012, los tres primeros volúmenes y la primera parte del volumen cuatro de sus series han sido publicados.

Otras obras

Él es también el autor de Números Surrealista, una novela corta en matemática De John Conway teoría de conjuntos de construcción de un sistema alternativo de números. En lugar de limitarse a explicar el tema, el libro trata de mostrar el desarrollo de las matemáticas. Knuth quería que el libro preparar a los estudiantes para hacer la investigación original, creativo.

En 1995 , Knuth escribió el prólogo del libro A = B por Marko Petkovsek, Herbert Wilf y Doron Zeilberger.

Las creencias religiosas y el trabajo

Además de sus escritos sobre ciencias de la computación, Knuth, un luterano, es también el autor de 3:16 Biblia Textos Iluminado, en el que se examina la Biblia por un proceso de muestreo sistemático, es decir, un análisis del capítulo 3, versículo 16 de cada libro. Cada verso es acompañado por una representación en el arte caligráfico, aportados por un grupo de calígrafos, bajo la dirección de Hermann Zapf.

Las preocupaciones de salud

En 2006, Knuth fue diagnosticado con cáncer prostático. Fue operado en diciembre de ese año y comenzó "un poco de terapia de radiación ... como medida de precaución, pero el pronóstico se ve muy bien", como informó en su autobiografía de vídeo.

Reflexiones de ordenador

Knuth da charlas un par de veces al año en La Universidad de Stanford, que él llamó ordenador Reflexiones. También fue profesor visitante en la Oxford University Laboratorio de Computación en el Reino Unido y miembro honorario de Magdalen College.

Humor

Knuth es conocido por su "humor profesional".

Uno de Cheques de recompensa del Knuth

"Anidado parens "- Donald Knuth y Jacob Appelbaum

• Se utiliza para pagar los honorarios de un buscador de 2,56 dólares de los errores tipográficos o errores descubiertos en sus libros, porque "256 peniques es uno hexadecimal dólar ", y $ 0,32 para" sugerencias valiosas ". Según un artículo publicado en el Massachusetts Institute of Technology Review Technology, éstos Cheques de recompensa Knuth están "entre los trofeos más preciados de computerdom". Knuth tuvo que dejar de enviar los cheques reales en 2008, debido a fraude bancario, y en cambio ahora le da a cada buscador de error de un "certificado de depósito" de un equilibrio que cotiza en bolsa en su ficticia "Banco de San Serriffe ".
• Él advirtió una vez un corresponsal: "Guardaos de los errores en el código anterior, yo sólo he demostrado correcto, no lo intentó."
• El prefacio de Concreto Matemáticas incluye la siguiente anécdota: "Cuando Knuth enseñó Matemáticas de hormigón en Stanford, por primera vez, explicó el título un tanto extraño por decir que era su intento de enseñar un curso de matemáticas que fue duro en lugar de suave. Anunció que, contrariamente a las expectativas de algunos de sus colegas, no se le va a enseñar la teoría de la Agregados, ni de Piedra incrustación de Teorema, ni siquiera el Piedra-Čech teorema compactificación. (Varios estudiantes de la ingeniería civil departamento se levantaron y abandonaron la sala en silencio.) "

• Knuth publicó su primer artículo "científico" en una revista de la escuela en 1957 bajo el título " Sistema Potrzebie de Pesos y Medidas ". En ella, él definió la unidad fundamental de la longitud que el espesor de Mad # 26, y el nombre de la unidad fundamental de la fuerza "whatmeworry." Mad publicó el artículo en la edición # 33 (junio de 1957).
• El artículo de Knuth sobre la complejidad computacional de canciones " La complejidad de los Cantares ", se reimprimió dos veces en revistas de informática.
• Para demostrar el concepto, Knuth refiere intencionalmente "definición Circular" y "Definición, circular" el uno al otro en el índice de The Art of Computer Programming, Volumen 1.
• En el TUG 2010 Conferencia, Knuth anunció un XML-basado sucesor de TeX, titulado "Itex" (pronunciado [Iː˨˩˦tɛks˧˥], con un sonido de campana), lo que apoyaría características tales como unidades irracionales escala arbitraria, La impresión 3D, animación, y sonido estereofónico.

Premios

En 1971, Knuth fue el ganador de la primera ACM Gracia Premio Hopper Murray. Ha recibido varios premios, entre otros el Premio Turing, el Medalla Nacional de la Ciencia, la John von Neumann Medalla, y la Premio Kyoto.

En reconocimiento de las contribuciones de Knuth en el campo de la informática, en 1990 le fue concedido el título académico uno-de-uno-tipo de Profesor de The Art of Computer Programming, que desde entonces ha sido revisada para el profesor Emérito de The Art of Computer Programming.

En 1992, se convirtió en socio de la Academia de Ciencias francés. También ese año, se retiró de la investigación regular y enseñanza en La Universidad de Stanford con el fin de terminar The Art of Computer Programming. En 2003 fue elegido como miembro extranjero de la Real Sociedad.

Knuth fue elegido como becario (primera promoción de becarios) de la Society for Industrial and Applied Mathematics en 2009 por sus destacadas contribuciones a las matemáticas . Es miembro de la Academia Noruega de Ciencias y Letras. En 2012 se convirtió en miembro de la American Mathematical Society.

Honores otorgados a Knuth incluyen:

• Primero ACM Grace Murray Hopper Award 1971
• Turing Award, 1974
• Medalla Nacional de la Ciencia, 1979
• Medalla Franklin, 1988
• John von Neumann Medalla, 1995
• Premio Harvey de la Technion, 1995
• Premio Kyoto, 1996
• Miembro de la Computer History Museum, 1998
• Premio Katayanagi, 2010
• Fundación BBVA Fronteras del Conocimiento, 2010
• Universidad de Stanford Escuela de Ingeniería Premio Héroe de 2011

Obras

Una breve lista de sus obras:

• Donald E. Knuth, The Art of Computer Programming, Volúmenes 1-4, Addison-Wesley Professional

1. Volumen 1: Algoritmos Fundamentales (tercera edición), 1997. Addison-Wesley Professional, ISBN 0-201-89683-4
2. Volumen 2: Seminumerical Algoritmos (tercera edición), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
3. Volumen 3: Clasificación y búsqueda (segunda edición), 1998. Addison-Wesley Professional, ISBN 0-201-89685-0
4. 4A Volumen: Combinatoria Algoritmos, Parte 1, 2011. Addison-Wesley Professional, ISBN 0-201-03804-8
5. Volumen 4: algoritmos combinatorios (resto), en preparación

• Donald E. Knuth, The Art of Computer Programming, fascículos:

1. Volumen 1, Fascículo 1: MMIX-A RISC Informática para el Nuevo Milenio, 2005. ISBN 0-201-85392-2
2. Volumen 4, Fascículo 0: Introducción a los algoritmos combinatorios y funciones booleanas. 2008. ISBN 0-321-53496-4
3. Volumen 4, Fascículo 1: Trucos y técnicas a nivel de bit; Diagramas de decisión binaria. 2009. ISBN 0-321-58050-8
4. Volumen 4, Fascículo 2: Generación de todas las tuplas y permutaciones, 2005. ISBN 0-201-85393-0
5. Volumen 4, Fascículo 3: Generación de todas las combinaciones y particiones, 2005. ISBN 0-201-85394-9
6. Volumen 4, Fascículo 4: Generación de todos los árboles-Historia de Combinatoria Generación de 2006. ISBN 0-321-33570-8

• Donald E. Knuth, Computadoras y Composición:

1. Volumen A, El TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), x + 483pp. ISBN 0-201-13447-0
2. Volumen B, TeX: El Programa (Reading, Massachusetts: Addison-Wesley, 1986), xviii + 600pp. ISBN 0-201-13437-3
3. Volumen C, El METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), xii + 361pp. ISBN 0-201-13445-4
4. Volumen D, METAFONT: El Programa (Reading, Massachusetts: Addison-Wesley, 1986), xviii + 566pp. ISBN 0-201-13438-1
5. Volumen E, Computadora tipografías modernas (Reading, Massachusetts: Addison-Wesley, 1986), xvi + 588pp.

• Knuth, Donald E. Seleccionado serie de documentos

1. Donald E. Knuth, Programación literaria (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no. 27), 1992. ISBN 0-937073-80-6
2. Donald E. Knuth, Papeles seleccionados en Ciencias de la Computación (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no 59.), 1996. ISBN 1-881526-91-7
3. Donald E. Knuth, Tipografía Digital (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no 78.), 1999. ISBN 1-57586-010-4
4. Donald E. Knuth, Papeles seleccionados sobre Análisis de Algoritmos (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no 102.), 2000. ISBN 1-57586-212-3
5. Donald E. Knuth, Papeles seleccionados de Lenguajes (Stanford, California: Centro para el Estudio de la Lengua y de la información - CSLI Lecture Notes, no 139.), 2003. ISBN 1-57586-381-2 (tela), ISBN 1-57586-382-0 (paperback)
6. Donald E. Knuth, Papeles seleccionados en Matemática Discreta (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no 106.), 2003. ISBN 1-57586-249-2 (tela), ISBN 1-57586-248-4 (paperback)
7. Donald E. Knuth, Papeles seleccionados en Diseño de Algoritmos (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no 191.), 2010. ISBN 1-57586-583-1 (tela), ISBN 1-57586-582-3 (paperback)
8. Donald E. Knuth, Papeles seleccionados en Diversión y Juegos (Stanford, California: Centro para el Estudio de la Lengua y de la Información - CSLI Lecture Notes, no 192.), 2011. ISBN 978-1-57586-585-0 (tela), ISBN 978-1-57586-584-3 (paperback)
9. Donald E. Knuth, Compañero de los Documentos de Donald Knuth (Stanford, California: Centro para el Estudio de la Lengua y de la información - CSLI Lecture Notes, no 202.), 2011. ISBN 978-1-57586-635-2 (tela), ISBN 978-1-57586-634-5 (paperback)

• Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). Matemáticas Hormigón: Una base para la informática (Segunda ed.). Reading, MA: Addison-Wesley Publishing Company. pp. xiv + 657. ISBN 0-201-55802-5. SR 1.397.498.  
• Donald E. Knuth, números surreales: Cómo Dos Ex-Alumnos encendido para Matemáticas Puras y encontrado la felicidad total. 1974, ISBN 0-201-03812-9. Más información se puede encontrar en página oficial del libro
• Donald E. Knuth, The Stanford GraphBase: Una plataforma para Combinatoria Computing (Nueva York, ACM Press) 1993. segunda edición de bolsillo de impresión 2009. ISBN 0-321-60632-9
• Donald E. Knuth, 03:16 Biblia Textos Iluminado (Madison, Wisconsin: AR Editions), 1990. ISBN 0-89579-252-4
• Donald E. Knuth, Cosas a Informático Rara vez habla sobre (Centro para el Estudio de la Lengua y de la Información - CSLI Lecturas no 136), 2001. ISBN 1-57586-326-X