Proseminar: Algorithmen für NP-schwere Probleme

Wir beschäftigen uns mit der Technik der parametrisierten Algorithmen (fixed parameter tractability) bei denen NP-vollständige Probleme effizient gelöst werden sollen. Die Effizienz bezieht sich hier auf eine polynomielle Laufzeit hinsichtlich der Größe der Instanz wenn ein zusätzlicher Parameter der Instanz als konstant angenommen werden darf. Wir betrachten vor allem Graphenprobleme. Hier könnte der zusätzliche Parameter beispielsweise der Maximalgrad sein.

• Die Themen sind verteilt; die Homepage wurde dahingehend aktualisiert.

• Dieses Proseminar basiert auf und vertieft algorithmische Kenntnisse aus der Vorlesung „Theoretische Grundlagen der Informatik“.
• Die Kenntnis von Graphen, grundlegenden Algorithmentechniken und Komplexitätsklassen wird vorausgesetzt.

• Jeder Teilnehmer erhält ein Auszug aus einem Buch zur eigenhändigen Bearbeitung.
• Das Proseminar basiert auf dem Buch Parametrized Algorithms von Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk und Saurabh, erhältlich als E-Ressource in der KIT-Bibliothek: https://services.bibliothek.kit.edu/primo/start.php?recordid=KITSRC455177058
• Die Themen werden am ersten Termin, dem 29.4. bekanntgegeben und verteilt.
• Jeder Teilnehmer wird von einem Mitarbeiter betreut. Dieser Mitarbeiter steht für Fragen und Hinweise nach voriger Absprache zur Verfügung.
• Das Proseminar wird von Torsten Ueckerdt geleitet.

• Organisation: Torsten Ueckerdt
• Ort: Gebäude 50.34, Raum 301 (Am Fasanengarten 5, 76131 Karlsruhe).
• Zeit: Montags von 11:30 Uhr bis 13:00 Uhr.
• Sprache: Die Proseminarsprache ist Deutsch.

• Alle Plätze sind belegt.
• Teilnehmer melden sich bitte unter der Prüfungsnummer 7500173 („Proseminar Algorithmen für NP-schwere Probleme“) verbindlich für das Seminar an.

• Jeder Seminarteilnehmer hält einen fünfminütigen Kurzvortrag und einen 35-minütigen Vortrag im Proseminar und steht danach für Fragen der Teilnehmer zur Verfügung.
• Eine regelmäßige Teilnahme am Seminar wird vorausgesetzt.
• Spätestens zwei Wochen vor dem Vortragstermin ist das Vortragskonzept mit dem jeweiligen Betreuer zu besprechen.
• Ein vorläufiger Foliensatz ist eine Woche vor dem Vortrag beim jeweiligen Betreuer abzugeben.
• Die Seminarnote ergibt aus der Note für den Vortrag und Kurzvortrag, sowie der Beteiligung am Seminar.

Änderungen vorbehalten.

• Dr. Valentin Buchhold
• Dr. Matthias Wolf
• Dr. Lukas Barth
• Dr. Lars Gottesbüren
• Dr. Franziska Wegner
• Guido Brückner
• Dr. Sascha Gritzbach
• Dr. Marcel Radermacher
• Dr. Tamara Mchedlidze
• Torsten Ueckerdt
• Jonas Sauer
• Dr. Tobias Zündorf