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
Lehrinhalte:
  • Strukturelle und deskriptive Komplexitätstheorie
  • Algorithmisches Lernen
  • Kommunikationskomplexität
  • Schaltkreiskomplexität
  • Probabilistische Methoden in der Algorithmik
  • Exakte Algorithmen
  • Multivariate Algorithmenanalyse
  • Endliche Modelltheorie
  • Algorithmische Spieltheorie
  • 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

Aufbau

Dieses Modul setzt sich aus 3 Teilen zusammen, die alle besucht werden müssen.
Modulteil A: Komplexitätstheorie
Modulteil B: Algorithmisches Lernen und Data Mining
Modulteil C: Seminar im Wintersemester 2015/2016