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 presentando algoritmos de programación y su análisis. Los volúmenes 1 a 5 pretenden representar el núcleo central de la programación de computadoras 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 redacción 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. 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 publicó en diciembre de 2015; El Volumen 4, Fascículo 5 ("Mathematical Preliminaries Redux; Backtracking; Dancing Links") se lanzó en noviembre de 2019.

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

Historia

Donald Knuth en 2005

Después de ganar una beca de Westinghouse Talent Search, Knuth se inscribió 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 la licenciatura. grado. 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 de tiempo completo durante todo un año. 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 estudiante de posgrado en el departamento de matemáticas de Caltech, Addison-Wesley se acercó a Knuth para escribir un libro sobre el diseño de compiladores, y él propuso un alcance más amplio. Se le ocurrió una lista de doce títulos de capítulos el mismo día. En el verano de 1962 trabajó en un compilador FORTRAN para UNIVAC. Durante este tiempo, también ideó un análisis matemático de sondeo lineal, que lo convenció de presentar el material con 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, en 3000 páginas escritas a mano. Había asumido que alrededor de 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 aproximadamente 2000 páginas impresas de material, lo que se acerca mucho al tamaño de las tres primeras publicadas. volúmenes En este punto, 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, 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 solo uno o dos capítulos. Debido al crecimiento en el Capítulo 7, que era menos de 100 páginas del manuscrito de 1965, según 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 volviera a componer, pero el estilo de letra utilizado en la primera edición (llamado tipo caliente) ya no estaba disponible. En 1977, decidió pasar algún tiempo creando algo más adecuado. Ocho años después, volvió con TEX, que actualmente se utiliza para todos los volúmenes.

La oferta del 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 naturaleza altamente pulida y aún autoritaria del trabajo. mucho tiempo 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.

La dedicatoria de Knuth dice:

Esta serie de libros es afectuosamente dedicado
al ordenador Tipo 650 una vez instalado en
Case Institute of Technology,
con quien he pasado muchas noches agradables.

Lenguaje ensamblador en el libro

Todos los ejemplos en los libros usan un lenguaje llamado "lenguaje ensamblador MIX", que se ejecuta en la computadora MIX hipotética. Actualmente, la computadora MIX está siendo reemplazada por la computadora MMIX, que es una versión RISC. Existe software como GNU MDK 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 la memoria de los algoritmos.

Respuesta crítica

Knuth recibió el Premio Turing de 1974 "por sus principales contribuciones al análisis de algoritmos […], y en particular por sus contribuciones al 'arte de la programación de computadoras' a través de sus conocidos libros en una serie continua con este título." American Scientist ha incluido este trabajo entre los "aproximadamente 100 libros que dieron forma a un siglo de ciencia", refiriéndose al estilo del siglo XX,y dentro de la comunidad informática se considera como el primer y mejor tratamiento integral de su tema. Las portadas de la tercera edición del Volumen 1 citan a Bill Gates diciendo: 'Si crees que eres un programador realmente bueno... lee (Knuth's) Art of Programación de computadoras... Definitivamente deberías enviarme un currículum si puedes leerlo completo." The New York Times se refirió a él como "el tratado que define la profesión".

Volúmenes

Completado

• Volumen 1 - Fundamental Algoritmos
  • Capítulo 1 - Conceptos básicos
  • Capítulo 2 - Estructuras de información
• Volumen 2 – Seminumerical Algoritmos
  • Capítulo 3 - Números aleatorios
  • Capítulo 4 – Aritmética
• Volumen 3 - Clasificación y búsqueda
  • Capítulo 5 - Clasificación
  • Capítulo 6 - Búsqueda
• Volumen 4A – Algoritmos Combinatoriales
  • Capítulo 7 - Búsqueda combinada (parte 1)
• Volumen 4B – Algoritmos combinados
  • Capítulo 7 - Búsqueda combinada (parte 2)

Planificada

• Volumen 4C... – Algoritmos Combinatoriales (capítulos 7 > 8 liberados en varios subvolúmenes)
  • Capítulo 7 – Búsqueda combinada (continuación)
  • Capítulo 8 - Recursión
