Allgemeines

Veranstaltungsnummer 040399
Titel Konzepte und Methoden der Theoretischen Informatik
Veranstalter Prof. Dr. Thomas Schwentick
Übungsleiter Prof. Dr. Thomas Schwentick
Klassifikation Wahlmodul in den Informatik-Bachelorstudiengängen
Semester Wintersemester 2020/21
SWS 3 (2V+1Ü)
Kreditpunkte 4
Ort und Zeit Webinar: Dienstags, 10-12 Uhr, inklusive Übung
Voraussetzungen GTI und Logik für Informatiker
Materialien Im Moodle Arbeitsraum

Die Veranstaltung findet rein virtuell statt.

Der Stoff der Vorlesung soll fast vollständig durch Videos abgedeckt werden. Am Dienstags-Termin wird es jeweils eine Vorschau auf das nächste Video und einen Rückblick auf das nächste Video geben. Außerdem werden dienstags die Übungsaufgaben besprochen. Bei großer Teilnehmerzahl wird es voraussichtlich einen weiteren Übungstermin geben.

Die Veranstaltung  gibt einen Einblick in Methoden und Denkweisen der Theoretischen Informatik, die über die kanonischen Inhalte des Moduls Grundbegriffe der Theoretischen Informatik hinausgehen. Voraussichtliche Themen  sind unter anderen:

  • Kolmogorovkomplexität
  • Kommunikationskomplexität
  • Unendliche Berechnungen und reguläre Omega-Sprachen
  • Alternierung
  • Logik und Berechnungen
  • Parametrisierte Komplexität
  • Kombinatorische Methoden
  • Bäume, Baumautomaten, und Baumweite
  • Model Checking
  • Beweissysteme und Komplexität
  • Derandomisierung
  • Term Rewriting