Konsten att programmera

Konsten att programmera [ 1] är en  grundläggande monografi av den berömde amerikanske matematikern och datavetaren Donald Knuth , tillägnad övervägande och analys av de viktigaste algoritmerna som används inom datavetenskap . 1999 erkändes boken som en av århundradets tolv bästa fysiska och matematiska monografier [2] .

Bokskrivarprojektet startades av författaren 1962. Från början var det planerat att släppa den i en volym, men mängden material visade sig vara så stor att antalet volymer utökades till sju. De tre första volymerna publicerades ganska snabbt: volym 1 - 1968, volym 2 - 1969, volym 3 - 1973. Detta följdes av ett uppehåll fram till februari 2005, där författaren publicerade den första delen av fjärde volymen. Beslutet togs att ge ut de återstående delarna av fjärde volymen cirka två gånger om året i separata nummer, varefter hela fjärde volymen skulle publiceras officiellt. Under 2005-2009 utkom nummer 0, 1, 2, 3 och 4 och 2011 släpptes volym 4A som innehöll information från dessa nummer. Även 2005 släpptes nummer 1 "MMIX - A RISC Computer for the New Millennium", vars information kommer att inkluderas i den nya, fjärde upplagan av den första volymen. Nummer 6 (år 2015) och nummer 5 (år 2017) publicerades som en del av volym 4B. Själva volym 4B släpptes 2022.

Eftersom Knuth alltid hade ansett att konsten att programmera var hans livs huvudprojekt , gick han i pension 1993 med avsikten att helt koncentrera sig på att skriva de saknade delarna och städa upp de befintliga [3] . Han trodde att det skulle ta 20 år att slutföra arbetet [4] .

Historik

Som en erkänd expert på kompilatordesign började Knuth 1962 skriva en bok om kompilatordesign. Han insåg snart att omfattningen av materialet behövde vara mycket bredare. I juni 1965 skrev han färdigt den första versionen av det han från början ville ge ut i en bok med tolv avsnitt. Volymen på den handskrivna texten var 3000 sidor. Enligt Knuths beräkningar skulle denna volym ha rymt in på 600 tryckta sidor, men, som hans förläggare meddelade honom, skulle den faktiska volymen vara 2000 sidor. I detta avseende reviderades bokens struktur till förmån för flera volymer, 1-2 avsnitt vardera. Sedan dess, på grund av den ständiga tillväxten av material, beslutades att den fjärde volymen också skulle delas upp i separata böcker: 4A, 4B, 4C och möjligen 4D. Men denna uppdelning kommer tydligen inte att vara slutgiltig, eftersom avsnitten 7.1 och 7.2.1 redan upptar mer än 650 sidor totalt.

1976 producerade Knuth en andra upplaga av den andra volymen, som krävde omskrivningar . Men den typografiska designen ( monotypi ) som användes i den första upplagan var inte längre tillgänglig vid det här laget. För att undvika liknande frustrationer i framtiden började Knuth 1977 utveckla sitt eget typografiska datorsättningssystem. Enligt hans beräkningar borde arbetet inte ha tagit mer än ett halvår, men det tog ungefär tio år innan det var klart [5] . Systemet kallades TeX , och används för närvarande för att typsätta alla volymer av The Art of Programming. Dessutom blev TeX senare de facto standarden för att skriva artiklar och monografier inom naturvetenskap.

Precis som Knuths andra böcker bär The Art of Programming hans varumärke: för varje fel som hittas i texten betalar författaren en hexadecimal dollar eller 2,56 $ (0x100 cent , bas 16 ). Ett annat utmärkande drag för boken är överflöd av övningar för självuppfyllelse, av varierande svårighetsgrad, allt från enkla "uppvärmningsproblem" till problem med öppna slutar. Svårighetsgraden för varje övning är bedömd på en numerisk skala från 0 till 50. Så i de tidiga utgåvorna markerades Fermats sista sats med siffran 50 , men i den tredje upplagan "devalverades" detta betyg till 45, eftersom det då gång dess bevis redan hade upphört att vara ett öppet problem.

