Approximationsalgorithmen (WS 2024/2025)

user: apa24
pwd: dasselbe doppelt

Aktuelles

Vorlesung

Dr. Annamaria Kovacs

Mittwoch, 10:15 Uhr – 11:45 Uhr, Magnus-Hörsaal (Informatik-Gebäude)
Donnerstag, 12:15 Uhr – 13:45 Uhr, H8 (Hörsaalgebäude)

QIS: APX1, APX12, APX2.

Übungsbetrieb

Kontakt für Fragen und Anmerkungen: Conrad Schecker (schecker@em.uni-frankfurt.de)

Gruppe 1 (Lukas Geis): Donnerstag, 14:15 – 15:45 Uhr, SR11 (Informatik-Gebäude)
Gruppe 2 (Conrad Schecker): Donnerstag, 16:15 – 17:45 Uhr, SR11 (Informatik-Gebäude)

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch selbstständiges Lösen der Übungsaufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch die erfolgreiche Teilnahme am Übungsbetrieb eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden und im Tutorium mindestens einmal vorgerechnet wurde.

• Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
• Die Abgabefrist für ein Übungsblatt endet am Samstag in der darauffolgenden Woche um 12:00 Uhr.
• Die Abgabe erfolgt online über einen individuellen Link, den Sie nach erfolgter Anmeldung erhalten haben.
• Die Zuordnung der Abgaben erfolgt automatisch. Dennoch schadet es nicht, Namen oder Matrikelnummer darauf zu vermerken.
• Wir nehmen Abgaben in Form von einer PDF-Datei mit maximal 10MB entgegen. Schwer lesbare Abgaben werden nicht bewertet.
  • Gut lesbare und kleine Dateien erhält man bei der Verwendung von LaTeX. Wir bieten auch eine LaTeX Vorlage an.
  • Alternativ können Sie auch Scans oder Bilder zu einer PDF-Datei zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.
• Laden Sie Ihre Lösung nicht in letzter Minute hoch. Ein reibungsloser Ablauf kann ansonsten nicht garantiert werden.
• Vergewissern Sie sich, die korrekte Datei hochgeladen zu haben.

Plagiate und KI-Tools

Es wird empfohlen, in Gruppen über die Aufgaben zu diskutieren, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Zur Lösung der Aufgaben ist es nicht nötig, externe Quellen zu verwenden, sofern nicht anders angegeben. Sollten dennoch Quellen verwendet werden, die nicht von uns bereitgestellt wurden, sind diese nach den Regeln der guten wissenschaftlichen Praxis anzugeben. Insbesondere ist die Eigenleistung eindeutig zu kennzeichnen, denn nur diese wird bewertet. Die Verwendung von KI-Tools ist untersagt. Abgaben, die plagiierte, kopierte oder nicht selbstständig erarbeitete Lösungen enthalten, werden für jeden Betroffenen mit 0 Punkten bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Aktive Beteiligung am Tutorium

Um eine Bonifikation für die Prüfung zu erhalten, muss mindestens einmal im Tutorium vorgerechnet werden. Danach besteht die Möglichkeit, durch erneutes Vorrechnen in den Tutorien Bonuspunkte zu erwerben, welche zu den erworbenen Übungspunkten hinzuaddiert werden. Dabei gelten die folgenden Regeln:

• Pro Übungsblatt wird der Bonus höchstens einmal pro Person vergeben.
• Beim ersten Vorrechnen gibt es 5 Bonuspunkte.
• Beim zweiten Vorrechnen gibt es 4 Bonuspunkte.
• Beim dritten Vorrechnen gibt es 3 Bonuspunkte.
• Beim vierten Vorrechnen gibt es 2 Bonuspunkte.
• Jedes weitere Vorrechnen gibt 1 Bonuspunkt.

Inhalt

Die Veranstaltung befasst sich mit verschiedenen Algorithmenklassen und deren Analyse. Hierzu gehören:

• Greedy-Algorithmen und Heuristiken
• Dynamische Programmierung
• Lokale Suche
• Branch & Bound
• Lineare Programmierung

Dabei werden Approximationsalgorithmen für fundamentale Probleme, wie etwa Bin Packing, Scheduling-, Clustering- und Graph-Probleme, untersucht.

Literaturhinweise

Skript

Es steht das Skript von Herrn Prof. Dr. Georg Schnitger zum Download bereit, an dem sich diese Veranstaltung orientiert.

Zusätzliche Literatur

• Vijay V. Vazirani: Approximation Algorithms, Springer, 2001
• David P. Williamson, David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011
• Dimitris Bertsimas, John N. Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997
• Christopher Moore, Stephan Mertens: The Nature of Computation, Kapitel 9, S. 351–449, Oxford University Press, 2011
• Klaus Jansen, Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008
• Rolf Wanka: Approximationsalgorithmen – Eine Einführung, Teubner, 2006

Leistungsnachweise

Weitere Informationen folgen

Materialien

Videoaufzeichnungen

Weitere Informationen folgen

Handschriftliches Skript

Approximationsalgorithmen 1

• SKRIPT 1

• SKRIPT 2

• SKRIPT 3

• SKRIPT 4

• SKRIPT 5

• SKRIPT 6

• SKRIPT 7

• SKRIPT 8

Approximationsalgorithmen 2

• SKRIPT 9

• SKRIPT 10

Folien

Approximationsalgorithmen 1

• Einführung
• Greedy
• Lokale Suche
• Dynamische Programmierung
• Lineare Programmierung und Empfohlene Lesung

Approximationsalgorithmen 2

• LP Dualität

Übungsblätter

Approximationsalgorithmen 1

• Übungsblatt 1. Abgabe: 26.10.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 2. Abgabe: 02.11.2024, 12:00 Uhr.
• Übungsblatt 3. Abgabe: 09.11.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 4. Abgabe: 16.11.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 5. Abgabe: 23.11.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 6. Abgabe: 30.11.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 7. Abgabe: 07.12.2024, 12:00 Uhr.

Approximationsalgorithmen 2

• Übungsblatt 8. Abgabe: 14.12.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 9. Abgabe: 21.12.2024, 12:00 Uhr. LaTeX-Datei.
• Übungsblatt 10. Abgabe: 18.01.2025, 12:00 Uhr.

LaTeX

Nützliches

• LaTeX-Vorlage
• LaTeX-Cheat-Sheet

Klausuren und Prüfungsmaterial

• Altklausuren finden Sie hier