|
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
/ 2 SWS
-
Selbststudium
/ 150 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 Hausaufgaben und/oder erfolgreiche Bearbeitung von Hörsaaltestaten jeweils während eines Vorlesungstermins
(Die Art der Voraussetzung wird zu Semesterbeginn bekannt gegeben.)
Modulabschlussprüfung: |
| 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 2023
-
Bachelor (universitär) - Duales Studium, praxisintegrierend /
Mathematik - dual /
PO 2023
-
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: | |
