Komplexitätstheorie: als Instrument zur Klassifizierung und Beurteilung von Problemen des Operations Research (Programm Angewandte Informatik)

by Stephan Zelewski

0 ratings • 0 reviews • 0 shelved
Book cover for Komplexitätstheorie

Bookhype may earn a small commission from qualifying purchases. Full disclosure.

Im Rahmen der Komplexitatstheorie wird versucht, die Schwierigkeit von Problemen durch den Ressourcenverzehr zu messen, der durch die Problem- loesung verursacht wird. Zur Untersuchung dieser Problemschwierigkeit ("Komplexitat") werden der Loesungsaufwand fur den schlechtest denkmoeg- lichen Fall (worst case-Analysen) oder der durchschnittlich zu erwartende Loesungsaufwand (average case-Analysen) betrachtet. Wesentl iche Analyse- konzepte der Komplexitatstheorie stellen Entscheidungsprobleme und Turing-Automaten dar. Auf ihrer Grundlage lassen sich Komplexitatsklassen von Problemen bilden. Diese Problemklassen und die ihnen zugehoerige Pro- blemschwierigkeit bilden ein Fundament, aus dem Empfehlungen fur erfolg- versprechende Loesungsalgorithmen abgeleitet werden koennen. Einen Schwerpunkt bildet die Klasse der NP-vollstandigen Probleme. Sie zeichnen sich dadurch aus, dass ihre Loesung einerseits besonders aufwendig ist. Andererseits besitzen sie fur die Bewaltigung zahlreicher praktisch inter- essanter Aufgaben aus dem Bereich des Operations Research eine heraus- ragende Rolle. Hierzu gehoeren beispielsweise die Planung von Transport- routen, das Festlegen von Standorten fur Auslieferungslager oder die inner- betriebliche Belegung von Maschinen mit Fertigungsauftragen. Es werden neuere Erkenntnisse der Komplexitatstheorie vorgestellt, welche die Klasse NP-vollstandiger Probleme intern differenzieren und uber sie hinausfuhren. Einschrankungen solcher Analysen werden an hand mehrfacher Validitats- probleme aufgezeigt.
  • ISBN10 3528036087
  • ISBN13 9783528036089
  • Publish Date 1 January 1989
  • Publish Status Active
  • Publish Country DE
  • Publisher Springer Fachmedien Wiesbaden
  • Imprint Vieweg+Teubner Verlag
  • Edition 1989 ed.
  • Format Paperback (US Trade)
  • Pages 162
  • Language German