Algorithmics
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.
- Complexity theory. Limits of the efficiency of algorithms
- scientific article; zbMATH DE number 1024633 (Why is no real title available?)
- Algorithms and data structures. Basics and probabilistic methods for design and analysis
- scientific article; zbMATH DE number 958772 (Why is no real title available?)
- A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
This page was built for publication: Algorithmics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2756798)
