Programmierung 1 und 2 und Mathematik für Informatiker 1 und 2 oder vergleichbare Veranstaltungen der Mathematik sind empfohlen.
Erfolgreiche Bearbeitung der Übungsaufgaben berechtigt zur Klausurteilnahme.
Wird aus Leistungen in Klausuren, Übungen und praktischen Aufgaben ermittelt. Die genauen Modalitäten werden vom Modulverantwortlichen bekannt gegeben.
4 SWS Vorlesung
+ 2 SWS Übung
= 6 SWS
90 h Präsenzstudium
+ 180 h Eigenstudum
= 270 h (= 9 ECTS)
Die Studierenden kennen verschiedene Rechenmodelle und ihre relativen Stärken und Mächtigkeiten.
Sie können für ausgewählte Probleme zeigen, ob diese in bestimmten Rechenmodellen lösbar sind oder nicht.
Sie verstehen den formalen Begriff der Berechenbarkeit wie auch der Nicht-Berechenbarkeit.
Sie können Probleme aufeinander reduzieren.
Sie sind vertraut mit den Grundzügen der Ressourcenbeschränkung (Zeit, Platz) für Berechnungen und der sich daraus ergebenden Komplexitätstheorie.
Die Sprachen der Chomsky Hierarchie und ihre verschiedenen Definitionen über Grammatiken und Automaten; Abschlusseigenschaften; Klassifikation von bestimmten Sprachen („Pumping lemmas“);
Determinismus und Nicht-Determinismus;
Turing Maschinen und äquivalente Modelle von allgemeiner Berechenbarkeit (z.B. μ-rekursive Funktionen, Random Access Machines) Reduzierbarkeit, Entscheidbarkeit, Nicht-Entscheidbarkeit;
Die Komplexitätsmaße Zeit und Platz; die Komplexitätsklassen P und NP;
Grundzüge der Theorie der NP-Vollständigkeit
Bekanntgabe jeweils vor Beginn der Vorlesung auf der Vorlesungsseite im Internet.
Dieses Modul ist inhaltsgleich mit dem englischsprachigen Modul Introduction to Theoretical Computer Science.
This module is part of the following study programmes: