Theoretische Informatik

Die Studierenden sollen einen der Grundpfeiler der Informatik als Wissenschaft, nämlich die theoretische Modellierung von Berechenbarkeit durch verschiedene Algorithmenmodelle, verstehen lernen. Dies umfasst das Verstehen und Anwenden von Formalisierungen, das Umsetzen sowie sichere Umgehen mit mathematischen Arbeitsweisen in der theoretischen Informatik, und das Erkennen der Stärken und der Begrenzungen der wichtigsten Maschinenmodelle. Folgende Themen werden in der Vorlesung behandelt:

  • Reguläre Sprachen; deterministische und nicht-deterministische endliche Automaten; Minimalisierung; Abschlusseigenschaften regulärer Sprachen;
  • Push-Down Automaten und kontextfreie Grammatiken; Normalformen; algorithmische Fragestellungen zu kontextfreien Sprachen; Abschlusseigenschaften;
  • Turing-Maschine; Berechenbarkeit von Wortfunktionen; Entscheidungsprobleme; rekursive Aufzählbarkeit und Entscheidbarkeit; Halteproblem für Turing-Maschinen; Satz von Rice; Reduktion; allgemeine Grammatiken;
  • linear-beschränkte Turing-Maschinen; Chomsky-Hierarchie;
  • Simulation von Automaten durch Grammatiken und umgekehrt;
  • Primitiv-rekursive und μ–rekursive Funktionen

Zielgruppe

  • Informatik B.Sc. und Diplom Pflichtfach im Grundstudium
  • IMT M.Sc. PO 2008 Wahlpflichtfach
    Komplex Methodische Grundlagen
  • Mathematik B.Sc. und Diplom
  • Modul: 11787, 8 LP, 4 SWS VL, 2 SWS UE, 2 SWS Tutorium

Zu erbringende Leistung

  • 75% erfolgreich bearbeitete Übungsblätter (Vorleistung)
    Bei 13 Blätter müssen somit zum Beispiel 10 Blätter erfolgreich bearbeitet werden. Sind bis zum 1. Stichtag nicht 10 Blätter erfolgreich bearbeitet, so gelten die Übungsblätter als erstmalig nicht bestanden. Sie können dann bis zum 2. Stichtag noch nachbearbeitet werden. Sind bis dahin wiederum keine 10 Blätter erfolgreich bearbeitet, so gelten die Übungsblätter als wiederholt nicht bestanden. Es gibt dann eine letzte Frist bis zum 3. Stichtag. Sind bis dahin keine 10 Blätter erfolgreich bearbeitet, so sind die Übungsblätter endgültig nicht bestanden. Dann erfolgt entsprechend der Rahmenordnung eine Abmeldung vom Modul wegen nicht erbrachter Vorleistung.
  • Abschlussklausur: 
    Im zweiten Prüfungszeitraum.
    Es wird einen Termin zur Einsicht in die Klausur geben.
  • Benotung des Moduls:
    Die Note ergibt sich aus der Abschlussklausur.
  • Wiederholungsklausur
    Im zweiten Prüfungszeitraum des Sommersemesters.
    Bearbeitungszeit: 180 Minuten
    Der Stoff des gesamten Moduls ist Prüfungsstoff. An der Wiederholungsklausur kann nur teilgenommen werden, wenn schon ein Fehlversuch vorliegt. Es müssen genügend Übungsaufgaben erfolgreich bearbeitet worden sein.

Literatur

  • Alexander Asteroth, Christel Baier: Theoretische Informatik: eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen, Pearson Studium 2002.
  • Peter Bachmann: Grundlagen der Theoretischen Informatik, bookboon.com, 2015. Kostenloser Download hier
  • Katrin Erk, Lutz Priese: Theoretische Informatik - Eine umfassende Einführung, eXamen.press, 2008. [auf dem Campus online lesbar]
  • Dirk W. Hoffmann: Theoretische Informatik, Hanser, 2009.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, 3., aktualisierte Auflage, Pearson Studium 2011.
  • Juraj Hromkovic Theoretische Informatik Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie, Teubner, 2007. [auf dem Campus online lesbar]
  • Dexter C. Kozen: Automata and Computability, Springer 1997.
  • Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1981.
  • John E. Savage: Models of computation: Exploring the Power of Computing, Addison-Wesley, 1998. [elektronisch verfügbar auf der Webseite von Prof. John Savage, Computer Science Department, Brown University]
  • Michael Sipser: Introduction to the Theory of Computation, 3rd Edition, Cengage Learning 2013.