Umění počítačového programování - The Art of Computer Programming

Umění počítačového programování
ArtOfComputerProgramming.jpg
The Art of Computer Programming, Volume 1: Fundamental Algorithms
AutorDonald Knuth
ZeměSpojené státy
JazykAngličtina
ŽánrLiteratura faktu
Monografie
VydavatelAddison-Wesley
Datum publikace
1968– (kniha je stále neúplná)
Typ médiaTisk (Tvrdý obal )
ISBN0-201-03801-3
519
LC třídaQA76.75

Umění počítačového programování (TAOCP) je komplexní monografie napsáno počítačový vědec Donald Knuth který pokrývá mnoho druhů programování algoritmy a jejich analýza.

Knuth zahájil projekt, původně koncipovaný jako samostatná kniha s dvanácti kapitolami, v roce 1962. První tři svazky toho, co se tehdy očekávalo jako sedmisvazkový soubor, byly vydány v letech 1968, 1969 a 1973. Práce začaly ve velkém objemu 4 v roce 1973, ale byl pozastaven v roce 1977 pro práci na sazbu. Psaní finální kopie svazku 4A začalo dlouhodobě v roce 2001 a první online předfaskula, 2A, se objevila později v roce 2001.[1] První publikovaná část svazku 4 se objevila v brožované podobě jako Fascicle 2 v roce 2005. Pevná vazba, svazek 4A, kombinující svazek 4, Fascicles 0–4, byla vydána v roce 2011. Svazek 4, Fascicle 6 („Satisfiability“) byl vydán v prosinci 2015; Svazek 4, Fascicle 5 („Mathematical Preliminaries Redux; Backtracking; Dancing Links“) byl vydán v listopadu 2019.

Očekává se, že fascicles 5 a 6 tvoří první dvě třetiny svazku 4B. Knuth neoznámil žádné odhadované datum vydání svazku 4B, ačkoli jeho metodou používanou pro svazek 4A je uvolnění svazku vázaných knih někdy po vydání brožovaných svazků v něm obsažených. Odhady vydavatelů v blízké budoucnosti uvádějí datum vydání na květen nebo červen 2019, což se ukázalo jako nesprávné.[2][3]

Dějiny

Donald Knuth v roce 2005

Po získání stipendia Westinghouse Talent Search se Knuth zapsal na Case Institute of Technology (nyní Case Western Reserve University ), kde byl jeho výkon tak vynikající, že fakulta po jeho ukončení bakalářského studia hlasovala pro udělení titulu Master of Science. Během letních prázdnin byl Knuth najat Burroughs Corporation psát překladače, který v letních měsících vydělával více než řádní profesoři za celý rok.[4] Díky těmto explozím se Knuth stal předmětem diskuse mezi matematickým oddělením, které zahrnovalo Richard S.Varga.

V lednu 1962, když byl postgraduálním studentem matematického oddělení na Caltech, byl Knuth osloven Addison-Wesley napsat knihu o designu překladače a on navrhl větší rozsah. Ve stejný den přišel se seznamem 12 titulů kapitol. V létě 1962 pracoval na kompilátoru FORTRAN pro UNIVAC. Během této doby také přišel s matematickou analýzou lineární sondování, který ho přesvědčil, aby předložil materiál s kvantitativním přístupem. Po získání doktorátu v červnu 1963 začal pracovat na svém rukopisu, jehož první verzi dokončil v červnu 1965, 3000 ručně psané stránky.[5] Předpokládal, že asi pět ručně psaných stránek se převede na jednu vytištěnou stránku, ale jeho vydavatel místo toho řekl asi1 1⁄2 ručně psané stránky přeložené na jednu vytištěnou stránku. To znamenalo, že měl přibližně 2000 tištěné stránky materiálu, který těsně odpovídá velikosti prvních tří vydaných svazků. Vydavatel byl nervózní z přijetí takového projektu od postgraduálního studenta. V tomto okamžiku získal Knuth podporu od Richarda S. Vargy, který byl vědeckým poradcem vydavatele. Varga byl na návštěvě Olga Taussky-Todd a John Todd na Caltech. S nadšeným souhlasem Vargy vydavatel přijal rozšířené plány Knutha. V rozšířené verzi bude kniha vydána v sedmi svazcích, každý bude obsahovat pouze jednu nebo dvě kapitoly.[6] Vzhledem k nárůstu materiálu se plán svazku 4 od té doby rozšířil o svazky 4A, 4B, 4C, 4D a možná i další.

V roce 1976 připravil Knuth druhé vydání svazku 2, které vyžadovalo jeho vydání vysázet znovu, ale styl typu použitý v prvním vydání (tzv horký typ ) již nebyl k dispozici. V roce 1977 se rozhodl strávit nějaký čas vytvořením něčeho vhodnějšího. O osm let později se vrátil s TEX, který se aktuálně používá pro všechny svazky.

Nabídka tzv Knuth odměna v hodnotě "jeden šestnáctkový dolar" (100ŠEST základna 16 centů, v desetinný, je 2,56 $) za jakékoli nalezené chyby a oprava těchto chyb v následných tiscích přispěla k vysoce leštěné a stále autoritativní povaze díla, dlouho po jeho prvním vydání. Další charakteristikou svazků je kolísání obtížnosti cvičení. Knuth má dokonce číselnou stupnici obtížnosti pro hodnocení těchto cvičení, která se pohybuje od 0 do 50, kde 0 je triviální, a 50 je v současném výzkumu otevřenou otázkou. [7]

Knuthovo odhodlání zní:

Tato série knih je láskyplně věnována
do Zadejte počítač 650 po instalaci na
Case Institute of Technology,
se kterými jsem strávil mnoho příjemných večerů.[A]

Jazyk shromáždění v knize

Všechny příklady v knihách používají jazyk zvaný „SMĚS assembler ", který běží na hypotetickém počítači MIX. V současné době je počítač MIX nahrazen MMIX počítač, což je a RISC verze. Software jako GNU MDK existuje poskytovat emulaci architektury MIX. Knuth zvažuje použití montážní jazyk nezbytné pro posouzení rychlosti a využití paměti algoritmů.

Kritická odpověď

Knuth byl oceněn v roce 1974 Turing Award "za jeho hlavní příspěvky do analýza algoritmů […], A zejména za jeho příspěvky k „umění počítačového programování“ prostřednictvím jeho známých knih v souvislé sérii s tímto titulem. “[8] Americký vědec zařadil tuto práci mezi „100 knih, které formovaly století vědy“ s odkazem na dvacáté století,[9] a v rámci komunity počítačových věd je považován za první a stále nejlepší komplexní zpracování svého předmětu. Obálky třetího vydání svazku 1 citátu Bill Gates jak říká: „Pokud si myslíte, že jste opravdu dobrý programátor ... přečtěte si (Knuth's) Umění počítačového programování… Určitě byste mi měli poslat životopis, pokud si můžete přečíst celou věc. “[10] The New York Times odkazoval se na to jako „pojednání určující povolání“.[11]

Svazky

Dokončeno

  • Svazek 1 - Základní algoritmy
  • Kapitola 1 - Základní pojmy
  • Kapitola 2 - Informace struktur
  • Svazek 2 - Seminumerické algoritmy
  • Kapitola 7 - Kombinatorické vyhledávání (část 1)

Plánováno

  • Svazek 4B ... - Kombinatorické algoritmy (kapitoly 7 a 8 vydané v několika dílčích svazcích)
  • Kapitola 7 - Kombinatorické vyhledávání (pokračování)
  • Kapitola 8 - Rekurze
  • Svazek 5 - Syntaktické algoritmy (od roku 2017, odhaduje se na vydání v roce 2025)

Obrysy kapitoly

Dokončeno

Svazek 1 - Základní algoritmy

  • Kapitola 1 - Základní pojmy
  • Kapitola 2 - Informační struktury
    • 2.1. Úvod
    • 2.2. Lineární seznamy
      • 2.2.1. Hromádky, fronty a deques
      • 2.2.2. Postupné přidělování
      • 2.2.3. Propojené přidělení
      • 2.2.4. Kruhové seznamy
      • 2.2.5. Dvojnásobně propojené seznamy
      • 2.2.6. Pole a ortogonální seznamy
    • 2.3. Stromy
      • 2.3.1. Traverzující binární stromy
      • 2.3.2. Binární stromová reprezentace stromů
      • 2.3.3. Další znázornění stromů
      • 2.3.4. Základní matematické vlastnosti stromů
        • 2.3.4.1. Zdarma stromy
        • 2.3.4.2. Orientované stromy
        • 2.3.4.3. „Lema nekonečna“
        • 2.3.4.4. Výčet stromů
        • 2.3.4.5. Délka cesty
        • 2.3.4.6. Historie a bibliografie
      • 2.3.5. Seznamy a sběr odpadu
    • 2.4. Vícelinkové struktury
    • 2.5. Dynamické přidělení úložiště
    • 2.6. Historie a bibliografie

