Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Algorithmen und Datenstrukturen

Wintersemester 2009/2010

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


[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.)


Begleitmaterial

Mitschrift (Stand: 23.02.09 (vorläufig))



Übungen

Übungsgruppen:

Zeit: Ort:
Gruppe 1: Dienstag, 16.15-17.45 Uhr OH 14, 304
Gruppe 2: Mittwoch, 8.15-9.45 Uhr OH 14, 304

Übungsblätter:

Präsenzblatt 1 (keine Abgabe, Besprechung am 21.10.09)
Übungsblatt 1 (Abgabe bis zum 21.10.09)
Präsenzblatt 2 (keine Abgabe, Besprechung am 04.11.09)
Übungsblatt 2 (Abgabe bis zum 04.11.09)
Präsenzblatt 3 (keine Abgabe, Besprechung am 18.11.09)
Übungsblatt 3 (Abgabe bis zum 18.11.09)
Präsenzblatt 4 (keine Abgabe, Besprechung am 25.11.09)
Übungsblatt 4 (Abgabe bis zum 02.12.09)
Zusatzinformationen zu Blatt 4
Präsenzblatt 5 (keine Abgabe, Besprechung am 16.12.09)
Übungsblatt 5 (Abgabe bis zum 16.12.09)
Präsenzblatt 6 (keine Abgabe, Besprechung am 11.01.09)
Zusatzinformationen zu Blatt 6
Übungsblatt 6 (Abgabe bis zum 16.12.09)
Präsenzblatt 7 (keine Abgabe, Besprechung am 27.01.09)
Übungsblatt 7 (Abgabe bis zum 27.12.09)


Letzte Änderung am 23.02.2009 von M.Schmidt