• Volumen 5 - Sintaxis Algoritmos
  • Capítulo 9 – Escaneo Lexical (también incluye búsqueda de cadenas y compresión de datos)
  • Capítulo 10 - Técnicas de paráseo
• Volumen 6 – Teoría de Lenguas Sin Contexto
• Volumen 7 - Técnicas de compilador

Esquemas de los capítulos

Completado

Volumen 1: algoritmos fundamentales

• Capítulo 1 - Conceptos básicos
  • 1.1. Algoritmos
  • 1.2. Preliminares matemáticos
    • 1.2.1. Inducción matemática
    • 1.2.2. Números, potencias y logaritmos
    • 1.2.3. Sumas y productos
    • 1.2.4 Funciones enteros y teoría elemental del número
    • 1.2.5 Permutaciones y factores
    • 1.2.6. Coeficientes binomiales
    • 1.2.7. Números armónicos
    • 1.2.8 Números de Fibonacci
    • 1.2.9. Funciones generadoras
    • 1.2.10. Análisis de un algoritmo
    • 1.2.11 Representaciones sintomáticas
      • 1.2.11.1. La nota O
      • 1.2.11.2. Fórmula de absorción de Euler
      • 1.2.11.3. Algunos cálculos asintoticos
  • 1.3 MMIX (MIX en la copia de devolución pero actualizada por fascículo 1)
    • 1.3.1. Descripción de MMIX
    • 1.3.2. The MMIX Assembly Language
    • 1.3.3. Aplicaciones a las permutaciones
  • 1.4. Algunas técnicas fundamentales de programación
    • 1.4.1. Subroutines
    • 1.4.2. Coroutines
    • 1.4.3. Rutinas interpretativas
      • 1.4.3.1. Un simulador MIX
      • 1.4.3.2. Trace routines
    • 1.4.4 Input and Output
    • 1.4.5 Historia y bibliografía
• Capítulo 2 - Estructuras de información
  • 2.1. Introducción
  • 2.2. Listas lineales
    • 2.2.1 Stacks, Queues, and Deques
    • 2.2.2. Asignación secuencial
    • 2.2.3. Asignación enlazada (clasificación topológica)
    • 2.2.4. Listas circulares
    • 2.2.5 Listas doblemente vinculadas
    • 2.2.6. Arrays and Orthogonal Lists
  • 2.3. Árboles
    • 2.3.1. Traversing Binary Trees
    • 2.3.2. Representación de los árboles binarios
    • 2.3.3. Otras representaciones de los árboles
    • 2.3.4. Propiedades matemáticas básicas de los árboles
      • 2.3.4.1. Árboles libres
      • 2.3.4.2. Árboles de orientación
      • 2.3.4.3. El "lema infinito"
      • 2.3.4.4. Enumeración de árboles
      • 2.3.4.5. Longitud del camino
      • 2.3.4.6. Historia y bibliografía
    • 2.3.5. Listas y colección de basura
  • 2.4. Estructuras multirelacionadas
  • Asignación dinámica de almacenamiento
  • 2.6. Historia y bibliografía

Volumen 2: Algoritmos semiméricos

• Capítulo 3 - Números aleatorios
  • 3.1. Introducción
  • 3.2. Generación de números aleatorios uniformes
    • 3.2.1. El método lineal de congruencia
      • 3.2.1.1. Elección del módulo
      • 3.2.1.2. Elección del multiplicador
      • 3.2.1.3. Potency
    • 3.2.2. Otros métodos
  • 3.3. Pruebas estadísticas
    • 3.3.1. Procedimientos generales de examen para el estudio de los datos aleatorios
    • 3.3.2. Pruebas empíricas
    • 3.3.3. Tests teóricos
    • 3.3.4. El examen espectral
  • 3.4. Otros tipos de cantidades aleatorias
    • 3.4.1. Distribución numérica
    • 3.4.2. muestreo aleatorio y suciedad
  • 3.5. ¿Qué es una secuencia aleatoria?
  • 3.6. Resumen
