English English

Allgemeine Informationen

ECTS: 6
Sprache: Deutsch
Campus: hier
Art Wo / Wann Beginn Dozent
V3 Mi 10:15h - 11:45h / AH I
Fr 14:15h - 15:45h / AH VI
9. April 2014 Unger

Ü2 Mo 10:15 - 11:45 / 4017
Mo 16:15 - 17:45 / 4017
Mi 12:00 - 13:30 / 4017
Fr 10:15 - 11:45 / 4017
23. oder 25. 04.
23. oder 25. 04.
23. 04.
25. 04.
Al-Bawani / Radke


Aktuelles

  • Hier noch die kompakte Liste von Beispielfragen.
  • UPDATE: Neuer Abgabetermin der Übungszettel ist Dienstag 10:00 Uhr.
  • Am Mittwoch den 18.6. fällt die Vorlesun aus.
  • Die Webseite zur Terminfindung für die mündlichen Prüfungen ist hier.
    Studierende, welche die Punktehürde erreicht haben, bekommen von uns ein Passwort.
    Studierende, die noch eine Zulassung aus früheren Semestern haben, melden sich bitte bei uns.

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
  • Approximationsalgorithmen
  • Online-Algorithmen
  • Randomisierte Algorithmen


Übungen, Zulassung und Prüfung

  • Wir empfehlen sehr, die Übungszettel in Gruppen von bis zu 3 Studierenden zu bearbeiten.
  • Für die Zulassung zur Prüfung werden mindestens 50 Prozent der Übungspunkte benötigt.
  • Die Prüfung wird mündlich sein.

Übungsblätter


Folien

  • Aktueller Stand der der Vorlesung: Fertig

    Hilfreiche Literatur

    Neben dem Skript von Prof. Berthold Vöcking (Sommersemester 2011) eignen sich die folgenden Bücher als zusätzliche Literatur und stehen in der Informatikbibliothek zur Verfügung.

    Flüsse und Matchings:
    • Ahuja, Magnanti, Orlin: Network Flows - Theory, Algorithms, and Applications. Prentice Hall, 1993.
    • Cormen, Leiserson, Rivest: Introduction to Algorithms. MIT Press, 1990.
    • Ottmann, Widmayer: Algorithmen und Datenstrukturen. BI-Wiss.-Verl., 1990.
    Lineare Programmierung:
    • Chvátal: Linear Programming. Freeman, 1983.
    • Korte, Vygen: Combinatorial Optimization - Theory and Algorithms. Springer, 2000.
    Approximationsalgorithmen:
    • Vazirani: Approximation Algorithms, Springer, 2001.
    • Williamson, Shmoys: The Design of Approximation Algorithms, Campbidge University Press, 2011.
    • Hochbaum: Approximation Algorithms for NP-Hard Problems, Thomson Publishing, 1996.
    Online-Algorithmen:
    • Borodin, El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998.

    Kontakt

    Kamal Al-Bawani und Klaus Radke