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.
Die Studierenden
Die Teilnehmer sind außerdem in der Lage zu analysieren, welchen Einfluss typische Eigenschaften von Instanzen auf die Effizienz von Algorithmen haben.
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.
Aufgabe 0: Aufwärmübung
Aufgabe 1:
Aufgabe 2:
Aufgabe 3:
Aufgabe 4 / Ausarbeitung: