The Art of Computer Programming

The Art of Computer Programming (tsz. The Art of Computer Programmings)

1. (informatika) The Art of Computer Programming (TAOCP) egy többkötetes könyvsorozat, amelyet Donald E. Knuth amerikai informatikus írt. A sorozat a számítástechnika egyik alapműve, különösen az algoritmusok és azok hatékonyságának mélyreható tárgyalásában. Knuth e munkájával lefektette az algoritmikus gondolkodás alapjait, amely a mai napig jelentős hatással van az informatikai oktatásra és kutatásra.

1. Volume 1: Fundamental Algorithms (1968, legutóbbi frissítés: 3rd ed. 1997)
   • Alapvető fogalmak
   • A számítógépek matematikai modelljei
   • Algoritmusok végrehajtása és költsége
2. Volume 2: Seminumerical Algorithms (1969, 3rd ed. 1997)
   • Számábrázolás
   • Véletlenszám-generálás
   • Számelméleti algoritmusok (pl. prímszámok, legnagyobb közös osztó)
3. Volume 3: Sorting and Searching (1973, 2nd ed. 1998)
   • Rendezési algoritmusok (pl. quicksort, mergesort, heapsort)
   • Keresési technikák (pl. bináris keresés, hash-elés, keresőfák)
4. Volume 4A: Combinatorial Algorithms, Part 1 (2011)
   • Generatív kombinatorika
   • Permutációk, kombinációk, sorozatok generálása

📦 A Volume 4B, 4C és Volume 5–7 előkészületben vannak, és fokozatosan jelennek meg a “Fascicle” sorozatokon keresztül.

• Formális pontosság: Knuth nem csak algoritmusokat ír le, hanem azok matematikai megalapozottságát is, különös figyelmet fordítva a bonyolultságelemzésre.
• Példakód MIX-ben: Az algoritmusokat egy saját tervezésű oktató-assembler nyelven, a MIX-en demonstrálja. Később ezt a MMIX nyelv váltotta fel.
• TeX-ben szedett: Knuth a könyv szépsége miatt saját szedőrendszert fejlesztett: ez lett a TeX, amellyel a TAOCP is készült.

Knuth a pseudokód helyett MIX assembly nyelvet használ a példákban, például egy bináris keresésre így nézhet ki a logika:

Binary Search:
Set L to 1
Set R to N
While L ≤ R:
    Set M to floor((L+R)/2)
    If X = A, return M
    If X < A, set R = M-1
    Else set L = M+1

De ezt a könyvben általában alacsony szintű gépi utasításokkal, lépésenkénti memóriaműveletekkel mutatja be.

• A TAOCP sorozat a számítástudomány „Bibliája”.
• Az algoritmuselmélet és programozás mélyebb, elméleti megközelítését hangsúlyozza.
• Knuth kitalálta a „literate programming” fogalmát is, amelyben a kód és annak magyarázata együtt szerepel dokumentált formában.

Knuth műve nem kezdőknek szól. A könyv matematikailag és logikailag erősen megalapozott, sokszor részletes levezetésekkel és bizonyításokkal dolgozik. Az olvasóktól magas szintű absztrakciós készséget és algoritmikus gondolkodást vár el.

• Knuth minden olyan olvasónak, aki hibát talál a könyvben, egy igazi, aláírt csekket küld (jellemzően $2.56 értékben – “256 cents”, utalás a bájt méretére).
• A TAOCP késleltetett kiadásai miatt gyakran elhangzik: „Knuth csak akkor fejezi be a TAOCP sorozatot, amikor a P vs NP kérdést megoldják.”

• Donald Knuth – szerző, TeX/LaTeX megalkotója
• MIX/MMIX – oktatási célú gépi architektúra
• Literate programming – dokumentált programozás
• Pseudocode – Knuth saját stílusában, gépközelibb formában
• Algorithm analysis – aszimptotikus viselkedés vizsgálata

• volume 1 – fundamental algorithms
  • chapter 1 – basic concepts
  • chapter 2 – information structures
• volume 2 – seminumerical algorithms
  • chapter 3 – random numbers
  • chapter 4 – arithmetic
• volume 3 – sorting and searching
  • chapter 5 – sorting
  • chapter 6 – searching
• volume 4a – combinatorial algorithms
  • chapter 7 – combinatorial searching (part 1)
• volume 4b – combinatorial algorithms
  • chapter 7 – combinatorial searching (part 2)

• volume 4c, 4d, ...  combinatorial algorithms (chapters 7 & 8 released in several subvolumes)
  • chapter 7 – combinatorial searching (continued)
  • chapter 8 – recursion
• volume 5 – syntactic algorithms
  • chapter 9 – lexical scanning (also includes string search and data compression)
  • chapter 10 – parsing techniques
• volume 6 – the theory of context-free languages
  • chapter 11 – mathematical linguistics
• volume 7 – compiler techniques
  • chapter 12 – programming language translation

• chapter 1 – basic concepts
  • 1.1. algorithms
  • 1.2. mathematical preliminaries
    • 1.2.1. mathematical induction
    • 1.2.2. numbers, powers, and logarithms
    • 1.2.3. sums and products
    • 1.2.4. integer functions and elementary number theory
    • 1.2.5. permutations and factorials
    • 1.2.6. binomial coefficients
    • 1.2.7. harmonic numbers
    • 1.2.8. fibonacci numbers
    • 1.2.9. generating functions
    • 1.2.10. analysis of an algorithm
    • 1.2.11. asymptotic representations
      • 1.2.11.1. the o-notation
      • 1.2.11.2. euler's summation formula
      • 1.2.11.3. some asymptotic calculations
  • 1.3 mix (updated with mmix in volume 1 fascicle 1)
    • 1.3.1. description of mix
    • 1.3.2. the mix assembly language
    • 1.3.3. applications to permutations
  • 1.4. some fundamental programming techniques
    • 1.4.1. subroutines
    • 1.4.2. coroutines
    • 1.4.3. interpretive routines
      • 1.4.3.1. a mix simulator
      • 1.4.3.2. trace routines
    • 1.4.4. input and output
    • 1.4.5. history and bibliography
• chapter 2 – information structures
  • 2.1. introduction
  • 2.2. linear lists
    • 2.2.1. stacks, queues, and deques
    • 2.2.2. sequential allocation
    • 2.2.3. linked allocation (topological sorting)
    • 2.2.4. circular lists
    • 2.2.5. doubly linked lists
    • 2.2.6. arrays and orthogonal lists
  • 2.3. trees
    • 2.3.1. traversing binary trees
    • 2.3.2. binary tree representation of trees
    • 2.3.3. other representations of trees
    • 2.3.4. basic mathematical properties of trees
      • 2.3.4.1. free trees
      • 2.3.4.2. oriented trees
      • 2.3.4.3. the "infinity lemma"
      • 2.3.4.4. enumeration of trees
      • 2.3.4.5. path length
      • 2.3.4.6. history and bibliography
    • 2.3.5. lists and garbage collection
  • 2.4. multilinked structures
  • 2.5. dynamic storage allocation
  • 2.6. history and bibliography

• chapter 3 – random numbers
  • 3.1. introduction
  • 3.2. generating uniform random numbers
    • 3.2.1. the linear congruential method
      • 3.2.1.1. choice of modulus
      • 3.2.1.2. choice of multiplier
      • 3.2.1.3. potency
    • 3.2.2. other methods
  • 3.3. statistical tests
    • 3.3.1. general test procedures for studying random data
    • 3.3.2. empirical tests
    • 3.3.3. theoretical tests
    • 3.3.4. the spectral test
  • 3.4. other types of random quantities
    • 3.4.1. numerical distributions
    • 3.4.2. random sampling and shuffling
  • 3.5. what is a random sequence?
  • 3.6. summary
• chapter 4 – arithmetic
  • 4.1. positional number systems
  • 4.2. floating point arithmetic
    • 4.2.1. single-precision calculations
    • 4.2.2. accuracy of floating point arithmetic
    • 4.2.3. double-precision calculations
    • 4.2.4. distribution of floating point numbers
  • 4.3. multiple precision arithmetic
    • 4.3.1. the classical algorithms
    • 4.3.2. modular arithmetic
    • 4.3.3. how fast can we multiply?
  • 4.4. radix conversion
  • 4.5. rational arithmetic
    • 4.5.1. fractions
    • 4.5.2. the greatest common divisor
    • 4.5.3. analysis of euclid's algorithm
    • 4.5.4. factoring into primes
  • 4.6. polynomial arithmetic
    • 4.6.1. division of polynomials
    • 4.6.2. factorization of polynomials
    • 4.6.3. evaluation of powers (addition-chain exponentiation)
    • 4.6.4. evaluation of polynomials
  • 4.7. manipulation of power series

• chapter 5 – sorting
  • 5.1. combinatorial properties of permutations
    • 5.1.1. inversions
    • 5.1.2. permutations of a multiset
    • 5.1.3. runs
    • 5.1.4. tableaux and involutions
  • 5.2. internal sorting
    • 5.2.1. sorting by insertion
    • 5.2.2. sorting by exchanging
    • 5.2.3. sorting by selection
    • 5.2.4. sorting by merging
    • 5.2.5. sorting by distribution
  • 5.3. optimum sorting
    • 5.3.1. minimum-comparison sorting
    • 5.3.2. minimum-comparison merging
    • 5.3.3. minimum-comparison selection
    • 5.3.4. networks for sorting
  • 5.4. external sorting
    • 5.4.1. multiway merging and replacement selection
    • 5.4.2. the polyphase merge
    • 5.4.3. the cascade merge
    • 5.4.4. reading tape backwards
    • 5.4.5. the oscillating sort
    • 5.4.6. practical considerations for tape merging
    • 5.4.7. external radix sorting
    • 5.4.8. two-tape sorting
    • 5.4.9. disks and drums
  • 5.5. summary, history, and bibliography
• chapter 6 – searching
  • 6.1. sequential searching
  • 6.2. searching by comparison of keys
    • 6.2.1. searching an ordered table
    • 6.2.2. binary tree searching
    • 6.2.3. balanced trees
    • 6.2.4. multiway trees
  • 6.3. digital searching
  • 6.4. hashing
  • 6.5. retrieval on secondary keys

• chapter 7 – combinatorial searching
  • 7.1. zeros and ones
    • 7.1.1. boolean basics
    • 7.1.2. boolean evaluation
    • 7.1.3. bitwise tricks and techniques
    • 7.1.4. binary decision diagrams
  • 7.2. generating all possibilities
    • 7.2.1. generating basic combinatorial patterns
      • 7.2.1.1. generating all n-tuples
      • 7.2.1.2. generating all permutations
      • 7.2.1.3. generating all combinations
      • 7.2.1.4. generating all integer partitions
      • 7.2.1.5. generating all set partitions
      • 7.2.1.6. generating all trees
      • 7.2.1.7. history and further references

• chapter 7 – combinatorial searching (continued)
  • 7.2. generating all possibilities (continued)
    • 7.2.2. backtrack programming
      • 7.2.2.1. dancing links (includes discussion of exact cover)
      • 7.2.2.2. satisfiability

• chapter 7 – combinatorial searching (continued)
  • 7.2. generating all possibilities (continued)
    • 7.2.2. backtrack programming (continued)
      • 7.2.2.3. constraint satisfaction (released as pre-fascicle 7a)
      • 7.2.2.4. hamiltonian paths and cycles
      • 7.2.2.5. cliques
      • 7.2.2.6. covers (vertex cover, set cover problem, exact cover, clique cover)
      • 7.2.2.7. squares
      • 7.2.2.8. a potpourri of puzzles (includes perfect digital invariant)
      • 7.2.2.9. estimating backtrack costs (chapter 6 of "selected papers on analysis of algorithms", and fascicle 5, pp. 44−47, under the heading "running time estimates")
    • 7.2.3. generating inequivalent patterns (includes discussion of pólya enumeration theorem) (see "techniques for isomorph rejection", chapter 4 of "classification algorithms for codes and designs" by kaski and östergård)
  • 7.3. shortest paths
  • 7.4. graph algorithms
    • 7.4.1. components and traversal
      • 7.4.1.1. union-find algorithms
      • 7.4.1.2. depth-first search
      • 7.4.1.3. vertex and edge connectivity
    • 7.4.2. special classes of graphs
    • 7.4.3. expander graphs
    • 7.4.4. random graphs
  • 7.5. graphs and optimization
    • 7.5.1. bipartite matching (including maximum-cardinality matching, stable marriage problem, mariages stables)
    • 7.5.2. the assignment problem
    • 7.5.3. network flows
    • 7.5.4. optimum subtrees
    • 7.5.5. optimum matching
    • 7.5.6. optimum orderings
  • 7.6. independence theory
    • 7.6.1. independence structures
    • 7.6.2. efficient matroid algorithms
  • 7.7. discrete dynamic programming (see also transfer-matrix method)
  • 7.8. branch-and-bound techniques
  • 7.9. herculean tasks (aka np-hard problems)
  • 7.10. near-optimization
• chapter 8 – recursion (chapter 22 of "selected papers on analysis of algorithms")

• chapter 9 – lexical scanning (includes also string search and data compression)
• chapter 10 – parsing techniques

• chapter 11 – mathematical linguistics

• chapter 12 – programming language translation

• The Art of Computer Programming - Szótár.net (en-hu)
• The Art of Computer Programming - Sztaki (en-hu)
• The Art of Computer Programming - Merriam–Webster
• The Art of Computer Programming - Cambridge
• The Art of Computer Programming - WordNet
• The Art of Computer Programming - Яндекс (en-ru)
• The Art of Computer Programming - Google (en-hu)
• The Art of Computer Programming - Wikidata
• The Art of Computer Programming - Wikipédia (angol)