Hispanopedia Wiki
Articulo de referencia

El arte de la programación informática

[[Monograph]]"},"publisher":{"wt":"[[Addison-Wesley]]"},"pub_date":{"wt":"1968–present"},"media_type":{"wt":"Print ([[Hardcover]])"},"isbn":{"wt":"0-201-03801-3"}},"i":0}}]}"> V...

Hispanopedia WikiContenido en espanolLectura gratuita

Volúmenes 1 a 4B

El arte de la programación informática ( TAOCP ) es una monografía exhaustiva de varios volúmenes(Volúmenes 1-7) escrita por el científico informático Donald Knuth que presenta algoritmos de programación y su análisis . A partir de 2026Consta de los volúmenes publicados 1, 2, 3, 4A y 4B, y se prevé la publicación de más en el futuro. Los volúmenes 1 a 5 pretenden representar el núcleo central de la programación informática para máquinas secuenciales; los temas de los volúmenes 6 y 7 son importantes, pero más especializados. [ 1 ]

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 el trabajo de composición tipográfica motivado 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. [ 2 ] La primera entrega publicada del Volumen 4 apareció en rústica como Fascículo 2 en 2005. El Volumen 4A en tapa dura, que combina el Volumen 4, Fascículos 0–4, se publicó en 2011. El Volumen 4, Fascículo 6 ("Satisfacibilidad") se publicó en diciembre de 2015; El volumen 4, fascículo 5 ("Preliminares Matemáticas Revisadas; Retroceso; Enlaces Danzantes") se publicó en noviembre de 2019.

El volumen 4B consta de material derivado de los fascículos 5 y 6. [ 3 ] El manuscrito se envió al editor el 1 de agosto de 2022 y el volumen se publicó en septiembre de 2022. [ 4 ] El fascículo 7 ("Satisfacción de restricciones"), previsto para el volumen 4C, fue el tema de la charla de Knuth el 3 de agosto de 2022 [ 5 ] y se publicó el 5 de febrero de 2025. [ 6 ]

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 desempeño fue tan sobresaliente que el profesorado votó a favor de 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 esos meses que los catedráticos en todo un año. [ 7 ] Tales hazañas convirtieron a Knuth en tema de conversación en 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 se puso en contacto con Knuth para que escribiera un libro sobre diseño de compiladores, y él propuso un alcance mayor. Elaboró ​​una lista de doce títulos de capítulos ese mismo día. En el verano de 1962 trabajó en un compilador de FORTRAN para UNIVAC , considerando que había "vendido su alma al diablo" para desarrollar un compilador de FORTRAN [ 8 ] : 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 manuscritas. [ 9 ] Había asumido que unas cinco páginas manuscritas equivaldrían a una página impresa, pero su editor le dijo que aproximadamente 1 + 1/2 páginas manuscritas equivaldrían a una página impresa. Esto significaba que tenía aproximadamente2000 páginas impresas, un tamaño que se corresponde bastante 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 con cariño a la computadora Tipo 650 que una vez estuvo instalada en el Instituto Tecnológico Case , en recuerdo de muchas veladas 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. [ 10 ] : xii

La sección 2.5 de "Algoritmos Fundamentales" trata sobre la asignación dinámica de memoria . Partes de esta se utilizan en el enfoque de Burroughs para la gestión de memoria. Knuth se atribuye el mérito de: "el método de "etiqueta de límite", introducido 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". [ 10 ] : 460

Knuth recibió el apoyo de Richard S. Varga, asesor científico de la editorial. Varga visitaba 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. [ 11 ] Debido al crecimiento del Capítulo 7, que ocupaba menos de 100 páginas del manuscrito de 1965, según el 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, que requería una nueva composición tipográfica , pero el tipo de letra utilizado en la primera edición (conocido como hot type ) ya no estaba disponible. En 1977, decidió dedicar tiempo a crear una tipografía más adecuada. Ocho años después, regresó con TEX , que actualmente se utiliza en todos los volúmenes .

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

