42 
Algorithmen und Komplexität 2:
Komplexitätstheorie (WS 2008)
Inhalt ![[^]](layout/up.png)
In der Komplexitätstheorie stehen die Frage nach den Grenzen der Berechenbarkeit und die Klassifizierung von Problemen bezüglich ihrer algorithmischen Komplexität im Mittelpunkt. Unter anderem werden anhand wichtiger Probleme zusätzlich zu den aus dem Grundstudium bekannten Komplexitätsklassen wie P und NP weitere Klassen wie PSPACE und co-NP eingeführt und untersucht. Es werden die folgenden Themen behandelt:
Inhaltliche Gliederung:
- Komplexitätsklassen, P vs. NP
- Reduktionen und Vollständigkeit
- Platzkomplexität
- Hierarchiesätze
- Relativierung
- Polynomialzeit-Hierarchie
- Probalistische Komplexitätsklassen
- Approximationsalgoritmen
Modulinformationen
- Modul II.2.1: Modelle und Algorithmen
- V4 + Ü2 (Kontaktzeit), nur zweite Semesterhälfte!
- 3 ECTS-Credits (Workload)
- Voraussetzungen: Einführung in Berechenbarkeit, Komplexität und formale Sprachen oder eine äquivalente Veranstaltung wird vorausgesetzt
- Kenntnisse: Studium der in der ersten Semesterhälfte stattfindenden Vorlesung Algorithmen und Komplexität 1: Grundlegende Algorithmen von Vorteil
Für weiterführende Informationen siehe auch den Eintrag im Modulhandbuch.
koaLA
Alle weiteren Informationen entnehmen Sie der koaktiven Lernumgebung koaLA. Melden Sie sich dort bitte zu der Veranstaltung Algorithmen und Komplexität II: Komplexitätstheorie (175508) an, um an der Vorlesung teilzunehmen.
