50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Algorithm, Logic, Complexity


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