Einführung in die Komplexitätstheorie
Modulnummer: W08-05
Englischer Titel: Introduction to Complexity Theory
Leistungspunkte: 8
Lehrperson: Köbler
Empfohlene Vorkenntnisse
keine
Zwingende Voraussetzungen
keine
Inhalt
Die Komplexitätstheorie beschäftigt sich mit der Frage, welcher Aufwand, etwa an Rechenzeit oder Speicherplatz, erforderlich ist, um bestimmte algorithmische Probleme zu lösen. Dieses Modul ist eine Einführung in die Themen und Methoden der Komplexitätstheorie. Im Mittelpunkt stehen dabei die grundlegenden Zeit- und Platzkomplexitätsklassen.
Konkrete Inhalte des Moduls sind: Hierarchiesätze, NP-Vollständigkeit und die P vs NP-Frage, Orakelmodelle und die polynomielle Hierarchie, deskriptive Komplexität und der Satz von Fagin, Platzkomplexität und der Satz von Savitch, die Klassen L, NL und PSPACE.
Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung
- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben
Lehrveranstaltungen
Vorlesung: 4 SWS
Übung: 2 SWS
Forschungsorientiert
ja
Angeboten für Studiengänge
Monobachelor: ja
Kombinationsbachelor: ja
Infomit: ja
Angeboten im
Wintersemester: ja
Sommersemester: nein
Turnus
Alle zwei Jahre