Algorithmik ist die Kunst der Problemlösung. Sowohl im Berufs- als auch unserem alltäglichen Leben werden wir regelmäßig mit algorithmischen Problemen und deren Lösungen konfrontiert. Das reicht von einfachen Navigationsproblemen (“Was ist die schnellste Strecke von Köln nach Hamburg unter der laufenden Berücksichtigung der Verkehrslage?”), über die automatische Filterung der Informationsflut im Internet (Google) bis hin zu komplexen Optimierungsaufgaben in der Berufswelt. Der Entwurf von beweisbar effizienten Algorithmen und deren Analyse gehört zum Kernbereich der Informatik. Die Vorlesung vertieft diese Kompetenz mittels weiterführender Methoden für den Entwurf und die Analyse von Algorithmen. Neben einem Überblick über Standardmethoden aus den Gebieten der Approximations-, Online-, randomisierten und kombinatorischen Algorithmen wird zumindest eines diser Themen vertief behandelt. Dabei werden wir sowohl auf klassische als auch aktuelle Forschungsergebnisse eingehen.

Weitere Informationen zum Modul sind in STiNE zu finden.

Aktuelles

• 2017-06-19

  Die Vorlesung fällt am Mittwoch dem, 21. Juni, aufgrund des Dies Academicus aus.

• 2017-04-11

  Die Vorlesung findet ab sofort in Raum F-132 statt.

• 2017-04-10

  Vorlesungs-/Seminarzeiten angepasst (siehe unten).

• 2017-04-01

  Die Vorlesung startet am Mittwoch, dem 5. April.

• 2017-03-31

  Der Übungs-/Seminarbetrieb startet in der zweiten Vorlesungswoche (10. bis 14. April).

Allgemeine Informationen

Veranstalter: Dr. Peter Kling und Prof. Dr. Petra Berenbrink

Zeit & Ort:

• Vorlesung
  • Montags, 8:15 - 9:45 in F-132
• Vorlesung + Übung
  • Mittwochs, 8:00 - 10:00 in F-132
• Blockseminar
  • Dienstag, der 18. Juli, und Mittwoch, der 19. Juli
  • jeweils ab 8:30 in F-132
  • Programm
  • Folien der Vorträge

Prüfungsmodalitäten

Anmeldung für die mündliche Modulprüfung erfolgt direkt bei Dr. Peter Kling. Anmeldeformulare sind auf der Homepage des Studienbüros zu finden.

• 1. Prüfungsblock: 1. August und 2. August, jeweils ab 10 Uhr
• 2. Prüfungsblock: 26. September und 27. September, jeweils ab 10 Uhr

Terminvergabe:

• Melden Sie sich zunächst informell per E-Mail(peter.kling"AT"uni-hamburg.de) bis spätestens zum 30. Juni 2017 an.
• Geben Sie in der E-Mail an, in welchem Prüfungsblock sie geprüft werden möchten.
• Sie bekommen anschließend per E-Mail einen genauen Prüfungstermin zugewiesen.
• Das ausgefüllte Anmeldeformular ist bis spätestens 1 Woche vor dem Prüfungstermin bei Dr. Peter Kling oder im ART Sekretariat abzugeben.

Übungsblätter

Hier werden regelmäßig Übungsblätter erscheinen. Diese sind freiwillig zu bearbeiten. Lösungen werden in den Übungen von den Studenten vorgetragen und zusammen diskutiert.

• Übungsblatt 1
• Übungsblatt 2
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5

Literatur

Vorlesungsmaterialien sind zum Teil auf Deusch und zum Teil auf Englisch. Die Vorlesung basiert unter anderem auf folgender Literatur:

• Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA.
• The Design of Competitive Online Algorithms Via a Primal-Dual Approach. Now publishers Inc.
• Vijay V. Vazirani. 2010. Approximation Algorithms. Springer Publishing Company, Incorporated.

Inhaltsübersicht

Die folgende Inhaltsübersicht der Vorlesung ist ohne Gewähr und wird laufend weiterentwickelt. Gegebenenfalls wird zu einzelnen Kapiteln auch hilfreiche Literatur angegeben. Die Vorlesung enthält allerdings auch Stoff, der über die angegebene Literatur hinaus geht.

• Kapitel 1: Klassische Optimierungsprobleme
• Kapitel 2: Online Optimierungsprobleme
• Kapitel 3: Das List Accessing Problem
  • Literatur: Kapitel 1 von „Online Computation and Competitive Analysis“
• Kapitel 4: Randomisierung in Online Algorithmen
  • Literatur: Kapitel 2 von „Online Computation and Competitive Analysis“
• Kapitel 5: Paging
  • Literatur: Kapitel 3 von „Online Computation and Competitive Analysis“
• Kapitel 6: Randomized Paging
  • Literatur: Kapitel 4 von „Online Computation and Competitive Analysis“
• Kapitel 7: Das k-Server Problem
  • Literatur: Kapitel 10 von „Online Computation and Competitive Analysis“
• Kapitel 8: Scheduling
  • Literatur: Kapitel 12 von „Online Computation and Competitive Analysis“