64-334 Vorlesung Methoden des Algorithmenentwurfes

Lehrende: Prof. Dr. Petra Berenbrink; Prof. Dr. Peter Kling

Veranstaltungsart: Vorlesung

Anzeige im Stundenplan: MDAE-VL

Semesterwochenstunden: 4

Unterrichtssprache: Deutsch

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. 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.

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
  

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:
Je nach Teilnehmerzahl entweder eine mündliche Prüfung oder durch ein Referat am Ende des Semesters. Wird in der Vorlesung besprochen.