Theoretische Informatik 2

Prof. Dr. Irma Lindt

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

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

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.