Arta de a programa

The Art of Computer Programming [ 1] este o  monografie fundamentală a celebrului matematician și informatician american Donald Knuth , dedicată luării în considerare și analizei celor mai importanți algoritmi folosiți în informatică . În 1999, cartea a fost recunoscută drept una dintre cele mai bune douăsprezece monografii fizice și matematice ale secolului [2] .

Proiectul de scriere a cărții a fost început de autor în 1962. Inițial, sa planificat lansarea lui într-un singur volum, dar cantitatea de material s-a dovedit a fi atât de mare încât numărul de volume a crescut la șapte. Primele trei volume au fost publicate destul de repede: volumul 1 - în 1968, volumul 2 - în 1969, volumul 3 - în 1973. A urmat o pauză până în februarie 2005, în care autorul a publicat prima parte a volumului al patrulea. S-a luat decizia de a lansa părțile rămase ale volumului al patrulea de aproximativ două ori pe an în numere separate, după care întregul volum al patrulea va fi publicat oficial. În perioada 2005-2009 au fost publicate numerele 0, 1, 2, 3 și 4, iar în 2011 a fost lansat volumul 4A, care cuprindea informații din aceste numere. Tot în 2005 a fost lansat și numărul 1 „MMIX - A RISC Computer for the New Millennium”, informații din care vor fi incluse în noua, a patra ediție a primului volum. Numărul 6 (în 2015) și numărul 5 (în 2017) au fost publicate ca parte a volumului 4B. Volumul 4B în sine a fost lansat în 2022.

Întrucât Knuth a considerat întotdeauna Arta de a programa ca fiind proiectul principal al vieții sale , s-a retras în 1993 cu intenția de a se concentra pe deplin pe scrierea părților lipsă și a aranja pe cele existente [3] . El credea că va dura 20 de ani pentru a finaliza lucrarea [4] .

Istorie

În calitate de expert recunoscut în proiectarea compilatorului , în 1962 Knuth a început să scrie o carte despre proiectarea compilatorului. Curând și-a dat seama că domeniul de aplicare al materialului trebuia să fie mult mai larg. În iunie 1965, a terminat de scris prima versiune a ceea ce a vrut inițial să publice într-o singură carte de douăsprezece secțiuni. Volumul textului scris de mână a fost de 3000 de pagini. Conform calculelor lui Knuth, acest volum ar fi trebuit să se încadreze în 600 de pagini tipărite, dar, după cum l-a informat editorul său, volumul real ar fi de 2000 de pagini. În acest sens, structura cărții a fost revizuită în favoarea mai multor volume, câte 1-2 secțiuni. De atunci, din cauza creșterii constante a materialului, s-a decis ca și al patrulea volum să fie împărțit în cărți separate: 4A, 4B, 4C și, eventual, 4D. Dar această împărțire, aparent, nu va fi definitivă, deoarece secțiunile 7.1 și 7.2.1 ocupă deja peste 650 de pagini în total.

În 1976, Knuth a produs o a doua ediție a celui de-al doilea volum, care a necesitat retipări . Dar designul tipografic ( monotip ) folosit în prima ediție nu mai era disponibil până la acest moment. Pentru a evita frustrări similare în viitor, în 1977 Knuth a început să-și dezvolte propriul sistem de tipografie computerizată. După calculele sale, lucrarea ar fi trebuit să nu dureze mai mult de șase luni, dar a durat aproximativ zece ani până să fie finalizată [5] . Sistemul a fost numit TeX și este utilizat în prezent pentru compunerea tuturor volumelor din The Art of Programming. În plus, mai târziu TeX a devenit standardul de facto pentru scrierea de articole și monografii în științele naturii.

La fel ca celelalte cărți ale lui Knuth, Arta programarii poartă marca sa comercială: pentru fiecare eroare găsită în text, autorul plătește un dolar hexazecimal sau 2,56 USD (0x100 cenți , bază 16 ). O altă trăsătură distinctivă a cărții este abundența de exerciții de autoîmplinire, de diferite grade de dificultate, variind de la simple probleme de „încălzire” până la probleme deschise. Dificultatea fiecărui exercițiu este evaluată pe o scară numerică de la 0 la 50. Deci, în primele ediții , Ultima Teoremă a lui Fermat a fost marcată cu numărul 50 , dar în a treia ediție acest rating a fost „devalorizat” la 45, deoarece prin aceea vremea dovada ei încetase deja să fie o problemă deschisă.

Rezumatul convențiilor pentru volumul trei, 1978 „Sortarea și căutarea” (stânga - evaluare, dreapta - scurtă explicație)

• Triunghi negru - Recomandat
• M - Cu o părtinire matematică
• VM - Necesită cunoștințe de „matematică superioară”
• 00 - Necesită un răspuns imediat
• 10 - Simplu (timp de 1 minut)
• 20 - Dificultate medie (timp de 15 minute)
• 30 - Dificultate crescută
• 40 - Pentru „matpraktikum”
• 50 - Problemă de cercetare

Cuprins

Planul original pentru scrierea cărții a sugerat următoarea defalcare a materialului.

• Volumul 1. Algoritmi de bază.
  • Capitolul 1. Concepte de bază.
  • Capitolul 2. Structuri informaţionale.
• Volumul 2. Algoritmi derivați.
  • Capitolul 3. Numere aleatorii.
  • Capitolul 4. Aritmetica.
• Volumul 3. Sortare și căutare.
  • Capitolul 5. Sortarea.
  • Capitolul 6
• Volumul 4. Algoritmi combinatori.
  • Capitolul 7. Căutare combinatorie.
  • Capitolul 8. Recursiune.
• Volumul 5. Algoritmi sintactici.
  • Capitolul 9. Căutare lexicografică.
  • Capitolul 10. Căutare sintactică.
• Volumul 6. Teoria Limbilor.
• Volumul 7. Compilatoare.

De fapt, această schemă a fost implementată până la cel de-al treilea volum inclusiv.

In prezent[ când? ] a publicat volumul 4A, care conține primele secțiuni ale capitolului 7. Noile secțiuni sunt planificate să fie publicate inițial în numere separate (aproximativ 128 de pagini), aproximativ două numere pe an (numerele 0, 1, 2, 3 și 4 au fost publicate în mod similar înainte de lansarea volumului 4A).

Exemplu de limbaj orientat către mașină

Exemplele de programe din carte folosesc un „asamblator MIX” proiectat să ruleze pe un computer MIX ipotetic. În cea de-a treia ediție, MIX -ul învechit a fost înlocuit cu MMIX , ​​care are o arhitectură RISC cu drepturi depline . Există software care oferă emularea mașinii (M)MIX pe computere standard compatibile cu IBM. GNU Compiler Collection are capacitatea de a compila cod C/C++ pe arhitectura țintă MMIX.

Mulți cititori sunt descurajați de faptul că folosesc un limbaj de nivel scăzut, dar Knuth consideră că alegerea sa este justificată, deoarece legarea la arhitectură este necesară pentru a putea judeca cu precizie caracteristici ale algoritmului precum viteza, consumul de memorie, si asa mai departe. Ca urmare a acestei alegeri, publicul țintă este însă mult restrâns. În plus, domeniul său de aplicare este limitat ca o „carte de rețete” pentru programatori practici, dintre care mulți nu cunosc limbajul de asamblare și, dacă o cunosc, nu au chef să traducă algoritmi de nivel scăzut din carte în limbi de nivel înalt. . Multe ghiduri de practică care prezintă același material într-un mod mai popular sunt publicate tocmai din acest motiv.

Critica

Principala caracteristică a monografiei lui Knuth, care o deosebește favorabil de alte cărți despre programare, este bara excepțional de ridicată pentru calitatea materialului și a prezentării academice, precum și profunzimea analizei problemelor luate în considerare. Datorită acestui fapt, a devenit un adevărat bestseller și o carte de referință pentru fiecare programator profesionist [6] . Revista American Scientist a inclus The Art of Programming în lista sa cu cele mai bune 12 monografii fizice și matematice ale secolului al XX-lea [2] împreună cu lucrările lui Dirac despre mecanica cuantică , Einstein despre teoria relativității , Russell și Whitehead despre fundamente. de matematică , și alții câțiva [7] .

Coperta celei de-a treia ediții a primului volum al cărții conține un citat din Bill Gates : „Dacă te consideri un programator cu adevărat bun... citește The Art of Programming (Knuth)... Dacă poți citi toată această lucrare , atunci cu siguranță ar trebui să-mi trimiteți un CV” [8] .

Ediții

Original