50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Modulteil Komplexitätstheorie - CS4501A


Art und Inhalt

Titel: Modulteil Komplexitätstheorie
Veranstalter: Prof. Dr. Rüdiger Reischuk
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
  • Kommunikationskomplexität
  • Schaltkreiskomplexität
  • Algorithmische Spieltheorie
  • Nichtstandardberechnungsmodelle
Kompetenzen:
  • 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

Vorlesung

Veranstalter: Prof. Dr. Rüdiger Reischuk
Umfang: 2 SWS, ECTS-Credits: 4
Termine: Do. 10:00–12:00 Uhr, Seminarraum Cook & Karp

Übung

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