50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Modul: Computational Complexity


Art und Inhalt

Title: Modul: Computational Complexity
Lecturer: Prof. Dr. Rüdiger Reischuk
Classification: Master Entrepreneurship in digitalen Technologien, Vertiefungsmodul, 2. und/oder 3 Fachsemester
Master Informatik, Vertiefungsmodul, 2. und/oder 3. Fachsemester
Content:
  • Strukturelle und deskriptive Komplexitätstheorie
  • Kommunikationskomplexität
  • Schaltkreiskomplexität
  • Algorithmische Spieltheorie
  • Nichtstandardberechnungsmodelle
Competence:
  • 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
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

Lecture

Lecturer: Prof. Dr. Rüdiger Reischuk
Umfang: 2 SWS, ECTS-Credits: 4
Dates: Thu. 10:00h–12:00h, Seminarroom Cook & Karp

Exercise

Assistent: Max Bannach M.Sc.
Umfang: 2 SWS
Dates: Wed. 09:00 – 10:00, ITCS seminar room 2021