Algorithmics
type: Item
instance of: scholarly article
zbMATH Open document ID: 0993.68143
publication date: 2001-11-19T00:00:00Z
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68P01
Mathematics Subject Classification ID: 68-01
zbMATH DE Number: 1674735
zbMATH Keywords: dynamical programming
zbMATH Keywords: data compression
zbMATH Keywords: greedy algorithm
author: Uwe Schöning
MaRDI profile type: Publication
title: Algorithmics
review text: 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…
reviewed by: Hans-Dietrich Hecker
description: scientific article; zbMATH DE number 1674735