Svazek 2 - Seminumerické algoritmy

  • Kapitola 3 - Náhodná čísla
    • 3.1. Úvod
    • 3.2. Generování jednotných náhodných čísel
      • 3.2.1. Metoda lineární kongruence
        • 3.2.1.1. Volba modulu
        • 3.2.1.2. Výběr multiplikátoru
        • 3.2.1.3. Potence
      • 3.2.2. Jiné metody
    • 3.3. Statistické testy
      • 3.3.1. Obecné zkušební postupy pro studium náhodných dat
      • 3.3.2. Empirické testy
      • 3.3.3. Teoretické testy
      • 3.3.4. Spektrální test
    • 3.4. Další typy náhodných veličin
      • 3.4.1. Numerická rozdělení
      • 3.4.2. Náhodné vzorkování a míchání
    • 3.5. Co je to Náhodná sekvence ?
    • 3.6. souhrn
  • Kapitola 4 - Aritmetika
    • 4.1. Systémy pozičních čísel
    • 4.2. Plovoucí bod Aritmetický
      • 4.2.1. Jednopřesné výpočty
      • 4.2.2. Přesnost aritmetiky s plovoucí desetinnou čárkou
      • 4.2.3. Výpočty s dvojitou přesností
      • 4.2.4. Rozdělení čísel s plovoucí desetinnou čárkou
    • 4.3. Vícenásobná přesná aritmetika
      • 4.3.1. Klasické algoritmy
      • 4.3.2. Modulární aritmetika
      • 4.3.3. Jak rychle se můžeme množit?
    • 4.4. Základ Konverze
    • 4.5. Racionální Aritmetický
      • 4.5.1. Zlomky
      • 4.5.2. Největší společný dělitel
      • 4.5.3. Analýza Euklidův algoritmus
      • 4.5.4. Faktoring do prvočísel
    • 4.6. Polynomiální Aritmetický
      • 4.6.1. Rozdělení polynomů
      • 4.6.2. Faktorizace polynomů
      • 4.6.3. Hodnocení pravomocí
      • 4.6.4. Hodnocení polynomů
    • 4.7. Manipulace s Power Series

Svazek 3 - Třídění a vyhledávání

  • Kapitola 5 - Třídění
    • 5.1. Kombinatorické vlastnosti Permutace
      • 5.1.1. Inverze
      • 5.1.2. Obměny multisetu
      • 5.1.3. Běží
      • 5.1.4. Tablo a zapojení
    • 5.2. Interní třídění
      • 5.2.1. Řazení podle vložení
      • 5.2.2. Řazení podle výměny
      • 5.2.3. Řazení podle výběru
      • 5.2.4. Řazení podle sloučení
      • 5.2.5. Řazení podle distribuce
    • 5.3. Optimální třídění
      • 5.3.1. Třídění minimálního srovnání
      • 5.3.2. Sloučení minimálního srovnání
      • 5.3.3. Výběr minimálního srovnání
      • 5.3.4. Sítě pro třídění
    • 5.4. Externí třídění
      • 5.4.1. Víceúčelové slučování a výběr náhradních dílů
      • 5.4.2. Polyfázové sloučení
      • 5.4.3. Kaskádové sloučení
      • 5.4.4. Čtení pásky zpět
      • 5.4.5. Oscilační řazení
      • 5.4.6. Praktická doporučení pro slučování pásky
      • 5.4.7. Externí třídění Radix
      • 5.4.8. Třípásmové třídění
      • 5.4.9. Disky a bubny
    • 5.5. Shrnutí, historie a bibliografie
  • Kapitola 6 - Hledání
    • 6.1. Sekvenční vyhledávání
    • 6.2. Vyhledávání podle srovnání Klíče
      • 6.2.1. Hledání objednané tabulky
      • 6.2.2. Hledání binárního stromu
      • 6.2.3. Vyvážené stromy
      • 6.2.4. Vícecestné stromy
    • 6.3. Digitální vyhledávání
    • 6.4. Hashing
    • 6.5. Načtení na sekundárních klávesách

Svazek 4A - Kombinatorické algoritmy, část 1

Plánováno

Svazek 4B, 4C, 4D - kombinatorické algoritmy

Svazek 5 - Syntaktické algoritmy

od roku 2017, jehož vydání se odhaduje na rok 2025

