×

zbMATH — the first resource for mathematics

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ß

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