Classification and Contents |
|
| Title | Deskriptive Komplexitätstheorie |
| Lecturer | Prof. Tantau, Elberfeld |
| Einordnung |
Hauptseminar Diplom-Studiengang ab 5. Semester Master-Studiengang ab 1. Semester |
| Contents |
In der Komplexitätstheorie untersucht man,
welche Probleme sich mit bestimmten
ressourcenbeschränkten Maschinenmodellen lösen
lassen. Zum Beispiel lässt sich die Frage, ob es
einen Weg zwischen zwei Knoten in einem Graphen
gibt, durch eine Turingmaschine mit
logarithmischem Platzaufwand beantworten.
Die Maschine entscheidet, ob der Graph eine
bestimmte Eigenschaft besitzt. In der
deskriptiven Komplexitätstheorie wird untersucht
mit welchen logischen Sprachen sich solche
Eigenschaften beschreiben lassen. Das obige
Wegeproblem lässt sich zum Beispiel nicht durch
eine prädikatenlogische Formel erster Stufe
(First-Order Logic) beschreiben. Durch eine etwas
mächtigere Logik wird eine Beschreibung des
Wegeproblems aber möglich. In dem Seminar werden anhand von Vorträgen und Ausarbeitungen die Grundlagen der deskriptiven Komplexitätstheorie besprochen, wichtige Resultate vorgestellt und Zusammenhänge zu sequentiellen und parallelen Maschinenmodellen hergestellt. |
| Hours | Thur. 16:00 – 18:00, ITCS seminar room 2021 |
| Wiki | Wiki zum Seminar »Deskriptive Komplexitätstheorie« |
