Die 2. mündliche Prüfung findet am 19. September 2017 im Raum II.67 im LBH statt. Um die genaue Uhrzeit Ihrer Prüfung zu erfahren, schicken Sie bitte eine E-Mail an Adrian Schmitz.

In Online-Berechnungen muss ein Algorithmus beim Eintreffen von Anforderungen Entscheidungen treffen, ohne Kenntnis über zukünftige Entwicklungen zu haben. Dies ist eine in der Praxis häufig anzutreffende Situation. Man denke nur an Fragen wie:

• Welcher Block soll aus dem Cache entfernt werden, wenn er voll ist?
• Über welche Knoten soll der nächste Telefonanruf laufen?

Einmal getroffene Entscheidungen können sich später als suboptimal herausstellen, da sich die Zukunft anders entwickelt hat als angenommen. Die Qualität eines Online-Algorithms wird häufig durch Vergleich mit dem Resultat bestimmt, das ein Algorithmus erreichen würde, der alle Anforderungen von vorneherein kennt. Die Vorlesung wird anhand zahlreicher typischer Probleme grundlegende Techniken dieses Teilgebiets der Algorithmik behandeln.

• Vorlesungsnotizen

• Übungsblatt 1 (Besprechung am 4.Mai)
• Übungsblatt 2 (Besprechung am 11.Mai)
• Übungsblatt 3 (Besprechung am 18.Mai)
• Übungsblatt 4 (Besprechung am 24.Mai)
• Übungsblatt 5 (Besprechung am 1.Juni)
• Übungsblatt 6 (Besprechung am 14.Juni)
• Übungsblatt 7 (Besprechung am 22.Juni)
• Übungsblatt 8 (Besprechung am 6.Juli)
• Übungsblatt 9 (Besprechung am 13.Juli)
• Übungsblatt 10 (Besprechung am 20.Juli)