stringtranslate.com

El arte de la programación informática

El arte de la programación informática ( TAOCP ) es una monografía completa escrita por el científico informático Donald Knuth que presenta algoritmos de programación y su análisis . Los volúmenes 1 a 5 tienen como objetivo representar el núcleo central de la programación informática para máquinas secuenciales.

Cuando Knuth comenzó el proyecto en 1962, originalmente lo concibió como un solo libro con doce capítulos. Los primeros tres volúmenes de lo que entonces se esperaba que fuera un conjunto de siete volúmenes se publicaron en 1968, 1969 y 1973. El trabajo comenzó en serio en el Volumen 4 en 1973, pero se suspendió en 1977 para trabajar en la composición tipográfica impulsada por la segunda edición del Volumen 2. La escritura de la copia final del Volumen 4A comenzó a mano en 2001, y el primer prefascículo en línea, 2A, apareció más tarde en 2001. [1] La primera entrega publicada del Volumen 4 apareció en rústica como Fascículo 2 en 2005. El Volumen 4A de tapa dura, que combina el Volumen 4, Fascículos 0-4, se publicó en 2011. El Volumen 4, Fascículo 6 ("Satisfiability") se lanzó en diciembre de 2015; El volumen 4, fascículo 5 ("Preliminares matemáticos Redux; Retroceso; Enlaces danzantes") se publicó en noviembre de 2019.

El volumen 4B consta de material desarrollado a partir de los fascículos 5 y 6. [2] El manuscrito se envió al editor el 1 de agosto de 2022 y el volumen se publicó en septiembre de 2022. [3] El fascículo 7, planificado para el volumen 4C, fue el tema de la charla de Knuth del 3 de agosto de 2022. [4]

Historia

Donald Knuth en 2005

Después de ganar una beca de Westinghouse Talent Search , Knuth se matriculó en el Case Institute of Technology (ahora Case Western Reserve University ), donde su rendimiento fue tan sobresaliente que la facultad votó para otorgarle una maestría en ciencias al completar la licenciatura . Durante sus vacaciones de verano, Knuth fue contratado por la Burroughs Corporation para escribir compiladores , ganando más en sus meses de verano de lo que ganaban los profesores titulares durante un año entero. [5] Tales hazañas hicieron de Knuth un tema de discusión entre el departamento de matemáticas, que incluía a Richard S. Varga .

En enero de 1962, cuando era estudiante de posgrado en el departamento de matemáticas de Caltech, Addison-Wesley le pidió a Knuth que escribiera un libro sobre el diseño de compiladores, y él propuso un alcance mayor. El mismo día, presentó una lista de doce títulos de capítulos. En el verano de 1962, trabajó en un compilador FORTRAN para UNIVAC , considerando que había "vendido mi alma al diablo" para desarrollar un compilador FORTRAN [6] : 15  después de los desarrollos de ALGOL con Burroughs. Permaneció como consultor de Burroughs durante el período de 1960 a 1968 mientras escribía el Volumen 1 'Algoritmos fundamentales'.

Durante este tiempo, también desarrolló un análisis matemático del sondeo lineal , lo que lo convenció de presentar el material con un enfoque cuantitativo. Después de recibir su doctorado en junio de 1963, comenzó a trabajar en su manuscrito, del cual terminó su primer borrador en junio de 1965, en3000 páginas escritas a mano. [7] Había asumido que unas cinco páginas escritas a mano se traducirían en una página impresa, pero su editor dijo en cambio que aproximadamente 1+12 páginas escritas a mano traducidas a una página impresa. Esto significaba que tenía aproximadamente2000 páginas impresas de material, tamaño que coincide aproximadamente con el de los tres primeros volúmenes publicados.

El primer volumen de 'El arte de la programación informática', 'Algoritmos fundamentales', tardó cinco años en completarse entre 1963 y 1968, mientras trabajaba en Caltech y Burroughs.

La dedicatoria de Knuth en el Volumen 1 dice:

Esta serie de libros está dedicada cariñosamente
a la computadora Tipo 650 que alguna vez se instaló en el
Instituto Tecnológico Case ,
en recuerdo de muchas tardes agradables. [a]

En el prefacio, agradece primero a su esposa Jill, luego a Burroughs por el uso de las computadoras B220 y B5500 para probar la mayoría de los programas, y a Caltech, la Fundación Nacional de Ciencias y la Oficina de Investigación Naval. [8] : xii 

