Art und Inhalt |
| Titel: |
Algorithmik, Logik und Komplexität |
| Veranstalter: |
Prof. Dr. Till Tantau |
| Einordnung: |
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 |
| Lehrinhalte: |
- 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
|
| Qualifikationsziele: |
- 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
|
| Buchempfehlungen: |
- 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
|
Creditierung |
|
Vorlesung und seminar. Unterricht |
| Dozent |
Prof. Dr. Till Tantau |
| Umfang |
2 SWS |
| Termine |
Do 10:00 – 12:00, Seminarraum ITCS 2021
|
Übung |
| Assistent |
Max Bannach M.Sc. |
| Umfang |
2 SWS |
| Termine |
Mi 16:00 – 18:00, Seminarraum ITCS 2021
|
