Topic outline
Vorlesung Exakte Algorithmen
Umfang: 5 ETCS, 2+2 SWS Modul: Ausgewählte Kapitel der Algorithmik / Theorie / Informatik
Zeit & Ort: VL Mi 16:00–17:30 Uhr, Informatikgebäude, Seminarraum I ÜB Fr 8:30–10:00 Uhr, Informatikgebäude, Übungsraum II Zielgruppe: MA Inf. Vorlesung: Alexander Wolff und Thomas van Dijk Übung: Myroslav Kryven JedeR TeilnehmerIn muss sich rechtzeitig unter sb@home für eines der oben genannten Module ("Ausgewählte Kapitel der...") eintragen, so dass wir nach der Prüfung die Leistung verbuchen können.
Wer im Durchschnitt 50% der Punkte bei den Übungsaufgaben erreicht, bekommt bei erfolgreicher Prüfungsteilnahme (im selben Semester) einen Bonus in Höhe von 0,3 Notenpunkten. Übungsaufgaben dürfen zu zweit bearbeitet und abgegeben werden.
Die Prüfungen finden am 21. 2. als mündliche Prüfungen (von je 20 Minuten) statt.
Kursbeschreibung
Für viele wichtige Probleme in der Informatik ist derzeit kein effizienter (d.h. polynomieller) Algorithmus bekannt. Ein prominentes Beispiel ist das Problem des Handlungsreisenden, bei dem es darum geht eine kürzeste Rundreise zu finden, die eine vorgegebene Menge von Stationen besucht. In dieser Vorlesung beschäftigen wir uns mit Entwurfs- und Analysetechniken für Algorithmen, die zwar im schlechtesten Fall exponentielle Laufzeit besitzen können, aber dennoch nachweisbar schneller als naheliegende Brute-Force-Ansätze sind. Bei Interesse der Kursteilnehmer wird auch auf das Verhalten solcher Algorithmen in der Praxis eingegangen.
Stichworte: Exakte exponentielle Algorithmen; parametrisierte Algorithmen
LernzieleAm Ende dieses Kurses sollen die Teilnehmer in der Lage sein, einfache exakte Algorithmen zu entwickeln oder zu analysieren. Außerdem sollen sie grundlegende Entwurfstechniken, wie beispielsweise Branching, dynamische Programmierung, Inclusion-Exclusion, Measure & Conquer, Kernelisierung und Suchbäume mit begrenzter Tiefe verstehen und anwenden können.
Übungsblätter
Vorlesungsskript