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.
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 Zustimmung 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 [1].
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. ( [2])
URL dieses Artikels:
https://www.heise.de/-5019249
Links in diesem Artikel:
[1] https://www.heise.de/Datenschutzerklaerung-der-Heise-Medien-GmbH-Co-KG-4860.html
[2] mailto:webmaster@goloroden.de
Copyright © 2021 Heise Medien