Algorithms and Complexity 1+2 - Interactive curriculae of TU Ilmenau

The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the course catalogue.

Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.

module properties module number 201171 - common information
module number	201171
department	Department of Computer Science and Automation
ID of group	2242 (Algorithms)
module leader	Prof. Dr. Christoph Berkholz
language	Deutsch
term	Sommersemester
previous knowledge and experience	Algorithmen und Komplexitätstheorie aus den Bachelor-Grundvorlesungen (Algorithmen und Datenstrukturen 1+2, Berechenbarkeit und Komplexität)
learning outcome	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. - Die Studierenden können eigenständig fortgeschrittene Algorithmendesigntechniken benennen und strategieorientiert anwenden. Sie sind in Lage, Komplexitätsaussagen für solche algorithmischen Probleme herzuleiten. - Die Studierenden sind in der Lage, aktuelle Forschungsergebnisse im Bereich Algorithmen und Komplexität durchdacht einzuordnen, nachzuvollziehen und methodisch anzuwenden.
content	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. In der zweiten Semesterhälfte werden fortgeschrittene Algorithmen und Komplexitätsaussagen für algorithmische Probleme vorgestellt. Der Inhalt orientiert sich am aktuellen Forschungsstand sowie an den Forschungsaktivitäten des Fachgebiets Algorithmik und eignet sich als Vorbereitung für ein Hauptseminar oder eine Abschlussarbeit.
media of instruction and technical requirements for education and examination in case of online participation	Tafelvortrag, Beamerpräsentation
literature / references	Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Jörg Flum, Martin Grohe: Parameterized Complexity Theory.
evaluation of teaching

Details reference subject
module name	Algorithms and Complexity 1+2
examination number	2200868
credit points	10
SWS	6 (4 V, 2 Ü, 0 P)
on-campus program (h)	67.5
self-study (h)	232.5
obligation	obligatory module
exam	oral examination performance, 30 minutes
details of the certificate
link to Moodle course	https://moodle.tu-ilmenau.de/course/view.php?id=2849
teacher
signup details for alternative examinations
maximum number of participants

Details in degree program Master Informatik 2021
module name	Algorithms and Complexity 1+2
examination number	2200868
credit points	10
on-campus program (h)	67
self-study (h)	233
obligation	elective module
exam	oral examination performance, 30 minutes
details of the certificate
link to Moodle course	https://moodle.tu-ilmenau.de/course/view.php?id=2849
signup details for alternative examinations
maximum number of participants