El arte de la programación informática -The Art of Computer Programming

El arte de la programación informática
ArtOfComputerProgramming.jpg
El arte de la programación informática, volumen 1: algoritmos fundamentales
Autor Donald Knuth
País Estados Unidos
Idioma inglés
Género Monografía de no ficción
Editor Addison-Wesley
Fecha de publicación
 1968– (el libro aún está incompleto)
Tipo de medio Imprimir ( tapa dura )
ISBN 0-201-03801-3
519
Clase LC QA76.75

The Art of Computer Programming ( TAOCP ) es una monografía completaescrita por el científico informático Donald Knuth que cubre muchos tipos de algoritmos de programación y su análisis .

Knuth comenzó el proyecto, originalmente concebido como un solo libro con doce capítulos, en 1962. 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 Volume 4 en 1973, pero se suspendió en 1977 por trabajos de composición tipográfica a raíz de 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 prefací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 a 4, se publicó en 2011. El Volumen 4, Fascículo 6 ("Satisfacción") se publicó en diciembre 2015; El volumen 4, fascículo 5 ("Redux de los preliminares matemáticos; retroceso; enlaces de baile") se publicó en noviembre de 2019.

Se espera que los fascículos 5 y 6 constituyan los primeros dos tercios del Volumen 4B. Knuth no ha anunciado ninguna fecha estimada para el lanzamiento del Volumen 4B, aunque su método utilizado para el Volumen 4A es publicar el volumen de tapa dura en algún momento después de la publicación de los fascículos de tapa blanda que contiene. Las estimaciones de los editores a corto plazo sitúan la fecha de lanzamiento en mayo o junio de 2019, lo que resultó ser incorrecto.

Historia

Donald Knuth en 2005

Después de ganar una beca 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. 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. 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 un estudiante graduado en el departamento de matemáticas de Caltech, Addison-Wesley se acercó a Knuth para que escribiera un libro sobre diseño de compiladores, y propuso un alcance más amplio. Se le ocurrió una lista de 12 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 se le ocurrió un análisis matemático de sondeo lineal , 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. 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 asemeja mucho al tamaño de los tres primeros volúmenes publicados. El editor estaba nervioso por aceptar un proyecto de este tipo de un estudiante de posgrado. 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 apoyo 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 tenía menos de 100 páginas del manuscrito de 1965, por 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, requiriendo que se compusiera nuevamente, pero el estilo de tipografía utilizado en la primera edición (llamado hot type ) ya no estaba disponible. En 1977, decidió dedicar un tiempo a crear algo más adecuado. Ocho años después, regresó con T E X , que actualmente se usa para todos los volúmenes.

La oferta del llamado cheque de recompensa de 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 que el y naturaleza todavía 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.

La dedicación de Knuth dice:

Esta serie de libros está dedicada cariñosamente
al ordenador Type 650 una vez instalado en el
Case Institute of Technology ,
con el que he pasado muchas veladas agradables.

Lenguaje ensamblador en el libro

Todos los ejemplos de los libros utilizan un lenguaje llamado " lenguaje ensamblador MIX ", que se ejecuta en la hipotética computadora MIX. 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 de lenguaje ensamblador es necesario para evaluar la velocidad y el uso de memoria de los algoritmos.

respuesta crítica

Knuth fue galardonado con el Premio Turing 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". American Scientist ha incluido este trabajo entre los "100 libros que dieron forma a un siglo de ciencia", en referencia al siglo XX, y dentro de la comunidad de las ciencias de la computación se considera el primer y aún mejor tratamiento integral de este tema. Las portadas de la tercera edición del Volumen 1 citan a Bill Gates diciendo: "Si crees que eres un buen programador ... lee El arte de la programación informática (de Knuth) ... Definitivamente deberías enviarme un currículum vitae si puedes leerlo completo. " El New York Times se refirió a él como "el tratado que define la profesión".

Volúmenes

Terminado

Planificado

Esquemas del capítulo

Terminado

Volumen 1 - Algoritmos fundamentales

  • Capítulo 1 - Conceptos básicos
  • Capítulo 2 - Estructuras de información
    • 2.1. Introducción
    • 2.2. Listas lineales
      • 2.2.1. Pilas, colas y deques
      • 2.2.2. Asignación secuencial
      • 2.2.3. Asignación vinculada ( clasificación topológica )
      • 2.2.4. Listas circulares
      • 2.2.5. Listas doblemente enlazadas
      • 2.2.6. Matrices y listas ortogonales
    • 2.3. Árboles
      • 2.3.1. Atravesando árboles binarios
      • 2.3.2. Representación de árboles binarios de árboles
      • 2.3.3. Otras representaciones de árboles
      • 2.3.4. Propiedades matemáticas básicas de los árboles
        • 2.3.4.1. Árboles libres
        • 2.3.4.2. Árboles orientados
        • 2.3.4.3. El "lema del infinito"
        • 2.3.4.4. Enumeración de árboles
        • 2.3.4.5. Longitud de la trayectoria
        • 2.3.4.6. Historia y bibliografía
      • 2.3.5. Listas y recolección de basura
    • 2.4. Estructuras multienlace
    • 2.5. Asignación dinámica de almacenamiento
    • 2.6. Historia y Bibliografía

Volumen 2 - Algoritmos seminumé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 congruencial lineal
        • 3.2.1.1. Elección de módulo
        • 3.2.1.2. Elección de multiplicador
        • 3.2.1.3. Potencia
      • 3.2.2. Otros metodos
    • 3.3. Pruebas estadísticas
      • 3.3.1. Procedimientos generales de prueba para estudiar datos aleatorios
      • 3.3.2. Pruebas empíricas
      • 3.3.3. Pruebas teóricas
      • 3.3.4. La prueba espectral
    • 3.4. Otros tipos de cantidades aleatorias
      • 3.4.1. Distribuciones numéricas
      • 3.4.2. Muestreo aleatorio y barajado
    • 3.5. ¿Qué es una secuencia aleatoria ?
    • 3.6. Resumen
  • Capítulo 4 - Aritmética

Volumen 3 - Clasificación y búsqueda

  • Capítulo 5 - Clasificación
    • 5.1. Propiedades combinatorias de las permutaciones
      • 5.1.1. Inversiones
      • 5.1.2. Permutaciones de un multiset
      • 5.1.3. Carreras
      • 5.1.4. Cuadros e involuciones
    • 5.2. Clasificación interna
      • 5.2.1. Ordenar por inserción
      • 5.2.2. Ordenar por intercambio
      • 5.2.3. Ordenar por selección
      • 5.2.4. Ordenar por fusión
      • 5.2.5. Clasificación por distribución
    • 5.3. Clasificación óptima
      • 5.3.1. Clasificación de comparación mínima
      • 5.3.2. Fusió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. Selección de fusión y reemplazo de múltiples vías
      • 5.4.2. La fusión polifásica
      • 5.4.3. La fusión en cascada
      • 5.4.4. Leyendo la cinta al revés
      • 5.4.5. La especie oscilante
      • 5.4.6. Consideraciones prácticas para la fusión de cintas
      • 5.4.7. Clasificación de radix externa
      • 5.4.8. Clasificación de dos cintas
      • 5.4.9. Discos y tambores
    • 5.5. Resumen, historia y bibliografía
  • Capítulo 6 - Buscando
    • 6.1. Búsqueda secuencial
    • 6.2. Búsqueda por comparación de claves
      • 6.2.1. Buscando una tabla ordenada
      • 6.2.2. Búsqueda de árbol binario
      • 6.2.3. Árboles equilibrados
      • 6.2.4. Árboles de múltiples vías
    • 6.3. Búsqueda digital
    • 6.4. Hashing
    • 6.5. Recuperación de claves secundarias

Volumen 4A - Algoritmos combinatorios, Parte 1

Planificado

Volumen 4B, 4C, 4D - Algoritmos combinatorios

Volumen 5 - Algoritmos sintácticos

  • Capítulo 9 - Escaneo léxico (incluye también búsqueda de cadenas y compresión de datos)
  • Capítulo 10 - Técnicas de análisis

Volumen 6 - La teoría de los lenguajes libres de 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 en caja . Tercera edición (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp. ISBN  978-0-321-75104-1 , 0-321-75104-3
    • 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] (2011-01-08), [2] (2020-03-26, 27ª impresión ). Adiciones: [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] (2011-01-08), [5] (2020-03-26, 26ª impresión). Adiciones: [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] (2011-01-08), [8] (2020-03-26, 27ª impresión). Addenda: [9] (2011).
    • Volumen 4A: Algoritmos combinatorios, Parte 1 . Primera edición (Reading, Massachusetts: Addison-Wesley, 2011), xv + 883pp. ISBN  978-0-201-03804-0 , 0-201-03804-8 . Fe de erratas: [10] (2020-03-26,? 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: [11] (2020-03-16) (estará en la cuarta edición del volumen 1)
  • Volumen 4, Fascículo 5: Preliminares matemáticos Redux; Retroceso; Enlaces de baile . (Addison-Wesley, 2019-11-22) xiii + 382pp, ISBN  978-0-13-467179-6 . Fe de erratas: [12] (2020-03-27) (pasará a formar parte del volumen 4B)
  • Volumen 4, Fascículo 6: Satisfacción . (Addison-Wesley, 8 de diciembre de 2015) xiii + 310pp, ISBN  978-0-13-439760-3 . Fe de erratas: [13] (2020-03-26) (pasará a formar parte del volumen 4B)

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 seminuméricos . Primera edición, 1969, xi + 624pp, ISBN  0-201-03802-1 .
  • 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-3 en caja . Segunda edición (Reading, Massachusetts: Addison-Wesley, 1998), págs. ISBN  978-0-201-48541-7 , 0-201-48541-9

Fascículos

Los fascículos 0-4 del Volumen 4 se revisaron y publicaron como Volumen 4A:

  • Volumen 4, Fascículo 0: Introducción a los algoritmos combinatorios y las funciones booleanas . (Addison-Wesley Professional, 2008-04-28) vi + 240pp, ISBN  0-321-53496-4 . Fe de 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 . 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 + 127pp, 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 + 150pp, ISBN  0-201-85394-9 . Fe de 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 . Fe de erratas: [21] (1 de enero de 2011).

Los fascículos 5-6 del Volumen 4 pasarán a formar parte del Volumen 4B:

  • Volumen 4, Fascículo 5: Preliminares matemáticos Redux; Retroceso; Enlaces de baile . (Addison-Wesley, 2019-11-22) xiii + 382pp, ISBN  978-0-13-467179-6 . Fe de erratas: [22] (27/03/2020)
  • Volumen 4, Fascículo 6: Satisfacción . (Addison-Wesley, 8 de diciembre de 2015) xiii + 310pp, ISBN  978-0-13-439760-3 . Fe de erratas: [23] (2020-03-26)

Pre-fascículos

Los pre-fascículos 5A, 5B y 5C del Volumen 4 fueron revisados ​​y publicados como fascículo 5.

El pre-fascículo 6A del Volumen 4 fue revisado y publicado como fascículo 6.

Ver también

Referencias

Notas

Citas

Fuentes

enlaces externos