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

Unsere Webseite verwendet Cookies. Diese haben zwei Funktionen: Zum einen sind sie erforderlich für die grundlegende Funktionalität unserer Website. Zum anderen können wir mit Hilfe der Cookies unsere Inhalte für Sie immer weiter verbessern. Hierzu werden pseudonymisierte Daten von Website-Besuchern gesammelt und ausgewertet. Das Einverständnis in die Verwendung der technisch nicht notwendigen Cookies können Sie jeder Zeit wiederrufen. Weitere Informationen erhalten Sie auf unseren Seiten zum Datenschutz.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Statistik

Für den Zweck der Statistik betreiben wir die Plattform Matomo, auf der mittels pseudonymisierter Daten von Websitenutzern der Nutzerfluss analysiert und beurteilt werden kann. Dies gibt uns die Möglichkeit Websiteinhalte zu optimieren.

Name Zweck Ablauf Typ Anbieter
_pk_id Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern. 13 Monate HTML Matomo
_pk_ref Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern. 6 Monate HTML Matomo
_pk_ses Kurzzeitiges Cookie, um vorübergehende Daten des Besuchs zu speichern. 30 Minuten HTML Matomo