Willkommen, schön sind Sie da!
Logo Ex Libris

Eine Grundlegung der Average-Case Komplexitätstheorie

  • Kartonierter Einband
  • 156 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
Dieses Buch hat die sogenannte average-case Komplexitätstheorie zum Gegenstand, ein vergleichsweise junges Gebiet der strukt... Weiterlesen
20%
70.00 CHF 56.00
Sie sparen CHF 14.00
Print on Demand - Auslieferung erfolgt in der Regel innert 4 bis 6 Wochen.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

Klappentext

Dieses Buch hat die sogenannte average-case Komplexitätstheorie zum Gegenstand, ein vergleichsweise junges Gebiet der strukturellen Komplexitätstheorie. Die "klassische" strukturelle Komplexitätstheorie untersucht, wie schwierig ein al­ gorithmisches Problem im schwierigsten Fall (worst-case) ist. Ein solches algorith­ misches Problem ist zum Beispiel das Traveling Salesman Problem: gegeben eine Menge von Städten mit einer Entfernungstabelle, man suche die kürzeste Route, die einen Handlungsreisenden alle Städte genau einmal besuchen läßt und ihn an seinen Ausgangsort zurückbringt. Jede konkrete Entfernungstabelle ist eine soge­ nannte Probleminstanz des obigen, allgemeinen Problems. Vom Traveling Salesman Problem wird angenommen, daß es im worst-case sehr schwierig ist, d. h. , jeder Algo­ rithmus, der zu jeder Probleminstanz eine Lösung findet, benötigt für einige "schwie­ rige" Eingaben eine sehr lange Laufzeit. In der Praxis beobachtet man aber häufig bei derartigen worst-case schwierigen Problemen, daß man die tatsächlich auftreten­ den Probleminstanzen in sehr kurzer Zeit lösen kann, daß also das Auftreten von schwierigen Probleminstanzen sehr unwahrscheinlich ist. Unterliegt die Eingabe ei­ ner Wahrscheinlichkeitsverteilung, so ist es daher wichtig zu wissen, wie die mittlere Laufzeit eines Algorithmus zum Lösen des Problems aussieht. Man interessiert sich somit dafür, wie aufwendig die Problemlösung im Mittel ist, d. h. zum Beispiel welche mittlere Laufzeit ein optimaler Lösungsalgorithmus hat. Die average-case Komple­ xitätstheorie beschäftigt sich mit der Frage nach dem mittleren Aufwand, der zum Lösen einer Probleminstanz notwendig ist, wenn die Probleminstanzen einer gege­ benen Verteilung unterliegen.



Inhalt
1 Einleitung.- 2 Starke und schwache average-case Modelle.- 3 Klassen von Dichten und Sprachklassen.- 4 Komplexitätstheorie.- 5 Vollständigkeitstheorie.

Produktinformationen

Titel: Eine Grundlegung der Average-Case Komplexitätstheorie
Autor:
Ghostwriter:
EAN: 9783815423011
ISBN: 978-3-8154-2301-1
Format: Kartonierter Einband
Hersteller: Vieweg & Teubner
Herausgeber: Vieweg+Teubner Verlag
Genre: Sonstiges
Anzahl Seiten: 156
Gewicht: 289g
Größe: H244mm x B170mm x T8mm
Jahr: 1996
Untertitel: Deutsch
Auflage: 1996

Weitere Produkte aus der Reihe "Teubner Texte zur Informatik"