
Komplexität von Algorithmen
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Persons
Arne Meier ist Lecturer am Institut für Theoretische Informatik an der Leibniz Universität Hannover.
Content
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]
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.