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, previsto 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+1 ⁄ 2 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.
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 respaldo entusiasta 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 "una computadora mítica llamada MIX". Actualmente, [¿ cuándo? ] la computadora MIX está siendo reemplazada por la computadora MMIX , que es una versión RISC . La conversión de MIX a MMIX fue un gran proyecto en curso para el cual 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]
7.2.2.9 Estimación de los costos de retroceso (capítulo 6 de "Artículos seleccionados sobre análisis de algoritmos", y fascículo 5, págs. 44-47, bajo el título "Estimaciones de tiempo de ejecución")
7.2.3 Generación de patrones no equivalentes (incluye un análisis del teorema de enumeración de Pólya ) (véase "Técnicas para el rechazo de isomorfos", capítulo 4 de "Algoritmos de clasificación para códigos y diseños" de Kaski y Östergård)
Volumen 6 – La teoría de los lenguajes independientes del contexto[16]
Capítulo 11 – Lingüística matemática [17]
Volumen 7 – Técnicas de compilación
Capítulo 12 – Traducción de lenguajes de programación [17]
Ediciones en inglés
Ediciones actuales
Estas son las ediciones actuales en orden por número de volumen:
El arte de la programación informática, volúmenes 1-4B, edición en caja . (Reading, Massachusetts: Addison-Wesley, 2023), 3904 páginas. ISBN 978-0-13-793510-9 , 0-13-793510-2
Volumen 1: Algoritmos fundamentales . Tercera edición (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 978-0-201-89683-1 , 0-201-89683-4 . Erratas: [1] (8 de enero de 2011), [2] (49.ª edición de 2022 ). Adenda: [3] (2011).
Volumen 2: Algoritmos seminuméricos . Tercera edición (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 978-0-201-89684-8 , 0-201-89684-2 . Erratas: [4] (8 de enero de 2011), [5] (45.ª edición de 2022). Adenda: [6] (2011).
Volumen 3: Ordenación y búsqueda . Segunda edición (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 978-0-201-89685-5 , 0-201-89685-0 . Erratas: [7] (2011-01-08), [8] (2022, 45.ª impresión). Adenda: [9] (2011).
Volumen 4A: Algoritmos combinatorios, parte 1. Primera edición (Upper Saddle River, Nueva Jersey: Addison-Wesley, 2011), xv+883pp. ISBN 978-0-201-03804-0 , 0-201-03804-8 . Erratas: [10] (2011), [11] (2022, 22.ª impresión).
Volumen 4B: Algoritmos combinatorios, parte 2. Primera edición (Upper Saddle River, Nueva Jersey: Addison-Wesley, 2023), xviii+714pp. ISBN 978-0-201-03806-4 , 0-201-03806-4 . Erratas: [12] (2023, primera impresión).
Volumen 1, Fascículo 1: MMIX – Una computadora RISC para el nuevo milenio . (Addison-Wesley, 14 de febrero de 2005), 144 págs. ISBN 0-201-85392-2 . Erratas: [13] (14 de mayo de 2024) (estará en la cuarta edición del volumen 1)
Ediciones anteriores
Tomos completos
Estos volúmenes fueron reemplazados por ediciones más nuevas y están ordenados por fecha.
Volumen 1: Algoritmos fundamentales . Primera edición, 1968, xxi+634pp, ISBN 0-201-03801-3 . [18]
Volumen 2: Algoritmos seminuméricos . Primera edición, 1969, xi+624pp, ISBN 0-201-03802-1 . [18]
Volumen 3: Ordenación y búsqueda . Primera edición, 1973, xi+723pp+foldout, ISBN 0-201-03803-X . Erratas: [14].
Volumen 1: Algoritmos fundamentales . Segunda edición, 1973, xxi+634pp, ISBN 0-201-03809-9 . Erratas: [15].
Volumen 2: Algoritmos seminuméricos . Segunda edición, 1981, xiii+ 688pp, ISBN 0-201-03822-6 . Erratas: [16].
El arte de la programación informática, volúmenes 1-3, edición en caja . Segunda edición (Reading, Massachusetts: Addison-Wesley, 1998), págs. ISBN 978-0-201-48541-7 , 0-201-48541-9
El arte de la programación informática, volúmenes 1-4A, edición en caja . Tercera edición (Reading, Massachusetts: Addison-Wesley, 2011), 3168 páginas. ISBN 978-0-321-75104-1 , 0-321-75104-3
Fascículos
El volumen 4, fascículos 0 a 4 fueron revisados y publicados como Volumen 4A.
Volumen 4, Fascículo 0: Introducción a los algoritmos combinatorios y funciones booleanas . (Addison-Wesley Professional, 28 de abril de 2008) vi+240pp, ISBN 0-321-53496-4 . Erratas: [17] (1 de enero de 2011).
Volumen 4, Fascículo 1: Trucos y técnicas bit a bit; Diagramas de decisión binaria . (Addison-Wesley Professional, 27 de marzo de 2009) viii+260pp, ISBN 0-321-58050-8 . Erratas: [18] (1 de enero de 2011).
Volumen 4, Fascículo 2: Generación de todas las tuplas y permutaciones . (Addison-Wesley, 14 de febrero de 2005) v+127pp, ISBN 0-201-85393-0 . Erratas: [19] (1 de enero de 2011).
Volumen 4, Fascículo 3: Generación de todas las combinaciones y particiones . (Addison-Wesley, 26 de julio de 2005) vi+150pp, ISBN 0-201-85394-9 . Erratas: [20] (1 de enero de 2011).
Volumen 4, Fascículo 4: Generación de todos los árboles; Historia de la generación combinatoria . (Addison-Wesley, 2006-02-06) vi+120pp, ISBN 0-321-33570-8 . Erratas: [21] (2011-01-01).
El volumen 4, fascículos 5 y 6 fueron revisados y publicados como Volumen 4B.
Volumen 4, Fascículo 5: Preliminares matemáticos, redux; retroceso; vínculos danzantes . (Addison-Wesley, 22 de noviembre de 2019) xiii+382pp, ISBN 978-0-13-467179-6 . Erratas: [22] (27 de marzo de 2020)
Volumen 4, Fascículo 6: Satisfacción . (Addison-Wesley, 8 de diciembre de 2015) xiii+310pp, ISBN 978-0-13-439760-3 . Erratas: [23] (26 de marzo de 2020)
Prefascículos
Volumen 1
El prefascículo 1 fue revisado y publicado como Volumen 1, fascículo 1.
Volumen 4
Los prefascículos 0A, 0B y 0C fueron revisados y publicados como Volumen 4, fascículo 0.
Los prefascículos 1A y 1B fueron revisados y publicados como Volumen 4, fascículo 1.
Los prefascículos 2A y 2B fueron revisados y publicados como Volumen 4, fascículo 2.
Los prefascículos 3A y 3B fueron revisados y publicados como Volumen 4, fascículo 3.
Los prefascículos 4A y 4B fueron revisados* y publicados como Volumen 4, fascículo 4.
Los prefascículos 5A, 5B y 5C fueron revisados y publicados como Volumen 4, fascículo 5.
El prefascículo 6A fue revisado y publicado como Volumen 4, fascículo 6.
Los prefascículos restantes contienen material borrador que aparecerá en futuros fascículos y volúmenes.
Volumen 4, prefascículo 7A: Satisfacción de restricciones
Volumen 4, prefascículo 8A: Caminos y ciclos hamiltonianos
Volumen 4, prefascículo 8B: Camarillas
Volumen 4, prefascículo 9B: Un popurrí de acertijos
Volumen 4, prefascículo 9C: Estimación de los costos de retroceso
Volumen 4, prefascículo 12A: componentes y recorrido (versión PDF)
^ La dedicatoria fue redactada de manera ligeramente diferente en la primera edición.
Citas
^ "nota para la caja 3, carpeta 1".
^ Página web de Pearson InformIT, pestaña Contenido del libro. Addison-Wesley Professional. 28 de septiembre de 2022. ISBN9780201038064.
^ Página web de Pearson InformIT. Addison-Wesley Professional. 28 de septiembre de 2022. ISBN9780201038064.
^ "CP 2022: Respuestas a todas las preguntas, del 31 de julio al 5 de agosto de 2022, Haifa, Israel".
^ Frana, Philip L. (8 de noviembre de 2001). "Entrevista con Donald E. Knuth". hdl :11299/107413.
^ 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 .
^ Knuth, Donald E. (23 de agosto de 1993). "El clásico de las citas de esta semana" (PDF) . Contenido actual . pág. 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 .
^ "GNU MDK - Proyecto GNU - Free Software Foundation". www.gnu.org . Consultado el 23 de octubre de 2022 .
^ "Donald E. Knuth – Ganador del premio AM Turing". AM Turing . Consultado el 25 de enero de 2017 .
^ 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 .
^ Weinberger, Matt. "Bill Gates dijo una vez: 'Sin duda, envíame un currículum' si terminas de leer este libro endiabladamente difícil". Business Insider . Consultado el 13 de junio de 2016 .
^ 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 .
^ 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.
^ "TAOCP – Planes futuros".
^ ab "TAOCP – Folleto" (PDF) .
^ 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
Pizarrero, Robert (1987). Retratos en Silicio. Prensa del MIT. ISBN 0-262-19262-4.
Shasha, Dennis ; Lazere, Cathy (1995). Fuera de sí: Las vidas y descubrimientos de 15 grandes científicos informáticos . Copernicus. ISBN 0-387-97992-1.
Enlaces externos
Resumen de temas (página personal de Knuth)
Anuncio del Volumen 1 de 'El arte de la programación informática'
Entrevista oral con Donald E. Knuth en el Instituto Charles Babbage , Universidad de Minnesota, Minneapolis, 2001. Knuth habla sobre patentes de software, programación estructurada , colaboración y su desarrollo de TeX . La entrevista oral trata sobre la redacción de El arte de la programación informática .
"Robert W Floyd, In Memoriam", de Donald E. Knuth, 2003 - (sobre la influencia de Bob Floyd )
TAoCP y su influencia en la informática (Softpanorama)
