50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Theoretische Informatik


Veranstaltungsart und -inhalt

Titel Theoretische Informatik
Dozent Prof. Reischuk
Einordnung Bachelor-Studiengang Informatik (Pflicht) 3. Semester
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
  • (Un-)Entscheidbarkeit und Aufzählbarkeit
  • Halteproblem und Church-Turing These
Qualifikationsziele:
  • 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
Leistungsnachweise erfolgen durch:
  • Übungsaufgaben (wöchentlich)
  • Projektaufgaben
  • aktive Teilnahme in Übungsgruppen
  • Klausuren, 90 Min. (voraus. 26.2.2008)
Diese Veranstaltung baut direkt auf folgenden Lehrmodulen auf, die erfolgreich abgeschlossen sein sollten:
  • Logik für Informatiker
  • Algorithmen und Datenstrukturen
Buchempfehlungen:
  • J. Hopcroft, J. Ullman, R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison Wesley 2001
  • R. Reischuk, Komplexitätstheorie, Band I, Teubner 1998
  • Savage: Models of Computation, Addison Wesley 1998
  • Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit, Teubner 1992
  • C. Papadimitriou: Computational Complexity, Addison Wesley 1994
  • E. Rich, Automata, Computability, and Complexity, Pearson 2008
Wiki Wiki zur Veranstaltung »Theoretische Informatik«

Vorlesung

Dozent Prof. Reischuk
Umfang 4 SWS, ECTS-Credits: 8
Termine Di 10:45 – 12:15, H1; Do 10:00 – 12:00 V2

Übung

Assistent Elberfeld
Umfang 2 SWS
Termine Mo 12:00 – 18:00, Seminarraum Informatik 2 + 3; Gruppe 1: 12:00-14:00, Gruppe 2: 14:00-16:00, Gruppe 3: 16:00-18:00