Schöning / Meier / Vollmer Komplexität von Algorithmen

Mathematik für Anwendungen Band 4
1. Auflage 2015
ISBN: 978-3-86541-766-4
Verlag: Lehmanns Media
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Deutsch, Band 4, 203 Seiten

Reihe: Mathematik für Anwendungen

Dieses Lehrbuch, entstanden aus einer Anfängervorlesung aus dem Informatik-Studiengang an der Leibniz Universität Hannover, bietet einen ersten Einstieg in den Bereich der Komplexitätstheorie. Der Leser wird mit den wichtigsten Begriffen und Resultaten aus diesem Bereich vertraut gemacht: Komplexitätsklassen, vollständige („schwierigste“) Probleme in einer Komplexitätsklasse – detailliert am Begriff der NP-Vollständigkeit und an vielen Beispielen ausgeführt – sowie Approximationsalgorithmen als Lösungsmöglichkeit für viele NP-vollständige Probleme. Außerdem enthält das Buch eine große Anzahl an Übungsaufgaben (mit vielen Lösungen) wie auch abschließend die Möglichkeit, sein erarbeitetes Wissen in zwei exemplarischen Klausuren zu prüfen.

Autoren/Hrsg.

Meier, Arne

Vollmer, Heribert

Schöning, Uwe

Inhaltsverzeichnis

1;Titel;2
2;Inhaltsverzeichnis;4
3;I.Komplexitätsmaße;9
3.1;1.Wie aus Raum Zeit wird und umgekehrt;10
3.1.1;1.1.Welche Probleme wollen wir lösen?;12
3.1.2;1.2.Eine Universalmaschine;14
3.1.3;1.3.Viele Bänder bringen nicht viel mehr als zwei;21
3.1.4;1.4.Nichtdeterminismus;26
3.1.5;1.5.Beziehungen zwischen den Komplexitätsklassen;29
3.1.6;1.6.Die Hierarchiesätze;35
3.2;2.Sind Turingmaschinen ein realistisches Modell?;52
3.2.1;2.1.Computerprogramme auf Turingmaschinen;53
3.3;3.Effizienz – Warum P einfach besser als EXP ist;60
3.3.1;3.1.Polynomialzeit – die Klasse P;60
3.3.2;3.2.NP – the class of dashed hopes and idle dreams;66
3.3.3;3.3.Die größte Frage der Informatik: Das P-NP-Problem;71
4;II.NP-Vollständigkeit;78
4.1;4.Der Weg zur Vollständigkeit;80
4.1.1;4.1.Reduzierbarkeit – aus Problem A wird Problem B;80
4.1.2;4.2.Vollständigkeit – das (vorerst) letzte Wort;82
4.1.3;4.3.Der Satz von Cook und Levin – der Anfang ist gemacht;84
4.2;5.Ein Bausatz von NP-vollständigen Problemen;96
4.2.1;5.1.Graphenprobleme;97
4.2.2;5.2.Numerische Probleme;108
4.2.3;5.3.Mahaney's Theorem;113
4.2.4;5.4.Rezepte;115
5;III.Approximierbarkeit;127
5.1;6.Optimierung – ein Lichtblick;128
5.1.1;6.1.Optimierungsprobleme – bis wohin geht's?;129
5.1.2;6.2.Approximationsalgorithmen;135
5.2;7.Beispiele von Approximierbarkeit;142
5.2.1;7.1.Das Problem des Handlungsreisenden MinTSP;143
5.2.2;7.2.Das Partitionierungsproblem;151
5.2.3;7.3.Das Erfüllbarkeitsproblem;153
5.2.4;7.4.Optimierungsklassen;155
6;IV.Anhang;165
6.1;Graphen;166
6.2;Aussagenlogik;168
6.3;Klausuren;174
6.4;Abkürzungen;190
6.5;Liste von behandelten Problemen;192
6.6;Index;200

Über Autor(innen)

Heribert Vollmer ist Leiter des Instituts für Theoretische Informatik an der Leibniz Universität Hannover.
Arne Meier ist Lecturer am Institut für Theoretische Informatik an der Leibniz Universität Hannover.