Allgemeines

Veranstaltungsnummer  
Veranstalter Nils Vortmeier
Klassifikation Proseminar
Semester Wintersemester 2017/18
Ort und Zeit OH12 2.063, Mi 12-14 Uhr
Vorbesprechung  
Querverbindungen DAP 2, GTI
Voraussetzungen DAP 2, GTI wünschenswert

Inhalt

Um Optimierungsprobleme zu lösen, wünscht man sich üblicherweise einen Algorithmus, der zu einer gegebenen Probleminstanz in möglichst geringer Laufzeit eine optimale Lösung erzeugt. Bedauerlicherweise ist es nicht immer möglich, gleichzeitig eine geringe Laufzeit und eine optimale Lösung zu garantieren. Wir beschäftigen uns in diesem Proseminar also mit Algorithmen, die zwar effizient sind (also höchstens polynomielle Laufzeit benötigen), allerdings nur eine näherungsweise optimale Lösung erzeugen. Dabei betrachten wir zwei verschiedene Sorten von Optimierungsproblemen, die jeweils auf ihre eigene Weise "zu schwierig" sind, um sie effizient exakt zu lösen.

  • Optimierungsprobleme, deren zugehörige Entscheidungsprobleme NP-schwierig sind, lassen sich (vermutlich) nicht effizient lösen. Da diese Probleme in der Praxis dennoch gelegentlich auftauchen, beschäftigen wir uns mit Approximationsalgorithmen, die in polynomieller Zeit eine "hinreichend gute" Lösung liefern sollen.
  • Speziell bei maschinennahen Optimierungsproblemen wie dem Paging-Problem, also der Frage, wann Speicherseiten aus einem schnellen, aber kleinen Speicher in einen großen, dafür langsamen Speicher ausgelagert werden sollen, kommt es öfters vor, dass die Eingabeinstanz (im Beispiel: eine Folge von Speicherzugriffen) nicht im Voraus bekannt ist sondern erst zur Laufzeit des Algorithmus Stück für Stück bekannt gegeben wird. Zu dieser Art von Problemen betrachten wir Online-Algorithmen, die darauf ausgelegt sind,  eine solche "streaming-artige" Form der Eingabe möglichst gut zu verarbeiten.

In beiden Fällen betrachten wir Algorithmen, die ein gegebenes Problem nicht exakt lösen, allerdings gewisse Qualitätsgarantien erfüllen (wie z.B. Paging-Algorithmen, die höchstens doppelt so viele Auslagerungs-Operationen durchführen wie ein Algorithmus, der die Eingabe bereits im Voraus kennt). Insbesondere werden Sie in diesem Proseminar diverse Techniken und Strategien zum Entwurf und zur Analyse entsprechender Algorithmen kennenlernen. Darüber hinaus beschäftigen wir uns mit der Komplexitätstheorie von Optimierungsproblemen und deren Approximierbarkeit, welche die aus der GTI-Vorlesung bekannte Theorie NP-vollständiger Probleme erweitert.

Die Vortragsthemen basieren auf Teilen der Lehrbücher Complexity and Approximation von Ausiello et al. und Online Computation and Competitive Analysis von Borodin und El-Yaniv. Abhängig von der Teilnehmerzahl könnten auch noch weitere Quellen in Frage kommen.

Als Voraussetzung für die Teilnahme an diesem Proseminar sind solide algorithmische Grundkenntnisse notwendig, wie sie in der Veranstaltung DAP2 vermittelt werden. Kenntnisse zur Theorie NP-vollständiger Probleme sind für viele Themen hilfreich. Einige Themen erfordern darüber hinaus grundlegende Kenntnisse der Wahrscheinlichkeitsrechnung.