50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Algorithm, Logic, Complexity


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