Themen dieses Kurses

  • Allgemeines

  • 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

    An der Vorlesung Interessierte schreiben sich bitte hier in WueCampus in den Kurs ein!

    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 einen Bonus in Höhe von 0,3 Notenpunkten. Übungsaufgaben dürfen zu zweit bearbeitet und abgegeben werden.

    Die Prüfungen finden voraussichtlich in der Woche nach Semesterende 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


      Lernziele

      Am 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