NP-Probleme

Letztmalig dran rumgefummelt: 14.04.18 18:00:08

	1972 griff Richard Karp diese Idee auf und zeigte für 21 verschiedene kombinatorische und graphentheoretische Probleme, die dafür bekannt waren, dass sie sich hartnäckig einer effizienten algorithmischen Lösbarkeit entzogen, dass diese ebenfalls NP-vollständig sind. Indem er aufzeigte, dass eine große Anzahl von bedeutenden Problemen NP-vollständig sind, motivierte Karp die weitere Erforschung der Klasse NP, der Theorie der NP-Vollständigkeit sowie der Fragestellung, ob die Klassen P und NP identisch sind oder sich unterscheiden (P-NP-Problem). Letzteres zählt heute zu den wichtigsten offenen mathematischen Fragestellungen. Unter anderem zählt es zu den sieben Millennium-Problemen des Clay Mathematics Institute, für deren Lösung Preisgelder von jeweils einer Million US-Dollar ausgelobt wurden.
	1. Eigenschaften von Problemklassen 2. Einfache Polynomiale Probleme 3. Entscheidbarkeit 4. NP-vollständige Probleme 5. NP-schwierige Probleme 6. Verwandte Themen
	Lösbarkeit und Problemlösungsstrategien Logo der NP-vollständigen sowie NP-schweren Probleme begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	„Talente finden Lösungen, Genies entdecken Probleme.“ Krailsheimer
	Gretchen-Frage

1. Eigenschaften von Problemklassen

	Lassen wir y gleich der Anzahl der zur Lösung des Problems mit dem gefundenen Algorithmus notwendigen Elementaroperationen sein, dann verhält sich die Anzahl n der gegebenen Elemente im günstigsten Falle y = n. Das ist allerdings niemals in der Praxis der Fall - ja es sieht schon gut aus, wenn gilt y = x • n. Nun gilt aber für die weitaus größte Klasse von informatischen Problemen y = x • n² oder gar y = x • n³. Und Extreme verhalten sich wie y = x • 2n, wie y = x • 3n.
	Polynomiale Probleme Polynomiale Probleme am Beispiel mit kleiner Knotenanzahl - empirisch lösbar Polynomiale Probleme am Beispiel mit kleiner Knotenanzahl - empirisch lösbar Komplexität NP-Vollständigkeit NP-schwere Probleme Gretchen-Frage Beispiele für NP-schwere Probleme
	das Cliquenproblem das Dominoproblem das Halteproblem das K-Farben-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! The Busy Beaver-Problem Greedy Algorithm das Knotenüberdeckungsproblem das Teilsummensummenproblem
	Lösungsverfahren Graphentheorie in der Anwendung - Laufzeitoptimierung und Zeitkomplexität das ist Komplexität die Zusammenhänge zwischen den Faktoren die Zusammenhänge zwischen den Faktoren die Komplexität eines Problems & Komplexitätsklassen
	Permutationen

2. Einfache Polynomiale Probleme - Lösbarkeit von Problemen

	Lösbar ist eine Aufgabe nur, wenn es ein irgendwie sinnvolles Antwortzeitverhalten auf eine sinnvolle Datenmenge mit eindeutigen (als zum Beispiel schon mal nicht gerundeten) Zwischenergebnissen gibt, deren Aufwand sich im Sinne der Problemstellung

3. Entscheidbarkeit

	Entscheidbar ist ein Problem hinsichtlich seiner Lösung, wenn die Anzahl der Zwischenargumente zwar groß, im Extremfall auch sehr groß - aber endlich ist. Ist dies nicht mehr gegeben, so ist auch das Problem hinsichtlich seiner Lösung und/oder seines Lösungsumfanges nicht mehr entscheidbar
	Backtracking

4. NP-vollständige Probleme

Hiermit soll die Aussage getroffen werden, ob ein Algorithmus in endlicher Zeit zum Halten und damit zu einer sinnvollen Menge definierter Ergebnisse kommt oder aber auch nicht! Alle Aufgaben und/oder Algorithmen, welche dies nicht grundsätzlich bejahen, fallen in die Menge der nicht entscheidbaren bzw. nicht lösbaren Probleme - und dies grundsätzlich.

Der folgende Baum zeigt Karps 21 Probleme, inklusive der zugehörigen Reduktion, die er nutzte, um ihre NP-Vollständigkeit nachzuweisen. Zum Beispiel wurde die NP-Vollständigkeit des Rucksackproblems gezeigt, indem das Problem der exakten Überdeckung darauf reduziert wurde. SATISFIABILITY: das Erfüllbarkeitsproblem der Aussagenlogik für Formeln in Konjunktiver Normalform CLIQUE: Cliquenproblem SET PACKING: Mengenpackungsproblem VERTEX COVER: Knotenüberdeckungsproblem SET COVERING: Mengenüberdeckungsproblem FEEDBACK ARC SET: Feedback Arc Set FEEDBACK NODE SET: Feedback Vertex Set DIRECTED HAMILTONIAN CIRCUIT: siehe Hamiltonkreisproblem UNDIRECTED HAMILTONIAN CIRCUIT: siehe Hamiltonkreisproblem 0-1 INTEGER PROGRAMMING: siehe Integer Linear Programming 3-SAT: siehe 3-SAT CHROMATIC NUMBER: graph coloring problem CLIQUE COVER: Covering by cliques EXACT COVER: Problem der exakten Überdeckung 3-dimensional MATCHING: 3-dimensional matching STEINER TREE: Steinerbaumproblem HITTING SET: Hitting set KNAPSACK: Rucksackproblem JOB SEQUENCING: Job sequencing PARTITION: Partitionsproblem MAX-CUT: Max cut

5. NP-schwierige Probleme

	Die Klasse der NP-vollständigen ist die komplexeste aller Problemklassen. Nicht das es immer ihre Kompliziertheit innerhalb des Algorithmus darstellt - nein, die schiere Menge an zu untersuchenden Fällen kann dazu führen, dass diese Probleme praktisch nicht mehr lösbar sind und nach Alternativen gesucht werden muss.
	das Halteproblem das Cliquenproblem das K-Farben-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Hamiltonproblem das Knotenüberdeckungsproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Post'sche Korrespondenz-Problem das Teilsummensummenproblem
	Turing-Maschine

6. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching
	Funktionen & Prozeduren mit Parameterübergabe Rekursion

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost September 2007