Lehrveranstaltungen in der Informatik

Theoretische Informatik

Prof. Dr. H.W. Lang

zurück zurück

Inhalt

Vorlesung

  • Alphabet, Wort, Sprache, Grammatik
  • Regulärer Ausdruck, reguläre Sprache
  • Nichtdeterministischer endlicher Automat
  • Kontextfreie Sprachen und Stack-Automaten
  • Recursive-Descent-Parser / -Übersetzer
  • Turing-Maschine, Berechenbarkeit
  • Komplexitätstheorie

 

Übungen / Labor

In der ersten Semesterhälfte werden wöchentlich Übungsaufgaben gestellt, die korrigiert werden und in gemeinsamen Übungsstunden besprochen werden.

In der zweiten Semesterhälfte wird in Laborübungen ein Recursive-Descent-Übersetzer für arithmetische Ausdrücke gebaut.

Organisation

5. Semester, Vorlesung / Übung  4-std.

Sprache: deutsch

Präsenzstudium: 60 h, Eigenstudium: 90 h
Gesamtaufwand: 150 h

Leistungspunkte (credit points): 5

Medienformen: Tafel, Webseiten

Vorbedingungen: Orientierungsprüfung

Prüfung: PL (Mündliche Prüfung)

Lernziele

Sie kennen die wichtigsten theoretischen Konzepte aus dem Bereich der Formalen Sprachen und Automaten sowie der Komplexitätstheorie; Sie können auf Basis einer Grammatik einen Parser und Übersetzer bauen.

Literatur

A. Asteroth, C. Baier: Theoretische Informatik. Pearson Studium (2002)

U. Schöning: Theoretische Informatik kurz gefasst. BI-Wissenschaftsverlag (1992)

M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company (1996)