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

 Präsenzveranstaltung mit Folienpräsentation und Tafel

Sprache: Deutsch
Turnus: WS
ECTS: 6
Prüfungsleistung

Klausur (120 Minuten)

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, SAT, weitere NP-vollständige Probleme)

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.

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:

The theory of computability and complexity is an important foundation of computer science. Here we are interested in questions such as: what can we compute? How expensive is such a computation? We will also treat the P-NP problem, the most significant unsolved problem in theoretical computer science. The course will teach fundamental knowledge in the areas of computability and complexity, in particular:

  • Computability (Turing machines, intuitive notion of computability, Church‘s thesis, LOOP-/WHILE-/GOTO-programs, primitive recursive and mu-recursive functions, Ackermann function, halting problem, undecidability, reductions, Post‘s correspondence problem, further undecidable problems)
  • Complexity (complexity classes, P-NP problem, NP-completeness, SAT, further NP-complete problems)
Learning Targets:

The students should acquire knowledge in the area of computability and complexity. They should know about various computation models such as Turing machines, LOOP-, WHILE- and GOTO-programs, primitive recursive and mu-recursive functions. Via the proof of equivalence of these models they should be able to understand Church‘s thesis. They should understand and apply concepts such as undecidability and reduction and know about undecidable problems (halting problem, Post‘s correspondence problem, etc.). They should be able to make judgements about the undecidability of a problem and prove this. In the area of complexity the should know about various complexity classes, the P-NP problem and NP-completeness. They should apraise the complexity of problems and have the ability to perform simple reductions.

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: