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.
Im Kurs 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" (01659) des Bachelorstudiengangs Informatik vermittelt werden. |
Aktuelles Angebot
Prüfungsinformation
| M.Sc. Praktische Informatik | |
|---|---|
| Art der Prüfungsleistung | bestandene benotete mündliche Modulprüfung |
| Voraussetzung | keine |
| Stellenwert der Note | 1/8 |
| Formale Voraussetzungen | keine |
| M.Sc. Informatik | |
| Art der Prüfungsleistung | bestandene benotete mündliche Modulprüfung |
| Voraussetzung | keine |
| Stellenwert der Note | 1/12 |
| Formale Voraussetzungen | keine |
| M.Sc. Mathematik | |
| Art der Prüfungsleistung | bestandene benotete mündliche Modulprüfung |
| Voraussetzung | keine |
| Stellenwert der Note | 1/12 |
| Formale Voraussetzungen | keine |
Download
- Seite Modulhandbuch M.Sc. Praktische Informatik
- Seite Modulhandbuch M.Sc. Informatik
- Seite Modulhandbuch M.Sc. Mathematik
- Leseprobe zu Kurs 01686: Komplexitätstheorie
Ansprechpersonen
André Schulz
mathinf.webteam
| 12.08.2021
