| Kurzkommentar |
Notwendige Voraussetzungen:
- Grundzüge von Algorithmen und Datenstrukturen
- Theoretische Informatik
Hilfreich aber nicht notwendig:
- Algorithmen und Datenstrukturen
Literatur:
"Parameterized Algorithms" von Cygan et al. (ISBN 3319212745)
"Parameterized Complexity Theory" von Flum und Grohe (ISBN 3642067573)
"Fundamentals of Parameterized Complexity" von Downey und Fellows (ISBN
1447155580)
Beschreibung:
This course is about fast algorithms for NP-hard problems. The approach
is to measure the running time of an algorithm as a function of not just
the input length, but multiple parameters of the input. For example,
while a database may contain a very large amount of data, the size of
the database queries is typically extremely small in comparison.
You will learn many different intriguing algorithmic techniques to deal
with NP-hard problems when a secondary input parameter is small. You
will be brought to the cutting edge of current research in the area of
multivariate algorithmics. You will also learn about complexity results
which for some computational problems show that algorithms with a faster
running time may be impossible even when the chosen secondary parameter
is relatively small. |
