Arta programării pe calculator

The Art of Computer Programming ( TAOCP , germană  The Art of Computer Programming ) este o lucrare pe mai multe volume a informaticienului american Donald Knuth privind algoritmii de bază și structurile de date , pentru care a dezvoltat programele de tipare TeX și Metafont .

Programele de exemplu sunt prezentate într-un limbaj de asamblare conceput de Knuth , pe care l-a dezvoltat pentru un computer „ideal” fictiv numit MIX ; acesta a fost înlocuit cu volumul 4a de „modelul succesor” MMIX . Folosește limbajul asamblor MIXAL (MIX-Assembler-Language). Este planificată revizuirea volumelor 1–3 și rescrierea tuturor exemplelor de cod pe MMIX. Knuth a justificat pasul radical al utilizării propriului limbaj de asamblare, în concordanță atât cu argumentele tehnice, cât și cu cele educaționale și cu intenția de a crea o lucrare pe termen lung care nu ar trebui să fie influențată de limbajul respectiv de programare a modei.

De la o carte de compilare la o lucrare de bază cu mai multe volume

Inițial, editorul îi însărcinase lui Knuth, care era încă student la acel moment, să scrie o singură carte despre compilatoare . Cu toate acestea, Knuth a dorit să prezinte toate cunoștințele necesare pe această temă și într-o formă matură.

„M-am gândit că, atâta timp cât voi face o carte despre compilatoare, ar trebui să includ câteva alte capitole despre tehnicile de bază pe care oamenii le-ar folosi înainte de a ajunge până la compilatoare. Așa că am aruncat un capitol despre tot ceea ce mă interesa. ”

„M-am gândit că dacă scriu o carte despre compilatoare ar trebui să includ câteva capitole despre tehnicile de bază pe care oamenii le-ar întâlni înainte de a le întâlni pe compilatoare. Așa că am pus un capitol pe fiecare subiect care mă interesa ".

După terminarea studiilor, el i-a scris editorului cerându-i permisiunea de a descrie lucrurile mai puțin în detaliu.

„Vă deranjează dacă fac această carte puțin mai lungă, pentru că cred că este nevoie să explic aceste lucruri într-o oarecare măsură mai detaliat”.

„Te-ar deranja dacă aș face cartea puțin mai detaliată, deoarece cred că aceste lucruri au nevoie de o explicație puțin mai detaliată”.

Răspunsul editorului său a fost pozitiv.

„Au spus:„ Nu, du-te chiar înainte. Faceți-o atât timp cât vă simțiți necesar. ”

„Au spus:„ Dar nu, începeți imediat. Faceți-l la fel de extins pe cât credeți că este necesar. "

Prima versiune scrisă de mână din 1967 a fost de 3900 de pagini. Așadar, a apărut planul de a scrie o serie din șapte părți care acoperă elementele de bază esențiale ale programării computerizate .

Structura seriei de cărți

Seria este planificată după cum urmează:

Volumul 1. Algoritmi fundamentali (prima ediție 1968)
Capitolul 1: Concepte de bază
Capitolul 2: Structuri informaționale
Volumul 2. Algoritmi seminumerici (prima ediție 1969)
Capitolul 3: Numere aleatorii
Capitolul 4: Aritmetica
Volumul 3. Sortare și căutare (prima ediție 1973)
Capitolul 5: Sortare
Capitolul 6: Căutarea
Volumul 4. Algoritmi combinatori (prima ediție 2011)
Capitolul 7: Căutarea combinatorie
Capitolul 8: Recursivitate
Volumul 5. Algoritmi sintactici (data de lansare planificată 2025)
Capitolul 9: Scanare lexicală
Capitolul 10: Analizarea
Volumul 6. Teoria limbilor libere de context
Capitolul 11: Teoria limbajelor libere de context
Volumul 7. Compilatoare
Capitolul 12: Compilatoare

Până în prezent, primele trei părți și un capitol au fost publicate, în mai multe ediții revizuite. Un fascicul cu specificația MMIX a fost publicat în 2005 pentru volumul 1 . Volumul 4 a fost, de asemenea, publicat în avans sub formă de două fascicule pe an începând cu 2005. Volumul 4A este disponibil din februarie 2011. Pe site-ul Knuth, primele pre-fascicule sunt disponibile ca fascicule înainte de a fi publicate, astfel încât părțile interesate să poată găsi primele erori înainte de tipărire. Volumele 4B și 4C (și, eventual, mai multe) trebuie urmate.

