Algorithms and Complexity 1 - 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 Algorithms and Complexity 1 in degree program Master Informatik 2021

module number

201170

examination number

2200867

department

Department of Computer Science and Automation

ID of group

2242 (Algorithms)

module leader

Prof. Dr. Christoph Berkholz

term

summer term only

language

Deutsch

credit points

on-campus program (h)

self-study (h)

116

obligation

elective module

exam

oral examination performance, 20 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

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.

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.

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

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