Kunsten at programmere

The Art of Computer Programming [ 1] er en  grundlæggende monografi af den berømte amerikanske matematiker og datalog Donald Knuth , dedikeret til overvejelse og analyse af de vigtigste algoritmer , der bruges i datalogi . I 1999 blev bogen anerkendt som en af ​​århundredets tolv bedste fysiske og matematiske monografier [2] .

Bogskrivningsprojektet blev startet af forfatteren i 1962. I første omgang var det planlagt at udgive det i et bind, men mængden af ​​materiale viste sig at være så stor, at antallet af bind blev øget til syv. De første tre bind blev udgivet ret hurtigt: bind 1 - i 1968, bind 2 - i 1969, bind 3 - i 1973. Herefter fulgte en pause indtil februar 2005, hvor forfatteren udgav første del af fjerde bind. Det blev besluttet at udgive de resterende dele af fjerde bind cirka to gange om året i separate numre, hvorefter hele fjerde bind ville blive udgivet officielt. I løbet af 2005-2009 blev nummer 0, 1, 2, 3 og 4 udgivet, og i 2011 udkom bind 4A, som indeholdt information fra disse numre. Også i 2005 blev nummer 1 "MMIX - A RISC Computer for the New Millennium" udgivet, hvorfra information vil blive inkluderet i den nye, fjerde udgave af første bind. Nummer 6 (i 2015) og Nummer 5 (i 2017) blev udgivet som en del af bind 4B. Selve bind 4B blev udgivet i 2022.

Da Knuth altid havde anset The Art of Programming for at være sit livs hovedprojekt , trak han sig tilbage i 1993 med den hensigt at koncentrere sig fuldt ud om at skrive de manglende dele og rydde op i de eksisterende [3] . Han mente, at det ville tage 20 år at færdiggøre arbejdet [4] .

Historie

Som en anerkendt ekspert i compilerdesign begyndte Knuth i 1962 at skrive en bog om compilerdesign. Han indså hurtigt, at omfanget af materialet skulle være meget bredere. I juni 1965 var han færdig med at skrive den første version af det, han oprindeligt ønskede at udgive i en bog med tolv sektioner. Volumen af ​​den håndskrevne tekst var 3000 sider. Efter Knuths beregninger skulle dette bind have passet til 600 trykte sider, men som hans forlag oplyste, ville det faktiske bind være 2000 sider. I denne henseende blev bogens struktur revideret til fordel for flere bind, hver 1-2 afsnit. Siden da, på grund af den konstante vækst af materiale, blev det besluttet, at det fjerde bind også skulle opdeles i separate bøger: 4A, 4B, 4C og muligvis 4D. Men denne opdeling vil tilsyneladende ikke være endelig, da afsnit 7.1 og 7.2.1 allerede fylder mere end 650 sider i alt.

I 1976 producerede Knuth en anden udgave af andet bind, som krævede genskrivninger . Men det typografiske design ( monotypi ), der blev brugt i den første udgave, var ikke længere tilgængelig på dette tidspunkt. For at undgå lignende frustrationer i fremtiden begyndte Knuth i 1977 at udvikle sit eget typografiske computeropsætningssystem. Arbejdet skulle ifølge hans beregninger højst have taget seks måneder, men der gik omkring ti år, før det var afsluttet [5] . Systemet hed TeX , og bruges i øjeblikket til at sætte alle bind af The Art of Programming. Derudover blev TeX senere de facto standarden for at skrive artikler og monografier inden for naturvidenskab.

Ligesom Knuths andre bøger bærer The Art of Programming hans varemærke: For hver fejl fundet i teksten betaler forfatteren en hexadecimal dollar eller 2,56 $ (0x100 cent , base 16 ). Et andet kendetegn ved bogen er overfloden af ​​øvelser til selvopfyldelse, af varierende sværhedsgrader, lige fra simple "opvarmnings"-problemer til åbne problemer. Sværhedsgraden af ​​hver øvelse er vurderet på en numerisk skala fra 0 til 50. Så i de tidlige udgaver blev Fermats sidste sætning markeret med tallet 50 , men i den tredje udgave blev denne vurdering "devalueret" til 45, da gang dets bevis allerede var holdt op med at være et åbent problem.

Sammendrag af konventioner for bind tre, 1978 "Sortering og søgning" (venstre - vurdering, højre - kort forklaring)

• Sort trekant - anbefales
• M - Med en matematisk skævhed
• VM - Kræver viden om "højere matematik"
• 00 - Kræver et øjeblikkeligt svar
• 10 - Enkel (i 1 minut)
• 20 - Middel svær (i 15 minutter)
• 30 - Øget sværhedsgrad
• 40 - For "matpraktikum"
• 50 - Forskningsproblem

Indhold

Den oprindelige plan for at skrive bogen foreslog følgende opdeling af materialet.

• Bind 1. Grundlæggende algoritmer.
  • Kapitel 1. Grundlæggende begreber.
  • Kapitel 2. Informationsstrukturer.
• Bind 2. Afledte algoritmer.
  • Kapitel 3. Tilfældige tal.
  • Kapitel 4. Aritmetik.
• Bind 3. Sortering og søgning.
  • Kapitel 5. Sortering.
  • Kapitel 6
• Bind 4. Kombinatoriske algoritmer.
  • Kapitel 7. Kombinatorisk søgning.
  • Kapitel 8. Rekursion.
• Bind 5. Syntaktiske algoritmer.
  • Kapitel 9. Leksikografisk søgning.
  • Kapitel 10. Syntaktisk søgning.
• Bind 6. Sprogteori.
• Bind 7. Kompilatorer.

Faktisk blev denne ordning implementeret til og med tredje bind.

På nuværende tidspunkt[ hvornår? ] udgivet bind 4A, som indeholder de første afsnit af kapitel 7. De nye sektioner er planlagt til i første omgang at blive udgivet i separate numre (ca. 128 sider), ca. to numre om året (udgave 0, 1, 2, 3 og 4 blev tilsvarende udgivet før udgivelsen af ​​bind 4A).

Maskinorienteret eksempelsprog

Eksempelprogrammerne i bogen bruger en "MIX assembler" designet til at køre på en hypotetisk MIX computer. I den tredje udgave blev den forældede MIX erstattet af MMIX , ​​som har en fuldgyldig RISC - arkitektur. Der er software , der giver emulering af (M)MIX-maskinen på standard IBM-kompatible computere. GNU Compiler Collection har evnen til at kompilere C/C++-kode på MMIX-målarkitekturen.

Mange læsere er afskrækket af det faktum at bruge et sprog på lavt niveau, men Knuth anser hans valg for berettiget, da bindingen til arkitekturen er nødvendig for nøjagtigt at kunne bedømme sådanne karakteristika ved algoritmen som hastighed, hukommelsesforbrug, og så videre. Som følge af dette valg er målgruppen dog stærkt indsnævret. Derudover er dens omfang begrænset som en "bog med opskrifter" for praktiske programmører, hvoraf mange ikke kender assemblersprog, og hvis de gør det, har de ikke lyst til at oversætte lavniveaualgoritmer fra bogen til højniveausprog . Mange praksisvejledninger, der præsenterer det samme materiale på en mere populær måde, udgives netop af denne grund.

Kritik

Hovedtrækket i Knuths monografi, som adskiller den gunstigt fra andre bøger om programmering, er den usædvanligt høje bar for kvaliteten af ​​materialet og den akademiske præsentation, samt dybden af ​​analyse af de emner, der overvejes. Takket være dette er den blevet en rigtig bestseller og en opslagsbog for enhver professionel programmør [6] . The American Scientist magazine inkluderede The Art of Programming på sin liste over de 12 bedste fysiske og matematiske monografier i det 20. århundrede [2] sammen med Diracs værker om kvantemekanik , Einstein om relativitetsteorien , Russell og Whitehead om grundlaget. af matematik og nogle få andre [7] .

Forsiden af ​​tredje udgave af bogens første bind indeholder et citat fra Bill Gates : "Hvis du betragter dig selv som en rigtig god programmør ... læs The Art of Programming (Knuth) ... Hvis du kan læse alt dette arbejde , så skal du helt klart sende mig et CV" [8] .

Udgaver

Original