RTFM #2: Computers and Intractability
Die Serie RTFM stellt in unregelmäßigen Abständen zeitlose und empfehlenswerte Bücher für Entwicklerinnen und Entwickler vor. Primär geht es um Fachbücher, doch gelegentlich sind auch Romane darunter. Heute geht es um "Computers and Intractability" von Michael R. Garey und David S. Johnson.
- Golo Roden
Die Serie RTFM stellt in unregelmäßigen Abständen zeitlose und empfehlenswerte Bücher für Entwicklerinnen und Entwickler vor. Primär geht es um Fachbücher, doch gelegentlich sind auch Romane darunter. Heute geht es um "Computers and Intractability" von Michael R. Garey und David S. Johnson.
Das Buch "Computers and Intractability: A Guide to the Theory of NP-Completeness" von Michael R. Garey und David S. Johnson beschäftigt sich mit der Komplexitätstheorie, einem Themenbereich der theoretischen Informatik. Das Buch stammt bereits aus dem Jahr 1979, ist aber zeitlos und daher heute nicht minder aktuell als vor vier Jahrzehnten.
Es umfasst ungefähr 350 Seiten, die sich in zwei Hälften zerlegen lassen, eine Einführung und eine Referenz. Die Einführung erläutert zunächst die Grundlagen und beschäftigt sich mit der Frage, warum es lohnenswert ist, sich mit dem Thema zu befassen. Besonderes Augenmerk wird auf die verschiedenen Komplexitätsklassen gelegt, unter anderem P, NP, NP-schwer und NP-vollständig.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
NP-vollständige Probleme
Darüber hinaus geht es um die Herausforderung, NP-Vollständigkeit für Probleme überhaupt nachzuweisen, und natürlich auch um die bis heute ungeklärte Frage, ob die Komplexitätsklassen P und NP identisch sind oder nicht. Insgesamt stellt die erste Hälfte eine gute und anschauliche Einführung in dieses theoretische Thema dar.
Die zweite Hälfte des Buchs enthält als Referenz eine Liste hunderter NP-vollständiger Probleme, nach verschiedenen Kategorien sortiert. Für jedes Problem wird eine (mehr oder weniger) anschauliche Fragestellung genannt und die mathematische Definition. Außerdem gibt es zu zahlreichen Problemen hilfreiche Kommentare, die auf Besonderheiten oder spezielle Eigenschaften des jeweiligen Problems eingehen.
Fazit
Das Buch ist ein zeitloses Nachschlagewerk und eine Referenz, die zum Stöbern einlädt. Auch wer sich im Alltag nicht mit theoretischer Informatik beschäftigt, kann aus dem Buch eine Menge lernen, was hilfreich für die Praxis ist. Daher sei dieses Buch jeder Entwicklerin und jedem Entwickler zur Lektüre empfohlen. ()
