Hauptinhalt
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]
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.
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.
Ü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.
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
