64-334 Vorlesung Methoden des Algorithmenentwurfes

Lehrende

Prof. Dr. Peter Kling

Zeit/Ort:

Mo 14 - 16, G-021/022
Fr 12 - 14, G-021/022

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/2023-ss/mdae.html (ab 1. März 2023)

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. Vorträge erfolgen zu Semesterende an einem Blocktermin.

Literatur:

Unter Anderem eine Auswahl von:

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