Algorithmen und Komplexität 1 - Interaktive Studienpläne der TU Ilmenau

- Die Studierenden kennen grundlegende Designkonzepte, um eigenständig parametrische Algorithmen zu entwickeln.
- Die Studierenden sind in der Lage, FPT-Algorithmen anforderungsgerecht zu entwickeln und Methoden parametrisierter Algorithmik auf neue Probleme strategieorientiert anzuwenden.
- Die Studierenden kennen grundlegende Begriffe und Methoden der parametrischen Komplexitätstheorie und sind in der Lage, selbständig Reduktionsmethoden zu entwickeln. Sie sind mit gängigen Komplexitätshypothesen vertraut, um algorithmische Probleme einordnen und bewerten zu können.
- Die Studierenden können die Komplexität von Problemen mit Methoden der parametrischen Komplexitätstheorie und der feinkörnigen Komplexitätsanalyse unter Berücksichtigung unterschiedlicher Beurteilungsmaßstäbe untersuchen, in Beziehung setzen und bewerten.

Wie kann man Probleme möglichst ressourcenschonend lösen und wo liegt die Grenze effizienter Methoden? Wann ist die Laufzeit eines Algorithmus optimal? Klassischerweise werden Entscheidungsprobleme in leichte (lösbar in Polynomialzeit) und schwere (NP-hart) eingeteilt. Allerdings können in der Praxis manche schwere Probleme auf den typischerweise auftretenden Instanzen schnell gelöst werden, während nicht jeder Polynomialzeitalgorithmus effizient ist.

In diesem Modul werden moderne algorithmische Verfahren sowie Techniken zum Beweisen von unteren Schranken zusammen betrachtet. Im algorithmischen Teil des Kurses werden Methoden vorgestellt, welche die besondere Struktur von Eingabeinstanzen (wie bspw. Graphen) miteinbeziehen. Einen besonderen Schwerpunkt bilden FPT-Algorithmen und die Kernelisierungstechnik. Diese algorithmischen Verfahren werden komplementiert durch eine genaue Analyse ihrer inhärenten Komplexität mit Methoden der parametrischen Komplexitätstheorie und der feinkörnigen Komplexitätsanalyse.

Das Modul entspricht der ersten Semesterhälfte des Moduls Algorithmen und Komplexität 1+2.