Summer 2022
Parametrisierte Komplexit?t
Parameterized Complexity
03-ME-602.22 (03-IMAT-PK)
Vorlesung
ECTS: 6
Termine:
w?chentlich Mo 10:00 - 12:00 MZH 3150 Vorlesung Pr?senz
w?chentlich Mi 10:00 - 12:00 MZH 3150 ?bung Pr?senz
Profil: SQ
Schwerpunkt: SQ
Die parametrisierte Komplexit?tstheorie ist ein relativ junges Teilgebiet der theoretischen Informatik. In der klassischen Komplexit?tstheorie werden Laufzeiten von Algorithmen bezüglich der Eingabel?nge n gemessen. In der parametrisierten Komplexit?tstheorie wird eine feinere Analyse angewendet und Laufzeiten bezüglich einem oder 澳门皇冠_皇冠足球比分-劲爆体育eren zus?tzlichen Parametern beschrieben. So k?nnen in vielen F?llen Algorithmen entwickelt werden, die selbst für NP-schwere Probleme auf Instanzen mit kleinen Parametern effizient sind. Insbesondere sind Instanzen, die in der Praxis auftreten, h?ufig strukturell einfach. Die parametrisierte Komplexit?tstheorie kann in diesen F?llen erkl?ren, warum NP-schwere Probleme in der Praxis h?ufig schnell gel?st werden k?nnen. In dieser Vorlesung lernen wir viele Techniken zum Entwurf effizienter parametrisierter Algorithmen kennen.
Inhalte.
1. Motivation
2. FPT und XP
3. Kernelization und ?quivalenz zu FPT
4. Crown Decompositions und Vertex Cover
5. Sunflower Lemma und Hitting sets
6. Lineare Programmierung für Vertex Cover
7. Bounded Search Trees
8. Feedback Vertex Set
9. Above Guarantee Parameterizations
10. Iterative Kompression und Odd Cycle Transversal
11. Dynamische Programmierung über Baumzerlegungen
(11b. Color Coding)
12. Beyond FPT: die W-Hierarchie
13. Die Exponential Time Hypothesis (ETH) in der parametrisierten Welt
14. FPT und Approximation
Projekt GraPA
(WiSe 21/22 bis SoSe 2022)
03-IMPJ-GRAPA
Projektplenum
ECTS: 12
Termine:
w?chentlich Fr 08:00 - 10:00 MZH 3150 Plenum Pr?senz
Sparsity - Graphs and algorithms (in englischer Sprache)
03-ME-602.21 (03-IMVT-SGA)
Vorlesung
ECTS: 6
Termine:
w?chentlich Di 08:00 - 10:00 MZH 3150 ?bung Pr?senz
w?chentlich Do 10:00 - 12:00 MZH 3150 Vorlesung Pr?senz
Profil: SQ