|
Modulnummer:
| 12510
- Modul nicht mehr im Angebot ab WS 2008/9 |
| Modultitel: | Abstrakte Komplexitätstheorie |
| |
Abstract Complexity Theory
|
| Einrichtung: |
Fakultät 1 - Mathematik, Naturwissenschaften und Informatik
|
| Verantwortlich: | -
Prof. Dr.rer.nat.habil von Braunmühl, Burchard
|
| Lehr- und Prüfungssprache: | Deutsch |
| Dauer: | 1 Semester |
| Angebotsturnus: |
sporadisch nach Ankündigung
|
| Leistungspunkte: |
8
|
| Lernziele: | Einblick in die Grundlagen der Komplexitätstheorie. Die abstrakte Komplexitätstheorie löst sich ganz von den konkreten Aufwandsmaßen und Modellen. Sie definiert axiomatisch, welche Eigenschaften ein Maß haben soll, und leitet daraus Sätze ab, die für alle (vernünftigen) Maße gelten. |
| Inhalte: | Gödelnummerierung, Blumsches Maß, Speed-up-Theorem, Gap-Theorem, Union-Theorem, Naming-Theorem. |
| Empfohlene Voraussetzungen: | keine |
| Zwingende Voraussetzungen: | keine |
| Lehrformen und Arbeitsumfang: | -
Vorlesung
/ 4 SWS
-
Übung
/ 2 SWS
|
| Unterrichtsmaterialien und Literaturhinweise: | Manuel Blum: A Machine-Independent Theory of the Complexity of Recursive Functions. J. ACM 14(2): 322-336 (1967) |
| 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: | keine |
| Veranstaltungen zum Modul: | keine |
| Veranstaltungen im aktuellen Semester: | - keine Zuordnung vorhanden
|
