El arte de la programación informática ( TAOCP ) es una monografía completa escrita por el informático Donald Knuth que presenta algoritmos de programación y su análisis . Los volúmenes 1 a 5 pretenden representar el núcleo central de la programación informática para máquinas secuenciales.
Cuando Knuth inició 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 en serio en el Volumen 4 comenzó en 1973, pero se suspendió en 1977 por el trabajo de composición tipográfica impulsado por la segunda edición. del Volumen 2. La redacción de la copia final del Volumen 4A comenzó a mano en 2001, y el primer prefascículo en línea, el 2A, apareció más tarde en 2001. [1] La primera entrega publicada del Volumen 4 apareció en edición de bolsillo como Fascículo 2 en 2005. El volumen 4A de tapa dura, que combina el volumen 4, fascículos 0 a 4, se publicó en 2011. El volumen 4, fascículo 6 ("Satisfiabilidad") se publicó en diciembre de 2015; El volumen 4, fascículo 5 ("Mathematical Preliminaries Redux; Backtracking; Dancing Links") 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 el 3 de agosto de 2022. [4]
Historia
Donald Knuth en 2005
Después de ganar una beca Westinghouse Talent Search , Knuth se matriculó en el Case Institute of Technology (ahora Case Western Reserve University ), donde su desempeño fue tan sobresaliente que la facultad votó para otorgarle una maestría en ciencias al completar su licenciatura . Durante sus vacaciones de verano, Knuth fue contratado por Burroughs Corporation para escribir compiladores , ganando más en sus meses de verano que los profesores titulares durante todo un año. [5] Tales hazañas convirtieron a Knuth en un tema de discusión entre el departamento de matemáticas, que incluía a Richard S. Varga .
En enero de 1962, cuando era un estudiante de posgrado en el departamento de matemáticas de Caltech, Addison-Wesley se acercó a Knuth para que escribiera un libro sobre el diseño de compiladores y propuso un alcance más amplio. El mismo día se le ocurrió una lista de títulos de doce capítulos. En el verano de 1962 trabajó en un compilador FORTRAN para UNIVAC . Durante este tiempo también se le ocurrió un análisis matemático del sondeo lineal , que le convenció para presentar el material desde un enfoque cuantitativo. Después de recibir su Ph.D. 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. [6] 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 alrededor de 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, que se acerca mucho al tamaño de los tres primeros volúmenes publicados. En este punto, Knuth recibió el apoyo de Richard S. Varga, quien era el asesor científico del editor. Varga estaba visitando a Olga Taussky-Todd y John Todd en Caltech . Con el entusiasta respaldo de Varga, el editor aceptó los planes ampliados de Knuth. En su versión ampliada, el libro se publicaría en siete volúmenes, cada uno con sólo uno o dos capítulos. [7] Debido al crecimiento del Capítulo 7, que tenía menos de 100 páginas del manuscrito de 1965, por vol. 4A pág. 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, requiriendo que se compusiera nuevamente, pero el estilo tipográfico utilizado en la primera edición (llamado tipografía caliente ) 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.
La oferta de un llamado cheque de recompensa Knuth por valor de "un dólar hexadecimal" (100 HEX base 16 centavos, en decimal , es $2,56) por cualquier error encontrado, y la corrección de estos errores en impresiones posteriores, ha contribuido a la publicación altamente pulida. y la naturaleza aún autorizada del trabajo, mucho después de su primera publicación. Otra característica de los volúmenes es la variación en la dificultad de los ejercicios. Knuth incluso tiene una escala de dificultad numérica para calificar esos ejercicios, que varía de 0 a 50, donde 0 es trivial y 50 es una pregunta abierta en la investigación contemporánea.
Todos los ejemplos de los libros utilizan un lenguaje llamado " lenguaje ensamblador MIX ", que se ejecuta en la hipotética computadora MIX. Actualmente, [ ¿cuándo? ] la computadora MIX está siendo reemplazada por la computadora MMIX , que es una versión RISC . Existe software como GNU MDK [8] para proporcionar emulación de la arquitectura MIX. Knuth considera necesario el uso del lenguaje ensamblador para juzgar la velocidad y el uso de memoria de los algoritmos.
respuesta crítica
Knuth recibió el Premio Turing de 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". [9] American Scientist ha incluido este trabajo entre "100 libros que dieron forma a un siglo de ciencia", en referencia al siglo XX, [10] . Las portadas de la tercera edición del Volumen 1 citan a Bill Gates diciendo: "Si crees que eres un muy buen programador... lee El arte de la programación informática (de Knuth) ... Definitivamente deberías enviarme un currículum si puedes leerlo completo. " [11] El New York Times se refirió a él como "el tratado que define la profesión". [12]
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 a 47, bajo el título "Estimaciones del tiempo de ejecución")
7.2.3. Generación de patrones no equivalentes (incluye discusión del teorema de enumeración de Pólya ) (ver "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 libres de contexto [14]
Capítulo 11 - Lingüística Matemática [15]
Volumen 7 – Técnicas de compilación
Capítulo 12 - Traducción del lenguaje de programación [15]
ediciones en ingles
Ediciones actuales
Estas son las ediciones actuales ordenadas por número de volumen:
El arte de la programación informática, volúmenes 1-4B en caja . (Reading, Massachusetts: Addison-Wesley, 2023), 3904 págs. 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 . Fe de erratas: [1] (8 de enero de 2011), [2] (2022, 49ª edición ). Anexo: [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 . Fe de erratas: [4] (8 de enero de 2011), [5] (2022, 45ª edición). Adenda: [6] (2011).
Volumen 3: Clasificación y búsqueda . Segunda edición (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+desplegable. ISBN 978-0-201-89685-5 , 0-201-89685-0 . Fe de erratas: [7] (8 de enero de 2011), [8] (2022, 45ª edició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 . Fe de erratas: [10] (2011), [11] (2022, 22.ª edició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 . Fe de 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) ISBN 0-201-85392-2 . Fe de erratas: [13] (2020-03-16) (estará en la cuarta edición del volumen 1)
Ediciones anteriores
Volúmenes 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 . [dieciséis]
Volumen 2: Algoritmos seminuméricos . Primera edición, 1969, xi+624pp, ISBN 0-201-03802-1 . [dieciséis]
Volumen 3: Clasificación y búsqueda . Primera edición, 1973, xi+723pp+desplegable, ISBN 0-201-03803-X . Fe de erratas: [14].
Volumen 1: Algoritmos fundamentales . Segunda edición, 1973, xxi+634pp, ISBN 0-201-03809-9 . Fe de erratas: [15].
Volumen 2: Algoritmos seminuméricos . Segunda edición, 1981, xiii+ 688pp, ISBN 0-201-03822-6 . Fe de erratas: [16].
El arte de la programación informática, volúmenes 1 a 3 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 en caja . Tercera edición (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp. ISBN 978-0-321-75104-1 , 0-321-75104-3
fascículos
El Volumen 4, Fascículos 0–4 fueron revisados y publicados como Volumen 4A.
Volumen 4, Fascículo 0: Introducción a algoritmos combinatorios y funciones booleanas . (Addison-Wesley Professional, 28 de abril de 2008) vi+240 páginas, ISBN 0-321-53496-4 . Fe de erratas: [17] (1 de enero de 2011).
Volumen 4, Fascículo 1: Técnicas y trucos bit a bit; Diagramas de decisión binaria . (Addison-Wesley Professional, 27 de marzo de 2009) viii + 260 páginas, ISBN 0-321-58050-8 . Fe de 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+127 páginas, ISBN 0-201-85393-0 . Fe de 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+150 páginas, ISBN 0-201-85394-9 . Fe de erratas: [20] (01/01/2011).
Volumen 4, Fascículo 4: Generando todos los árboles; Historia de la Generación Combinatoria . (Addison-Wesley, 6 de febrero de 2006) vi+120 páginas, ISBN 0-321-33570-8 . Fe de erratas: [21] (01/01/2011).
El Volumen 4, Fascículos 5-6 fueron revisados y publicados como Volumen 4B.
Volumen 4, Fascículo 5: Redux preliminares matemáticos; Retroceder; Enlaces de baile . (Addison-Wesley, 22 de noviembre de 2019) xiii + 382 páginas, ISBN 978-0-13-467179-6 . Fe de erratas: [22] (2020-03-27)
Volumen 4, Fascículo 6: Satisfacibilidad . (Addison-Wesley, 8 de diciembre de 2015) xiii + 310 páginas, ISBN 978-0-13-439760-3 . Fe de erratas: [23] (2020-03-26)
Pre-fascículos
Volúmen 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 borradores que aparecerán en futuros fascículos y volúmenes.
Volumen 4, Prefascículo 7A: Satisfacción de restricciones
Volumen 4, Prefascículo 8A: Rutas y ciclos hamiltonianos
Volumen 4, Prefascículo 8B: Camarillas
Volumen 4, Prefascículo 9B: Un popurrí de acertijos
Volumen 4, Pre-fascículo 9C: Estimación de los costos de retroceso
Volumen 4, Prefascículo 12A: Componentes y recorrido (Versión PDF)
^ "GNU MDK - Proyecto GNU - Fundación de Software Libre". www.gnu.org . Consultado el 23 de octubre de 2022 .
^ "Donald E. Knuth - Ganador del premio AM Turing". Soy Turing . Consultado el 25 de enero de 2017 .
^ Morrison, Felipe ; Morrison, Phylis (noviembre-diciembre de 1999). "Un centenar de libros que dieron forma a un siglo de ciencia". Científico americano . Sigma Xi, Sociedad de Investigación Científica. 87 (6). Archivado desde el original el 20 de agosto de 2008 . Consultado el 11 de enero de 2008 .
^ Weinberger, mate. "Bill Gates dijo una vez 'definitivamente envíame un currículum' si terminas 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, primera programadora informática". Los 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". Revista Quanta . 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 la F.
^ "TAOCP - Planes futuros".
^ ab (PDF) https://www-cs-faculty.stanford.edu/~knuth/brochure.pdf.{{cite web}}: Falta o está vacío |title=( ayuda )
^ ab Wells, Mark B. (1973). "Revisión: 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 Estadounidense . 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 sus mentes: las vidas y los descubrimientos de 15 grandes informáticos . Copérnico. ISBN 0-387-97992-1.
enlaces externos
Resumen de temas (página de inicio personal de Knuth)
Entrevista de historia oral con Donald E. Knuth en el Instituto Charles Babbage , Universidad de Minnesota, Minneapolis, 2001. Knuth analiza las patentes de software, la programación estructurada , la colaboración y su desarrollo de TeX . La historia oral analiza la escritura 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)
