A programozás művészete

A számítógép-programozás művészete [ 1] a  híres amerikai matematikus és informatikus, Donald Knuth alapvető monográfiája , amely a számítástechnikában használt legfontosabb algoritmusok figyelembevételével és elemzésével foglalkozik . 1999-ben a könyvet az évszázad tizenkét legjobb fizikai és matematikai monográfiája közé sorolták [2] .

A könyvírási projektet a szerző indította el 1962-ben. Kezdetben egy kötetben tervezték kiadni, de az anyag mennyisége olyan nagynak bizonyult, hogy a kötetek számát hétre emelték. Az első három kötet meglehetősen gyorsan megjelent: az 1. kötet - 1968-ban, a 2. kötet - 1969-ben, a 3. kötet - 1973-ban. Ezt 2005 februárjáig szünet követte, ebben a negyedik kötet első részét adta ki a szerző. Az a döntés született, hogy a negyedik kötet fennmaradó részeit évente körülbelül két alkalommal, külön számban adják ki, majd a teljes negyedik kötetet hivatalosan is kiadják. 2005-2009 között a 0., 1., 2., 3. és 4. számok jelentek meg, 2011-ben pedig a 4A. kötet, amely ezekből a számokból tartalmazta az információkat. Szintén 2005-ben jelent meg az 1. szám, „MMIX – A RISC Computer for the New Millennium”, amelyből származó információk az első kötet új, negyedik kiadásában fognak szerepelni. A 6. szám (2015-ben) és az 5. szám (2017-ben) a 4B kötet részeként jelent meg. Maga a 4B kötet 2022-ben jelent meg.

Mivel Knuth mindig is a Programozás művészetét tartotta élete fő projektjének, 1993-ban visszavonult azzal a szándékkal, hogy teljes mértékben a hiányzó részek megírására és a meglévők rendbetételére koncentráljon [3] . Úgy vélte, hogy a munka befejezése 20 évig tart [4] .

Történelem

A fordítóprogramok tervezésének elismert szakértőjeként 1962-ben Knuth könyvet kezdett írni a fordítóprogramok tervezéséről. Hamar rájött, hogy az anyag terjedelmét sokkal szélesebbre kell terjeszteni. 1965 júniusában befejezte annak az első változatának megírását, amit eredetileg ki akart adni egy tizenkét részből álló könyvben. A kézzel írt szöveg terjedelme 3000 oldal volt. Knuth számításai szerint ennek a kötetnek 600 nyomtatott oldalba kellett volna beleférnie, de – mint kiadója tájékoztatta – a tényleges mennyiség 2000 oldal lenne. E tekintetben a könyv szerkezetét több kötet, egyenként 1-2 szakasz javára módosították. Azóta az anyag folyamatos gyarapodása miatt úgy döntöttek, hogy a negyedik kötetet is külön könyvekre osztják: 4A, 4B, 4C, esetleg 4D. De ez a felosztás a jelek szerint nem lesz végleges, mivel a 7.1 és 7.2.1 szakaszok összesen már több mint 650 oldalt foglalnak el.

1976-ban Knuth elkészítette a második kötet második kiadását, amely újragépelést igényelt . A jövőbeni hasonló csalódások elkerülése érdekében Knuth 1977-ben megkezdte saját tipográfiai számítógépes szedőrendszerének fejlesztését. Számításai szerint a munkának nem kellett volna több hat hónapnál, de körülbelül tíz évbe telt, mire elkészült [5] . A rendszert TeX - nek hívták , és jelenleg a The Art of Programming összes kötetének szedésére használják. Ráadásul később a TeX a természettudományi cikkek és monográfiák írásának de facto szabványává vált.

Knuth többi könyvéhez hasonlóan a Programozás művészete is a védjegyét viseli: minden, a szövegben talált hibáért a szerző egy hexadecimális dollárt , azaz 2,56 dollárt (0x100 cent , 16 -os alap ) fizet. A könyv másik megkülönböztető vonása az önmegvalósítást szolgáló gyakorlatok bősége, különböző nehézségi fokú, az egyszerű „bemelegítő” feladatoktól a nyílt végű feladatokig. Az egyes gyakorlatok nehézségi fokát egy numerikus skálán értékelik 0-tól 50-ig. Tehát a korai kiadásokban Fermat Utolsó tételét 50-es számmal jelölték , de a harmadik kiadásban ezt az értékelést 45-re "leértékelték", mivel ezzel annak bizonyítása már megszűnt nyitott probléma lenni.

Az 1978-as „Válogatás és keresés” harmadik kötetének egyezményeinek összefoglalása (balra - értékelés, jobbra - rövid magyarázat)

• Fekete háromszög – ajánlott
• M - Matematikai torzítással
• VM - "Felsőfokú matematika" ismerete szükséges
• 00 – Azonnali választ igényel
• 10 - Egyszerű (1 percig)
• 20 - Közepes nehézségű (15 percig)
• 30 - Fokozott nehézség
• 40 - "matpraktikum"
• 50 - Kutatási probléma

Tartalom

A könyv megírásának eredeti terve az anyag következő bontását javasolta.

• 1. kötet. Alapvető algoritmusok.
  • 1. fejezet Alapfogalmak.
  • 2. fejezet Információs struktúrák.
• 2. kötet. Származtatott algoritmusok.
  • 3. fejezet Véletlen számok.
  • 4. fejezet Aritmetika.
• 3. kötet. Rendezés és keresés.
  • 5. fejezet. Rendezés.
  • 6. fejezet
• 4. kötet. Kombinatorikus algoritmusok.
  • 7. fejezet Kombinatorikus keresés.
  • 8. fejezet Rekurzió.
• 5. kötet. Szintaktikai algoritmusok.
  • 9. fejezet Lexikográfiai keresés.
  • 10. fejezet Szintaktikai keresés.
• 6. kötet. Nyelvek elmélete.
• 7. kötet. Összeállítók.

Valójában ezt a rendszert a harmadik kötetig bezárólag végrehajtották.

Jelenleg[ mikor? Az új rovatokat kezdetben külön-külön (kb. 128 oldal) tervezzük, évente körülbelül két számmal (a 0., 1., 2., 3. és 4. szám hasonlóképpen a 4A kötet megjelenése előtt jelent meg).

Géporientált példanyelv

A könyvben található példaprogramok "MIX assemblert" használnak, amelyet feltételezett MIX számítógépen való futtatásra terveztek. A harmadik kiadásban az elavult MIX -et az MMIX váltotta fel , amely teljes értékű RISC architektúrával rendelkezik. Létezik olyan szoftver , amely az (M)MIX gép emulációját biztosítja szabványos IBM-kompatibilis számítógépeken. A GNU Compiler Collection képes C/C++ kódot fordítani az MMIX célarchitektúrán.

Sok olvasót elriaszt az alacsony szintű nyelvhasználat ténye, de Knuth indokoltnak tartja választását, hiszen az architektúrához való kötés szükséges ahhoz, hogy pontosan meg lehessen ítélni az algoritmus olyan jellemzőit, mint a sebesség, a memóriafelhasználás, stb. E választás eredményeként azonban a célközönség erősen leszűkül. Ezen túlmenően hatóköre korlátozott, mint „receptkönyv” gyakorlati programozók számára, akik közül sokan nem ismerik az assembly nyelvet, és ha ismerik, nincs kedvük alacsony szintű algoritmusokat lefordítani a könyvből magas szintű nyelvekre. . Sok gyakorlati útmutatót adnak ki, amelyek ugyanazt az anyagot népszerűbben mutatják be.

Kritika

Knuth monográfiájának fő jellemzője, amely kedvezően különbözteti meg a többi programozással foglalkozó könyvtől, az anyag és az akadémiai prezentáció minőségének kiemelkedően magas léce, valamint a vizsgált kérdések elemzésének mélysége. Ennek köszönhetően igazi bestsellerré és referenciakönyvvé vált minden profi programozó számára [6] . Az American Scientist magazin felvette a The Art of Programming-t a 20. század 12 legjobb fizikai és matematikai monográfiájának listájára [2] , valamint Dirac kvantummechanikáról , Einstein a relativitáselméletről , Russell és Whitehead az alapokról szóló munkáit . a matematika és néhány másik [7] .

A könyv első kötetének harmadik kiadásának borítója Bill Gates idézetét tartalmazza : "Ha igazán jó programozónak tartod magad... olvasd el a Programozás művészetét (Knuth)... Ha el tudod olvasni ezt a munkát , akkor mindenképpen küldjön önéletrajzot" [8] .

Kiadások

Eredeti