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 Hausaufgaben und/oder erfolgreiche Bearbeitung von Hörsaaltestaten jeweils während eines Vorlesungstermins (Die Art der Voraussetzung wird zu Semesterbeginn bekannt gegeben.) Modulabschlussprüfung: • Klausur, 120 min.

Remarks

• Studiengang Informatik B.Sc.: Pflichtmodul • Studiengang Medizininformatik B.Sc.: Wahlpflichtmodul im Komplex „Informatik” • Studiengang Mathematik B.Sc.: Wahlpflichtmodul im Komplex „Anwendungen”, Bereich „Informatik” • Studiengang Wirtschaftsmathematik B.Sc.: Wahlpflichtmodul im Komplex „Anwendungen”, Bereich „Informatik” • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Analysis/Algebra/Kombinatorik” und im Komplex „Anwendungen”, Bereich „Informatik” • Studiengang Künstliche Intelligenz B.Sc.: Pflichtmodul im Komplex „Methodische Grundlagen” • Studiengang Künstliche Intelligenz Technologie B.Sc.: Wahlpflichtmodul im Komplex „Software-basierte Systeme”