Art und Inhalt |
| Title: |
Algorithm, Logic, Complexity |
| Lecturer: |
Prof. Dr. Till Tantau |
| Classification: |
Master Informatik und Master Entrepreneurship in digitalen Technologien
Vertiefungsmodul 12 KP, 2. und/oder 3. Fachsemester
Lehrformen: Vorlesung, seminaristischer Unterricht, Übungen im SoSe18 sowie
ein Seminar wahlweise:
"Computing beyond Turing", SoSe18, Fr. 10-12h oder
"Komplexität und Parallelverarbeitung", WiSe18
Prüfung: mündlich am Ende des SoSe 2018 oder WiSe 2018, Termine nach individueller Vereinbarung |
| Content: |
- Maschinenmodelle
- Problemreduktion und Maschinensimulation
- Komplexitätsklassen und Hierarchien
- Descriptive Komplexität
- Logische Kalküle und Beweissysteme
- Schaltkreis- und Kommunikations-Komplexität
- Algorithmisches Lernen
- Algorithmische Spieltheorie
- Nichtstandardberechnungsmodelle, Quantum Computing
|
| Competence: |
- Fähigkeit, komplexe algorithmische Problemstellungen adäquat formal beschreiben zu können
- Tieferes Verständnis der Methoden algorithmischer Modellierung und Analyse
mit Hilfe von Maschinenmodellen
- Komplexitätsanalysen komplexer Problemstellungen durchführen können und die dazu eingesetzen
Techniken beherrschen
- Fähigkeit, algorithmische Probleme bezüglich ihrer Komplexität einzuordnen und
daraus Lösungsmethoden abzuleiten
- Bedeutung unterer Komplexitätsschranken verstehen und die Beweistechniken nachvollziehen können
|
| Literature: |
- R. Reischuk: Einführung in die Komplexitätstheorie - Teubner, 1990
- S. Arora, B. Barak: Computational Complexity - Cambridge UP 2009
- C. Papadimitriou: Computational Complexity - Addison-Wesley, 1994
- M. Kearns, V. Vazirani: An Introduction to Computational Learning Theory - MIT Press, 1997
- R. Downey, M. Fellows: Fundamentals of Parameterized Complexity, Springer 2013
- N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory, Cambridge UP, 2007
- D. Kozen: Theory of Computation - Springer, 2006
|
|
|
Lecture |
| Lecturer |
Prof. Dr. Till Tantau |
| Credits |
2 SWS |
| Hours |
|
Exercises |
| Assistent |
Max Bannach M.Sc. |
| Credits |
2 SWS |
| Hours |
|
