Sztuka programowania

Sztuka programowania (The Art of Computer Programming) – fundamentalna monografia autorstwa Donalda Knutha dotycząca analizy algorytmów.

W 1962, gdy został poproszony przez wydawnictwo Addison-Wesley o napisanie książki, był już uznanym specjalistą od kompilatorów. Do 1966 notatki sporządzone przez Knutha do książki o kompilatorach urosły do 3000 stron. Knuth postanowił wydać siedmiotomowe dzieło – Sztuka programowania – traktujące o analizie algorytmów. Materiał dotyczący kompilatorów ma być zawarty w tomie VII. W 1968 wydano pierwszy tom, a kolejne w latach 1969, 1973. Z części IV Knuth opublikował na razie fragmenty (są one również dostępne na jego stronie), części V, VI i VII jeszcze nie napisał.

W 1976, gdy przygotowywał nowe wydanie Sztuki programowania, postanowił napisać program do składu tekstu TeX i system do projektowania znaków METAFONT, ponieważ ówczesne rozwiązania nie były dla niego zadowalające. Po ośmiu latach zakończył pracę i T_EX jest obecnie używany do składania tekstów przez matematyków i fizyków na całym świecie.

Części

Tom I – Algorytmy podstawowe

• Rozdział 1. Pojęcia podstawowe
• Rozdział 2. Struktury danych

Tom I to wprowadzenie do analizy algorytmów, jest tu omówiony repertuar matematyczny używany w kolejnych tomach. Rozdział 1. można traktować jako podręcznik do matematyki dyskretnej. Omówione jest tu też programowanie w języku maszynowym i komputer MIX. W rozdziale drugim Knuth omówił podstawowe struktury danych – listy liniowe i drzewa.

Tom II – Algorytmy seminumeryczne

• Rozdział 3. Liczby losowe
• Rozdział 4. Arytmetyka

Rozdział 3. poświęcony jest liczbom losowym, metodom ich generowania i testowania. W rozdziale 4. autor omówił systemy liczbowe, konwersje między nimi, arytmetykę liczb całkowitych, liczb zmiennopozycyjnych, wymiernych.

Tom III – Sortowanie i wyszukiwanie

• Rozdział 5. Sortowanie
• Rozdział 6. Wyszukiwanie

Tom III traktuje o sortowaniu wewnętrznym, optymalnym i zewnętrznym. Szczegółowo omówione są rodzaje wyszukiwań elementów w zbiorach i tablicach. Dodatkowo autor na przykładzie algorytmów sortowania i wyszukiwania odpowiada na takie pytania jak: W jaki sposób tworzyć dobre algorytmy? Jak matematycznie analizować efektywność algorytmów? Co to znaczy, że algorytm jest „najlepszy z możliwych”?

Tom IV – Algorytmy kombinatoryczne

• Rozdział 7. Wyszukiwanie kombinatoryczne
• Rozdział 8. Rekurencja

Tom IV nie został jeszcze wydany w całości. Obecnie Knuth planuje wydać Algorytmy kombinatoryczne w trzech lub czterech podtomach – Tom 4A – Enumeracja i Backtracking, Tom 4B – Grafy i Algorytmy sieciowe, Tom 4C i prawdopodobnie 4D – Optymalizacja i Rekursja. Dotychczas z tomu IV autor wydał 5 zeszytów obejmujących swoim zakresem część rozdziału 7, których wydanie jako tom 4A planowane jest na rok 2010.

Tom V – Algorytmy składniowe

• Rozdział 9. Analiza leksykalna
• Rozdział 10. Analiza składniowa

Tom jeszcze nie wydany. Nie są jeszcze znane szczegóły dotyczące tego tomu. Autor planuje zakończyć pracę nad tym tomem do roku 2015, wtedy też ma zamiar przeprowadzić rewizję tomów 1-3 w ostatecznej edycji. Następnie zamierza wydać skróconą formę tomów 1-5 w jednej książce.

Tom VI – Teoria języków

Planowany. Nad tomem VI i VII Knuth ma zamiar rozpocząć pracę po ostatecznym zakończeniu prac nad tomami I–V i jeśli uzna, że materiał będzie wciąż istotny do omówienia.

Tom VII – Kompilatory

Planowany.

Zawartość

Autor zakłada u czytelnika znajomość podstaw programowania, wiedzę na temat podstawowych technik obliczeniowych (pętle, podprogramy), znajomość niektórych pojęć żargonowych (pamięć, przepełnienie, zmiennopozycyjny). Jak sam Knuth twierdzi: Czytelnik powinien mieć na swoim koncie przynajmniej cztery napisane i przetestowane programy. Matematyka na poziomie szkoły średniej pozwala na zrozumienie podstaw materiału matematycznego książek, jednak do pełnego zrozumienia wymagana jest znajomość analizy matematycznej.