Sammanfattning av konventioner för volym tre, 1978 "Sortering och sökning" (vänster - bedömning, höger - kort förklaring)

• Svart triangel - rekommenderas
• M - Med en matematisk bias
• VM - Kräver kunskap om "högre matematik"
• 00 - Kräver ett omedelbart svar
• 10 - Enkel (i 1 minut)
• 20 - Medellång svårighet (i 15 minuter)
• 30 - Ökad svårighetsgrad
• 40 - För "matpraktikum"
• 50 - Forskningsproblem

Innehåll

Den ursprungliga planen för att skriva boken föreslog följande uppdelning av materialet.

• Volym 1. Grundläggande algoritmer.
  • Kapitel 1. Grundläggande begrepp.
  • Kapitel 2. Informationsstrukturer.
• Volym 2. Härledda algoritmer.
  • Kapitel 3. Slumptal.
  • Kapitel 4. Aritmetik.
• Volym 3. Sortering och sökning.
  • Kapitel 5. Sortering.
  • Kapitel 6
• Volym 4. Kombinatoriska algoritmer.
  • Kapitel 7. Kombinatorisk sökning.
  • Kapitel 8. Rekursion.
• Volym 5. Syntaktiska algoritmer.
  • Kapitel 9. Lexikografisk sökning.
  • Kapitel 10. Syntaktisk sökning.
• Volym 6. Språkteori.
• Volym 7. Kompilatorer.

Faktum är att detta schema implementerades till och med den tredje volymen.

För närvarande[ när? ] publicerade volym 4A, som innehåller de första avsnitten av kapitel 7. De nya avsnitten är planerade att initialt publiceras i separata nummer (cirka 128 sidor), cirka två nummer per år (nummer 0, 1, 2, 3 och 4 publicerades på liknande sätt före utgivningen av volym 4A).

Maskinorienterat exempelspråk

Exempelprogrammen i boken använder en "MIX assembler" utformad för att köras på en hypotetisk MIX-dator. I den tredje upplagan ersattes den föråldrade MIX av MMIX , ​​som har en fullfjädrad RISC - arkitektur. Det finns programvara som ger emulering av (M)MIX-maskinen på standard IBM-kompatibla datorer. GNU Compiler Collection har förmågan att kompilera C/C++-kod på MMIX-målarkitekturen.

Många läsare blir avskräckta av att använda ett lågnivåspråk, men Knuth anser att hans val är motiverat, eftersom bindningen till arkitekturen är nödvändig för att korrekt kunna bedöma sådana egenskaper hos algoritmen som hastighet, minnesförbrukning, och så vidare. Som ett resultat av detta val minskar dock målgruppen kraftigt. Dessutom är dess omfattning begränsad som en "receptbok" för praktiska programmerare, av vilka många inte kan assemblerspråk, och om de gör det känner de inte för att översätta lågnivåalgoritmer från boken till högnivåspråk . Många övningsguider som presenterar samma material på ett mer populärt sätt publiceras just av denna anledning.

Kritik

Huvuddraget i Knuths monografi, som skiljer den gynnsamt från andra böcker om programmering, är den exceptionellt höga ribban för kvaliteten på materialet och den akademiska presentationen, samt djupet i analysen av de frågor som behandlas. Tack vare detta har den blivit en riktig storsäljare och en referensbok för varje professionell programmerare [6] . Tidskriften American Scientist inkluderade The Art of Programming i sin lista över de 12 bästa fysiska och matematiska monografierna under 1900-talet [2] tillsammans med verk av Dirac om kvantmekanik , Einstein om relativitetsteorin , Russell och Whitehead om grunderna. av matematik och några andra [7] .

Omslaget till den tredje upplagan av den första volymen av boken innehåller ett citat från Bill Gates : "Om du anser dig vara en riktigt bra programmerare ... läs The Art of Programming (Knuth) ... Om du kan läsa allt detta arbete , då ska du definitivt skicka mig ett CV" [8] .

Upplagor

Original