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: |
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
|