Modulnummer

Modulbezeichnung

Titel (englisch)

Pflicht/Wahl

Erklärung

CP

Berechnung des Workloads

Turnus

Dauer

Form

Prüfung

Anforderungen

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

Quellen

• 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
• C. Lutz: Theoretische Informatik 2, Skript

Sprache

Bemerkung

Zuletzt geändert