Modules

Prerequisites

Contents

• 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

Learning outcomes

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, • das Erkennen der Stärken und der Begrenzungen der wichtigsten Maschinenmodelle.

Assessment

Voraussetzung für die Modulabschlussprüfung: • erfolgreiche Bearbeitung von Übungsaufgaben (75% müssen erbracht werden) Modulabschlussprüfung: • Klausur, 180 min.

Remarks

• Studiengang Informatik B. Sc.: Pflichtmodul im Grundstudium. • Studiengang Informations- und Medientechnik M. Sc.: Wahlpflichtmodul im Komplex „Methodische Grundlagen". • Studiengang Mathematik B. Sc.: Wahlpflichtmodul im Anwendungsfach "Informatik". Modul wird nicht im WS 17/18 angeboten, stattdessen Nachfolgemodul 11787 Theoretische Informatik besuchen.