11787 - Theoretische Informatik Modulübersicht

Modulnummer: 11787
Modultitel:Theoretische Informatik
  Theoretical Computer Science
Einrichtung: Fakultät 1 - MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Verantwortlich:
  • Prof. Dr. rer. nat. habil Meer, Klaus
Lehr- und Prüfungssprache:Deutsch
Dauer:1 Semester
Angebotsturnus: jedes Wintersemester
Leistungspunkte: 8
Lernziele: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.
Inhalte:
  • 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
Empfohlene Voraussetzungen:Kenntnis des Stoffes der Module
  • 11112: Mathematik IT-1 (Diskrete Mathematik)
  • 12101: Algorithmieren und Programmieren bzw 11756 : Algorithmen und Datenstrukturen
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 4 SWS
  • Selbststudium / 120 Stunden
Unterrichtsmaterialien und Literaturhinweise:
  • Hopcroft, Motwani, Ullmann: Introduction to Automata Theory, Languages and Computation, Addison & Wesley
  • Lewis, Papadimitriou: Elements of the Theory of Computation, Prentice Hall
  • Savage: Models of Computation, Addison & Wesley
Modulprüfung:Voraussetzung + Modulabschlussprüfung (MAP)
Prüfungsleistung/en für Modulprüfung:Voraussetzung für die Modulabschlussprüfung:
  • erfolgreich bearbeitete Übungen (75% der Gesamtpunkte müssen erbracht werden)

Modulabschlussprüfung:

  • Klausur, 120 min.
Bewertung der Modulprüfung:Prüfungsleistung - benotet
Teilnehmerbeschränkung:keine
Zuordnung zu Studiengängen:
  • Master (universitär) / Angewandte Mathematik / PO 2008
  • Master (universitär) / Angewandte Mathematik / PO 2019
  • Bachelor (universitär) / Informatik / PO 2008
  • Bachelor (universitär) / Informations- und Medientechnik / PO 2017
  • Bachelor (universitär) / Künstliche Intelligenz / PO 2022
  • Bachelor (universitär) / Künstliche Intelligenz Technologie / PO 2022
  • Bachelor (universitär) / Mathematik / PO 2019
  • Bachelor (universitär) / Mathematik / PO 2023
  • Bachelor (universitär) - Duales Studium, praxisintegrierend / Mathematik - dual / PO 2023
  • Bachelor (universitär) / Medizininformatik / PO 2016
  • Bachelor (universitär) / Wirtschaftsinformatik / PO 2024
  • Bachelor (universitär) / Wirtschaftsmathematik / PO 2007
  • Bachelor (universitär) / Wirtschaftsmathematik / PO 2023
  • Bachelor (universitär) - Duales Studium, praxisintegrierend / Wirtschaftsmathematik - dual / PO 2023
Bemerkungen:
  • Studiengang Informatik B.Sc.: Pflichtmodul
  • Studiengang Informations- und Medientechnik B.Sc.: Pflichtmodul im Komplex „Informatik“
  • Studiengang Medizininformatik B.Sc.: Pflichtmodul
  • 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“
Veranstaltungen zum Modul:
  • Vorlesung: Theoretische Informatik - 4 SWS
  • Übung zur Vorlesung - 4 SWS
  • zugehörige Prüfung
Veranstaltungen im aktuellen Semester: