Theoretische Informatik 2

Prof. Dr. Martin Eisemann

Kreditpunkte
5
Studiensemester
2
Sprache
deutsch
Kürzel
TI2
Voraussetzungen nach Prüfungsordnung
keine

Empfohlene Voraussetzungen

Einfache Kenntnisse der naiven Mengenlehre, wie sie in der Schule vermittelt und bei der mathematischen Begriffsbildung verwendet werden.

Lehrform/SWS

4 SWS: Vorlesung 2 SWS; Übung 2 SWS

Arbeitsaufwand

Gesamtaufwand 150h, davon - 36h Vorlesung - 36h Übung - 78h Selbstlernphase

Angestrebte Lernergebnisse

siehe Theoretische Informatik 1.

Inhalt

  • Reguläre (Typ-3) Sprachen: Endliche Automaten, Reguläre Ausdrücke; Typ3-Grammatiken, Zustandsübergangsdiagramme; Chomsky-Hierarchie
  • Modellierung sequentieller und paralleler (Ausgabe-) Prozesse: Endliche Maschinen / Automaten; Automatennetze, Petri-Netze, Zelluläre Automaten
  • Kontextfreie (Typ-2) Sprachen: Kontextfreie Grammatiken, Chomsky-Normalform; Kellerautomaten; Anwendungen (Ableitungs- und Syntaxbäume, Syntax von Programmiersprachen, Backus-Naur-Form)
  • Kontextsensitive (Typ-1) und rekursiv aufzählende (Typ-0) Sprachen: Grammatiken, Turingautomaten, Einführung in die Begriffe: Berechenbarkeit, Entscheidbarkeit und Komplexität

Studien-/Prüfungsleistungen

Schriftliche Prüfung.

Literatur

  • Hoffmann, D. (2011): Theoretische Informatik, 2. Auflage
  • Vossen, G., Witt K. (2004): Grundlagen der Theoretischen Informatik mit Anwendungen. 3. Aufl.  Vieweg & Sohn, Braunschweig.
  • Hedtstück, U. ( 2004 ): Einführung in die Theoretische Informatik. Oldenbourg, München.
  • Asteroth, A., Baier, C. (2002) Theoretische Informatik. Pearson Studium München
  • Hopcroft, J. E.  et al. (2002): Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, München.
  • Schöning, U. (1997): Theoretische Informatik - kurzgefaßt. 3. Aufl. Spektrum Akademischer Verlag, Heidelberg.