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): Farke Felix
- Lehrende(r): Grzesch Tobias
- Lehrende(r): König Barbara
- Lehrende(r): Litvine Michael
- Lehrende(r): Lohaus Leander
- Lehrende(r): Stoltenow Lara
- Lehrende(r): Wittbold Florian