szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
The Art of Computer Programming (tsz. The Art of Computer Programmings)
- (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.
Tulajdonság
|
Adat
|
Szerző
|
Donald E. Knuth
|
Kiadás kezdete
|
1968 (Volume 1)
|
Tervezett kötetek száma
|
7 (jelenleg 4 jelent meg + előzetes fejezetek a következőkhöz)
|
Téma
|
Algoritmusok, adatstruktúrák, kombinatorika, számelmélet, programozáselmélet
|
Célközönség
|
Előrehaladott egyetemi hallgatók, kutatók, fejlesztők
|
📘 Megjelent kötetek
- 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
- 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ó)
- 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)
- 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.
🧠 Miért jelentős?
- 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.
🔢 Példa a TAOCP stílusára
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.
🏆 Hatása
- 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.
🧩 Nehézségi szint és közönség
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.
🎖️ Érdekességek
- 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.”
📚 További kapcsolódó fogalmak
- 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
volumes
completed
- volume 1 – fundamental algorithms
- chapter 1 – basic concepts
- chapter 2 – information structures
- volume 2 – seminumerical algorithms
- volume 3 – sorting and searching
- volume 4a – combinatorial algorithms
- chapter 7 – combinatorial searching (part 1)
- volume 4b – combinatorial algorithms
- chapter 7 – combinatorial searching (part 2)
planned
- volume 4c, 4d, ... combinatorial algorithms (chapters 7 & 8 released in several subvolumes)
- chapter 7 – combinatorial searching (continued)
- chapter 8 – recursion
- volume 5 – syntactic algorithms
- volume 6 – the theory of context-free languages
- volume 7 – compiler techniques
- chapter 12 – programming language translation
chapter outlines
completed
volume 1 – fundamental algorithms
- chapter 1 – basic concepts
- 1.1. algorithms
- 1.2. mathematical preliminaries
- 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
- chapter 2 – information structures
volume 2 – seminumerical algorithms
volume 3 – sorting and searching
- 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
volume 4a – combinatorial algorithms, part 1
- chapter 7 – combinatorial searching
- 7.1. zeros and ones
- 7.2. generating all possibilities
- 7.2.1. generating basic combinatorial patterns
volume 4b – combinatorial algorithms, part 2
- chapter 7 – combinatorial searching (continued)
- 7.2. generating all possibilities (continued)
planned
volumes 4c, 4d, 4e, 4f – combinatorial algorithms
- chapter 7 – combinatorial searching (continued)
- chapter 8 – recursion (chapter 22 of "selected papers on analysis of algorithms")
volume 5 – syntactic algorithms
volume 6 – the theory of context-free languages
volume 7 – compiler techniques