|
Modulnummer:
| 11449
|
| Modultitel: | Strukturelle Komplexitätstheorie |
| |
Structural Complexity Theory
|
| Einrichtung: |
Fakultät 1 - MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik
|
| Verantwortlich: | -
Prof. Dr. rer. nat. habil Meer, Klaus
|
| Lehr- und Prüfungssprache: | Deutsch |
| Dauer: | 1 Semester |
| Angebotsturnus: |
jedes Sommersemester gerader Jahre
|
| Leistungspunkte: |
8
|
| Lernziele: | Ziel des Moduls ist es, grundlegende Methoden zu erlernen mit deren Hilfe es möglich ist, Probleme gemäß der inhärenten Schwierigkeit bei ihrer algorithmischen Behandlung zu klassifizieren. Hierzu gehören: - das Kennenlernen sinnvoller Ressourcen zur Beurteilung der Komplexität eines Problems,
- das Verständnis für die grundlegende Struktur von Komplexitätsaussagen,
- das Beherrschen mathematischer Methoden zur Analyse und Klassifikation von Problemen,
- die selbständige Umsetzung der erlernten Methoden, um die Komplexität von Problemen richtig einzuschätzen.
|
| Inhalte: | Die Vorlesung stellt eine Einführung in die Strukturelle Komplexität dar. Die dabei zentralen Fragen sind die folgenden:
- Wie misst man sinnvoll den Aufwand, der nötig ist, ein Problem algorithmisch zu lösen?
- Welche Ressourcen spielen dabei eine Rolle?
- Wie lassen sich Probleme hinsichtlich dieser Ressourcen sinnvoll vergleichen und klassifizieren?
- Was sind inhärente Hindernisse, die der Existenz beliebig guter Lösungen gewisser Probleme entgegen stehen?
Im Einzelnen werden u. a. folgende Gesichtspunke behandelt:
- Turingmaschine, Zeit- und Platzverbrauch einer Rechnung
- Komplexitätsklassen bzgl. Zeit- oder Platzbedarf
- Hierarchiesätze
- die Klassen P und NP als Formalisierung effizient lösbarer und effizient verifizierbarer Probleme
- NP-Vollständigkeit, Reduktion
- Satz von Cook: NP-Vollständigkeit von SAT
- weitere Bsp. NP-vollständiger Probleme
- Randomisierte Algorithmen und die Klassen ZPP, RP und BPP
- Komplexitätsklassen innerhalb von P: Paralleles Rechnen und NC
- Komplexitätsklassen jenseits von NP: die Polynomhierarchie, PSPACE und NSPACE, Zählklassen
- Ausblicke auf andere Zugänge zu Komplexität
|
| Empfohlene Voraussetzungen: | Die Kenntnis des Modells der Turingmaschine sowie der Begriffe Entscheidungsproblem und Berechenbarkeit wird empfohlen. Zu Beginn der Vorlesung werden diese kurz wiederholt.
Zum Beispiel Kenntnis des Inhalts von Modul
- 11787 : Theoretische Informatik
|
| Zwingende Voraussetzungen: | keine |
| Lehrformen und Arbeitsumfang: | -
Vorlesung
/ 4 SWS
-
Übung
/ 2 SWS
-
Selbststudium
/ 150 Stunden
|
| Unterrichtsmaterialien und Literaturhinweise: | - M. R. Garey, D. S. Johnson: Computers and Intractability, Freeman 1979
- C. H. Papadimitriou: Computational Complexity, Addison & Wesley 1994
- I. Wegener: Komplexitätstheorie, Springer 2003
- J. L. Balcazar, J. Diaz, J. Gabarro: Structural Complexity I + II, Springer 1995
- S. Arora, B. Barak: Computational Complexity, Cambridge University Press 2009
|
| Modulprüfung: | Modulabschlussprüfung (MAP) |
| Prüfungsleistung/en für Modulprüfung: | - mündliche Prüfung, 30-45 Minuten
|
| Bewertung der Modulprüfung: | Prüfungsleistung - benotet |
| Teilnehmerbeschränkung: | keine |
| Zuordnung zu Studiengängen: | -
Master (universitär) /
Angewandte Mathematik /
PO 2008
-
Master (universitär) /
Angewandte Mathematik /
PO 2019
-
Master (universitär) /
Artificial Intelligence /
PO 2022
-
Master (universitär) /
Informatik /
PO 2008
- 2. SÄ 2017
|
| Bemerkungen: | - Studiengang Informatik M.Sc.: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 400)
- Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Anwendungen“, Bereich „Informatik“
|
| Veranstaltungen zum Modul: | Vorlesung: Strukturelle Komplexitätstheorie
Übung zur Vorlesung |
| Veranstaltungen im aktuellen Semester: | |
