Vorlesung Theoretische Informatik 2, SS 03
Theoretische Informatik 2 (Informatik IV)

Veranstaltung: Vorlesung, SS 03
Professur: Komplexität und Algorithmen
Dozent: Prof. Dr. Torben Hagerup
Zeit und Ort: Di,Do 8-10 Uhr, Magnus Hörsaal
Übungen n.V.
Studienabschnitt: Grundstudium
Scheinerwerb: Bei bestandener Klausur
Voraussetzungen: Keine
Inhalt: Die Vorlesung behandelt die folgenden Themen:
  • Reguläre Sprachen: Reguläre Sprachen sind die einfachsten formalen Sprachen. Eigenschaften regulärer Sprachen und mit Ihnen in Verbindung stehende Probleme und Algorithmen werden besprochen.
  • Kontextfreie Sprachen: Die kontextfreien Sprachen sind weitaus ausdrucksstärker als die regulären Sprachen und bilden die Grundlage der üblichen Programmiersprachen. Ihre Eigenschaften und Algorithmen zu ihrer Erkennung werden besprochen.
  • Berechenbarkeit: Welche Funktionen lassen sich mit Hilfe eines stets terminierenden Programms berechnen?
  • NP-Vollständigkeit: Welche Funktionen lassen sich mit Hilfe eines effizienten Programms berechnen?
Literatur: M. Sipser, Introduction to the Theory of Computation, PWS Publishing, Boston, MA, 1997.

Ein Skript steht ab sofort (13.03.03) in der Institutsbibliothek zur Verfügung.

Übungsblätter: Übung 3: Postscript
Übung 4: Postscript
Übung 5: Postscript
Übung 6: Postscript
Übung 7: Postscript
Übung 8: Postscript
Übung 9: Postscript
Übung 10: Postscript
Übung 11: Postscript