12215 - Theoretische Informatik Modulübersicht

Modulnummer: 12215 - Modul nicht mehr im Angebot ab WS 2018/19
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: 10
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
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 2 SWS
  • Tutorium / 2 SWS
  • Selbststudium / 180 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:

  • erfolgreiche Bearbeitung von Übungsaufgaben (75% müssen erbracht werden)

Modulabschlussprüfung:

  • Klausur, 180 min.
Bewertung der Modulprüfung:Prüfungsleistung - benotet
Teilnehmerbeschränkung:keine
Zuordnung zu Studiengängen:
  • keine Zuordnung vorhanden
Bemerkungen:
  • 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.

Veranstaltungen zum Modul:
  • Vorlesung Theoretische Informatik
  • Übung Theoretische Informatik
  • Tutorium Theoretische Informatik
  • Prüfung Theoretische Informatik
Veranstaltungen im aktuellen Semester:
  • keine Zuordnung vorhanden
Nachfolgemodul/e: Auslaufmodul ab: 13.06.2016