Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben:
Sie können beurteilen, mit welchem Aufwand algorithmische Probleme auf einer Maschine, unabhängig vom konkreten Computer, gelöst werden können.
Sie verstehen praktische Grenzen der algorithmischen Lösbarkeit von Problemen und können die Komplexität spezieller Probleme einschätzen und klassifizieren.
Sie sind in der Lage, mit Reduktions- und Simulationstechniken komplexitätstheoretische Untersuchungen anzustellen.
Sie verstehen abstrakte Zusammenhänge und können selbstständig mit grundlegenden mathematische Methoden umgehen.
Sie können verschiedene Problemlösestrategien und Beweisverfahren anwenden.
Modulinhalte
Das Bestreben der Komplexitätstheorie ist es, grundlegende Aussagen zu treffen, mit welchem Zeit- und Speicherplatzaufwand algorithmische Prozesse auf einer Maschine gelöst werden können. Als Grundlage für geräteunabhängige Untersuchungen dient die Turingmaschine, mit der Komplexitätsabschätzungen mathematisch exakt behandelt werden können. Konsequenzen der Resultate für den praktischen Rechnereinsatz erhält man über den Zwischenschritt der Registermaschine.
In dem Modul wird untersucht, mit welchem Aufwand ein nichtdeterministscher Algorithmus auf einer deterministischen Maschine simuliert werden kann. Bewiesen werden Enthaltenseinsbeziehungen zwischen verschiedenen Komplexitätsklassen.
Zusammenfassend betrachtet das Modul die Inhalte
Komplexitätsmaße für Turing- und Registermaschinen Raum- und Zeitkomplexität sowie bedeutende Komplexitätsklassen Deterministische und nichtdeterministische Berechnungen Hierarchien und Lücken bei Komplexitätsklassen Reduzierbarkeit und vollständige Probleme Das P-NP-Problem
Lehrveranstaltungsformen
Vorlesung (3 SWS)
Übung (1 SWS)
Kursus
Unterrichtsprachen
Deutsch, Englisch
Dauer in Semestern
1 Semester Semester
Angebotsrhythmus Modul
beginnend im Wintersemester im Wechsel mit
Aufnahmekapazität Modul
unbegrenzt
Prüfungsebene
Credit-Points
5 CP
Modulabschlussnote
LV1: %; LV2: %; LV3: %.
Faktor der Modulnote für die Endnote des Studiengangs
1
Hinweise
Vertiefungsmodul für die Vertiefungsrichtung "Algorithmen und Theoretische Informatik" im Masterstudiengang Informatik ab Version 2013.
Modulveranstaltung
Lehrveranstaltungsform
Veranstaltungstitel
SWS
Workload Präsenz
Workload Vor- / Nachbereitung
Workload selbstgestaltete Arbeit
Workload Prüfung incl. Vorbereitung
Workload Summe
LV 1
Vorlesung
Vorlesung
3
0
LV 2
Übung
Übung
1
0
LV 3
Kursus
Bearbeitung der Übungsaufgaben
0
Workload modulbezogen
150
150
Workload Modul insgesamt
150
Prüfung
Prüfungsvorleistung
Prüfungsform
LV 1
LV 2
LV 3
Gesamtmodul
mindestens 50% der Punkte aus den Übungsblättern zur Komplexitätstheorie