50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Theoretical Computer Science


Classification and Contents

Title Theoretical Computer Science
Lecturer Prof. Dr. Maciej Liskiewicz
Classification Bachelor-Studiengang Informatik (Pflicht) 3. Semester
Contents
  • 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
  • (Un-)Entscheidbarkeit und Aufzählbarkeit
  • Halteproblem und Church-Turing These
Qualification purpose:
  • theoretische Grundlagen der Syntax und der operationalen Semantik von Programmiersprachen kennen
  • Möglichkeiten und Grenzen der Informatik verstehen
  • algorithmische Probleme modellieren und mit geeigneten Werkzeugen lösen können
  • algorithmische Probleme nach ihrer Komplexität klassifizieren können
Studienleistungen:
  • Übungs- und Programmieraufgaben, Protokoll, aktive Übungsgruppenteilnahme
Abschlussprüfung:
  • Klausur
Diese Veranstaltung baut direkt auf folgenden Lehrmodulen auf, die erfolgreich abgeschlossen sein sollten:
  • Einführung in die Logik
  • Algorithmen und Datenstrukturen
Literature:
  • 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

Lecture

Lecturer Prof. Dr. Maciej Liskiewicz
Credits 4 SWS, ECTS-Credits: 8
Hours Tue 10:00 – 12:00, AM 1; Thu 10:00 – 12:00 H 1

Exercises

Assistant Oliver Witt M.Sc.
Credits 2 SWS
Hours 4 groups, Mon 10-12h, 14-16h, AM S 1, AM 4, Cook/Karp, Seminarraum Mathematik 1 (Hilbert), Seminarraum Mathematik 2 (Banach).