Approximationsalgorithmen (WS 2020/2021)

Dieses Semester findet die Kommunikation mehr denn je über diese Webseite und E-Mails statt.
Bitte schauen Sie regelmäßig hier vorbei, und verwenden Sie Ihre studentische E-Mail-Adresse (…@stud.uni-frankfurt.de), wenn Sie uns E-Mails schreiben. Wir haben immer wieder Probleme, dass unsere Antworten in Spamfiltern landen.

Aktuelles

  • Selbsteinschreibung in Moodle freigeschaltet!


Vorlesung

Die Vorlesungen und Übungen werden in elektronischer Form stattfinden.

  • Die Vorlesungen werden von StudiumDigitale aufgezeichnet und online gestellt (sie werden nicht “live gestreamt”).
  • Eine Fragerunde (30-60 Min.) zu der Vorlesung findet jeden Donnerstag um 13:00 Uhr in Form eines Video-Meetings statt. Bitte beachten Sie, dass manche kleine Fragen aus dem Stoff erst während der Fragerunde im Detail diskutiert werden. Die Fragerunde wird aufgezeichnet.
  • Anschließend, um 14:15, findet ebenfalls dort die Übung statt.
    Den Zugang zu diesen Meetings finden Sie unter Moodle.

    • Die Teilnahme an den Übungen wird sehr empfohlen! Eine Plusnote zur Klausur kann erworben werden (siehe unten).
  • Das erste Treffen findet am Do. 5.11. um 13:00 (bis spätestens 14:00) statt. Hier werden wir uns vorstellen, Organisatorisches besprechen, und eine einführende Fragerunde machen.

  • Die Übung fällt in der ersten Vorlesungswoche aus.

  • Für manche Inhalte dieser Seite benötigen Sie Zugangsdaten. Diese erhalten Sie über Moodle.
    Sollten Sie noch keinen HRZ-Account haben, melden Sie sich bitte bei Mahyar Behdju.
  • Hier können Sie sich mit dem digitalen Klassenraum vertraut machen.

Teilnahmevoraussetzungen:

  • Im Master: keine.

  • Im Bachelor PO-2011: das Modul B-GL1. Im Bachelor PO11 enfällt die 8CP Variante, es gibt aber die Möglichkeit die 5 CP (APX1) oder 10 CP Variante (APX12) zu belegen.

  • Im Bachelor PO-2019: 25 CP aus den Basismodulen. Bitte beachten Sie, dass im Bachelor PO19 nur die erste Hälfte (APX1 5CP) angerechnet werden kann. (APX2 kann ggf. für ein zukünftiges Master Studium im Voraus angerechnet werden. Vom Prüfungsamt haben wir folgende Auskunft erhalten: ‘Mastermodule während des Bachelors dürfen “im Voraus” gemacht werden, wenn mindestens 115 CP im Bachelor erfolgreich erbracht wurden und die Basismodule abgeschlossen sind. Die Studierenden müssen die Prüfung dann schriftlich bei uns anmelden.’)

Den Zugangslink zum virtuellen Ingo-Wegener-Lernzentrum finden Sie auf OLAT.

Dr. Annamaria Kovacs

Donnerstag 13:00 - 14:00

Übungsbetrieb

Mahyar Behdju, Conrad Schecker

Donnerstag 14:00 - 16:00

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch das Lösen der Aufgaben 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 wurde.

Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Hinweise zu den Übungsabgaben

  • Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
  • Die Abgabefrist für ein Blatt endet am Samstag in der darauffolgenden Woche.
  • Da es eine Online-Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.

Zu Online-Abgabe:

  • Die Abgabe wird Ihnen automatisch zugeordnet; bitte vermerken Sie trotzdem Ihren Namen und Ihre Matrikelnummer darauf.
  • Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle 5 Minuten vor Schluss abgeben wollen.
  • Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
    • Am besten ist es, wenn Sie gleich LaTeX verwenden. Das ist gut lesbar und erzeugt kleine Dateien. Wir bieten auch eine LaTeX Vorlage an.
    • Zur Not können Sie Scans oder Bilder zu einer PDF 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.

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

Leistungsnachweise

Je nach Teilnehmerzahl findet die Modulabschlussprüfung mündlich oder schriftlich statt.
Termine und Räume werden hier rechtzeitig bekannt gegeben.

Materialien

Videoaufzeichnungen

Handschriftliches Skript

Approximationsalgorithmen 1

Approximationsalgorithmen 2

Folien

Approximationsalgorithmen 1

Approximationsalgorithmen 2

Übungen

Approximationsalgorithmen 1

Approximationsalgorithmen 2

LaTeX

Nützliches

LaTeX-Code zu den Übungsblättern

Klausuren und Prüfungsmaterial

  • Altklausuren finden Sie hier.

Skript und zusätzliche Literatur

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