Knuth, Donald E. The art of computer programming. Vol. 3: Sorting and searching. (English) Zbl 0302.68010 Addison-Wesley Series in Computer Science and Information Processing. Reading, Mass. etc.: Addison-Wesley Publishing Company. XI, 722 p. (1973). Der 3. Band [vgl. Bd. 1, Fundamental algorithms (1968; Zbl 0191.17903) und Bd. 2, Seminumerical algorithms (1969; Zbl 0191.18001)] enthält die Kapitel 5 (Sorting) und 6 (Searching) der geplanten 7-bändigen Monographie über die “Kunst des Programmierens”. Die stürmische Entwicklung gerade dieser Teilgebiete der Datenverarbeitung in den letzten Jahren verzögerte zwar das Erscheinen des Buches um fast 3 Jahre, führte aber zu einer erstaunlichen Vielfalt des aufgenommenen Stoffes. Der Verf. umreißt die behandelten Probleme durch die folgenden Fragen: Wie findet man gute Algorithmen? Wie können gegebene Algorithmen und Programme verbessert werden? Wie kann die Effektivität von Algorithmen mathematisch analysiert werden? Wie kann man rationall zwischen verschiedenen Algorithmen für das gleiche Problem wählen? In welchem Sinne können Algorithmen optimal sein? Wie können externe Speicher effektiv eingesetzt werden? Inhaltlich schließt sich der vorliegende Band an Kapitel 2 (Information Structures) des 1. Bandes an. Kap. 5 (Sorting) enthält neben einem Abschnitt über Permutationen und einen über optimales Sortieren die beiden Hauptabschnitte “Internal Sorting” und “External Sorting”. Kap. 6 (Searching) ist in folgende Abschnitte untergliedert: Sequential Searching, Searching by Comparison of Keys, Digital Searching, Hashing, Retrieval an Secondary Keys. Das Buch eignet sich sowohl als Grundlage für Vorlesungen unterschiedlichen Schwierigkeitsgrades (Abschritte vorwiegend mathematischen Inhalts sind durch * gekennzeichnet) als auch zum Selbststudium. Dazu sind die Übungsaufgaben sowohl nach den benötigten mathematischen Kenntnissen als auch nach ihrem Schwierigkeitsgrad sorgfältig klassifiziert. Auch dieser Band ist durch einen Anhang, in dem die in den vorangegangenen Bänden eingeführten Bezeichnungen erklärt werden, weitgehend unabhängig benutzbar. Reviewer: Gerhard Maeß Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 39 ReviewsCited in 1429 Documents MSC: 68N01 General topics in the theory of software 68-02 Research exposition (monographs, survey articles) pertaining to computer science 68P10 Searching and sorting 68W99 Algorithms in computer science Citations:Zbl 0191.17903; Zbl 0191.18001 × Cite Format Result Cite Review PDF Full Text: Link Link Online Encyclopedia of Integer Sequences: a(n) = n^2 + n + 2. Numbers k such that k^2 - k + 1 is prime. Number of permutations of n^2 distinct integers free of any monotonic increasing or decreasing (n+1)-subsequence. Knuth’s standard example of an unsorted array. Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the ”first transposition” algorithm.