Нет обложки

Viele Probleme von großer praktischer Bedeutung erweisen sich als TVP-hart, das heißt, für sie sind keine effizienten Algorithmen bekannt. In der Praxis wird zu ihrer Lösung daher meist auf heuristische Verfahren zurückgegriffen, die zwar oftmals ausreichend gute Laufzeiten bzw. Lösungen liefern, aber leider meist schwer durchschaubar sind und keine garantierten Aussagen über ihre Leistungsgüte erlauben. Ein möglicher Ausweg aus dem "Dilemma der NF-Härte" kann in der Betrachtung von "parametrisierter Komplexität" bestehen: Bei vielen TVP-harten Problemen läßt sich die scheinbar inhärente "kombinatorische Explosion" auf einen kleinen Teil der Eingabe, einen sogenannten Parameter beschränken. Dies führt zu dem Konzept der para-metrisierten Algorithmen, welche eine sinnvolle Alternative zu heuristischen Methoden darstellen können. In der Vorlesung werden die Möglichkeiten und Grenzen parametrisierter Algorithmen aufgezeigt.

Скачать книгу бесплатно (ps.gz, 187 Kb)