Spezialvorlesung
"Approximations-und Online-Algorithmen"
Sommersemester 2003
Prof. Dr. Susanne Albers
Vorlesung
Montag, 14-16, und Mittwoch, 14-16, SR 00-034, Gebäude 051. Die Vorlesung am Mittwoch findet alle 14 Tage statt.
Übungen
Mittwoch, 14-16, SR 00-034, Gebäude 051. Die Übungen finden alle 14 Tage statt, im Wechsel mit der Vorlesung am Mittwoch.
Übungsblätter:
Übungsblatt 1
Übungsblatt 2
Übungsblatt 3
Übungsblatt 4
Übungsblatt 5
(Info zu CRS: Natürlich
muss man die Knoten (und damit die späteren
Verbindungen) zunächst "geeignet" klassifizieren, bevor man
dann mit
jeweils einer bestimmten Wkt. nur Verbindungen einer Klasse
zulässt)
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, daß 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+ epsilon)-Approximationen erzielen, für beliebiges epsilon > 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