La sección 2.5 de 'Fundamental Algorithms' trata sobre la asignación dinámica de almacenamiento . Algunas partes de esta sección se utilizan en el enfoque de Burroughs para la gestión de la memoria. Knuth se atribuye el mérito de "El método de "etiqueta de límite", presentado en la sección 2.5, fue diseñado por el autor en 1962 para su uso en un programa de control para la computadora B5000". [8] : 460 

Knuth recibió el apoyo de Richard S. Varga, quien era el asesor científico de la editorial. Varga estaba visitando a Olga Taussky-Todd y John Todd en Caltech . Con el entusiasta respaldo de Varga, la editorial aceptó los planes ampliados de Knuth. En su versión ampliada, el libro se publicaría en siete volúmenes, cada uno con solo uno o dos capítulos. [9] Debido al crecimiento en el Capítulo 7, que era menos de 100 páginas del manuscrito de 1965, según el Vol. 4A p. vi, el plan para el Volumen 4 se ha ampliado desde entonces para incluir los Volúmenes 4A, 4B, 4C, 4D y posiblemente más.

En 1976, Knuth preparó una segunda edición del Volumen 2, lo que requirió que se volviera a componer , pero el estilo de tipografía utilizado en la primera edición (llamado hot type ) ya no estaba disponible. En 1977, decidió dedicar algún tiempo a crear algo más adecuado. Ocho años después, regresó con T E X , que actualmente se utiliza para todos los volúmenes.

Otra característica de los volúmenes es la variación en la dificultad de los ejercicios incluyendo una calificación numérica que varía de 0 a 50, donde 0 es trivial y 50 es una pregunta abierta en la investigación contemporánea.

Recompensa por encontrar errores

La oferta de un cheque de recompensa llamado Knuth por valor de "un dólar hexadecimal" (100 HEX base 16 centavos, en decimal , son $2,56) por cualquier error encontrado, y la corrección de estos errores en impresiones posteriores, ha contribuido a la naturaleza altamente pulida y aún autorizada de la obra, mucho después de su primera publicación.

El lenguaje ensamblador en el libro

Todos los ejemplos de los libros utilizan un lenguaje hipotético llamado " lenguaje ensamblador MIX " (MIXAL), que se ejecuta en "un ordenador mítico llamado MIX". Actualmente, [¿ cuándo? ] el ordenador MIX está siendo reemplazado por el ordenador MMIX , que es una versión RISC . La conversión de MIX a MMIX fue un gran proyecto en curso para el que Knuth solicitó voluntarios para ayudar. Existe software como GNU MDK [10] para proporcionar emulación de la arquitectura MIX. Knuth considera que el uso del lenguaje ensamblador es necesario para juzgar la velocidad y el uso de memoria de los algoritmos.

El MIX era muy parecido a cualquier ordenador existente en aquel momento, pero más bonito. El nombre "MIX" es 1009 en números romanos y se obtiene mediante una fórmula que incluye los números de serie de varios ordenadores de la época: (360 + 650 + 709 + U3 + SS80 + 1107 + 1604 + G2- + B220 + S2000 + 920 + 601 + H800 + PDP-4 + 11)/16 = 1009 o MIX. El nombre MMIX es 2009 en números romanos y Knuth afirma que el MMIX es incluso mejor que el MIX.

Respuesta crítica

Knuth recibió el premio Turing en 1974 "por sus importantes contribuciones al análisis de algoritmos [...], y en particular por sus contribuciones al 'arte de la programación informática' a través de sus conocidos libros en una serie continua con este título". [11] American Scientist ha incluido esta obra entre los "100 libros que dieron forma a un siglo de ciencia", refiriéndose al siglo XX. [12] Las portadas de la tercera edición del Volumen 1 citan a Bill Gates diciendo: "Si crees que eres un programador realmente bueno... lee El arte de la programación informática (de Knuth) ... Definitivamente deberías enviarme un currículum si puedes leerlo completo". [13] El New York Times se refirió a él como "el tratado que define la profesión". [14]

Volúmenes

Terminado

Planificado

Esquemas de capítulos

Terminado

Volumen 1 – Algoritmos fundamentales

Volumen 2 – Algoritmos seminuméricos

Volumen 3 – Ordenación y búsqueda

Volumen 4A – Algoritmos combinatorios, parte 1

Volumen 4B – Algoritmos combinatorios, parte 2

Planificado