Książki zawierają dużą liczbę ćwiczeń o różnym stopniu trudności wraz z odpowiedziami. Każde zadanie jest ocenione ze względu na trudność w skali od 00 do 50, przy czym ocena 00 to zadanie trywialne, a 50 to prawdopodobnie jeszcze nierozwiązany problem badawczy. Dodatkowo oznaczone są zadania wymagające znajomości matematyki na poziomie wyższym.

Większość przykładów w książkach posługuje się archaicznym już językiem zwanym MIXAL (MIX Assembly Language), który jest uruchamiany na hipotetycznym komputerze MIX. Obecnie MIX jest zastępowany przez MMIX, wersję maszyny RISC, która zostanie wprowadzona w ostatecznym – czwartym – wydaniu Sztuki programowania. Niektórzy czytelnicy są zakłopotani użyciem asemblera, jednak Knuth uważa to za konieczne i słuszne z kilku powodów, m.in. języki wysokiego poziomu nie umożliwiają przedstawienia szczegółów niskopoziomowych omawianych w książkach i wychodzą z mody mniej więcej co pięć lat. Istnieją darmowe emulatory MIX (GNU MDK), dostępne do pobrania w Internecie.

W 1999 miesięcznik naukowy American Scientist umieścił tę pracę na liście najlepszych dwunastu prac z dziedziny nauk przyrodniczych XX wieku, pośród dzieł m.in. Einsteina, Mandelbrota, Diraca, Neumanna, Wienera, Feynmana.

Sławna oferta Knutha przyznania nagrody pieniężnej w wysokości 2 dolarów 56 centów za wszelkie znalezione błędy typograficzne, techniczne czy historyczne spowodowała, że praca jest w wysokim stopniu dopracowana i stanowi fundament programistyczny długo po jej pierwszej edycji. W świecie informatyków mówi się, że bardzo mała liczba czeków wystawionych przez Knutha została zrealizowana.

Wydania

Edycje polskojęzyczne

• Tom I: Algorytmy podstawowe. (Wydawnictwa Naukowo-Techniczne, Warszawa 2002), xxiv+679 s. ISBN 83-204-2540-9.
• Tom I, Zeszyt 1: MMIX – Komputer na nowe tysiąclecie. (Wydawnictwa Naukowo-Techniczne, Warszawa 2008), 148 s. ISBN 978-83-204-3373-9.
• Tom II: Algorytmy seminumeryczne. (Wydawnictwa Naukowo-Techniczne, Warszawa 2002), xviii+820 s. ISBN 83-204-2553-0.
• Tom III: Sortowanie i wyszukiwanie. (Wydawnictwa Naukowo-Techniczne, Warszawa 2002), xviii+838 s. ISBN 83-204-2554-9.
• Tom IV, Zeszyt 2: Generowanie wszystkich krotek i permutacji. (Wydawnictwa Naukowo-Techniczne, Warszawa 2007), 138 s. ISBN 978-83-204-3293-0.

Dostępne jest wydanie zbiorcze, trzytomowe – ISBN 83-204-2539-5.

Powyższe wydania są tłumaczeniem najnowszych, trzeciej edycji (Tom I i II) i drugiej (Tom III) wydania anglojęzycznego. Tom I przetłumaczył Grzegorz Jakacki, Tom II – Adam Malinowski, Tom III – Krzysztof Diks i Adam Malinowski.

Edycje anglojęzyczne

• Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650 s. ISBN 0-201-89683-4.
• Volume 1, Fascicle 1: MMIX -- A RISC Computer for the New Millennium. (Addison-Wesley, 14 lutego 2005) ISBN 0-201-85392-2 (zawarte będzie w czwartej edycji tomu I)
• Volume 2: Seminumerical Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762 s. ISBN 0-201-89684-2.
• Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780 s. + wkładka. ISBN 0-201-89685-0.
• Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions (Addison-Wesley Professional, 28 kwietnia 2008) vi+240 s. ISBN 0-321-53496-4.
• Volume 4, Fascicle 1: Bitwise tricks and techniques and Binary Decision Diagrams (Addison-Wesley Professional, 27 marca 2009) 272 s. ISBN 0-321-58050-8.
• Volume 4, Fascicle 2: Generating All Tuples and Permutations (Addison-Wesley, 14 lutego 2005) v+127 s. ISBN 0-201-85393-0.
• Volume 4, Fascicle 3: Generating All Combinations and Partitions. (Addison-Wesley, 26 lipca 2005) vi+150 s. ISBN 0-201-85394-9.
• Volume 4, Fascicle 4: Generating all Trees -- History of Combinatorial Generation (Addison-Wesley, 6 lutego 2006) vi+120 s. ISBN 0-321-33570-8.

Linki zewnętrzne

• Donald E.D.E. Knuth Donald E.D.E., The Art of Computer Programming (TAOCP) [online]  (ang.).