El arte de programar

The Art of Computer Programming [ 1] es una  monografía fundamental del famoso matemático e informático estadounidense Donald Knuth , dedicada a la consideración y análisis de los algoritmos más importantes utilizados en informática . En 1999, el libro fue reconocido como una de las doce mejores monografías físicas y matemáticas del siglo [2] .

El proyecto de escritura del libro fue iniciado por el autor en 1962. Inicialmente, se planeó lanzarlo en un volumen, pero la cantidad de material resultó ser tan grande que la cantidad de volúmenes se incrementó a siete. Los primeros tres volúmenes se publicaron con bastante rapidez: volumen 1, en 1968, volumen 2, en 1969, volumen 3, en 1973. A esto le siguió una pausa hasta febrero de 2005, en que el autor publicó la primera parte del cuarto volumen. Se tomó la decisión de publicar las partes restantes del cuarto volumen aproximadamente dos veces al año en números separados, después de lo cual se publicaría oficialmente el cuarto volumen completo. Durante 2005-2009 se publicaron los números 0, 1, 2, 3 y 4 y en 2011 se publicó el volumen 4A que incluye información de estos números. También en 2005, se publicó el número 1 "MMIX: una computadora RISC para el nuevo milenio", cuya información se incluirá en la nueva cuarta edición del primer volumen. El número 6 (en 2015) y el número 5 (en 2017) se publicaron como parte del Volumen 4B. El volumen 4B en sí se lanzó en 2022.

Dado que Knuth siempre había considerado El arte de la programación como el principal proyecto de su vida , se retiró en 1993 con la intención de concentrarse por completo en escribir las partes que faltaban y poner en orden las existentes [3] . Él creía que tomaría 20 años completar el trabajo [4] .

Historia

Como experto reconocido en diseño de compiladores , en 1962 Knuth comenzó a escribir un libro sobre diseño de compiladores. Pronto se dio cuenta de que el alcance del material debía ser mucho más amplio. En junio de 1965 terminó de escribir la primera versión de lo que originalmente quería publicar en un libro de doce secciones. El volumen del texto manuscrito era de 3000 páginas. Según los cálculos de Knuth, este volumen debería haber cabido en 600 páginas impresas, pero, como le informó su editor, el volumen real sería de 2000 páginas. En este sentido, la estructura del libro fue revisada a favor de varios volúmenes, 1-2 secciones cada uno. Desde entonces, debido al constante crecimiento del material, se decidió que el cuarto volumen también se dividiría en libros separados: 4A, 4B, 4C y posiblemente 4D. Pero esta división, al parecer, no será definitiva, ya que los apartados 7.1 y 7.2.1 ocupan ya más de 650 páginas en total.

En 1976, Knuth produjo una segunda edición del segundo volumen, que requirió reescribir . Pero el diseño tipográfico ( monotipo ) utilizado en la primera edición ya no estaba disponible a estas alturas. Para evitar frustraciones similares en el futuro, en 1977 Knuth comenzó a desarrollar su propio sistema tipográfico de composición tipográfica por computadora. Según sus cálculos, el trabajo no debería haber llevado más de seis meses, pero tardó unos diez años en completarse [5] . El sistema se llamó TeX y actualmente se utiliza para componer todos los volúmenes de El arte de la programación. Además, más tarde TeX se convirtió en el estándar de facto para escribir artículos y monografías en las ciencias naturales.

Al igual que los otros libros de Knuth, El arte de programar lleva su marca registrada: por cada error encontrado en el texto, el autor paga un dólar hexadecimal, o $ 2,56 (0x100 centavos , base 16 ). Otra característica distintiva del libro es la abundancia de ejercicios para la autorrealización, de diversos grados de dificultad, que van desde simples problemas de "calentamiento" hasta problemas abiertos. La dificultad de cada ejercicio se califica en una escala numérica de 0 a 50. Así, en las primeras ediciones , el Último Teorema de Fermat se marcaba con el número 50 , pero en la tercera edición esta calificación se "devaluó" ​​a 45, ya que por esa tiempo su demostración ya había dejado de ser un problema abierto.

Resumen de convenciones para el volumen tres, 1978 "Clasificación y búsqueda" (izquierda - evaluación, derecha - breve explicación)

• Triángulo Negro - Recomendado
• M - Con un sesgo matemático
• VM - Requiere conocimiento de "matemáticas superiores"
• 00 - Requiere una respuesta inmediata
• 10 - Simple (por 1 minuto)
• 20 - Dificultad media (durante 15 minutos)
• 30 - Mayor dificultad
• 40 - Para "matpraktikum"
• 50 - Problema de investigación

Contenidos

El plan original para escribir el libro sugería el siguiente desglose del material.

• Volumen 1. Algoritmos básicos.
  • Capítulo 1. Conceptos básicos.
  • Capítulo 2. Estructuras de información.
• Volumen 2. Algoritmos derivados.
  • 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
• Volumen 4. Algoritmos combinatorios.
  • Capítulo 7. Búsqueda combinatoria.
  • Capítulo 8. Recurrencia.
• Tomo 5. Algoritmos Sintácticos.
  • Capítulo 9. Búsqueda lexicográfica.
  • Capítulo 10. Búsqueda sintáctica.
• Tomo 6. Teoría de los Lenguajes.
• Tomo 7. Compiladores.

De hecho, este esquema se implementó hasta el tercer volumen inclusive.

Actualmente[ ¿cuándo? ] publicó el volumen 4A, que contiene las primeras secciones del capítulo 7. Está previsto que las nuevas secciones se publiquen inicialmente en números separados (aproximadamente 128 páginas), aproximadamente dos números por año (los números 0, 1, 2, 3 y 4 se publicaron de manera similar antes del lanzamiento del volumen 4A).

Lenguaje de ejemplo orientado a máquina

Los programas de ejemplo del libro utilizan un "ensamblador MIX" diseñado para ejecutarse en una computadora MIX hipotética. En la tercera edición, el MIX obsoleto fue reemplazado por MMIX , que tiene una arquitectura RISC completa . Existe un software que proporciona emulación de la máquina (M)MIX en computadoras estándar compatibles con IBM. La colección de compiladores GNU tiene la capacidad de compilar código C/C++ en la arquitectura de destino MMIX.

Muchos lectores se desaniman por el hecho de usar un lenguaje de bajo nivel, pero Knuth considera que su elección está justificada, ya que la unión a la arquitectura es necesaria para poder juzgar con precisión características del algoritmo como la velocidad, el consumo de memoria, y así. Sin embargo, como resultado de esta elección, el público objetivo se reduce en gran medida. Además, su alcance es limitado como un "libro de recetas" para programadores prácticos, muchos de los cuales no conocen el lenguaje ensamblador y, si lo saben, no tienen ganas de traducir algoritmos de bajo nivel del libro a lenguajes de alto nivel. . Muchas guías de práctica que presentan el mismo material de una manera más popular se publican por esta misma razón.

Crítica

La característica principal de la monografía de Knuth, que la distingue favorablemente de otros libros sobre programación, es el listón excepcionalmente alto de la calidad del material y la presentación académica, así como la profundidad del análisis de los temas en consideración. Gracias a ello, se ha convertido en un auténtico éxito de ventas y en un libro de referencia para todo programador profesional [6] . La revista American Scientist incluyó El arte de la programación en su lista de las 12 mejores monografías físicas y matemáticas del siglo XX [2] junto con los trabajos de Dirac sobre mecánica cuántica , Einstein sobre la teoría de la relatividad , Russell y Whitehead sobre los fundamentos . de matemáticas , y algunos otros [7] .

La portada de la tercera edición del primer volumen del libro contiene una cita de Bill Gates : "Si te consideras un programador realmente bueno... lee El arte de programar (Knuth)... Si puedes leer todo este trabajo , entonces definitivamente deberías enviarme un currículum" [8] .

Ediciones

originales