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, Prof. Dr. Maciej Liskiewicz
Einordnung: Master Entrepreneurship in digitalen Technologien, Vertiefungsmodul, 2. und/oder 3 Fachsemester
Master Informatik, Vertiefungsmodul, 2. und/oder 3. Fachsemester

Dieses Modul besteht aus Vorlesung und Seminar:

Seminar 2 SWS wahlweise:

  • im Sommersemeser 2016 "Computing beyond Turing", Fr. 10-12h
  • oder
  • im Wintersemester 2016 Oberseminar Theoretische Informatik
  • Prüfung mündlich Ende des SoSe 2016 oder WS 2016, Termine nach individueller Vereinbarung

    Lehrinhalte:
    • Problemreduktion und Maschinensimulation
    • Komplexitätsklassen-Hierarchie
    • Beweissysteme
    • Schaltkreiskomplexität
    • Kommunikationskomplexität
    • Algorithmisches Lernen
    • Algorithmische Spieletheorie
    • Nichtstandardberechnungsmodelle
    Qualifikationsziele:
    • Tieferes Verständnis der Konzepte und Methoden des Algorithmenentwurfs und der Komplexitätsanalyse
    • Fähigkeit, algorithmische Probleme bezüglich ihrer Komplexität einzuordnen und daraus Lösungsmethoden abzuleiten
    • Fähigkeit, komplexe Problemstellungen adäquat formal modellieren zu können
    • Bedeutung von unteren Komplexitätsschranken für reale Probleme verstehen
    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.J. Kearns, V.V. Vazirani: An Introduction to Computational Learning Theory - MIT Press, 1997
    • T.M. Mitchell: Machine Learning - WCB McGraw-Hill, 1997
    • D. Kozen: Theory of Computation - Springer, 2006

    Vorlesung

    Dozent Prof. Dr. Rüdiger Reischuk, , Prof. Dr. Maciej Liskiewicz
    Umfang 4 SWS
    Termine Di 14:00 – 16:00, Seminarraum ITCS 2021, Do. 10:00 – 12:00, Seminarraum Cook/Karp

    Übung

    Assistent Max Bannach M.Sc.
    Umfang 2 SWS
    Termine Di 10:30 – 10:00, Seminarraum ITCS 2021