Modulcode:	Inf-MS-TIAktF
Englische Bezeichnung:	Master Seminar - Theoretical Computer Science (New Challenges)
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS16/17 SS17 SS18 SS19 WS19/20 SS20 WS20/21 SS21 WS21/22 SS22 WS22/23 SS23 WS23/24 SS24 WS24/25 SS25)
Präsenzzeiten:	2S
ECTS:	5
Workload:	30 Std. Seminarteilnahme, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	MSc-Inf-Sem (MSc Inf (21)) Sem (MSc Inf (15))
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Gegenstand des Seminars sind exakte und approximative Algorithmen für kombinatorische Optimierungsprobleme sowie Komplexitätstheorie.

Lernziele:

Die Studierenden können komplexe Sachverhalte anhand der kompakten Darstellung, wie sie in fortgeschrittenen Fachbüchern und Facharbeiten üblich ist, eigenständig verstehen und in verständlicher Form schriftlich und im Rahmen eine Präsentation aufbereiten.

Lehrinhalte:

Gegenstand des Seminars sind neben exakten Algorithmen approximative Algorithmen, also solche, die zugunsten einer besseren Laufzeit statt einer optimalen Lösung nur eine "gute" Lösung berechnen. Es werden Techniken des Designs und der Analyse solcher Algorithmen behandelt. Außerdem wird betrachtet, wie sich die untere Schranken für Approximierbarkeit und Laufzeit untersuchen lassen.

Weitere Voraussetzungen:

Bachelorstudium 1.-4. Semester; Erfahrung im Bereich der effizienten und/oder approximativen Algorithmen, etwa durch Besuch der entsprechenden Vorlesung, ist wünschentswert, aber nicht zwingend erforderlich.

Prüfungsleistung:

Die Note setzt sich aus 3 Teilnoten zusammen.

• Schriftliche Ausarbeitung: Gerüst, Entwurf, Endversion (10-12 Seiten)
• Gutachten über Arbeiten anderer Teilnehmer
• Vortrag: Material und Durchführung (60 Minuten inklusive Fragen)

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Wird von Semester zu Semester bekanntgegeben

Verweise:

Kommentar: