Komplexität von Algorithmen

Mathematik für Anwendungen Band 4

Autor	Arne Meier, Heribert Vollmer
Verlag	Lehmanns Media GmbH
Erscheinungsjahr	2015
Seitenanzahl	203 Seiten
ISBN	9783865417664
Format	PDF
Kopierschutz	Wasserzeichen/DRM
Geräte	PC/MAC/eReader/Tablet
Preis	12,99 EUR

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.

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.

Kaufen Sie hier:

Blick ins Buch

Inhaltsverzeichnis

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

Weitere E-Books zum Thema: Statistik - Algorhitmen

Wahrscheinlichkeitstheorie

Format: PDF

Dieses Lehrbuch bietet eine umfassende moderne Einführung in die wichtigsten Gebiete der Wahrscheinlichkeitstheorie und ihre maßtheoretischen Grundlagen. Themenschwerpunkte sind: Ma…

Fathom 2

Eine Einführung Format: PDF

Fathom 2 ist eine einzigartige dynamische Stochastik- und Datenanalysesoftware, die den besonderen Bedürfnissen der schulischen und universitären Lehre gerecht wird und die hier erstmals in deutscher…

Fathom 2

Eine Einführung Format: PDF

Fathom 2

Eine Einführung Format: PDF

Schwingungen mechanischer Antriebssysteme