Summer 2020
Theoretische Informatik 2
(03-BA-601.02, 03-IBGT-THI1, Sebastian Siebertz und Mario Grobler)
Vorlesung
ECTS: 6
Die Vorlesungen finden online asynchron statt.
?bungstermine:
w?chentlich Di 10:00 - 12:00 ?bung Online
w?chentlich Di 12:00 - 14:00 ?bung Online
w?chentlich Di 14:00 - 16:00 ?bung Online
w?chentlich Mi 10:00 - 12:00 ?bung Online
w?chentlich Mi 12:00 - 14:00 ?bung Online
w?chentlich Mi 14:00 - 16:00 ?bung Online
w?chentlich Do 10:00 - 12:00 ?bung Online
Die Theoretische Informatik besch?ftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik. Sie besteht aus zahlreichen Teildisziplinen, von denen in dieser Vorlesung haupts?chlich die Theorie der Berechenbarkeit und die Komplexit?tstheorie behandelt werden. In der Theorie der Berechenbarkeit geht es um die Definition abstrakter Modelle von Berechnung und um die fundamentale Frage, welche Probleme prinzipiell berechenbar sind und welche nicht. Eine zentrale Rolle spielen dabei Turingmaschinen als elementares Berechnungsmodell, das aber dennoch ?quivalent zu komplexeren und praxisn?heren Modellen wie modernen Programmiersprachen ist. Die Komplexit?tstheorie betrachtet zus?tzlich die zur Berechnung verwendeten Ressourcen wie Laufzeit und Speicherplatz. Eine zentrale Frage ist dann, welche Probleme mit vertretbarem Aufwand berechenbar sind, wobei "vertretbarer Aufwand" meist mit "polynomieller Zeit" gleichgesetzt wird. Zus?tzlich zu den erw?hnten Themen werden wir auch einige in Theoretische Informatik 1 offen gebliebene Fragen aus dem Gebiet der formalen Sprachen kl?ren.
Parametrisierte Komplexit?t
(03-ME-602.22, 03-IMAT-PK, Sebastian Siebertz und Nikolas M?hlmann)
Vorlesung
ECTS: 6
Termine:
w?chentlich Mo 12:00 - 14:00 Vorlesung online
w?chentlich Mi 10:00 - 12:00 ?bung Online
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