Lehrveranstaltungen in der Informatik

Theoretische Informatik

Dr. P. Sadeghi

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 und -Ü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.

Die Programmiersprache ist Java oder Python.

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, Projektor

Vorbedingungen: Orientierungsprüfung

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

Lernvoraussetzungen

Sie sind mit den grundlegenden mathematischen Konzepten Menge, Relation, Abbildung, Folge, Graph vertraut und können damit umgehen. Sie können objektorientiert programmieren.

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)

R.H. Güting, M. Erwig: Übersetzerbau. Springer (1999)

J. Hromkovic: Theoretische Informatik. 2. Auflage, Teubner (2004)

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

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