50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Algorithmik, Logik und Komplexität - CS4501


Art und Inhalt

Titel: Algorithmik, Logik und Komplexität
Veranstalter: Prof. Dr. Rüdiger Reischuk
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", SoSe19, Fr. 10-12h oder
  • "Komplexität und Parallelverarbeitung", WiSe19
  • Prüfung: mündlich am Ende des SoSe 2019 oder WiSe 2019, 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
    • 12 KP

    Vorlesung und seminar. Unterricht

    Dozent Prof. Dr. Rüdiger Reischuk
    Umfang 2 SWS
    Termine
    Die 08:00 – 10:00, Seminarraum ITCS 2021
    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