50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Theoretische Informatik - CS2000


Veranstaltungsart und -inhalt

Titel Theoretische Informatik
Dozent Prof. Dr. Maciej Liskiewicz
Einordnung Bachelor-Studiengang Informatik (Pflicht) 3. Semester, Bachelor-Studiengang Medizinische Informatik (Pflicht) 3. Semester, Bachelor-Studiengang Medieninformatik Informatik (Pflicht) 3. Semester
Inhaltliche Voraussetzung: CS1000, CS1001
Inhalte
  • Formalisierung von Problemen mittels Sprachen
  • Formale Grammatiken
  • reguläre Sprachen, endliche Automaten
  • kontextfreie Sprachen, Kellerautomaten
  • sequentielle Berechnungsmodelle: Turing-Maschinen, Registermaschinen
  • sequentielle Komplexitätsklassen
  • Simulation, Reduktion, Vollständigkeit
  • Erfüllbarkeitsproblem, NP-Vollständigkeit
  • (Un-)Entscheidbarkeit und Aufzählbarkeit
  • Halteproblem und Church-Turing These
Qualifikationsziele:
  • Studierenden können die theoretischen Grundlagen der Syntax und der operationalen Semantik von Programmiersprachen selbst darstellen
  • Sie können Formalisierungen ineinander umwandeln, indem sie Sätze der Theoretischen Informatik anwenden
  • Sie können algorithmische Probleme nach ihrer Komplexität klassifizieren
  • Sie können algorithmische Probleme modellieren und mit geeigneten Werkzeugen lösen
  • Sie können die Möglichkeiten und Grenzen der Informatik beurteilen
Studienleistungen:
  • Übungs- bzw. Projektaufgaben
  • Klausur sowie Studienleistungen
Abschlussprüfung:
  • Klausur
Buchempfehlungen:
  • J. Hopcroft, J. Ullman, R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison Wesley 2001
  • Savage: Models of Computation, Addison Wesley 1998
  • Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit, Teubner 1992
  • C. Papadimitriou: Computational Complexity, Addison Wesley 1994
Creditierung
  • 8 KP

Vorlesung

Dozent Prof. Dr. Maciej Liskiewicz
Umfang 4 SWS
Termine Di 08:00 – 10:00, AM 1 , Do 10:00 – 12:00 Z 1/Z 2, ausser 8.2.18, dann im Z 3

Übung

Assistent Max Bannach M.Sc.
Umfang 2 SWS
Termine 6 Gruppen, Mo. 08-10h (Cook/Karp), 10-12h (Banach), 14-16h (ITCS2021, AM 4, Cook/Karp, Seminarraum Mathematik 1 (Hilbert)).