Parameterized Algorithms

Modulnummer: Q10-30
Englischer Titel: Parameterized Algorithms
Leistungspunkte: 10
Lehrperson: Kratsch

Empfohlene Vorkenntnisse

Solide Grundkenntnisse zu Algorithmen und Komplexität.

Zwingende Voraussetzungen

keine

Inhalt

Parameterized algorithms are an approach for coping with the intractability of NP-hard computational problems. The central idea therein is to quantify the structure of input instances by one or more parameters. Then, one seeks algorithms that provably perform well when the chosen parameters are sufficiently small. In this way, we can formalize the intuition that typical instances may have plenty of useful structure, which distinguishes them from the worst case.

There is a rich toolbox of algorithmic techniques that will be covered in the lecture. These include branching algorithms, kernelization, iterative compression, color coding, dynamic programming on tree decompositions, inclusion-exclusion, and others. The algorithmic techniques are complemented by lower bound methods that allow to rule out fast parameterized algorithms or that prove optimality of certain running times under appropriate assumptions.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben
- aktive Teilnahme

Lehrveranstaltungen

Vorlesung: 4 SWS
Übung: 2 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: ja
Sommersemester: ja

Turnus

Unregelmäßig