Volúmenes 4C, 4D, 4E, 4F – Algoritmos combinatorios[15]

Volumen 5 – Algoritmos sintácticos

Volumen 6 – La teoría de los lenguajes independientes del contexto[16]

Volumen 7 – Técnicas de compilación

Ediciones en inglés

Ediciones actuales

Estas son las ediciones actuales en orden por número de volumen:

Ediciones anteriores

Tomos completos

Estos volúmenes fueron reemplazados por ediciones más nuevas y están ordenados por fecha.

Fascículos

El volumen 4, fascículos 0 a 4 fueron revisados ​​y publicados como Volumen 4A.

El volumen 4, fascículos 5 y 6 fueron revisados ​​y publicados como Volumen 4B.

Prefascículos

Volumen 1

Volumen 4

Los prefascículos restantes contienen material borrador que aparecerá en futuros fascículos y volúmenes.

Véase también

Referencias

Notas

  1. ^ La dedicatoria fue redactada de manera ligeramente diferente en la primera edición.

Citas

  1. ^ "nota para la caja 3, carpeta 1".
  2. ^ Página web de Pearson InformIT, pestaña Contenido del libro. Addison-Wesley Professional. 28 de septiembre de 2022. ISBN 9780201038064.
  3. ^ Página web de Pearson InformIT. Addison-Wesley Professional. 28 de septiembre de 2022. ISBN 9780201038064.
  4. ^ "CP 2022: Respuestas a todas las preguntas, del 31 de julio al 5 de agosto de 2022, Haifa, Israel".
  5. ^ Frana, Philip L. (8 de noviembre de 2001). "Entrevista con Donald E. Knuth". hdl :11299/107413.
  6. ^ Feigenbaum, Edward (2007). "Historia oral de Donald Knuth" (PDF) . Museo de Historia de la Computación . Archivado (PDF) desde el original el 2008-12-09 . Consultado el 2020-09-17 .
  7. ^ Knuth, Donald E. (23 de agosto de 1993). "El clásico de las citas de esta semana" (PDF) . Contenido actual . pág. 8.
  8. ^ ab Knuth, Donald Ervin (3 de agosto de 2019). "El arte de la programación informática (TAOCP), segunda edición, 1973". Archivado desde el original el 3 de agosto de 2019. Consultado el 6 de febrero de 2018 .
  9. ^ Albers, Donald J. (2008). "Donald Knuth". En Albers, Donald J.; Alexanderson, Gerald L. (eds.). Personas matemáticas: perfiles y entrevistas (2 ed.). AK Peters . ISBN 978-1-56881-340-0.
  10. ^ "GNU MDK - Proyecto GNU - Free Software Foundation". www.gnu.org . Consultado el 23 de octubre de 2022 .
  11. ^ "Donald E. Knuth – Ganador del premio AM Turing". AM Turing . Consultado el 25 de enero de 2017 .
  12. ^ Morrison, Philip ; Morrison, Phylis (noviembre–diciembre de 1999). «100 or so Books that shaped a Century of Science» (Alrededor de 100 libros que dieron forma a un siglo de ciencia). American Scientist . 87 (6). Sigma Xi, The Scientific Research Society. Archivado desde el original el 2008-08-20 . Consultado el 11 de enero de 2008 .
  13. ^ Weinberger, Matt. "Bill Gates dijo una vez: 'Envíame un currículum' si terminas de leer este libro endiabladamente difícil". Business Insider . Consultado el 13 de junio de 2016 .
  14. ^ Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, 84, programadora de computadoras". The New York Times . Consultado el 17 de mayo de 2010 .
  15. ^ D'Agostino, Susan (16 de abril de 2020). "El informático que no puede dejar de contar historias". Quanta Magazine . Consultado el 26 de junio de 2023. Ahora, con 82 años, está trabajando arduamente en la parte B del volumen 4 y anticipa que el libro tendrá al menos las partes A a F.
  16. ^ "TAOCP – Planes futuros".
  17. ^ ab "TAOCP – Folleto" (PDF) .
  18. ^ ab Wells, Mark B. (1973). "Reseña: El arte de la programación informática, volumen 1. Algoritmos fundamentales y volumen 2. Algoritmos seminuméricos de Donald E. Knuth" (PDF) . Boletín de la Sociedad Matemática Americana . 79 (3): 501–509. doi : 10.1090/s0002-9904-1973-13173-8 .

Fuentes

Enlaces externos