• Capítulo 4 – Aritmética
  • 4.1. Sistemas del número de puestos
  • 4.2. Punto de flotación Aritmética
    • 4.2.1. Cálculos de una sola precisión
    • 4.2.2 Precisión del punto de flotación Aritmética
    • 4.2.3. Cálculos de doble precisión
    • 4.2.4 Distribución de los números de puntos flotantes
  • 4.3. Aritmética de precisión múltiple
    • 4.3.1. Los Algoritmos Clásicos
    • 4.3.2. Aritmética modular
    • 4.3.3. ¿Qué tan rápido podemos multiplicar?
  • 4.4. Conversión de radiación
  • 4.5. Aritmética racional
    • 4.5.1. Fracciones
    • 4.5.2 El Divisor Común más Grande
    • 4.5.3 Análisis del Algoritmo de Euclid
    • 4.5.4 Factoring into Primes
  • 4.6. Polynomial Arithmetic
    • 4.6.1 División de Polinomios
    • 4.6.2 Factorización de los polinomios
    • 4.6.3 Evaluación de las Potencias (explicación de cadenas de distribución)
    • 4.6.4 Evaluación de los polinomios
  • 4.7. Manipulación de la serie de energía

Volumen 3: clasificación y búsqueda

• Capítulo 5 - Clasificación
  • 5.1. Propiedades Combinadas de Permutaciones
    • 5.1.1. Inversiones
    • 5.1.2 Permutaciones de un multiset
    • 5.1.3. Corrientes
    • 5.1.4. Tableaux and Involutions
  • 5.2. Clasificación interna
    • 5.2.1. Clasificación por inserción
    • 5.2.2. Clasificación por intercambio
    • 5.2.3. Clasificación por selección
    • 5.2.4. Clasificación por fusión
    • 5.2.5. Clasificación por distribución
  • 5.3. Clasificación óptima
    • Clasificación mínima de comparación
    • 5.3.2 Medición de comparación mínima
    • 5.3.3. Selección de comparación mínima
    • 5.3.4. Redes de clasificación
  • 5.4. Clasificación externa
    • 5.4.1. Multiway Merging and Replacement Selection
    • 5.4.2. La fusión de Polyphase
    • 5.4.3. The Cascade Merge
    • 5.4.4. Reading Tape Backwards
    • 5.4.5. El orden oscilante
    • 5.4.6. Consideraciones prácticas para la fusión de la cinta
    • 5.4.7. Clasificación de radiación externa
    • Clasificación de dos cintas
    • 5.4.9. Discos y tambores
  • 5.5 Resumen, historia y bibliografía
• Capítulo 6 - Búsqueda
  • 6.1. Búsqueda secuencial
  • 6.2. Búsqueda por comparación de claves
    • 6.2.1 Buscar una tabla ordenada
    • 6.2.
    • 6.2.3. Árboles equilibrados
    • 6.2.4. Multiway Trees
  • 6.3. Búsqueda digital
  • 6.4. Hashing
  • 6.5. Retrieval on Secondary Keys

Volumen 4A: algoritmos combinatorios, parte 1

• Capítulo 7 – Combinatorial Búsqueda
  • 7.1. Cero y uno
    • 7.1.1. Básicos booleanos
    • 7.1.2 Evaluación booleana
    • 7.1.3. Trucos y Técnicas Bitwise
    • 7.1.4. Diagramas de decisiones binarias
  • 7.2. Generar todas las posibilidades
    • 7.2.1. Generación de patrones combinados básicos
      • 7.2.1.1. Generando todos los n-tuples
      • 7.2.1.2. Generando todas las permutaciones
      • 7.2.1.3. Generando todas las combinaciones
      • 7.2.1.4. Generando todas las particiones
      • 7.2.1.5. Generando todas las particiones de conjunto
      • 7.2.1.6. Generando todos los árboles
      • 7.2.1.7. Historia y nuevas referencias

Volumen 4B: algoritmos combinatorios, parte 2

• Capítulo 7 – Búsqueda Combinada (continuación)
  • 7.2. Generación de todas las posibilidades (continuación)
    • 7.2.2. Programación de retroceso (publicado en Fascicle 5)
      • 7.2.2.1. Enlaces de baile (incluye discusión de la cubierta Exact) (publicado en Fascicle 5)
      • 7.2.2.2 Satisfiabilidad (publicada en Fascículo 6)

