Algorithmics (Q2756798)

Dieses Buch von U. Schöning setzt die Reihe seiner beliebten Informatikbücher fort. Da es inzwischen auch in deutscher Sprache eine ganze Reihe von Büchern zu dem umfassenderen Gebiet ``Algorithmen und Datenstrukturen'' gibt, lohnt es sich vielleicht, hier auf einige Besonderheiten hinzuweisen. Es wird zunächst versucht, nicht Details in den Mittelpunkt der Überlegungen zu stellen, sondern die Grundprinzipien sind der rote Faden des Buches. Dabei wird relativ viel Raum solchen Themen wie amortisierte Kostenanalyse, Probabilistische Algorithmen und Pseudozufallszahlen und Derandomisierung gewidmet. So verwundert es auch nicht, dass bei der Thematik der Suchbäume die optimalen binären Suchbäume mit behandelt werden. Das findet man in analogen Büchern eher selten, aber hier liefert es ein sehr schönes Beispiel im Kapitel ``Dynamisches Programmieren'', das aus meiner Sicht insgesamt ein schöner Höhepunkt des Buches ist. Es folgen Greedy-Algorithmen und Matroide, Algorithmen auf Graphen (dort ist vor allem auf das für verschiedene Anwendungen in der algorithmischen Geometrie wichtige topologische Sortieren hinzuweisen), danach Betrachtungen u.a. zu Backtracking, Branch-and-bound, und-oder-Bäumen, Min-Max und Alpha-Beta.NEWLINENEWLINENEWLINENach den Kapiteln über Datenkompression, algebraische und zahlentheoretische Algorithmen, String Matching und über heuristische Algorithmen folgt aus meiner Sicht das besonders interessante Kapitel über Algorithmen für das Erfüllbarkeitsproblem. Der Autor betont, dass daraus, dass die Theorie zwar besagt, dass NP-vollständige Probleme vermutlich nicht effizient lösbar sind, noch nicht folgt, dass man nicht doch effiziente approximative, heuristische Lösungsalgorithmen bzw. solche mit gemäßigt ausgeprägtem exponentiellen Laufzeitverhalten finden kann. So werden in diesem letzten Kapitel u.a. die effizientesten Algorithmen für das Problem \(k\)-SAT studiert.NEWLINENEWLINENEWLINEAbschließend kann ich dem Autor nur zustimmen, wenn er meint, das die Algorithmik ein Gebiet ist, bei dem der Schulterschluss zwischen theoretisch orientierter Grundlagenforschung und anwendungsnaher Entwicklung von Software besonders gut geglückt ist. Und dass dieses Buch das sehr schön zeigt, bestätigen mir auch meine Studenten immer wieder.