Proseminar: Algorithmen für NP-Schwere Probleme

Bei der Betrachtung des Laufzeitverhaltens von Algorithmen wird häufig der langsamste Fall als Unterscheidungskriterium angeführt. Viele Algorithmen schneiden aber in der Praxis wesentlich besser ab, als es diese Worst-Case Analyse vermuten lassen würde. Ein bekanntes Beispiel dafür ist der Quicksort-Algorithmus, dessen Laufzeit im schlimmsten Fall O(n²) beträgt, der aber in der Praxis schneller ist als viele andere Sortieralgorithmen mit geringerer asymptotischer Laufzeit. Besonders auffällig ist dieses Phänomen jedoch wenn man NP-schwere Probleme betrachtet, die auf echten Instanzen oft erstaunlich effizient gelöst werden können.

In diesem Proseminar werden wir alternative Methoden zur Laufzeitanalyse mit erweiterten Modellen kennen lernen, die weitere Faktoren einbeziehen und dadurch eine genauere Einordnung der tatsächlich zu erwartenden Laufzeit ermöglichen. Weiter werden wir praktische Beispiele dieser erweiterten Laufzeitanalysemethoden betrachten.

• Die Homepage wurde eingerichtet.
• Allgemeine Informationen zum Ablauf eingetragen
• Die Themenverteilung wurde veröffentlicht

• Dieses Proseminar basiert auf und vertieft algorithmische Kenntnisse aus der Vorlesung “Theoretische Grundlagen der Informatik”.
• Die Kenntnis von Graphen, grundlegenden Algorithmentechniken und Komplexitätsklassen wird vorausgesetzt.

• Organisation: Max Göttlicher, Thomas Bläsius und Torsten Ueckerdt
• Ort: Gebäude 50.34, Raum 301 (Am Fasanengarten 5, 76131 Karlsruhe).
• Zeit: Montags von 11:30 Uhr bis 13:00 Uhr.
• Sprache: Die Proseminarsprache ist Deutsch.

• Jeder Teilnehmer erhält ein Auszug aus einem Buch zur eigenhändigen Bearbeitung.
• Das Proseminar basiert auf dem Buch Beyond the Worst-Case Analysis of Algorithms von Tim Roughgarden (Hrsg.), erhältlich als E-Ressource in der KIT-Bibliothek: https://primo.bibliothek.kit.edu/permalink/f/coi3a3/KITSRC1745081291
• Die Themen werden am 17.04. vorgestellt und verteilt.
• Jeder Teilnehmer wird von einem Mitarbeiter betreut. Dieser Mitarbeiter steht für Fragen und Hinweise nach voriger Absprache zur Verfügung.

• Alle Plätze sind belegt.

• Alle Seminarteilnehmer:innen halten einen fünfminütigen Kurzvortrag und einen 35-minütigen Vortrag im Proseminar und steht danach für Fragen der anderen Teilnehmer:innen zur Verfügung.
• Eine regelmäßige Teilnahme am Seminar wird vorausgesetzt.
• Spätestens zwei Wochen vor dem Vortragstermin ist das Vortragskonzept mit den jeweiligen Betreuer:innen zu besprechen.
• Ein vorläufiger Foliensatz ist eine Woche vor dem eigenen Vortrag bei der jeweiligen Betreuer:in abzugeben.
• Wir empfehlen zu Beginn der Ausarbeitung eine grobe Gliederung mit den jeweiligen Betreuer:innen abzusprechen
• Die Ausarbeitungen sind spätestens am 17.07. für Feedback an die jeweiligen Betreuer:in abzugeben. Die finale Abgabe erfolgt am 31.07.
• Die Seminarnote ergibt sich aus der Note für den Vortrag und die Ausarbeitung, sowie der Beteiligung am Seminar.

Vorläufiger Zeitplan

Für die Ausarbeitung verwenden Sie bitte diese Vorlage.