Art und Inhalt |
| Title: |
Algorithm, Logic, Complexity |
| Lecturer: |
Prof. Dr. Rüdiger Reischuk, Prof. Dr. Till Tantau |
| Classification: |
Master Informatik und Master Entrepreneurship in digitalen Technologien
Vertiefungsmodul 12 KP,
Lehrformen: Vorlesung, seminaristischer Unterricht und Seminar
Prüfung: mündlich, 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. Rüdiger Reischuk, , Prof. Dr. Till Tantau |
| Credits |
Teil 1: 4 KP SS 2018 oder SS 2019
Teil 2: 4 KP WS 2018/19
Teil 3: 4 KP Seminar WS 2018/19 |
| Hours |
|
