|
|
Beschreibung |
Die Komplexitätstheorie beschäftigt sich mit der Frage, welche Probleme mit beschränktem Aufwand lösbar sind: - Wie wird der Aufwand gemessen (Maschinenmodelle, Komplexitätsmaße)? - Was kann mit festgelegtem Aufwand gelöst werden? - Welche Eigenschaften haben alle Komplexitätsmaße (Komplexitätsklassen) gemeinsam (abstrakte Komplexitätstheorie)? - Wie verhalten sich gleichartige Komplexitätsklassen zueinander (Hierarchiesätze)? - Wie lassen sich verschiedene Komplexitätsmaße gegeneinander abschätzen (z.B. Band- und Zeitbedarf)? - Wie verhalten sich verschiedene Maschinenmodelle zueinander (z.B. P-NP-Problem)? Ausführlich gehen wir in dem Kurs auf deterministische und nichtdeterministische Maschinenmodelle ein. Die Komplexitätstheorie probabilistischer und paralleler Maschinen wird im weiterführenden Kurs 01687 behandelt. Für folgende Informatik-Studiengänge vorgesehen: B (über Katalog M), D, L, M, MC.
|
|
|