LEA

Online- und Approximationsalgorithmen

News

  • Die Vorlesung am Mittwoch, 09.07.2014 wurde auf den 07.07.2014 von 16-18 Uhr in Raum 02.13.010 verlegt.
  • Die Vorlesung am Mittwoch, 02.07.2014 entfällt
  • Die mündliche Klausur wird am 18.07.2014 stattfinden.
  • Aufgrund der Oster-Feiertage und der Fachschaftsversammlung am Mittwoch den 23. April wird es am 24. April von 14-16 Uhr einen zusätzlichen Vorlesungstermin in Raum 03.13.054 geben.

Vorlesung

  • Dozent:
    Prof. Dr. Susanne Albers
  • Modul: IN2304, TUMonline
  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
    Wahlpflichtvorlesung im Gebiet Algorithmen
  • Zeit und Ort:
    Montag, 14:00–16:00, 00.08.038
    Mittwoch, 10:00–12:00, 00.08.038
  • Übung:
    Mittwoch, 13:00–14:30, Raum 01.11.018
    Übungsleitung: Moritz Fuchs
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • ECTS: 8 Punkte
  • Voraussetzungen:
    Stoff des Informatik Grundstudiums
    Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
  • Klausurtermin:
    18.07.2014 (mündlich)

Inhalt

In der internationalen Algorithmenforschung bildet die Entwicklung von Online- und Approximationsalgorithmen seit geraumer Zeit einen Arbeitschwerpunkt. Ziel ist die Entwicklung von Näherungslösungen für Probleme, die schwer oder gar nicht exakt gelöst werden können.

Online-Algorithmen

Der klassische Algorithmenentwurf geht davon aus, dass die zur Lösung eines Problems benötigten Daten zu Beginn der Berechnungen vollständig vorliegen. In vielen praktischen Problemen treffen Eingabedaten jedoch online, d.h. nach und nach im Laufe der Zeit ein. Wir werden Algorithmen entwickeln, die mit solchen Bedingungen fertig werden. Wir werden insbesondere Probleme in der Datenstrukturierung, der Ressourcenverwaltung auf Betriebssystemebene, der Robotik und in großen Netzwerken untersuchen.

Approximationsalgorithmen

Viele Optimierungsprobleme in der Praxis sind NP-hart. Ziel ist wieder die Entwicklung von Näherungslösungen, die ein beweisbar gutes Verhalten aufweisen. Von besonderem Interesse sind Approximationsschemata, die in polynomieller Zeit (1+e)-Approximationen erzielen, wobei e > 0 beliebig ist. Wir werden Approximationsalgorithmen für klassische Optimierungsprobleme entwerfen. Neben dem Algorithmenentwurf liegt der Schwerpunkt der Veranstaltung auf der gründlichen mathematischen Analyse der vorgestellten Strategien und Lösungen.

Folien

Folien zu Online-Algorithmen sind hier verfügbar (werden jede Woche ergänzt).

Literatur

  • A. Borodin und R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, 1998. ISBN 0-521-56392-5
  • V.V. Vazirani. Approximation Algorithms. Springer Verlag, Berlin, 2001. ISBN 3-540-65367-8