Abschnittsübersicht

  • Allgemeines

    Alles einklappen Alles aufklappen

  • Kursbeschreibung

    Für viele wichtige Probleme in der Informatik ist derzeit kein effizienter (d.h. polynomieller) Algorithmus bekannt. Ein prominentes Beispiel ist das Traveling Salesperson Problem, 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 [ Illustration ]. Unser Ziel ist dabei stets das Berechnen von optimalen Lösungen, weshalb solche Algorithmen auch als exakte Algorithmen bezeichnet werden, um sie von Approximationsalgorithmen und Heuristiken abzugrenzen. Ein wichtiges (und relativ junges) Teilgebiet der exakten Algorithmik ist die Festparameterberechenbarkeit, die ebenfalls in der Vorlesung behandelt wird. Dabei geht es um den Entwurf von exakten Algorithmen, die nachweislich effizient sind, sofern die Probleminstanzen eine geeignete Struktur aufweisen.

    Am Ende dieses Kurses sollen die TeilnehmerInnen 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.


    Vorlesungen:
    		Die Vorlesungen werden als Videos zur Verfügung gestellt.
    Zum Vorlesungstermin (Dienstag, 16:15 Uhr) finden Frage- und Diskussionsrunden per Zoom statt (erstmal am 26. April).
    Der Meeting Link ist ganz oben auf der WueCampus Seite zu finden (nur angemeldet sichtbar).
    Übungen:
    		Donnerstag, 14:15 - 15:45 Uhr, SE 8 im Physikgebäude P1 (erstmalig  am 5. Mai)
    DozentInnen:
    		Boris Klemz (Vorlesungen), Oksana Firman (Übungen)

    Prüfung:
    		Der Termin für die mündlichen Prüfungen ist Freitag der 29. Juli 2022.
    Der Nachprüfungstermin ist Donnerstag der 20. Oktober 2022.
    Ein Bonus von 0,3 auf die finale Note wird an Studierende vergeben, die mindestens 50% der Punkte auf den Übungsblättern erreichen und die Prüfung bestehen.

    Umfang
    		5 ECTS (2+2 SWS)

    Modul:
    		Ausgewählte Kapitel der Algorithmik / Theorie / Informatik

    Vorraussetzung:   
    		Es kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen (Info., Bsc.), sowie Algorithmische Graphentheorie (Info., Bsc.) zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen.

    Zielgruppe: Master Informatik, Master Mathematik, Master Computational Mathematics
    Sprache:

    		 Die Vorlesung wird in deutscher Sprache gehalten. Das Material (Folien, Übungsblätter, Literatur) ist in englischer Sprache verfasst. Die Prüfung kann wahlweise in deutscher oder englischer Sprache durchgeführt werden. Die Übungen können wahlweise in deutscher oder englischer Sprache bearbeitet werden.
    Anmeldung: Für die Teilnahme an der Prüfung ist eine rechtzeitige Anmeldung in WueStudy erforderlich.
    Zusätzlich ist eine Anmeldung in WueCampus nötig, um auf das Lehrmaterial zugreifen zu können (oben links auf die weißen Zahnräder auf blauem Grund und dann auf "Mich in diesem Kurs einschreiben" klicken).