Seminar zur Effizienten Algorithmen

Dozent:

Seminar:

Seminar, 2 SWS, ECTS: 4, Fachgebiet: Theoretische und Praktische Informatik

Zeit und Ort:

n. V.

	Bemerkungen:	Das Seminar wird als Blockseminar am Ende des Wintersemesters stattfinden.
		Interessierte Studenten melden sich bitte bei Herrn Jansen unter: kj@informatik.uni-kiel.de

Vorbesprechung:	Mi, 24.10.2007, 10:30 - 11:00 Uhr, CAP4 - R.910
Vorträge:	voraussichtlich 20., 21. Februar 08, 10:00-12:30

Weitere Informationen sind bei Ralf Thöle, Florian Diedrich, oder Ulrich Michael Schwarz zu finden.

Inhalt:

Viele interessante Probleme, wie zum Beispiel Dominating Set (Gegeben einen Graph G=(V,E) und eine Zahl k, wähle eine Menge S von k Knoten, so dass jeder Knoten in G\S benachbart zu S ist), sind unter der Voraussetzung P!=NP nicht in polynomieller zeit zu lösen. Trotzdem stellt sich die Frage nach "guten" Algorithmen: ein Algorithmus mit Laufzeit O(2^k |V|²) ist sicherlich einem Algorithmus mit Laufzeit O(|V|^k) vorzuziehen. Thema dieses Seminars sind solche "fixed-parameter"-Algorithmen, bei denen die exponentiellen Terme der Laufzeit von den polynomiellen Termen getrennt sind. Es werden Themen aus dem Buch von Rolf Niedermeier vergeben.

Empfohlene Literatur:

Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006