| |
| Arbeitsbereich: |
Theoretische Informatik / Formale Sprachen |
| Dozent(en): |
Jens Gramm, gramm (AT) informatik.uni-tueb... |
| Sprechstunde: |
nach Vereinbarung, Sand 13, Raum 011, Tel. 29-77568 |
| Zeit: |
Do 10-13 (Übungen 12-13) |
| Umfang: |
2+1 |
| Beginn: |
17.10.2002 |
| Ort: |
Raum A104, Sand 13 |
| Turnus: |
2-jährig |
| Pruefungsfach: |
Theoretische Informatik |
| Home page: |
http://www-fs.informatik.uni-tuebingen.de/ |
| Beschreibung: |
| Viele Probleme von großer praktischer Bedeutung erweisen sich
als NP-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 NP-Härte''
kann in der Betrachtung von ,,parameterisierter Komplexität''
bestehen: Bei vielen NP-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 parametrisierten Algorithmen, welche eine sinnvolle
Alternative zu heuristischen Methoden darstellen können.
In der Vorlesung werden einige Methoden zur Entwicklung effizienter parametrisierter Algorithmen vorgestellt und Anwendungen aus Bereichen wie Graphprobleme oder algorithmische Biologie beschrieben.
|
| Voraussetzungen: |
| Grundstudium |
| Literatur: |
-
R. G. Downey and M. R. Fellows. Parameterized
Complexity. Springer-Verlag, 1999.
-
R. Niedermeier. Invitation to Fixed-Parameter
Algorithms, September 2002. ( gzipped ps file);
(ca. 300 KB, 160 Seiten)
-
R. Niedermeier und J. Alber. Parametrisierte
Algorithmen. Vorlesungsskript, 2001 (mit kleinen
Änderungen Februar 2003).
( gzipped ps
file)
|
| Bemerkungen: |
Einstündige Übungen im Anschluss an die zweistündige Vorlesung.
|
|