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. Im Einzelnen:
Berechenbarkeit:
- Turing-Maschinen
- Intuitiver Berechenbarkeitsbegriff, Churchsche These
- LOOP-/WHILE-/GOTO-Berechenbarkeit, Primitiv rekursive und mu-rekursive Funktionen
- Halteproblem, Unentscheidbarkeit, Reduktionen, Unentscheidbare Probleme
Komplexitätstheorie:
- Komplexitätsklassen, P-NP-Problem
- NP-Vollständigkeit, NP-vollständige Probleme
- Polynomielle Reduktion
Weitere Informationen zu dieser Veranstaltung finden Sie unter https://www.uni-due.de/theoinf/teaching/ws202425_beko.php
- Lehrende(r): Felix Farke
- Lehrende(r): Tobias Grzesch
- Lehrende(r): Barbara König
- Lehrende(r): Michael Litvine
- Lehrende(r): Leander Lohaus
- Lehrende(r): Lara Stoltenow
- Lehrende(r): Florian Wittbold