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 .
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 |
Decimal Dewey | 519 |
Clase LC | QA76.75 |
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 fue suspendido en 1977 por trabajos de composición tipográfica. La redacción de la copia final del Volumen 4A comenzó a mano en 2001, y el primer pre-fascí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. La tapa dura El Volumen 4A, que combina el Volumen 4, Fascículos 0–4, se publicó en 2011. El Volumen 4, Fascículo 6 ("Satisfacción") se publicó en diciembre de 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. [2] [3]
Historia
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 el bachillerato. 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. [4] 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. [5] 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. [6] Debido al crecimiento del material, 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 escribiera 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. [7]
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. [a]
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". [8] American Scientist ha incluido este trabajo entre "100 o más libros que dieron forma a un siglo de ciencia", en referencia al siglo XX, [9] y dentro de la comunidad de las ciencias de la computación se considera como el primer y aún 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 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. " [10] El New York Times se refirió a él como "el tratado que define la profesión". [11]
Volúmenes
Terminado
- Volumen 1 - Algoritmos fundamentales
- Capítulo 1 - Conceptos básicos
- Capítulo 2 - Estructuras de información
- Volumen 2 - Algoritmos seminuméricos
- 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 - Buscando
- Volumen 4A - Algoritmos combinatorios
- Capítulo 7 - Búsqueda combinatoria (parte 1)
Planificado
- Volumen 4B ... - Algoritmos combinatorios (capítulos 7 y 8 publicados en varios subvolúmenes)
- Capítulo 7 - Búsqueda combinatoria (continuación)
- Capítulo 8 - Recurrencia
- Volumen 5 - Algoritmos sintácticos (a partir de 2017[actualizar], estimado para su lanzamiento en 2025)
- Capítulo 9 - Escaneo léxico (también incluye 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
Esquemas del capítulo
Terminado
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 enteras y teoría de números elementales
- 1.2.5. Permutaciones y factoriales
- 1.2.6. Coeficientes binomiales
- 1.2.7. Números armónicos
- 1.2.8. Números de Fibonacci
- 1.2.9. Funciones de generación
- 1.2.10. Análisis de un algoritmo
- 1.2.11. Representaciones asintóticas
- 1.2.11.1. La notación O
- 1.2.11.2. Fórmula de suma de Euler
- 1.2.11.3. Algunos cálculos asintóticos
- 1.3 MMIX ( MIX en la copia impresa pero actualizado por el fascículo 1)
- 1.3.1. Descripción de MMIX
- 1.3.2. El lenguaje ensamblador MMIX
- 1.3.3. Aplicaciones a permutaciones
- 1.4. Algunas técnicas de programación fundamentales
- 1.4.1. Subrutinas
- 1.4.2. Corutinas
- 1.4.3. Rutinas interpretativas
- 1.4.3.1. Un simulador MIX
- 1.4.3.2. Rastrear rutinas
- 1.4.4. Entrada y salida
- 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. Pilas, colas y deques
- 2.2.2. Asignación secuencial
- 2.2.3. Asignación vinculada
- 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 binaria de árboles 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.2.1. El método congruencial lineal
- 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
- 4.1. Sistemas de números posicionales
- 4.2. Aritmética de coma flotante
- 4.2.1. Cálculos de precisión simple
- 4.2.2. Precisión de la aritmética de coma flotante
- 4.2.3. Cálculos de doble precisión
- 4.2.4. Distribución de números de coma flotante
- 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 radix
- 4.5. Aritmética racional
- 4.5.1. Fracciones
- 4.5.2. El mayor divisor común
- 4.5.3. Análisis del algoritmo de Euclides
- 4.5.4. Factorizar en Primes
- 4.6. Aritmética polinomial
- 4.6.1. División de polinomios
- 4.6.2. Factorización de polinomios
- 4.6.3. Evaluación de poderes
- 4.6.4. Evaluación de polinomios
- 4.7. Manipulación de Power Series
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
- 5.1. Propiedades combinatorias de las permutaciones
- 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
- Capítulo 7 - Búsqueda combinatoria
- 7.1. Ceros y unos
- 7.1.1. Conceptos básicos de booleanos
- 7.1.2. Evaluación booleana
- 7.1.3. Trucos y técnicas bit a bit
- 7.1.4. Diagramas de decisión binaria
- 7.2. Generando todas las posibilidades
- 7.2.1. Generación de patrones combinatorios básicos
- 7.2.1.1. Generando todas las n- tuplas
- 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 establecidas
- 7.2.1.6. Generando todos los árboles
- 7.2.1.7. Historia y otras referencias
- 7.2.1. Generación de patrones combinatorios básicos
- 7.1. Ceros y unos
Planificado
Volumen 4B, 4C, 4D - Algoritmos combinatorios
- Capítulo 7 - Búsqueda combinatoria (continuación)
- 7.2. Generando todas las posibilidades (continuación)
- 7.2.2. Programación de backtrack (publicado en el fascículo 5)
- 7.2.2.1. Enlaces de baile (publicados en el fascículo 5)
- 7.2.2.2. Satisfacción (publicado en el fascículo 6)
- 7.2.2.3. Satisfacción de restricciones
- 7.2.2.4. Caminos hamiltonianos (borrador en línea en el pre-fascículo 8A)
- 7.2.2.5. Camarillas
- 7.2.2.6. Cubiertas ( cubierta de vértice , problema de cubierta de conjunto , cubierta exacta , cubierta de Clique )
- 7.2.2.7. Cuadrícula
- 7.2.2.8. Un popurrí de rompecabezas (borrador en línea en el pre-fascículo 9B)
- 7.2.2.9. Estimación de los costos de retroceso (capítulo 6 de "Documentos seleccionados sobre análisis de algoritmos", y pre-fascículo 5b en la Sección 7.2.2 bajo el título "Estimaciones del tiempo de ejecución")
- 7.2.3. Generación de patrones inequivalentes (incluye discusión del teorema de enumeración de Pólya )
- 7.2.2. Programación de backtrack (publicado en el fascículo 5)
- 7.3. Caminos más cortos
- 7.4. Algoritmos de grafos
- 7.4.1. Componentes y recorrido
- 7.4.2. Clases especiales de gráficos
- 7.4.3. Gráficos expansores
- 7.4.4. Gráficos aleatorios
- 7.5. Algoritmos de red
- 7.5.1. Representantes distinguidos
- 7.5.2. El problema de la asignación
- 7.5.3. Flujos de red
- 7.5.4. Subárboles óptimos
- 7.5.5. Coincidencia óptima
- 7.5.6. Pedidos óptimos
- 7.6. Teoría de la independencia
- 7.6.1. Estructuras de independencia
- 7.6.2. Algoritmos matroides eficientes
- 7.7. Programación dinámica discreta (ver también método de matriz de transferencia )
- 7.8. Técnicas de ramificación y encuadernación
- 7,9. Tareas hercúleas (también conocidas como problemas NP-difíciles )
- 7.10. Casi optimización
- 7.2. Generando todas las posibilidades (continuación)
- Capítulo 8 - Recurrencia (capítulo 22 de "Artículos seleccionados sobre análisis de algoritmos")
Volumen 5 - Algoritmos sintácticos
a partir de 2017[actualizar], estimado para su lanzamiento en 2025
- 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 [12]
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 ). Addenda: [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). Addenda: [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). Adiciones: [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 . [13]
- Volumen 2: Algoritmos seminuméricos . Primera edición, 1969, xi + 624pp, ISBN 0-201-03802-1 . [13]
- 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.
- Volumen 4, Pre-fascículo 8A: Rutas y ciclos hamiltonianos
- Volumen 4, Pre-fascículo 9B: Un popurrí de rompecabezas
Ver también
- Introducción a los algoritmos
Referencias
Notas
- ^ La dedicatoria se redactó de forma ligeramente diferente en la primera edición.
Citas
- ^ nota para la casilla 3, carpeta 1
- ^ Página web de Addison-Wesley Pearson
- ^ Pearson educativo
- ^ Frana, Philip L. (8 de noviembre de 2001). "Una entrevista con Donald E. Knuth" . hdl : 11299/107413 .
- ^ Donald Knuth, Clásico de citas de esta semana , Contenidos actuales, Número 34 (23 de agosto de 1993), página 8.
- ^ Albers, Donald J. (2008). "Donald Knuth". En Albers, Donald J .; Alexanderson, Gerald L. (eds.). Gente matemática: perfiles y entrevistas (2 ed.). AK Peters. ISBN 978-1-56881-340-0.
- ^ "Reflexiones sobre un año de lectura de Knuth" . infinitepartitions.com . Consultado el 25 de julio de 2020 .
Trabajé, o al menos intenté trabajar, cada uno de los problemas del primer volumen. En algunos casos, me conformé con entender lo que la pregunta estaba tratando de pedir. En algunos casos, ni siquiera lo logré (no me juzgues hasta que lo pruebes tú mismo). A cada problema se le asigna una calificación de dificultad de 0 a 50, donde 0 es trivial y 50 es un "problema de investigación sin resolver" (en la primera edición, el último teorema de Fermat figuraba como 50, pero como Andrew Wiles lo demostró, se redujo a un 45 en la edición actual). Creo que pude resolver la mayoría de los problemas clasificados en <20; fue más allá de eso. La mayoría de los problemas cayeron en el rango de dificultad 20-30, pero la idea de Knuth de "difícil" es subjetiva, y los problemas que él considera de dificultad promedio terminaron por estirar dolorosamente mi cerebro comparativamente pequeño. Nunca he escalado el Monte Everest, pero imagino que todo el calvario se siente similar: doloroso mientras lo atraviesas, pero triunfante cuando llegas a la cima.
- ^ "Donald E. Knuth - ganador del premio AM Turing" . Soy Turing . Consultado el 25 de enero de 2017 .
- ^ Morrison, Philip ; Morrison, Phylis (noviembre-diciembre de 1999). "Un centenar de libros que dieron forma a un siglo de ciencia" . Científico estadounidense . 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, Matt. "Bill Gates dijo una vez 'definitivamente envíame un currículum' si terminas este libro diabólicamente difícil" . Business Insider . Consultado el 13 de junio de 2016 .
- ^ Lohr, Steve (17 de diciembre de 2001). "Frances E. Holberton, 84, programador informático temprano" . The New York Times . Consultado el 17 de mayo de 2010 .
- ^ "TAOCP - Planes futuros" .
- ^ a b Wells, Mark B. (1973). "Revisión: El arte de la programación de computadoras, Volumen 1. Algoritmos fundamentales y Volumen 2. Algoritmos seminuméricos por Donald E. Knuth" (PDF) . Boletín de la American Mathematical Society . 79 (3): 501–509. doi : 10.1090 / s0002-9904-1973-13173-8 .
Fuentes
- Slater, Robert (1987). Retratos en Silicona . MIT Press . ISBN 0-262-19262-4.
- Shasha, Dennis ; Lazere, Cathy (1995). Fuera de sus mentes: las vidas y los descubrimientos de 15 grandes científicos 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. 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 - (sobre la influencia de Bob Floyd )
- TAoCP y su influencia en la informática (Softpanorama)