Bachelor Master Dozenten

Medieninformatik an der TH Köln

Modulbeschreibungen, Prüfer:innenlisten und mehr :)

Theoretische Informatik 2

Bearbeiten
Modulverantwortlich
Prof. Dr. Florian Niebling
Kürzel
TI2
Studiensemester
2
Sprache
deutsch
Kreditpunkte
5
Studienleistungen
Schriftliche Prüfung: Prüfer:in Prof. Dr. Florian Niebling // Zweitprüfer bzw. Beisitzer Prof. Dr. Irma Lindt // Prüfungstermin: Sommersemester Woche 2, Ende September

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.