Exakte Exponentialzeit-Algorithmen
Modulnummer: W06-04
Englischer Titel: Exact Exponential Algorithms
Leistungspunkte: 6
Lehrperson: Kratsch
Empfohlene Vorkenntnisse
Algorithmen und Datenstrukturen II
Zwingende Voraussetzungen
Algorithmen und Datenstrukturen
Inhalt
Diese Vorlesung beschäftigt sich mit Algorithmen, die NP-schwere Probleme exakt (also optimal) lösen und dafür exponentielle Zeit aufwenden dürfen. Auch wenn es wohl keine exakten Polynomialzeitalgorithmen dafür gibt, wollen wir die Probleme trotzdem in möglichst geringer Zeit und nachweislich optimal lösen. Primär geht es in der Vorlesung um eine Vielzahl algorithmischer Techniken u.a. Branching Algorithmen, Dynamische Programmierung, Inklusion-Exklusion, Measure & Conquer, Subset Convolution und Lokale Suche.
Die Vorlesung basiert auf dem gleichnamigen Buch "Exact Exponential Algorithms" von Fedor V. Fomin und Dieter Kratsch. Das Buch kann aus dem Uninetz (oder VPN) über die Unibibliothek beim Verlag heruntergeladen werden.
Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung
Keine
Lehrveranstaltungen
Vorlesung: 3 SWS
Übung: 1 SWS
Forschungsorientiert
ja
Angeboten für Studiengänge
Monobachelor: ja
Kombinationsbachelor: ja
Infomit: ja
Angeboten im
Wintersemester: ja
Sommersemester: nein
Turnus
Alle zwei Jahre