Komplexität von Algorithmen
Mathematik für Anwendungen Band 4
1st Edition
Published on 29. April 2015
204 pages
978-3-86541-766-4 (ISBN)
Description
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.
More details
Other editions
Additional editions
Arne Meier | Heribert Vollmer | Uwe Schöning
Komplexität von Algorithmen
Mathematik für Anwendungen Band 4
Book
04/2015
Lehmanns Media
€9.95
Article exhausted; check for reprint
Persons
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.
Arne Meier ist Lecturer am Institut für Theoretische Informatik an der Leibniz Universität Hannover.
Content
1 - Titel [Seite 2]
2 - Inhaltsverzeichnis [Seite 4]
3 - I.Komplexitätsmaße [Seite 9]
3.1 - 1.Wie aus Raum Zeit wird und umgekehrt [Seite 10]
3.1.1 - 1.1.Welche Probleme wollen wir lösen? [Seite 12]
3.1.2 - 1.2.Eine Universalmaschine [Seite 14]
3.1.3 - 1.3.Viele Bänder bringen nicht viel mehr als zwei [Seite 21]
3.1.4 - 1.4.Nichtdeterminismus [Seite 26]
3.1.5 - 1.5.Beziehungen zwischen den Komplexitätsklassen [Seite 29]
3.1.6 - 1.6.Die Hierarchiesätze [Seite 35]
3.2 - 2.Sind Turingmaschinen ein realistisches Modell? [Seite 52]
3.2.1 - 2.1.Computerprogramme auf Turingmaschinen [Seite 53]
3.3 - 3.Effizienz - Warum P einfach besser als EXP ist [Seite 60]
3.3.1 - 3.1.Polynomialzeit - die Klasse P [Seite 60]
3.3.2 - 3.2.NP - the class of dashed hopes and idle dreams [Seite 66]
3.3.3 - 3.3.Die größte Frage der Informatik: Das P-NP-Problem [Seite 71]
4 - II.NP-Vollständigkeit [Seite 78]
4.1 - 4.Der Weg zur Vollständigkeit [Seite 80]
4.1.1 - 4.1.Reduzierbarkeit - aus Problem A wird Problem B [Seite 80]
4.1.2 - 4.2.Vollständigkeit - das (vorerst) letzte Wort [Seite 82]
4.1.3 - 4.3.Der Satz von Cook und Levin - der Anfang ist gemacht [Seite 84]
4.2 - 5.Ein Bausatz von NP-vollständigen Problemen [Seite 96]
4.2.1 - 5.1.Graphenprobleme [Seite 97]
4.2.2 - 5.2.Numerische Probleme [Seite 108]
4.2.3 - 5.3.Mahaney's Theorem [Seite 113]
4.2.4 - 5.4.Rezepte [Seite 115]
5 - III.Approximierbarkeit [Seite 127]
5.1 - 6.Optimierung - ein Lichtblick [Seite 128]
5.1.1 - 6.1.Optimierungsprobleme - bis wohin geht's? [Seite 129]
5.1.2 - 6.2.Approximationsalgorithmen [Seite 135]
5.2 - 7.Beispiele von Approximierbarkeit [Seite 142]
5.2.1 - 7.1.Das Problem des Handlungsreisenden MinTSP [Seite 143]
5.2.2 - 7.2.Das Partitionierungsproblem [Seite 151]
5.2.3 - 7.3.Das Erfüllbarkeitsproblem [Seite 153]
5.2.4 - 7.4.Optimierungsklassen [Seite 155]
6 - IV.Anhang [Seite 165]
6.1 - Graphen [Seite 166]
6.2 - Aussagenlogik [Seite 168]
6.3 - Klausuren [Seite 174]
6.4 - Abkürzungen [Seite 190]
6.5 - Liste von behandelten Problemen [Seite 192]
6.6 - Index [Seite 200]
2 - Inhaltsverzeichnis [Seite 4]
3 - I.Komplexitätsmaße [Seite 9]
3.1 - 1.Wie aus Raum Zeit wird und umgekehrt [Seite 10]
3.1.1 - 1.1.Welche Probleme wollen wir lösen? [Seite 12]
3.1.2 - 1.2.Eine Universalmaschine [Seite 14]
3.1.3 - 1.3.Viele Bänder bringen nicht viel mehr als zwei [Seite 21]
3.1.4 - 1.4.Nichtdeterminismus [Seite 26]
3.1.5 - 1.5.Beziehungen zwischen den Komplexitätsklassen [Seite 29]
3.1.6 - 1.6.Die Hierarchiesätze [Seite 35]
3.2 - 2.Sind Turingmaschinen ein realistisches Modell? [Seite 52]
3.2.1 - 2.1.Computerprogramme auf Turingmaschinen [Seite 53]
3.3 - 3.Effizienz - Warum P einfach besser als EXP ist [Seite 60]
3.3.1 - 3.1.Polynomialzeit - die Klasse P [Seite 60]
3.3.2 - 3.2.NP - the class of dashed hopes and idle dreams [Seite 66]
3.3.3 - 3.3.Die größte Frage der Informatik: Das P-NP-Problem [Seite 71]
4 - II.NP-Vollständigkeit [Seite 78]
4.1 - 4.Der Weg zur Vollständigkeit [Seite 80]
4.1.1 - 4.1.Reduzierbarkeit - aus Problem A wird Problem B [Seite 80]
4.1.2 - 4.2.Vollständigkeit - das (vorerst) letzte Wort [Seite 82]
4.1.3 - 4.3.Der Satz von Cook und Levin - der Anfang ist gemacht [Seite 84]
4.2 - 5.Ein Bausatz von NP-vollständigen Problemen [Seite 96]
4.2.1 - 5.1.Graphenprobleme [Seite 97]
4.2.2 - 5.2.Numerische Probleme [Seite 108]
4.2.3 - 5.3.Mahaney's Theorem [Seite 113]
4.2.4 - 5.4.Rezepte [Seite 115]
5 - III.Approximierbarkeit [Seite 127]
5.1 - 6.Optimierung - ein Lichtblick [Seite 128]
5.1.1 - 6.1.Optimierungsprobleme - bis wohin geht's? [Seite 129]
5.1.2 - 6.2.Approximationsalgorithmen [Seite 135]
5.2 - 7.Beispiele von Approximierbarkeit [Seite 142]
5.2.1 - 7.1.Das Problem des Handlungsreisenden MinTSP [Seite 143]
5.2.2 - 7.2.Das Partitionierungsproblem [Seite 151]
5.2.3 - 7.3.Das Erfüllbarkeitsproblem [Seite 153]
5.2.4 - 7.4.Optimierungsklassen [Seite 155]
6 - IV.Anhang [Seite 165]
6.1 - Graphen [Seite 166]
6.2 - Aussagenlogik [Seite 168]
6.3 - Klausuren [Seite 174]
6.4 - Abkürzungen [Seite 190]
6.5 - Liste von behandelten Problemen [Seite 192]
6.6 - Index [Seite 200]
