12411 - Strukturelle Komplexitätstheorie II Modulübersicht
| Modulnummer: | 12411 - Modul nicht mehr im Angebot ab WS 2008/9 |
| Modultitel: | Strukturelle Komplexitätstheorie II |
| Structural Complexity Theory II | |
| Einrichtung: | Fakultät 1 - Mathematik, Naturwissenschaften und Informatik |
| Verantwortlich: |
|
| Lehr- und Prüfungssprache: | Deutsch |
| Dauer: | 1 Semester |
| Angebotsturnus: | sporadisch nach Ankündigung |
| Leistungspunkte: | 8 |
| Lernziele: | Ziel der Veranstaltung ist es, die Kompliziertheit von Problemen zu vergleichen und eine Ordnung unter den Klassen gleichschwerer Probleme zu finden. |
| Inhalte: | Dieser Teil des Zyklus befasst sich mit fortgeschritteneren Techniken (Selbstreduzierbarkeit, Kolmogorovkomplexität, Superkonzentratoren, Pebble Games) und prominenten Komplexitätsklassen wie P, NP, PSPACE, E, NE, EXP, NEXP, L, NL und deren Struktur (polynomial time isomorphism, sparse sets, Berman-Hartmanis-Vermutung). Es werden besondere Modelle und Maße betrachtet (Counting Klassen, Schaltwerke, Parallele Maschinen, Alternierende Maschinen, Orakelmaschinen, Interactiv Proof Systems, Zero-Knowlegde) und verschiedene Hierarchien (polynomielle Hierarchie, starke und schwache exponentielle Hierarchie, Alternationshierarchien, Orakelhierarchien, NC- und AC-Hierarchien). |
| Empfohlene Voraussetzungen: | keine |
| Zwingende Voraussetzungen: | keine |
| Lehrformen und Arbeitsumfang: |
|
| Unterrichtsmaterialien und Literaturhinweise: | John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley 1994. Trotz seines Alters (es stammt aus dem Jahr 1979) ein Bestseller wegen seines hervorragenden Stils - einer Mischung aus Anschaulichkeit und Präzision, die sehr gelungen ist. Für den Anfang ist dieses Buch zu empfehlen, auch wenn nicht sehr viel Komplexitätstheorie darin vorkommt. José L. Balcázar, Josep Díaz, Joaquim Gabarró: Structural Complexity I+II, Springer 1995. Dies ist in einem ähnlich guten Stil geschrieben, überdeckt aber größere Bereiche der Theorie. Es ist sehr empfehlenswert Wolfgang J. Paul: Komplexitätstheorie, Teubner 1978 Der Autor ist brillant, das Buch alt und schnell geschrieben, zum Teil fordernd, aber umso lohnender. Karl Rüdiger Reischuk: Einführung in die Komplexitätstheorie, Teubner 1990. Ein Buch, in dem man viel findet, sehr umfangreich an Stoff, wegen der starken Formalisierung nicht leicht zu lesen. Manchmal fehlen Beweise, die man auf Grund der Aufmachung erwartet, aber wer sich auf den Stil einläßt, kann viel lernen. Michael R. Garey, David S. Johnson: Computers and Intractability, Freeman 1979. Eine große Sammlung an NP-vollständigen Problemen mit einer sehr ausfühlichen und leicht geschriebenen Einführung in die Problematik. Ein in der Szene sehr populäres Buch. |
| 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: |
|
| Bemerkungen: | keine |
| Veranstaltungen zum Modul: | keine |
| Veranstaltungen im aktuellen Semester: |
|