Beating the Worst Case
Dozenten: Jean-Pierre, Marcus
Campus-System: Veranstaltungsnr. 2400121
Plätze: 16
Anmeldung: Anmeldung mit Name und Matrikelnummer per Mail an Jean-Pierre heydt@kit.edu, alternativ einfach zum ersten Treffen kommen (first come first serve)
GitLab: Repo des Frameworks auf GitLab
Bei dem Praktikum Beating the Worst Case in Practice: Unerwartet effiziente Algorithmen beschäftigen wir uns mit Algorithmen, die auf praktischen Instanzen deutlich effizienter sind, als theoretische Worst-Case Analysen erwarten lassen. Diese unerwartete Effizienz wird im Rahmen des Praktikums mit empirischen Methoden untersucht. Hierfür geben wir verschiedene algorithmische Ansätze und Probleme vor, die von den Studierenden selbstständig implementiert und evaluiert werden.
Lernziele:
Die Studierenden
- können das in den Grundlagenmodulen zur Algorithmentechnik erlernte Wissen praktisch anwenden,
- sind in der Lage eigenständig effiziente Implementierungen algorithmischer Verfahren anzufertigen,
- beherrschen die Methodik zur praktischen Evaluierung von Algorithmen, inklusive der Aufarbeitung,
- Analyse und Interpretation von Messdaten,
- besitzen die Fähigkeit gefundene Ergebnisse zu kommunizieren.
Die Teilnehmer sind außerdem in der Lage zu analysieren, welchen Einfluss typische Eigenschaften von Instanzen auf die Effizienz von Algorithmen haben.
Ablauf:
Es gibt zwei Phasen. In der ersten Phase werden die Teilnehmer anhand von Übungsblättern schrittweise an die empirische Analyse einer algorithmischen Fragestellung herangeführt. Anschließend wird in der zweiten Phase das bereits Gelernte angewandt, um einen weiteren Algorithmus empirisch zu untersuchen. Die Arbeit erfolgt hierbei in kleinen Teams.
Wir treffen uns zum ersten Termin am 25. Oktober um 15:45 in Raum 301 im Informatikgebäude. Im ersten Treffen werden alle Details bezüglich des weiteren Ablaufs besprochen.
Folien werden auf dieser Webseite hochgeladen.
Material
Aufgabe 0: Aufwärmübung
- Aufgabenstellung: blatt00.pdf
- Rätselinstanzen: networks.zip
Aufgabe 1:
- Aufgabenstellung: blatt01.pdf
Aufgabe 2:
- Aufgabenstellung: blatt02.pdf
Aufgabe 3:
- Aufgabenstellung: blatt03.pdf
Aufgabe 4 / Ausarbeitung:
- Aufgabenstellung / Hinweise: blatt04.pdf
- Vorlage Ausarbeitung: LIPIcs (Template, Author Instructions)
Slides
- Intro-Slides: lecture01.pdf
- Treffen 2: lecture02.pdf Druckversion
- Treffen 3: lecture03.pdf Druckversion
- Treffen 4: lecture04.pdf Druckversion
- Treffen 5: lecture05.pdf Druckversion
- Treffen 6: lecture06.pdf Druckversion
- Treffen 7: lecture07.pdf Druckversion
- Treffen 8: lecture08.pdf Druckversion