În plus față de cărțile menționate mai sus, există o altă lucrare a lui Graham / Knuth / Patashnik Concrete Mathematics , care se ocupă cu fundamentele matematice ale Volumului 1 mai detaliat.

Progresul muncii și aprecierea muncii

Deși Knuth a început să scrie în 1962, nu este încă posibil să se prevadă când va fi finalizată lucrarea. Autorul se așteaptă ca volumul 5 să fie finalizat în 2025 și apoi planifică (din nou) să actualizeze și să revizuiască volumele 1-3 și să rezume cele mai importante conținuturi ale celor cinci volume într-o nouă lucrare. Apoi a vrut să scrie volumele „mai specializate” 6 și 7 dacă subiectele lor erau „încă relevante și încă nespuse”.

Knuth a fost pensionat din 1992 pentru a se dedica exclusiv completării seriei sale de cărți. Ca urmare, el nu mai primește un salariu, pe de altă parte, Arta programării pe calculator este o serie comercială foarte reușită: de la prima dată de publicare până în 1987 s-au vândut lunar între 1000 și 2000 de exemplare.

În timp ce lucra la noua ediție revizuită a volumului 2, Knuth s-a luptat cu insuficiențele tehnicilor de tipografie ale vremii și, în cele din urmă, și-a dezvoltat propriul sistem, sistemul de tipografie digital TeX , care a devenit acum standardul pentru publicațiile în matematică și științele naturii. .

Acuratețea lucrării sale, pe care omul de știință american o consideră una dintre cele mai bune douăsprezece monografii științifice din secolul al XX-lea, este atât de importantă pentru Knuth, încât publică în mod regulat corecții extinse de erori până la cea mai mică eroare tipografică și primul care găsește orice un cec pentru 256 USD -Cenți pentru erori în conținut și 32 de cenți SUA pentru erori de virgulă și altele asemenea. Cu toate acestea, cecurile nu sunt încasate de majoritatea destinatarilor - doar nouă au fost încasate - ci încadrate. Cu toate acestea, din octombrie 2008, cecurile nu mai sunt emise în dolari SUA, ci în moneda virtuală hexazecimală a Băncii din San Serriff - Knuth justifică acest lucru cu teama de fraudă a cecurilor.

La sfârșitul fiecărui capitol există o secțiune despre istorie și bibliografie cu informații istorice. Exercițiile sunt clasificate în funcție de nivelul lor de dificultate (și marcate în consecință), variind de la extrem de ușor (00) la o problemă de cercetare care nu a fost încă rezolvată (50).

literatură

  • Karen A. Frenkel: Donald E. Knuth - cărturar cu o pasiune pentru particular. În: Comunicări ale ACM. Vol. 30, nr. 10 octombrie 1987
  • Donald E. Knuth: Arta programării pe calculator
    • Vol. 1: Algoritmi fundamentali. Ediția a 3-a. Addison-Wesley 1997, ISBN 0-201-89683-4 , 672 de pagini
    • Vol. 1, Fascicul 1: MMIX - Un computer RISC pentru noul mileniu. Addison-Wesley 2005, ISBN 0-201-85392-2 , 134 pagini
    • Vol. 2: Algoritmi seminumerici. Ediția a 3-a. Addison-Wesley 1998, ISBN 0-201-89684-2 , 784 pagini
    • Vol. 3: Sortare și căutare. Ediția a II-a. Addison-Wesley 1998, ISBN 0-201-89685-0 , 800 de pagini
    • Vol. 4A: Algoritmi combinatori. Addison-Wesley 2011, ISBN 0-201-03804-8 , 883 pagini

Link-uri web

Note de subsol

  1. ^ A b Karen A. Frenkel: Donald E. Knuth - cărturar cu o pasiune pentru particular. În: Comunicări ale ACM. Vol. 30, nr. 10 octombrie 1987
  2. ^ Don Knuth: Arta programării pe calculator (TAOCP) - Planuri de viitor
  3. ↑ Philip și Phylis Morrison: aproximativ 100 de cărți care au modelat un secol al științei . În: American Scientist. Noiembrie / decembrie 1999
  4. ↑ https://www.heise.de/newsticker/meldung/Zahlen-bitte-Der-hexadezimale-Dollar-von-Donald-E-Knuth-3579447.html
  5. ^ Don Knuth: Știri recente: Fiasco financiar