64-334 Vorlesung Methoden des Algorithmenentwurfes

Lehrende: Prof. Dr. Peter Kling

Veranstaltungsart: Vorlesung

Anzeige im Stundenplan: MDAE-VL

Semesterwochenstunden: 4

Unterrichtssprache: Deutsch / Englisch

Min. | Max. Teilnehmerzahl: - | 20

Kommentare/ Inhalte:
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. Diese reichen 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.

Homepage: https://www.inf.uni-hamburg.de/en/inst/ab/tea/teaching/2019-ss/mdae.html

Lernziel:

• Entwurf und Analyse beweisbar effizienter Algorithmen
  
• Übersicht über sowohl klassische als auch aktuelle Methoden des Algorithmen Designs
  
• Fähigkeit theoretische Forschungspapiere aus dem Bereich der Algorithmik zu verstehen
  
• Kenntnisse der wichtigsten aktuellen Beweis- und Entwurfstechniken für Algorithmen Design
  
• Fähigkeit das erlernte Wissen selbständig auf neue Probleme anzuwenden
  

Vorgehen:
Die Vorlesung besitzt einen integrierten Übungsanteil. Hierfür haben die Teilnehmer in Heimarbeit Übungsaufgaben zu bearbeiten. Die Lösungen werden anschließend in der Vorlesung an der Tafel von den Studenten präsentiert und zusammen diskutiert. Die Bearbeitung der Übungsaufgaben sowie deren Präsentation und Diskussion sind Teil der Studienleistung. 

Der genaue Ablauf des zum Modul gehörigen Seminars wird in der ersten Vorlesungsstunde besprochen. Sollte sich eine beträchtliche Mehrheit finden, kann das Seminar gegebenenfalls auch als Blockseminar gegen Semesterende gehalten werden.

Literatur:
Unter Anderem eine Auswahl von:

• verschiedene Forschungspapieren
  
• Vijay V. Vazirani. 2010. Approximation Algorithms. Springer Publishing Company, Incorporated.
  
• Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA.
  
• Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA.
  
• Niv Buchbinder and Joseph (Seffi) Naor. 2009. The Design of Competitive Online Algorithms Via a Primal-Dual Approach. Now publishers Inc.
  

Zusätzliche Hinweise zu Prüfungen:
Die Modulprüfung findet voraussichtlich als mündliche Prüfung statt. Sie umfasst Inhalte aus der Vorlesung (und der integrierten Übung) sowie aus dem zugehörigen Seminar. Sollte die Anzahl der Teilnehmer unerwartet hoch sein, wird gegebenenfalls auf eine schriftliche Klausur zurückgegriffen. Dies wird in der ersten Vorlesungsstunde besprochen.