Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Algorithmen und Datenstrukturen

Wintersemester 2011/2012

Veranstalter:Prof. Dr. Christian Sohler
Termine: Montag 14:15-15:45 Uhr OH 14, 304
Dienstag 12:15-13:45 Uhr OH 14, 304
Beginn: 10. Oktober 2011


[Inhalt] [Begleitmaterial] [Übungen]


Inhalt


Im Rahmen dieser Vorlesung werden fortgeschrittene Entwurfsmethoden für Algorithmen und Datenstrukturen besprochen.

Inhalte der Vorlesung:

  • Grundlagen zur linearen Programmierung (lineare und affine Unterräume, Polytope, etc.)
  • Lineare Programmierung (Simplex Algorithmus, Ellipsoidmethode)
  • Approximationsalgorithmen (z.B. LP-basierte Algorithmen und randomisiertes Runden, primal-duale Algorithmen, lokale Suche, etc.)
  • Randomisierte Algorithmen (z.B. randomisiert inkrementelle Algorithmen, zufällige metrische Einbettungen, etc.)
  • Fortgeschrittene Datenstrukturen (z.B. Splay Bäume, randomisierte Suchbäume, Hashing, etc.)
Kapitel 8 der Mitschrift (Stringmatching) ist nicht prüfungsrelevant.


Begleitmaterial

Mitschrift (aus dem Jahr 2009)
Mitschrift zu Datenstromalgorithmen (zuletzt aktualisiert am 6.2.)
Pseudocode zum Simplex Algorithmus und zur Ellipsoid Methode
Alexander Schriver. Theory of Linear and Integer Programming. Wiley, 1998.
Vijay V. Vazirani. Approximation Algorithms. Springer, 2001.



Übungen

Übungsgruppen:

Beginn am 19.Oktober
Die Abgabe kann in Gruppen und sollte einzeln erfolgen. Es besteht keine Anwesenheits- oder Bearbeitungspflicht für die Zulassung zur Prüfung oder für den Erwerb eines Scheins.

Wichtiger Hinweis:

Die Musterlösungen werden nach dem Ende des Semesters wieder von der Seite genommen. Sie können dann aber immer noch bei Nachfrage erworben werden.
Zeit: Ort:
Gruppe 1: Mittwoch, 14.15-15.45 Uhr OH 14, 304
Gruppe 2: Donnerstag, 12.15-13.45 Uhr OH 14, 304

Übungsblätter:

Heimübungsblatt 1
Präsenzübungsblatt 1
Heimübungsblatt 2
Präsenzübungsblatt 2
Heimübungsblatt 3
Präsenzübungsblatt 3
Heimübungsblatt 4
Präsenzübungsblatt 4
Heimübungsblatt 5
Präsenzübungsblatt 5
Heimübungsblatt 6
Präsenzübungsblatt 6
Heimübungsblatt 7
Präsenzübungsblatt 7


Letzte Änderung am 6.2.2011 von C.Schwiegelshohn