Theoretische Informatik 2
Theoretical Computer Science 2
|
Modulnummer
IBGT-THI2
|
|
Bachelor
|
Zugeordnet zu Masterprofil
|
Modulbereich
:
Mathematik und Theoretische Informatik
Modulteilbereich
:
(keine Angabe)
|
Anzahl der SWS
| V |
UE |
K |
S |
Prak. |
Proj. |
∑ |
| 2 |
2 |
0 |
0 |
0 |
0 |
4 |
|
Kreditpunkte
:
6
|
Turnus
angeboten in jedem SoSe
|
|
Formale Voraussetzungen
:
-
|
|
Inhaltliche Voraussetzungen
:
-
|
|
Vorgesehenes Semester
:
4.Semester
|
|
Sprache
:
Deutsch
|
Ziele
:
- 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.
|
|
Inhalte
:
.
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
|
Unterlagen (Skripte, Literatur, Programme 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
- C. Lutz: Theoretische Informatik, Skript 2. Teil
|
|
Form der Prüfung
:
MP, Fachgespräch, Klausur, ggf. mit Bonusprüfung
|
Arbeitsaufwand
| Präsenz |
56 |
| Übungsbetrieb/Prüfungsvorbereitung |
124 |
| Summe |
180 h |
|
|
Lehrende:
Prof. Dr. C. Lutz, Prof. Dr. S. Siebertz
|
Verantwortlich
Prof. Dr. C. Lutz
|
Wirtschaftsinformatik-Format