Spezialvorlesung
"Approximations- und Online-Algorithmen"
Sommersemester 2005
Prof. Dr. Susanne Albers und Sylva Scholz
Vorlesung
Montag, 9 - 11 Uhr, und Mittwoch, 9 - 11 Uhr, SR 01-016, Gebäude 101. Die Vorlesung am Mittwoch findet alle 14 Tage statt.Übungen
Mittwoch, 9 - 11 Uhr, SR 01-016, Gebäude 101. Die Übungen finden alle 14 Tage statt, im Wechsel mit der Vorlesung am Mittwoch.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 kennenlernen, 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.
Kreditpunkte
In dieser Veranstaltung können 6 Kreditpunkte erworben werden.Prüfungen
Um Kreditpunkte zu erwerben, sind 50% der Übungen zu bearbeiten, die Hausaufgaben zweimal vorzurechnen und eine Abschlussprüfung zu bestehen.Übungsblätter
Übungsblatt 1 als Postscript.Übungsblatt 2 als Postscript.
Übungsblatt 3 als Postscript.
Übungsblatt 4 als Postscript.
Übungsblatt 5 als Postscript.
Übungsblatt 6 als Postscript.