| Eine Grundlegung Der Average-Case Komplexitätstheorie 1996 Edition Contributor(s): Biehl, Ingrid (With) |
|
 |
ISBN: 3815423015 ISBN-13: 9783815423011 Publisher: Vieweg+teubner Verlag OUR PRICE: $47.49 Product Type: Paperback Language: German Published: August 1996 |
| Additional Information |
| BISAC Categories: - Technology & Engineering | Engineering (general) |
| Dewey: 620 |
| Series: Teubner Texte Zur Informatik |
| Physical Information: 0.34" H x 6.69" W x 9.61" (0.58 lbs) 156 pages |
| Descriptions, Reviews, Etc. |
| Publisher Description: 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. |