Eine Grundlegung Der Average-Case Komplexitätstheorie [German]

By: Ingrid Biehl

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.

• Format: Paperback
• Language: German
• ISBN: 3815423015
• ISBN13: 9783815423011
• Release Date: August 1996
• Publisher: Vieweg+teubner Verlag
• Length: 156 Pages
• Weight: 0.58 lbs.
• Dimensions: 0.3" x 6.7" x 9.6"