Theoretische Informatik 2
Berechenbarkeitsmodelle und Komplexität
2
2
0
0
0
4
6
angeboten in jedem SoSe
Theoretical Computer Science 2
Berechnung des Workloads
Vorgesehenes Semester ab 1. Semester
Lernziele
Fundamentale Konzepte und Ergebnisse aus den Gebieten Berechenbarkeit, Komplexität und Prädikatenlogik kennen und verinnerlicht haben.
Verschiedene Berechnungsmodelle kennen und die Grenzen der Berechenbarkeit einschätzen können.
Die Komplexität von typischen Informatik-Problemen einschätzen können und sensibilisiert sein für die Existenz schwieriger Probleme.
Induktionsbeweise über die Struktur von Zahlen, Wörtern, Berechnungssequenzen und/oder ähnliche Strukturen nachvollziehen und selbständig durchführen können.
Selbständig Algorithmen entwerfen und formal spezifizieren können.
In Gruppen Probleme analysieren und gemeinsam Lösungsstrategien entwickeln und präsentieren können.
Lerninhalte
1) Berechenbarkeit
Turingmaschinen
Linear beschränkte Automaten
Grammatiken der Typen 0 und 1, Abschlusseigenschaften
LOOP-Programme und WHILE-Programme
Primitiv rekursive Funktionen und μ-rekursive Funktionen
Unentscheidbarkeit
Unentscheidbare Probleme für Turingmaschinen
Satz von Rice
Postsches Korrespondenzproblem
Äquivalenzproblem kontextfreier Grammatiken
Semi-Entscheidbarkeit und Rekursive Aufzählbarkeit
Universelle Turingmaschinen
Reduktionen
2) Komplexität
Zeit- und Platzbeschränkte Turingsmaschinen
Komplexitätsklassen P, NP, PSpace, ExpTime
P vs NP-Problem
NP-Vollständigkeit
NP-vollständige Probleme aus verschiedenen Gebieten
Komplemente und coNP
Approximation NP-harter Probleme
Satz von Savitch
Prüfungsformen
i. d. R. Bearbeitung von Übungsaufgaben und Fachgespräch
Dokumente (Skripte, Programme, Literatur, usw.)
J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium 2011
J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd edition). Pearson Education, 2014
Informatik-Format