Effiziente Algorithmen (WS 2016/17)

Die Wiederholungsklausur findet am 29.03. um 13:30 im FO1 statt.

Es sind keine Hilfsmittel erlaubt.

Übungsbetrieb

Es gibt keine von uns überprüfte Klausurzulassungsbeschränkung. Die Hausaufgaben koennen auf freiwilliger Basis abgegeben werden, sie werden aber nicht korrigiert. An der Klausur teilnehmen darf jeder, der an Hand der Musterloesungen nach eigenem Ermessen mindestens 50% der Punkte bei den Hausaufgaben erreicht hat.

Voraussetzungen

Stoff der ersten Semester des Informatikstudiums und der zugehörigen Mathematikvorlesungen.

Inhalt

Die Vorlesung gibt einen Überblick über verschiedene Gebiete der Algorithmik. Im Zentrum der Vorlesung steht die theoretische Analyse der vorgestellten Algorithmen bezüglich ihrer Korrektheit, Laufzeit und Güte. Die Themenauswahl berücksichtigt insbesondere die praktische Relevanz der vorgestellten algorithmischen Konzepte. Im Einzelnen widmen wir uns den folgenden Themen.
  • Flüsse und Matchings
  • Lineare Programmierung
  • Algorithmische Geometrie
  • Randomisierte Algorithmen
  • Approximationsalgorithmen
  • Online-Algorithmen

Vorlesungsfolien

Übungen

Literatur

Buch Introduction to Algorithms.
Buch The Art of Computer Programming.