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)

ECTS10
ArbeitsaufwandBearbeiten von Basistext und Leittext: 200 Stunden
Bearbeiten von Übungs- und Einsendeaufgaben: 50 Stunden
Studientag u. Prüfungsvorbereitung: 50 Stunden
Dauer des Modulsein Semester
Häufigkeit des Modulsin 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

Modul 63914 Komplexitätstheorie [VU]

Prüfungsinformation

M.Sc. Praktische Informatik
Art der Prüfungsleistungbenotete mündliche Prüfung (ca. 25 Minuten)
Voraussetzungkeine
Stellenwert der Note1/8
Formale Voraussetzungenkeine
M.Sc. Informatik
Art der Prüfungsleistungbenotete mündliche Prüfung (ca. 25 Minuten)
Voraussetzungkeine
Stellenwert der Note1/12
Formale Voraussetzungenkeine
M.Sc. Mathematik
Art der Prüfungsleistungbenotete mündliche Prüfung (ca. 25 Minuten)
Voraussetzungkeine
Stellenwert der Note1/12
Formale Voraussetzungenkeine

Download

Ansprechpersonen

mathinf.webteam | 10.05.2024