Veranstaltungsarten (SWS)
Vorlesung: 2 │ Übung: 2 │ Praktikum: 0 │ Seminar: 0
Prüfungsnummer: ZKD 21741
Lehrform:

 

Sprache: Deutsch
Turnus: WS
ECTS: 6
Prüfungsleistung Klausur
Mündliche Prüfung
zugeordnete Studiengänge
zugeordnete Personen
zugeordnete Module
Informationen
Beschreibung:

Die Berechenbarkeits- und Komplexitätstheorie ist eine wichtige Grundlage der Informatik. Hierbei geht es um Fragestellungen der Form: was kann überhaupt berechnet werden? Wie teuer ist diese Berechnung? Mit dem P-NP-Problem erläutert dieses Gebiet auch das wichtigste bisher ungelöste Problem der theoretischen Informatik. Im Rahmen dieser Veranstaltung werden grundlegende Kenntnisse zu den Bereichen Berechenbarkeit und Komplexität vermittelt.
Inhalte im Einzelnen:
- Berechenbarkeit (Turing-Maschinen, Intuitiver Berechenbarkeitsbegriff, Churchsche These, LOOP-, WHILE-, GOTO-Berechenbarkeit, Primitiv rekursive und mu-rekursive Funktionen, Ackermannfunktion, Halteproblem, Unentscheidbarkeit, Reduktionen, Postsches Korrespondenzproblem, weitere unentscheidbare Probleme)
- Komplexität (Komplexitätsklasen, P-NP-Problem, NP-Vollständigkeit, weitere NP-vollständige Probleme, Randomisierung, Primzahltests)

Lernziele:

Die Studierenden sollen Kenntnisse auf dem Gebiet Berechenbarkeitstheorie und Komplexität erwerben. Sie sollen verschiedene Berechnungsmodelle wie Turing-Maschinen, LOOP-, WHILE-, GOTO-Programme, primitiv rekursive und mu-rekursive Funktionen kennenlernen. Durch den Beweis der Äquivalenz dieser Berechnungsmodelle sollen sie die Churchsche These nachvollziehen. Sie sollen Begriffe wie Unentscheidbarkeit und Reduzierbarkeit verstehen und anwenden können und unentscheidbare Probleme (Halteproblem, Postsches Korrespondenzproblem, etc.) kennenlernen. Dabei sollen sie selbst in die Lage versetzt werden, die Unentscheidbarkeit einer Problemstellung einschätzen und beweisen zu können.
Im Bereich der Komplexitätstheorie sollen sie verschiedene Komplexitätsklassen kennenlernen und das P-NP-Problem und das Konzept der (NP-)Vollständigkeit verstehen. Dabei sollen sie die Komplexität von Problemen abschätzen können und in der Lage sein, einfache Reduktionen durchzuführen. Außerdem sollen sie randomisierte Algorithmen kennenlernen.

Literatur:

- Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum, 2001
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley/Pearson, 2002

Vorleistung:

Vorlesungen "Automaten und formale Sprachen", "Grundlegende Programmiertechniken"

Infolink:
Bemerkung:
Description:
Learning Targets:
Literature:

- Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum, 2001
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley/Pearson, 2002

Pre-Qualifications:
Info Link:
Notice: