|
Modulnummer:
| 12308
- Modul nicht mehr im Angebot ab WS 2013/14 |
| Modultitel: | Strukturelle Komplexitätstheorie I |
| |
Structural Complexity Theory I
|
| Einrichtung: |
Fakultät 1 - Mathematik, Naturwissenschaften und Informatik
|
| 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
- 12215: 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: | Keine Angabe - Angabe ab Wintersemester 2016/17 erforderlich! |
| Prüfungsleistung/en für Modulprüfung: | Prüfungsgespräch benotet |
| Bewertung der Modulprüfung: | Prüfungsleistung - benotet |
| Teilnehmerbeschränkung: | keine |
| Zuordnung zu Studiengängen: | - keine Zuordnung vorhanden
|
| Bemerkungen: | - Studiengang Informatik B. Sc. und Diplom: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 300).
- Studiengang Angewandte Mathematik M. Sc.: Wahlpflichtmodul im Anwendungsfach "Informatik".
|
| Veranstaltungen zum Modul: | Vorlesung: Strukturelle Komplexitätstheorie I
Übung zur Vorlesung |
| Veranstaltungen im aktuellen Semester: | - keine Zuordnung vorhanden
|
| Nachfolgemodul/e: |
Auslaufmodul ab: 20.04.2013
|