Svazek 6 - Teorie bezkontextových jazyků[12]

Svazek 7 - Techniky kompilátoru

Anglická vydání

Aktuální vydání

Toto jsou aktuální vydání v pořadí podle čísla svazku:

  • The Art of Computer Programming, Volumes 1-4A Boxed Set. Třetí vydání (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp. ISBN  978-0-321-75104-1, 0-321-75104-3
    • Svazek 1: Základní algoritmy. Třetí vydání (Reading, Massachusetts: Addison-Wesley, 1997), xx + 650pp. ISBN  978-0-201-89683-1, 0-201-89683-4. Errata: [1] (2011-01-08), [2] (2020-03-26, 27 tisk ). Dodatky: [3] (2011).
    • Svazek 2: Seminumerické algoritmy. Třetí vydání (Reading, Massachusetts: Addison-Wesley, 1997), xiv + 762pp. ISBN  978-0-201-89684-8, 0-201-89684-2. Errata: [4] (2011-01-08), [5] (2020-03-26, 26. tisk). Dodatky: [6] (2011).
    • Svazek 3: Třídění a vyhledávání. Druhé vydání (Reading, Massachusetts: Addison-Wesley, 1998), xiv + 780pp. + Rozložení. ISBN  978-0-201-89685-5, 0-201-89685-0. Errata: [7] (2011-01-08), [8] (2020-03-26, 27. tisk). Dodatky: [9] (2011).
    • Svazek 4A: Kombinatorické algoritmy, část 1. První vydání (Reading, Massachusetts: Addison-Wesley, 2011), xv + 883pp. ISBN  978-0-201-03804-0, 0-201-03804-8. Errata: [10] (2020-03-26,? Tisk).
  • Svazek 1, Fascicle 1: MMIX - počítač RISC pro nové tisíciletí. (Addison-Wesley, 2005-02-14) ISBN  0-201-85392-2. Errata: [11] (2020-03-16) (bude ve čtvrtém vydání svazku 1)
  • Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Taneční odkazy. (Addison-Wesley, 2019-11-22) xiii + 382pp, ISBN  978-0-13-467179-6. Errata: [12] (2020-03-27) (stane se součástí svazku 4B)
  • Svazek 4, Fascicle 6: Splnitelnost. (Addison-Wesley, 2015-12-08) xiii + 310pp, ISBN  978-0-13-439760-3. Errata: [13] (2020-03-26) (stane se součástí svazku 4B)

Předchozí vydání

Kompletní svazky

Tyto svazky byly nahrazeny novějšími vydáními a jsou seřazeny podle data.

  • Svazek 1: Základní algoritmy. První vydání, 1968, xxi + 634pp, ISBN  0-201-03801-3.[13]
  • Svazek 2: Seminumerické algoritmy. První vydání, 1969, xi + 624pp, ISBN  0-201-03802-1.[13]
  • Svazek 3: Třídění a vyhledávání. První vydání, 1973, xi + 723pp + rozložení, ISBN  0-201-03803-X. Errata: [14].
  • Svazek 1: Základní algoritmy. Druhé vydání, 1973, xxi + 634pp, ISBN  0-201-03809-9. Errata: [15].
  • Svazek 2: Seminumerické algoritmy. Druhé vydání, 1981, xiii + 688pp, ISBN  0-201-03822-6. Errata: [16].
  • The Art of Computer Programming, Volumes 1-3 Boxed Set. Druhé vydání (Reading, Massachusetts: Addison-Wesley, 1998), str. ISBN  978-0-201-48541-7, 0-201-48541-9

Fascicles

Svazek 4je chomáče 0–4 byly revidovány a publikovány jako svazek 4A:

  • Svazek 4, Fascicle 0: Úvod do kombinatorických algoritmů a booleovských funkcí. (Addison-Wesley Professional, 2008-04-28) vi + 240pp, ISBN  0-321-53496-4. Errata: [17] (2011-01-01).
  • Svazek 4, Fascicle 1: Bitové triky a techniky; Binární rozhodovací diagramy. (Addison-Wesley Professional, 2009-03-27) viii + 260pp, ISBN  0-321-58050-8. Errata: [18] (2011-01-01).
  • Svazek 4, Fascicle 2: Generování všech n-tic a permutací. (Addison-Wesley, 2005-02-14) v + 127pp, ISBN  0-201-85393-0. Errata: [19] (2011-01-01).
  • Svazek 4, Fascicle 3: Generování všech kombinací a oddílů. (Addison-Wesley, 2005-07-26) vi + 150pp, ISBN  0-201-85394-9. Errata: [20] (2011-01-01).
  • Svazek 4, Fascicle 4: Generování všech stromů; Historie kombinatorické generace. (Addison-Wesley, 2006-02-06) vi + 120pp, ISBN  0-321-33570-8. Errata: [21] (2011-01-01).

Svazek 4je svazky 5–6 se stanou součástí svazku 4B:

  • Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Taneční odkazy. (Addison-Wesley, 2019-11-22) xiii + 382pp, ISBN  978-0-13-467179-6. Errata: [22] (2020-03-27)
  • Svazek 4, Fascicle 6: Splnitelnost. (Addison-Wesley, 2015-12-08) xiii + 310pp, ISBN  978-0-13-439760-3. Errata: [23] (2020-03-26)

Předfasády

Svazek 4je pre-fascicles 5A, 5B a 5C byly revidovány a publikovány jako svazek 5.

Svazek 4je pre-fascicle 6A byl revidován a publikován jako fascicle 6.

Viz také

Reference

Poznámky

  1. ^ Věnování bylo v prvním vydání formulováno mírně odlišně.

Citace

  1. ^ poznámka k rámečku 3, složce 1
  2. ^ Webová stránka Addison-Wesley Pearson
  3. ^ Pearson vzdělávací
  4. ^ Frana, Philip L. (11. 11. 2001). „Rozhovor s Donaldem E. Knuthem“. hdl:11299/107413.
  5. ^ Donald Knuth, Klasická citace tohoto týdne, Aktuální obsah, číslo 34 (23. srpna 1993), strana 8.
  6. ^ Albers, Donald J. (2008). „Donald Knuth“. In Albers, Donald J .; Alexanderson, Gerald L. (eds.). Mathematical People: Profily a rozhovory (2. vyd.). K Peters. ISBN  1-56881-340-6.
  7. ^ „Úvahy o roce čtení Knutha“. infinitepartitions.com. Citováno 2020-07-25. Pracoval jsem, nebo jsem se alespoň pokoušel pracovat, každý problém v prvním svazku. V některých případech jsem se uspokojil s pouhým pochopením toho, na co se otázka pokoušela požádat. V některých případech se mi to ani nepodařilo (neodsuzujte mě, dokud to sami nezkusíte). Každému problému je přiřazeno hodnocení obtížnosti od 0 do 50, kde 0 je triviální a 50 je „nevyřešený výzkumný problém“ (v prvním vydání byla Fermatova poslední věta uvedena jako 50, ale protože to Andrew Wiles dokázal, narazil na 45 v aktuálním vydání). Myslím, že jsem dokázal vyřešit většinu problémů s hodnocením <20 - bylo to zasaženo a minout. Většina problémů spadala do rozsahu obtížnosti 20–30, ale Knuthova představa „obtížného“ je subjektivní a problémy, které považuje za průměrné, nakonec bolestivě protáhly můj poměrně malý mozek. Nikdy jsem nevylezl na Mount Everest, ale domnívám se, že celá zkouška se cítí podobně: bolestivá, když jí procházíte, ale vítězná, když dosáhnete vrcholu.
  8. ^ „Donald E. Knuth - vítěz ceny A. M. Turinga“. AM Turing. Citováno 2017-01-25.
  9. ^ Morrison, Philip; Morrison, Phylis (listopad – prosinec 1999). „Asi 100 knih, které formovaly století vědy“. Americký vědec. Sigma Xi, Vědecko-výzkumná společnost. 87 (6). Archivovány od originál dne 2008-08-20. Citováno 2008-01-11.
  10. ^ Weinberger, Matt. „Bill Gates jednou řekl:„ Určitě mi pošlete životopis “, pokud dokončíte tuto ďábelsky obtížnou knihu.“. Business Insider. Citováno 2016-06-13.
  11. ^ Lohr, Steve (2001-12-17). „Frances E. Holberton, 84 let, časná počítačová programátorka“. The New York Times. Citováno 2010-05-17.
  12. ^ „TAOCP - plány do budoucna“.
  13. ^ A b Wells, Mark B. (1973). "Posouzení: Umění počítačového programování, svazek 1. Základní algoritmy a Svazek 2. Seminumerické algoritmy Donald E. Knuth " (PDF). Bulletin of the American Mathematical Society. 79 (3): 501–509. doi:10.1090 / s0002-9904-1973-13173-8.

Zdroje

externí odkazy