|
|
|
|
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.
|
|
|
