Modul 63912 Grundlagen der Theoretischen Informatik

Modulinformation

Im ersten Kursteil 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 Kursteil 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)

ECTS10
Arbeitsaufwand
Das Modul besteht aus 8 Kurseinheiten.
Bearbeitungszeit je Kurseinheit (inkl. Übungs- und Einsendeaufgaben): 25 Stunden (insgesamt 200 Stunden).
Hinzu kommen 100 Stunden für Studientage und Prüfungsvorbereitung.
Dauer des Modulsein Semester
Häufigkeit des Modulsin jedem Semester
Anmerkung
-
Inhaltliche Voraussetzung
Elementare Begriffe und Methoden der Mathematik, wie sie in den einführenden Mathematikkursen des Studiengangs verwendet werden.

Aktuelles Angebot

Mentorielle Betreuung an den Campusstandorten

[mehr erfahren]

  • Coesfeld (Modul 63912 (virtuelle Veranstaltung), SoSe 2023)
  • Frankfurt am Main (Modul 63912 (virtuelle Veranstaltung), SoSe 2023)
  • München (Modul 63912 (virtuelle Veranstaltung), SoSe 2023)

Prüfungsinformation

B.Sc. Informatik
Art der Prüfungsleistungbenotete Prüfungsklausur
Voraussetzungkeine
Stellenwert der Note1/16
Formale Voraussetzungenmindestens 30 von 60 ECTS der Studieneingangsphase sind bestanden
M.Sc. Mathematik
Art der Prüfungsleistungbenotete mündliche Prüfung
Voraussetzungkeine
Stellenwert der Note1/12
Formale Voraussetzungenkeine
B.Sc. Mathematik
Art der Prüfungsleistungbenotete Prüfungsklausur
Voraussetzungkeine
Stellenwert der Note1/15
Formale Voraussetzungenmindestens 45 von 90 ECTS der Studieneingangsphase sind bestanden

Download

Ansprechpersonen

mathinf.webteam | 02.12.2021