Approximationsalgorithmen (WS 2022/2023)

Aktuelles

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

Weitere Informationen folgen

Vorlesung

Dr. Annamaria Kovacs

Weitere Informationen folgen

Übungsbetrieb

Weitere Informationen folgen

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.

Es besteht die Möglichkeit, durch 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.

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

Weitere Informationen folgen

Materialien

Videoaufzeichnungen

Weitere Informationen folgen

Handschriftliches Skript

Approximationsalgorithmen 1

  • Weitere Informationen folgen

Approximationsalgorithmen 2

  • Weitere Informationen folgen

Folien

Approximationsalgorithmen 1

  • Weitere Informationen folgen

Approximationsalgorithmen 2

  • Weitere Informationen folgen

Übungen

Approximationsalgorithmen 1

  • Übungen folgen

Approximationsalgorithmen 2

  • Übungen folgen

LaTeX

Nützliches

LaTeX-Code zu den Übungsblättern

  • TeX-Dateien folgen

Klausuren und Prüfungsmaterial

  • Materialien und Themenblatt folgen
  • 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.