Recompensa por encontrar errores

La oferta de un cheque de recompensa, denominado " cheque Knuth ", por valor de "un dólar hexadecimal" (100 centavos hexadecimales en base 16 , en decimal , son 2,56 dólares) por cualquier error encontrado, y la corrección de estos errores en las ediciones posteriores, ha contribuido al carácter altamente pulido y aún autorizado de la obra, mucho después de su primera publicación.

El lenguaje ensamblador en el libro

Todos los ejemplos en los libros usan un lenguaje hipotético llamado " lenguaje ensamblador MIX " (MIXAL), que se ejecuta en "una computadora mítica llamada 'MIX'", que fue desarrollada para ser contemporánea con otras computadoras de las décadas de 1960 y 1970. A pesar de la intención de Knuth de que MIX resistiera el paso del tiempo, comentó en la tercera edición del primer volumen que, no obstante, se había vuelto "bastante obsoleto". [ 12 ] Durante la década de 1990, Knuth comenzó a desarrollar MMIX , una computadora moderna basada en RISC , que Knuth describió como "Una computadora RISC para el nuevo milenio". [ 13 ] La conversión de MIX a MMIX fue un gran proyecto de varios años, para el cual Knuth solicitó ayuda de voluntarios. [ 12 ] MMIX alcanzaría su versión estable en 2011. [ 13 ] Knuth considera que el uso del lenguaje ensamblador es necesario para evaluar la velocidad y el uso de memoria de los algoritmos.

Respecto al origen de MIX, Knuth comentó que era muy parecido a cualquier computadora existente en ese momento, "pero, quizás, mejor". [ 12 ] El nombre MIX se puede representar como 1009 en números romanos . Además, Knuth explica que la derivación de 1009 provino de tomar dieciséis computadoras reales que consideró similares a MIX y en las cuales MIX se podía simular fácilmente. Promedió las partes numéricas de sus números de modelo con igual ponderación:

⌊(360 + 650 + 709 + 7070 + U3 + SS80 + 1107 + 1604 + G20 + B220 + S2000 + 920 + 601 + H800 + PDP-4 + II) / 16⌋ = 1009

Existe software como el GNU MIX Development Kit (MDK) para proporcionar emulación de la arquitectura MIX. [ 14 ]

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". [ 15 ] American Scientist ha incluido esta obra entre "unos 100 libros que moldearon un siglo de la ciencia", refiriéndose al siglo XX. [ 16 ] 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". [ 17 ] The New York Times se refirió a él como "el tratado definitorio de la profesión". [ 18 ]

Volúmenes

Terminado

Planificado

ediciones en inglés

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 (edición 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+650 págs. ISBN 978-0-201-89683-1,0-201-89683-4. Erratas:(desde el 08/01/2011),(de 2022, 49.ª edición ). Anexos:(2011).
    • Volumen 2: Algoritmos seminuméricos . Tercera edición (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762 págs. ISBN 978-0-201-89684-8,0-201-89684-2. Erratas:(desde el 08/01/2011),(de 2022, 45.ª edición). Anexos:(2011).
    • Volumen 3: Clasificación y búsqueda . Segunda edición (Reading, Massachusetts: Addison-Wesley, 1998), xiv + 780 págs. + desplegable. ISBN 978-0-201-89685-5,0-201-89685-0. Erratas:(desde el 08/01/2011),(de 2022, 45.ª edición). Anexos:(2011).
    • Volumen 4A: Algoritmos combinatorios, Parte 1. Primera edición (Upper Saddle River, Nueva Jersey: Addison-Wesley, 2011, 26.ª reimpresión), xv+883 págs. ISBN 978-0-201-03804-0,0-201-03804-8. Erratas:(desde 2011),(de 2022, vigésima edición).
    • Volumen 4B: Algoritmos combinatorios, Parte 2. Primera edición (Upper Saddle River, Nueva Jersey: Addison-Wesley, 2023, 3.ª impresión), xviii+714 págs. ISBN 978-0-201-03806-4,0-201-03806-4. Erratas:(a partir de 2023, primera edició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:(desde 2005, primera edición) (estará en la cuarta edición del volumen 1)
  • El suplemento MMIX de Martin Ruckert. (Addison-Wesley), 193 págs. ISBN 0-13-399231-4. Una conversión de los problemas/programas MIX de los volúmenes 1, 2 y 3 a MMIX.
  • Volumen 4, Fascículo 7: Satisfacción de restricciones . (Addison-Wesley, 5 de febrero de 2025), xiv+281 págs. ISBN 978-0-13-532824-8. Erratas:(28-12-2025).

Ediciones anteriores

volúmenes completos

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

  • Volumen 1: Algoritmos fundamentales . Primera edición, 1968, xxi+634 págs., ISBN 0-201-03801-3. [ 24 ]
  • Volumen 2: Algoritmos seminuméricos . Primera edición, 1969, xi+624 págs., ISBN 0-201-03802-1. [ 24 ]
  • Volumen 3: Clasificación y búsqueda . Primera edición, 1973, xi+723 págs.+desplegable, ISBN 0-201-03803-X. Erratas:.
  • Volumen 1: Algoritmos fundamentales . Segunda edición, 1973, xxi+634 págs., ISBN 0-201-03809-9. Erratas:.
  • Volumen 2: Algoritmos seminuméricos . Segunda edición, 1981, xiii + 688 págs., ISBN 0-201-03822-6. Erratas:.
  • El arte de la programación informática, volúmenes 1-3, estuche . 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, estuche . Tercera edición (Reading, Massachusetts: Addison-Wesley, 2011), 3168 págs. ISBN 978-0-321-75104-1,0-321-75104-3

Fascículos

Los fascículos 0 a 4 del volumen 4 fueron revisados ​​y publicados como volumen  4A.

  • Volumen 4, Fascículo 0: Introducción a los algoritmos combinatorios y las funciones booleanas . (Addison-Wesley Professional, 28 de abril de 2008) vi+240 págs., ISBN 0-321-53496-4. Erratas:(01-01-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+260 págs., ISBN 0-321-58050-8. Erratas:(01-01-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:(01-01-2011).
  • Volumen 4, Fascículo 3: Generación de todas las combinaciones y particiones . (Addison-Wesley, 26 de julio de 2005) vi+150 págs., ISBN 0-201-85394-9. Erratas:(01-01-2011).
  • Volumen 4, Fascículo 4: Generación de todos los árboles; Historia de la generación combinatoria . (Addison-Wesley, 6 de febrero de 2006) vi+120 págs., ISBN 0-321-33570-8. Erratas:(01-01-2011).

Los fascículos 5 y 6 del volumen 4 fueron revisados ​​y publicados como volumen  4B.

  • Volumen 4, Fascículo 5: Preliminares Matemáticos Revisados; Retroceso; Enlaces Danzantes . (Addison-Wesley, 22 de noviembre de 2019) xiii+382 págs., ISBN 978-0-13-467179-6. Erratas:(27-03-2020)
  • Volumen 4, Fascículo 6: Satisfacibilidad . (Addison-Wesley, 8 de diciembre de 2015) xiii+310 págs., ISBN 978-0-13-439760-3. Erratas:(26-03-2020)

Prefascículos

Los prefasciculos contienen borradores de material en desarrollo para futuros fasciculos. Se publican en línea principalmente para que los expertos en la materia puedan revisar el contenido antes de distribuirlo a un público más amplio. [ 25 ]

Volumen 1

  • Prefascículo 1: MMIX fue revisado y publicado como Volumen 1, fascículo 1.

Volumen 4

  • Los prefascículos 0A: Introducción a la búsqueda combinatoria , 0B: Fundamentos booleanos y 0C: Evaluación booleana fueron revisados ​​y publicados como el volumen 4, fascículo 0.
  • Los prefascículos 1A: Trucos y técnicas bit a bit y 1B: Diagramas de decisión binaria fueron revisados ​​y publicados como el volumen 4, fascículo 1.
  • Los prefascículos 2A: Generación de todas las n-tuplas y 2B: Generación de todas las permutaciones fueron revisados ​​y publicados como el volumen 4, fascículo 2.
  • Los prefascículos 3A: Generación de todas las combinaciones y 3B: Generación de todas las particiones fueron revisados ​​y publicados como el volumen 4, fascículo 3.
  • Los prefascículos 4A: Generación de todos los árboles y 4B: Historia de la generación combinatoria fueron revisados ​​y publicados como el volumen 4, fascículo 4.
  • Los prefascículos 5A: Preliminares Redux , 5B: Introduction to Backtracking y 5C: Dancing Links fueron revisados ​​y publicados como el volumen 4, fascículo 5.
  • El prefascículo 6A: Satisfacibilidad fue revisado y publicado como Volumen 4, fascículo 6.
  • El prefascículo 7A: Satisfacción de restricciones fue revisado y publicado como el volumen 4, fascículo 7.

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

  • Volumen 4, Prefascículo 8A: Caminos y ciclos hamiltonianos (versión PDF no mantenida)
  • Volumen 4, Prefascículo 8B: Grupos
  • 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 no mantenida)
  • Volumen 4, Prefascículo 14A: Emparejamiento bipartito
  • Volumen 4, Prefascículo 16A: Introducción a la recursión

Véase también

Referencias

Notas

  1. ↑ La dedicatoria estaba redactada de forma ligeramente diferente en la primera edición.

Citas

  1. ↑ "Nota de Knuth sobre sus libros" . Archivado del original el 1 de marzo de 2025. Consultado el 28 de marzo de 2025 .
  2. ↑ "nota para la caja 3, carpeta 1" . Archivado del original el 3 de diciembre de 2019. Consultado el 3 de diciembre de 2019 .
  3. ↑ Página web de Pearson InformIT, pestaña Contenido del libro . Addison-Wesley Professional. 28/09/2022. ISBN 9780201038064. Archivado del original el 19-07-2022 . Consultado el 19-07-2022 .
  4. ↑ Página web de Pearson InformIT . Addison-Wesley Professional. 28 de septiembre de 2022. ISBN 9780201038064. Archivado del original el 19-07-2022 . Consultado el 19-07-2022 .
  5. ↑ "CP 2022 Todas las preguntas respondidas, 31 de julio–5 de agosto de 2022, Haifa, Israel" . Archivado del original el 22 de julio de 2022. Consultado el 22 de julio de 2022 .
  6. ↑ Página web de Pearson InformIT . Addison-Wesley Professional. 5 de febrero de 2025. ISBN 9780135328248Archivado del original el 18 de febrero de 2025. Consultado el 18 de febrero de 2025 .
  7. ↑ Frana, Philip L. (2001-11-08). "Una entrevista con Donald E. Knuth" . hdl : 11299/107413 . Archivado del original el 2018-06-20 . Recuperado el 2018-06-20 .
  8. ↑ Feigenbaum, Edward (2007). "Historia oral de Donald Knuth" (PDF) . Museo de Historia de la Computación . Archivado (PDF) del original el 9 de diciembre de 2008. Recuperado el 26 de noviembre de 2024 .
  9. ↑ Knuth, Donald E. (1993-08-23). ​​"El clásico de citas de esta semana" (PDF) . Contenidos actuales . pág. 8. Archivado (PDF) del original el 5 de enero de 2024. Recuperado el 26 de noviembre de 2024 . 
  10. 1 2 Knuth, Donald Ervin (2019-08-03). "El arte de la programación informática (TAOCP) 2.ª edición, 1973" . Archivado del original el 2019-08-03 . Recuperado el 2024-11-26 .
  11. ^ 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.
  12. 1 2 3 Knuth, Donald (1997). El arte de la programación informática, Volumen 1, Algoritmos fundamentales (Tercera ed.). Addison Wesley Professional. pág. 124. ISBN   0201896834.
  13. 1 2 Knuth, Donald (1 de septiembre de 2011). "Un mensaje de Don Knuth, 1 de septiembre de 2011" . Página principal de MMIX . Recuperado el 20 de abril de 2026 .
  14. ↑ "GNU MDK - Proyecto GNU - Fundación del Software Libre" . www.gnu.org . Archivado del original el 23/10/2022 . Consultado el 23/10/2022 .
  15. ↑ "Donald E. Knuth – Ganador del Premio AM Turing" . AM Turing . Archivado del original el 17 de octubre de 2019. Consultado el 25 de enero de 2017 .
  16. ↑ Morrison, Philip ; Morrison, Phylis (noviembre-diciembre de 1999). "Unos 100 libros que moldearon un siglo de ciencia" . American Scientist . 87 (6). Sigma Xi, The Scientific Research Society. Archivado del original el 17 de junio de 2017. Consultado el 26 de noviembre de 2024 .
  17. ↑ Weinberger, Matt. "Bill Gates dijo una vez: 'Sin duda, envíenme un currículum' si terminan este libro endiabladamente difícil" . Business Insider . Archivado del original el 12 de julio de 2023. Consultado el 25 de noviembre de 2024 .
  18. ↑ Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, de 84 años, pionera en la programación informática" . The New York Times . Archivado del original el 16 de diciembre de 2014. Consultado el 26 de noviembre de 2024 .
  19. ↑ "Ediciones futuras de Knuth, volúmenes 1-3" . Archivado del original el 23 de abril de 2025. Consultado el 25 de abril de 2025 .
  20. ↑ D'Agostino, Susan (16 de abril de 2020). "El científico informático que no puede dejar de contar historias" . Quanta Magazine . Archivado del original el 27 de noviembre de 2024. Recuperado el 26 de noviembre de 2024. Ahora, a sus 82 años, trabaja arduamente en la parte B del volumen 4 y anticipa que el libro tendrá al menos las partes A a la F.
  21. ↑ Knuth, Donald (2025). El arte de la programación informática, Volumen 4, Fascículo 7: Satisfacción de restricciones . Addison Wesley Professional. ISBN 9780135328248.
  22. ↑ "TAOCP – Planes futuros" . Archivado del original el 3 de agosto de 2019. Consultado el 20 de junio de 2018 .
  23. 1 2 "TAOCP – Folleto" (PDF) . Archivado (PDF) del original el 26-09-2024 . Recuperado el 26-11-2024 .
  24. 1 2 Wells, Mark B. (1973). "Reseña: El arte de la programación informática, volumen 1. Algoritmos fundamentales y volumen 2. Algoritmos seminuméricos por Donald E. Knuth" (PDF) . Boletín de la Sociedad Matemática Americana . 79 (3): 501– 509. doi : 10.1090/s0002-9904-1973-13173-8 . Archivado (PDF) del original el 20 de octubre de 2016. Recuperado el 20 de junio de 2018 .
  25. ↑ "Donald Knuth explica el uso de los prefascículos" . Consultado el 19 de enero de 2026 .{{cite web}}: CS1 mantenimiento: estado de la URL ( enlace )

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 los descubrimientos de 15 grandes científicos informáticos . Copernicus. ISBN 0-387-97992-1.
  • Resumen de temas (página web personal de Knuth)
  • Anuncio del Volumen 1 de 'El arte de la programación informática'
  • Entrevista de historia oral con Donald E. Knuth en el Instituto Charles Babbage de la Universidad de Minnesota, Minneapolis, 2001. Knuth habla sobre patentes de software, programación estructurada , colaboración y el desarrollo de TeX . La entrevista también aborda la escritura de El arte de la programación informática .
  • "Robert W Floyd, In Memoriam", por Donald E. Knuth , 2003 - (sobre la influencia de Bob Floyd )
  • TAoCP y su influencia en la informática (Softpanorama)