---

Vorlesung
"Approximations- und Online-Algorithmen"
Sommersemester 2006
Prof. Dr. Susanne Albers
Dr. Markus Schmidt
Sylva Scholz

---

Vorlesung

Mittwoch, 14 - 16 Uhr, und Donnerstag, 14 - 16 Uhr, SR 01-016, Gebäude 101. Die Vorlesung am Donnerstag findet alle 14 Tage statt. In den ersten beiden Vorlesungswochen (KW 17/18) ist jeweils sowohl mittwochs als auch donnerstags Vorlesung. An den beiden Mittwochen 31.05. und 21.06. findet keine Vorlesung statt, sondern werden die wegen Feiertagen verschobenen Übungen nachgeholt.

Übungen

Donnerstag, 14 - 16 Uhr, SR 01-016, Gebäude 101. Die Übungen finden alle 14 Tage statt, im Wechsel mit der Vorlesung am Donnerstag. Auf Grund der Feiertage Christi Himmelfahrt und Fronleichnam werden zwei Übungen auf den nachfolgenden Mittwoch verschoben. Die Übungen beginnen in der dritten Vorlesungswoche (KW 19) und finden somit an folgenden Tagen statt:

• Do. 11.05.2006
• Mi. 31.05.2006
• Mi. 21.06.2006
• Do. 29.06.2006
• Do. 13.07.2006
• Do. 27.07.2006

Inhalt der Veranstaltung

Effiziente Algorithmen werden in sehr vielen Bereichen der Informatik benötigt. Wer ein breites Wissen über die bekannten Entwurfsmethoden besitzt, ist in der Lage, sehr viele Probleme in der Informatik effizient zu lösen.

Während in der Kursvorlesung "Algorithmentheorie" grundlegende Probleme und Lösungen vorgestellt wurden, geht diese Vorlesung einen Schritt weiter: Wir werden uns mit jungen Problembereichen beschäftigen, die in den letzten zehn Jahren ein besonderes Forschungsinteresse erhalten haben. Dabei werden wir konkrete Probleme untersuchen, für die zum Teil beeindruckend schöne und elegante Lösungen vorgestellt worden sind. Die Schwerpunkte der Vorlesung liegen auf den folgenden Gebieten.

Online-Algorithmen: Beim klassischen Algorithmenentwurf geht man 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 kennen lernen, die mit solchen Bedingungen fertig werden.

Approximationsalgorithmen: Viele Optimierungsprobleme in der Praxis sind NP-hart. Ziel ist hier die Entwicklung von Näherungslösungen, die ein beweisbar gutes Verhalten aufweisen. Von besonderem Interesse sind Approximationsschemata, die in polynomieller Zeit (1+ ε)-Approximationen erzielen, für beliebiges ε > 0.

Die Vorlesung ist eine ideale Vorbereitung auf eine Studien- oder Diplomarbeit im Bereich Effiziente Algorithmen.

Literatur

• A. Borodin und R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
• V.V. Vazirani. Approximation Algorithms. Springer Verlag 2001.
  
• Vorlesungsmitschrift 2004
  

Kreditpunkte

In dieser Veranstaltung können 6 Kreditpunkte erworben werden.

Prüfungen

Um Kreditpunkte zu erwerben, sind 50% der Übungen zu bearbeiten, zweimal Übungsaufgaben vorzurechnen und eine Abschlussprüfung zu bestehen.

Übungsblätter

1. Übungsblatt
2. Übungsblatt
3. Übungsblatt
4. Übungsblatt
5. Übungsblatt
6. Übungsblatt