Modulnummer

Modulbezeichnung

Titel (englisch)

Pflicht/Wahl

Erklärung

CP

Berechnung des Workloads

Turnus

Dauer

Form

Prüfung

Anforderungen

Lernziele

• Formale Grundlagen und elementare Fragestellungen der Informatik kennen und die fundamentale Rolle der Theorie in der Informatik verstehen.
• Konzepte zur formalen Beschreibung und Analyse von Informatiksystemen kennen.
• Beherrschung der grundlegenden Methoden aus den Bereichen der Berechenbarkeit und Komplexität.
• Beherrschung elementarer Beweistechniken und Beweise selbst durchführen können.
• Probleme analysieren, von spezifischen Gegebenheiten abstrahieren und formale Modelle in mathematischen Definitionen darstellen können.
• Algorithmen für diese Probleme kennen und auf neue Problemvarianten anwenden können.
• Korrektheit von Algorithmen beweisen und Eigenschaften von Algorithmen analysieren können.
• Eigenständig und in Gruppen Lösungsstrategien für formale Problemstellungen entwickeln können und Lösungen verständlich präsentieren.

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

Lehrveranstaltung(en):

• 03-IBGT-THI2 Theoretische Informatik 2: Berechenbarkeit und Komplexität

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, Skript 2. Teil

Sprache

Bemerkung

Zuletzt geändert