272-0300-00L Algorithmik für schwere Probleme
Semester | Frühjahrssemester 2019 |
Dozierende | H.‑J. Böckenhauer, R. Kralovic |
Periodizität | 2-jährlich wiederkehrende Veranstaltung |
Lehrsprache | Deutsch |
Kommentar | Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t ! |
Kurzbeschreibung | Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme, insbesondere mit exakten Algorithmen mit moderat exponentieller Laufzeit und parametrisierten Algorithmen. Eine umfassende Reflexion über die Bedeutung der vorgestellten Ansätze für den Informatikunterricht an Gymnasien begleitet den Kurs. |
Lernziel | Auf systematische Weise eine Übersicht über die Methoden zur Lösung schwerer Probleme kennen lernen. Vertiefte Kenntnisse im Bereich exakter und parameterisierter Algorithmen erwerben. |
Inhalt | Zuerst wird der Begriff der Berechnungsschwere erläutert (für die Informatikstudierenden wiederholt). Dann werden die Methoden zur Lösung schwerer Probleme systematisch dargestellt. Bei jeder Algorithmenentwurfsmethode wird vermittelt, was sie uns garantiert und was sie nicht sichern kann und womit wir für die gewonnene Effizienz bezahlen. Ein Schwerpunkt liegt auf exakten Algorithmen mit moderat exponentieller Laufzeit und auf parametrisierten Algorithmen. |
Skript | Unterlagen und Folien werden zur Verfügung gestellt. |
Literatur | J. Hromkovic: Algorithmics for Hard Problems, Springer 2004. R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006. M. Cygan et al.: Parameterized Algorithms, 2015. F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010. |