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 DiplomPflichtfach im Grundstudium
  • IMT M.Sc. PO 2008 Wahlplichtfach
    Komplex Methodische Grundlagen
  • Mathematik B.Sc. und Diplom
  • Modul: Link zu einer externen Seite 12-2-15, 10 KP4 SWS VL, 2 SWS UE, 2 SWS Tutorium

Zu erbringende Leistung

  • 75% erfolgreich bearbeitete Übungsblätter
    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, und das Modul wird mit 5.0 bewertet. Bei nichtbestandener Modulprüfung verfallen die Resultate zu den Übungsblätter. Sie müssen beim nächsten Besuch des Moduls neu bearbeitet werden, denn die Bearbeitung ist dann wiederum ein Teil der dann statt findenden Modulprüfung.
  • Zwischenklausur: 20% Punkteanteil
    Während der Vorlesungzeit vor dem Ende der Rücktrittfrist, also innerhalb der ersten 7 Wochen.
    Es wird einen Termin zur Einsicht in die Klausur geben.
  • Endklausur: 80% Punkteanteil
    Im zweiten Prüfungszeitraum.
    Es wird einen Termin zur Einsicht in die Klausur geben.
  • Benotung des gesamten Moduls: Die Punkte der beiden Klausuren werden (gewichtet) addiert und daraus ergibt sich dann die Prüfungsnote.
  • Wiederholungsklausur
    Im zweiten Prüfungszeitraum des Sommersemesters.
    Bearbeitungszeit: 180 Minuten
    Die Zwischenklausur geht nicht mehr in die Wiederholungsklausurnote ein. 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 Link zu einer externen Seite hier
  • Katrin Erk, Lutz Priese: Theoretische Informatik - Eine umfassende Einführung, eXamen.press, 2008. [Link zu einer externen Seite 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. [Link zu einer externen Seite 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. [Link zu einer externen Seite 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.