Modul 63912 Grundlagen der Theoretischen Informatik
Modulinformation
Im ersten Lehrveranstaltungsteil wird mit Hilfe formaler Sprachen der Begriff der Berechenbarkeit entwickelt. Zunächst werden verschiedene Berechnungsmodelle vorgestellt, welche sich an der Chomsky-Hierarchie orientieren. Besonderes Augenmerk erfahren die regulären, kontextfreien und entscheidbaren Sprachen. Als Modelle werden der endliche Automat, der Kellerautomat und die Turingmaschine vorgestellt. Zudem wird auf das Konzept zur Beschreibung von Sprachen über Grammatiken vorgestellt. Dies führt zur Formulierung und Diskussion der Churchschen These.
Der zweite Lehrveranstaltungsteil widmet sich zuerst den nichtentscheidbaren Problemen. Hier werden wichtige Probleme, wie das Halteproblem, vorgestellt und wichtige Konsequenzen (Satz von Rice, Rekursionstheorem, Postsches Korrespondenzproblem) erläutert. Auch wird auf die Entscheidbarkeit von logischen Theorien eingegangen. In diesem Zusammenhang werden auch die Gödelschen Unvollständigkeitssätze diskutiert. Anschließend wird eine Einführung in die Komplexitätstheorie gegeben. In diesem Zusammenhang werden die Komplexitätsmaße Zeit und Speicherplatz eingeführt. Mit einer eingehenden Behandlung des P-vs-NP-Problems und der NP-Vollständigkeitstheorie schließt dieser Teil.
Vertiefungsrichtung
Angewandte Algebra und Diskrete Mathematik (AD)
| ECTS | 10 |
|---|---|
| Arbeitsaufwand | Die Lehrveranstaltung besteht aus 8 Lektionen.
Bearbeitungszeit je Lektion (inkl. Übungs- und Einsendeaufgaben): 25 Stunden (insgesamt 200 Stunden).
Hinzu kommen 100 Stunden für Studientage und Prüfungsvorbereitung. |
| Dauer des Moduls | ein Semester |
| Häufigkeit des Moduls | in jedem Semester |
| Anmerkung | - |
| Inhaltliche Voraussetzung | Elementare Begriffe und Methoden der Mathematik, wie sie in den einführenden Mathematiklektionen des Studiengangs verwendet werden. |
Aktuelles Angebot
Mentorielle Betreuung
Studierende können sich zu einem Mentoriat im Moodle-Kurs ab 01.04.2025 anmelden. Tragen Sie sich bitte nur in die Mentoriate ein, die Sie wirklich belegen.
[mehr erfahren]
Prüfungsinformation
| B.Sc. Informatik | |
|---|---|
| Art der Prüfungsleistung | benotete zweistündige Prüfungsklausur |
| Voraussetzung | keine |
| Stellenwert der Note | 1/16 |
| Formale Voraussetzungen | mindestens 30 von 60 ECTS der Studieneingangsphase sind bestanden |
| M.Sc. Mathematik | |
| Art der Prüfungsleistung | benotete mündliche Prüfung (ca. 25 Minuten) |
| Voraussetzung | keine |
| Stellenwert der Note | 1/12 |
| Formale Voraussetzungen | keine |
| B.Sc. Mathematik | |
| Art der Prüfungsleistung | benotete zweistündige Prüfungsklausur |
| Voraussetzung | keine |
| Stellenwert der Note | 1/15 |
| Formale Voraussetzungen | mindestens 45 von 90 ECTS der Studieneingangsphase sind bestanden |
Download
- Seite Modulhandbuch B.Sc. Informatik
- Seite Modulhandbuch M.Sc. Mathematik
- Seite Modulhandbuch B.Sc. Mathematik
- Leseprobe: Grundlagen der Theoretischen Informatik
Ansprechpersonen
Prof. Dr. André Schulz
mathinf.webteam
| 27.03.2025
