====== Proseminar: Algorithmen für NP-Schwere Probleme ====== == im Sommersemester 2023 == ===== Thema ===== 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. ===== Aktuelles ===== * Die Homepage wurde eingerichtet. * Allgemeine Informationen zum Ablauf eingetragen * Die Themenverteilung wurde veröffentlicht ===== Voraussetzungen ===== * 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. ===== Allgemeines ===== * **Organisation:** [[people:maxgoettlicher|Max Göttlicher]], [[people:thomasblaesius|Thomas Bläsius]] und [[https://i11www.iti.kit.edu/members/torsten_ueckerdt/|Torsten Ueckerdt]] * **Ort:** [[http://www.kit.edu/campusplan/index.php?id=50.34|Gebäude 50.34, Raum 301]] ([[https://goo.gl/maps/S4PJmif8xY22|Am Fasanengarten 5, 76131 Karlsruhe]]). * **Zeit:** Montags von 11:30 Uhr bis 13:00 Uhr. * **Sprache:** Die Proseminarsprache ist Deutsch. ===== Quellen und Betreuung ===== * 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. ===== Anmeldung ===== * Alle Plätze sind belegt. ===== Ablauf ===== * 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. ===== Zeitplan ===== Vorläufiger Zeitplan ^ Datum ^ Thema ^ Vortragende ^ Betreuung ^ | 17.04 | {{ :teaching:2023ss:proseminar:topics-presentation.pdf | Einführung und Themenvergabe}} | Max | – | | 24.04. | {{ :teaching:2023ss:proseminar:how-to-give-a-talk.pdf |How To Vortrag}} und {{ :teaching:2023ss:proseminar:intro-slides.pdf |How to Introduction}} (mit {{ :teaching:2023ss:proseminar:intro.pdf |Beispiel}}) | Torsten | – | | 8.05. ^ Kurzvorträge | alle | alle | | 5.06. ^ Parameterized Algorithms II | Oliver | [[https://i11www.iti.kit.edu/members/paul_jungeblut/|Paul Jungeblut]] | | | Kapitel 2.3, 2.4; Seiten 35–42 | | | | ^ From Adaptive Analysis to Instance Optimality | Yuqi | [[:people:michaelzuendorf|Michael Zündorf]] | | | Kapitel 3.1, 3.2.1; Seiten 52–61 | | | | 12.06. ^ Parameterized Algorithms I | Nikola | [[https://i11www.iti.kit.edu/members/laura_merker/|Laura Merker]] | | | Kapitel 2.1, 2.2; Seiten 27–34 | | | | ^ Resource Augmentation | Marc | [[:people:maxgoettlicher|Max Göttlicher]] | | | Kapitel 4.1, 4.2, 4.5; Seiten 72–76, 86–89 | | | | 19.06. ^ Perturbation Resilience | Linus | [[:people:adrianfeilhauer|Adrian Feilhauer]] | | | Kapitel 5.1, 5.2, 5.4; Seiten 95–100, 106f | | | | ^ Approximation Stability and Proxy Objectives | Patrick | [[https://i11www.iti.kit.edu/members/torsten_ueckerdt/|Torsten Ueckerdt]] | | | Kapitel 6.1, 6.2, 6.3.1, 6.3.2; Seiten 120–126, 135f | | | | 26.06. ^ Distributional Analysis | Florian | [[https://i11www.iti.kit.edu/members/jonas_sauer/|Jonas Sauer]] | | | Kapitel 8.1, 8.2; Seiten 167–174 | | | | ^ Distributional Analysis | Fynn | [[:people:marcuswilhelm|Marcus Wilhelm]] | | | Kapitel 8.3, 8.4; Seiten 175–182 | | | | 03.07. ^ Random Order Models | Nadine | [[:people:christopherweyand|Christopher Weyand]] | | | Kapitel 11.1, 11.2, 11.3.1; Seiten 234–240 | | | | ^ SAT Solver | Nils | [[:people:thomasblaesius|Thomas Bläsius]] | | | Kapitel 25.1, 25.2; Seiten 547–554 | | | | 10.07. ^ Distribution Free Models of Social Networks | Leo | [[:people:maximiliankatzmann|Maximilian Katzmann]] | | | Kapitel 28.1, 28.2; Seiten 606–612 | | | | ^ Distribution Free Models of Social Networks | Konstantin | [[:people:wendyyi|Wendy Yi]] | | | Kapitel 28.3, 28.4; Seiten 606, 612–619 | | | | 17.07. ^ From Adaptive Analysis to Instance Optimality | Yuqi | [[:people:michaelzuendorf|Michael Zündorf]] | |Ausweichtermin| Kapitel 3.1, 3.2.1; Seiten 52–61 | | | | | | | | ===== Vorlagen ===== Für die Ausarbeitung verwenden Sie bitte {{ :teaching:2023ss:proseminar:iti-vorlage-seminarausarbeitung.zip |diese Vorlage}}.