Modul 63914 Komplexitätstheorie
Modulinformationen
In der Komplexitätstheorie beschäftigt man sich damit, welche Probleme mit eingeschränkten Ressourcen (z.B. Zeit oder Speicherplatz) berechnet werden können. Man fasst Probleme dabei zu Komplexitätsklassen zusammen und untersucht deren Beziehung untereinander.
In der Lehrveranstaltung werden die Grundlagen der Komplexitätstheorie aus einer algorithmischen Perspektive vermittelt. Als Basistext wird das Buch von Ingo Wegener "Komplexitätstheorie: Grenzen der Effizienz von Algorithmen" verwendet. Der Leittext wird ergänzt mit Übungsaufgaben und Anmerkungen.
U.a. werden folgende Themen behandelt:
- grundlegende Komplexitätsklassen
- NP-Vollständigkeit
- Interaktive Beweissysteme
- probabilistische Komplexitätsklassen
- Approximation
Vertiefungsrichtung
Angewandte Algebra und Diskrete Mathematik (AD)
ECTS | 10 |
---|---|
Arbeitsaufwand | Bearbeiten von Basistext und Leittext: 200 Stunden Bearbeiten von Übungs- und Einsendeaufgaben: 50 Stunden Studientag u. Prüfungsvorbereitung: 50 Stunden |
Dauer des Moduls | ein Semester |
Häufigkeit des Moduls | in jedem Wintersemester |
Anmerkung | Der Basistext muss vor Semesterbeginn beschafft werden. Basistext: Ingo Wegener: Komplexitätstheorie: Grenzen der Effizienz von Algorithmen, Springer, 2003. Nicht zusammen mit dem nicht mehr angebotenen Modul "Grundzüge der Komplexitätstheorie" nutzbar. |
Inhaltliche Voraussetzung | Grundlagen der theoretischen Informatik, wie sie z.B. im Modul 63912 "Grundlagen der Theoretischen Informatik" des Bachelorstudiengangs Informatik vermittelt werden. |
Aktuelles Angebot
Prüfungsinformation
M.Sc. Praktische Informatik | |
---|---|
Art der Prüfungsleistung | benotete mündliche Prüfung (ca. 25 Minuten) |
Voraussetzung | keine |
Stellenwert der Note | 1/8 |
Formale Voraussetzungen | keine |
M.Sc. Mathematik | |
Art der Prüfungsleistung | benotete mündliche Prüfung (ca. 25 Minuten) |
Voraussetzung | keine |
Stellenwert der Note | 1/12 |
Formale Voraussetzungen | keine |
M.Sc. Informatik | |
Art der Prüfungsleistung | benotete mündliche Prüfung (ca. 25 Minuten) |
Voraussetzung | keine |
Stellenwert der Note | 1/12 |
Formale Voraussetzungen | keine |
Download
- Seite Modulhandbuch M.Sc. Praktische Informatik
- Seite Modulhandbuch M.Sc. Mathematik
- Seite Modulhandbuch M.Sc. Informatik
- Leseprobe: Komplexitätstheorie
Ansprechpersonen
Prof. Dr. André Schulz
mathinf.webteam
| 10.05.2024