Planificada

Volumen 4C, 4D: algoritmos combinatorios

• Capítulo 7 – Búsqueda Combinada (continuación)
  • 7.2. Generación de todas las posibilidades (continuación)
    • 7.2.2. Programación de retroceso (continuación)
      • 7.2.2.3 Satisfacción constante (proyecto en línea de prefase 7A)
      • 7.2.2.4. Rutas y ciclos Hamiltonianos (proyecto en línea de prefase 8A)
      • 7.2.2.5. Cliqueas
      • 7.2.2.6. Cubiertas (cubrimiento de Vertex, Cobertura de conjunto, Cubierta de salida, Cubierta de camarilla)
      • 7.2.2.7. Plazas
      • 7.2.2.8. A potpourri of puzzles (online draft in pre-fascicle 9B) (includes Perfect digital invariant)
      • 7.2.2.9. Estimación de los costos de retroceso (capítulo 6 de "Selected Papers on Analysis of Algorithms", y Fascicle 5, págs. 44 a 47, bajo el epígrafe "Running time estimates")
    • 7.2.3. Generar patrones inequivalentes (incluye la discusión del teorema de la enumeración de Pólya) (ver "Techniques for Isomorph Rejection", capítulo 4 de "Classification Algorithms for Codes and Designs" de Kaski y Östergård)
  • 7.3. Senderos más cortos
  • 7.4. algoritmos de Gráficos (en línea, borrador en prefascículo 12A)
    • 7.4.1. Componentes y traversales (proyecto en línea de prefase 12A)
      • 7.4.1.1. algoritmos de determinación de la Unión (proyecto en línea de prefase 12A)
      • 7.4.1.2. Primera búsqueda (en línea, proyecto de prefase 12A)
      • 7.4.1.3. Conectividad vertical y de borde
    • 7.4.2 Clases especiales de gráficos
    • 7.4.3. Gráficos más amplios
    • 7.4.4. Gráficos aleatorios
  • 7.5. Gráficos y optimización
    • 7.5.1 Coincidencia bipartita (incluido el emparejamiento máximo de la cardiopatía, el problema del matrimonio estable, Mariages Stables) (proyecto en línea de prefase 14A)
    • 7.5.2. El problema de la asignación
    • 7.5.3 Corrientes de red
    • 7.5.4. Subárboles óptimos
    • 7.5.5. Optimum matching
    • 7.5.6. Órdenes óptimas
  • 7.6. La teoría de la independencia
    • 7.6.1. Estructuras de la independencia
    • 7.6.2. algoritmos de esteroide eficientes
  • 7.7. Programación dinámica discreta (véase también el método Transfer-matrix)
  • 7.8. Técnicas de subdivisión y límites
  • 7.9. Tareas Hérculeas (también problemas de NP duro)
  • 7.10. Casi optimización
• Capítulo 8 – Recursión (capítulo 22 de "Documentos seleccionados sobre el análisis de algoritmos")

Volumen 5: algoritmos sintácticos

• Capítulo 9 – Escaneo Lexical (incluye también búsqueda de cadenas y compresión de datos)
• Capítulo 10 - Técnicas de paráseo

Volumen 6: La teoría de los lenguajes independientes del contexto

Volumen 7: Técnicas de compilación

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-4A juego en caja. Tercera edición (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp. ISBN 978-0-321-75104-1, 0-321-75104-3
• El arte de la programación informática, volúmenes 1-4B conjunto de cajas. (Reading, Massachusetts: Addison-Wesley, 2023), 3904pp. 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. Errata: [1] (2011-01-08), [2] (2020-03-26, 27a impresión). Adiciones: [3] (2011).
  • Volumen 2: Algoritmos sumergibles. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 978-0-201-89684-8, 0-201-89684-2. Errata: [4] (2011-01-08), [5] (2020-03-26, 26th printing). Adiciones: [6] (2011).
  • Volumen 3: Clasificació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. Errata: [7] (2011-01-08), [8] (2020-03-26, 27a impresión). Adiciones: [9] (2011).
  • Volumen 4A: Algoritmos combinados, Parte 1. First Edition (Upper Saddle River, New Jersey: Addison-Wesley, 2011), xv+883pp. ISBN 978-0-201-03804-0, 0-201-03804-8. Errata: [10] (2020-03-26?, 22nd printing).
  • Volumen 4B: Algoritmos combinados, Parte 2. Primera edición (Upper Saddle River, New Jersey: Addison-Wesley, 2023), xviii+714pp. ISBN 978-0-201-03806-4, 0-201-03806-4(2022-11-??, 2a impresión).
• Volumen 1, Fascículo 1: MMIX – Un ordenador del RISC para el nuevo milenio. (Addison-Wesley, 2005-02-14) ISBN 0-201-85392-2. Errata: [11] (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 recientes y están ordenados por fecha.

• Volumen 1: Algoritmos fundamentales. Primera edición, 1968, xxi+634pp, ISBN 0-201-03801-3.
• Volumen 2: Algoritmos sumergibles. Primera edición, 1969, xi+624pp, ISBN 0-201-03802-1.
• Volumen 3: Clasificación y búsqueda. Primera edición, 1973, xi+723pp+foldout, ISBN 0-201-03803-X. Errata: [12].
• Volumen 1: Algoritmos fundamentales. Segunda edición, 1973, xxi+634pp, ISBN 0-201-03809-9. Errata: [13].
• Volumen 2: Algoritmos sumergibles. Segunda edición, 1981, xiii+ 688pp, ISBN 0-201-03822-6. Errata: [14].
• El arte de la programación informática, volúmenes 1-3 conjunto de cajas. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), pp. ISBN 978-0-201-48541-7, 0-201-48541-9

Fascículos

El volumen 4's fascículos 0–4 se revisaron y publicaron como volumen 4A:

• Volumen 4, Fascículo 0: Introducción a Algoritmos Combinados y Funciones Booleanas. (Addison-Wesley Professional, 2008-04-28) vi+240pp, ISBN 0-321-53496-4. Errata: [15] (2011-01-01-01).
• Volumen 4, Fascículo 1: Tricks de bits y técnicas; Diagramas de decisiones binarias. (Addison-Wesley Professional, 2009-03-27) viii+260pp, ISBN 0-321-58050-8. Errata: [16] (2011-01-01).
• Volumen 4, Fascículo 2: Generando Todos los Tuplas y Permutaciones. (Addison-Wesley, 2005-02-14) v+127pp, ISBN 0-201-85393-0. Errata: [17] (2011-01-01).
• Volumen 4, Fascículo 3: Generando todas las combinaciones y particiones. (Addison-Wesley, 2005-07-26) vi+150pp, ISBN 0-201-85394-9. Errata: [18] (2011-01-01).
• Volumen 4, Fascículo 4: Generando Todos los Árboles; Historia de la Generación Combinada. (Addison-Wesley, 2006-02-06) vi+120pp, ISBN 0-321-33570-8. Errata: [19] (2011-01-01).

El volumen 4's fascículos 5 y 6 se revisaron y publicaron como volumen 4B:

• Volumen 4, Fascicle 5: Preliminaciones Matemáticas Redux; Backtracking; Dancing Links. (Addison-Wesley, 2019-11-22) xiii+382pp, ISBN 978-0-13-467179-6. Errata: [20] (2020-03-27)
• Volumen 4, Fascículo 6: Satisfiabilidad. (Addison-Wesley, 2015-12-08) xiii+310pp, ISBN 978-0-13-439760-3. Errata: [21] (2020-03-26)

Prefascículas

Los Volume 4 prefascículos 5A, 5B y 5C se revisaron y publicaron como fascículo 5.

El volumen 4's pre-fascículo 6A fue revisado y publicado como fascículo 6.

• Volumen 4, Prefascículo 7A: Satisfacción Constraint
• Volumen 4, Prefascículo 8A: Senderos y Ciclos Hamiltonianos
• Volumen 4, Prefascículo 9B: Un Potpourri de Puzzles
• Volumen 4, Prefascículo 12A: Componentes y Traversal (versión PDF)
• Volumen 4, Prefascículo 14A: Bipartite Matching