Komplexität —  3., erweiterte Auflage (Deutsch)

in eXamen.press ; 439-472
Theoretische Informatik
Springer Berlin Heidelberg , Berlin, Heidelberg; 2008

Auszug

In der Komplexitätstheorie stellt man sich die Frage nach Zeit- und Platzbedarf von Algorithmen. Gesucht sind mehr oder weniger genaue Abschätzungen, die in Abhängigkeit von der Größe der Eingabe vorhersagen, wieviel Ressourcen die Berechnung verbrauchen wird. Man kann Algorithmen mit ähnlichem Aufwand zu Klassen gruppieren, die sich bezüglich Laufzeit oder Platzbedarf ähnlich verhalten. Dabei kann man natürlich „ähnlich“ enger oder weiter fassen. Es gibt viele verschiedene Hierarchien von Aufwandsklassen. Zwei davon stellen wir in diesem Kapitel vor, zuerst die O-Notation, die eine recht engmaschige Einteilung von Algorithmen in Klassen liefert, und dann die Klassen P und NP, die weiter gefasst sind. P und NP sind keine komplette Hierarchie, es gibt Algorithmen, die in keine der beiden Klassen fallen. Aber diese zwei sind besonders interessant: In P sind Algorithmen, die sich vom Zeitbedarf her „gutartig“ verhalten, und in NP sind Algorithmen, von denen man vermutet, dass sie sich nicht gutartig verhalten können — genau bewiesen ist es bis heute nicht. Aber in vielen Fällen kann man auch für Algorithmen in NP einigermaßen brauchbare Näherungsverfahren angeben.

Wie erhalte ich diesen Titel?
Download
Kommerziell Vergütung an den Verlag: 24,95 € Grundgebühr: 4,00 € Gesamtpreis: 28,95 €
Akademisch Vergütung an den Verlag: 12,50 € Grundgebühr: 2,00 € Gesamtpreis: 14,50 €

Dokumentinformationen


Inhaltsverzeichnis E-Book

Das Inhaltsverzeichnis des E-Books wird automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Nachweisen der enthaltenen Aufsätze.

1
Einleitung
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
3
Begriffe und Notationen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
35
Eine kurze Einführung in die Aussagenlogik
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
53
Grammatiken und formale Sprachen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
63
Reguläre Sprachen und endliche Automaten
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
109
Kontextfreie Sprachen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
165
Turing-Maschinen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
195
Die Sprachklassen $$ \mathcal{L},\mathcal{L}_0 $$ und $$ \mathcal{L}_1 $$
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
215
Abschlußeigenschaften von Sprachklassen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
233
Registermaschinen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
253
Rekursive Funktionen
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
291
Unentscheidbare Probleme
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
327
Alternative Berechnungsmodelle
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008
439
Komplexität
Dr. Erk, Katrin / Prof. Dr. Priese, Lutz | 2008

Ähnliche Titel