Algorithmen und Datenstrukturen 2
WiSe-2021/22- Course codes: B-ALGO-2→ALGO2
- External links:
Overview
Übersicht
- Ab sofort finden die Veranstaltungen Di/Do 8:00-9:45 vollständig online statt:
- Der Zoom-Link hat die Meeting-ID 966 9678 8856 und den Passcode 004040. Bei schlechter Internetverbindung kann man sich auch telefonisch einwählen unter der Nummer
+49 69 3807 9883
. - Zeiten:
- 8:00-8:15 auf Zoom. Besprechung, Tipps, Überblick, Einordnung, Beispiele.
- 8:15-9:15 auf Discord. Die Tutor:innen sind auf Discord verfügbar! Arbeiten Sie dort in Gruppen und rufen Sie die Tutor:innen!
- 9:15-9:45 auf Zoom. Lösungsspaziergang. (Sie dürfen keine Screenshots oder Mitschnitte machen, weitergeben oder empfangen!)
- Die Helpdesks finden weiterhin als Mix zwischen Online und Präsenz statt.
- Der Zoom-Link hat die Meeting-ID 966 9678 8856 und den Passcode 004040. Bei schlechter Internetverbindung kann man sich auch telefonisch einwählen unter der Nummer
- Moodle. Die meisten Lernangebote und Informationen finden sich in Moodle.
- Bei wichtigen Fragen: Sie erreichen den senior staff unter algo221@uni-frankfurt.de (nicht: dell@ oder moodle)
Wochenplan
Die Veranstaltung dauert 15 Wochen, die Pläne sind vorläufig:
Einführung und All-Pairs Shortest Paths
Network Flow I: Max-flow min-cut theorem, augmenting paths, Ford-Fulkerson
Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths
Amortisierte Analyse: Dynamische Tabellen, MultiPop Stacks, Splay Trees
Randomisierte Algorithmen I: Contention resolution, Minimum cut
Randomisierte Algorithmen II: Selection, Quicksort
Hartnäckigkeit I: Sprachen, Polynomialzeitreduktionen
Hartnäckigkeit II: P, NP, NP-Vollständigkeit
Recap I
Berechnungsmodelle: Endliche Automaten, Turing-Maschinen, Nicht-Determinismus, starke Church-Turing Hypothese, Word-RAM
Berechenbarkeit: Halteproblem, Satz von Rice
Lineare Programmierung I: Konvexität, Polytope, Simplex-Algorithmus
Lineare Programmierung II: Dualität, Integrale Lineare Programmierung
Algorithmen für NP-schwere Probleme: Approximationsalgorithmen für Vertex-Cover durch LP-Relaxierung, Randomisiertes Runden, Greedy; FPT-Algorithmus für Vertex-Cover durch Bounded Search Trees
Recap II
Literatur
- E: Algorithms von Jeff Erickson. [pdf · web]. (Ein wunderschönes Buch.)
- KT: Algorithm Design von Jon Kleinberg und Éva Tardos. [pdf · e-UB · UB]. (Ein modernes Buch, das die verschiedenen Entwurfsmethoden in den Mittelpunkt stellt, anstatt einzelner Probleme.)
- CLRS: Algorithmen – Eine Einführung (4. Auflage) von Cormen, Leiserson, Rivest, Stein. [e-UB]. (Das Standardwerk.)
- C: Linear Programming von Vašek Chvátal. [UB] (Für eine Einführung in die Lineare Programmierung.)
- V: Approximation Algorithms von Vijay V. Vazirani [e-UB · UB] (Für eine Einführung in Approximationsalgorithmen.)
- CFKLMPPS: Parameterized Algorithms von Cygan, Fomin, Kowalik, et al. [pdf · e-UB · UB] (Für eine Einführung in parametrisierte Algorithmen.)
Lernziele
Nach der Veranstaltung können die Studierenden:
- Algorithmen und Datenstrukturen aus dem erweiterten Grundkanon und den Vertiefungsgebieten beschreiben, anwenden, und implementieren,
- sie an neue Problemstellungen anpassen,
- Eigenschaften (wie etwa die Komplexität und Korrektheit) dieser und ähnlicher Algorithmen untersuchen und begründen,
- neue Algorithmen für verwandte Problemstellungen entwickeln.
Außerdem können die Studierenden:
- Wichtige Ergebnisse und Konzepte in den Bereichen der NP-Vollständigkeit und Entscheidbarkeit wiedergeben, anwenden, und erläutern,
- einschätzen, welche praktischen und theoretischen Konsequenzen die Hartnäckigkeit eines Problems hat,
- untersuchen und begründen, ob und warum ein gegebenes Problem hartnäckig ist.
Inhalt
- Erweiterter Grundkanon von Algorithmen und Datenstrukturen: All Pairs Shortest Paths, Network Flow, Amortisierte Analyse, Randomisierte Algorithmen, Lineare Programmierung
- Hartnäckigkeit: Reduktionen, P und NP, NP-Vollständigkeit, Berechenbarkeit
- Vertiefungsgebiete, die in der Frankfurter Theorie vertreten sind: Approximationsalgorithmen, Parametrisierte Algorithmen, und weitere.
Allgemeines
- Kursformat.
- Präsenzelemente: Betreute Gruppenarbeit, Lösungsspaziergänge, Besprechungen im Plenum.
- Online-Elemente: Videos, Folien, Literatur, Übungsblätter, ⭐-Aufgaben, 🌱-Aufgaben, Chat, Helpdesk, individuelles Feedback auf ⭐-Aufgaben.
- Voraussetzungen. Der Kurs baut auf Algorithmen und Datenstrukturen 1 (ALGO1) auf. Sie müssen die Kompetenzen aus ALGO1 bereits meistern, um an ALGO2 teilnehmen zu können.
- Anmeldung. Bitte melden Sie sich in Moodle an. Eine Anmeldung per E-Mail ist nicht nötig! Auch die Anmeldung zur Klausur erfolgt nur über QIS oder das Prüfungsamt.
- E-Mail. Nur bei organisatorischen Anliegen (Nachteilsausgleich, Prüfungsvarianten, etc.): E-Mail an algo221@uni-frankfurt.de.
Vorlesungsteam
- Holger Dell (Professor)
- Claudia Gressler (Sekretärin)
- Leo Krull (Dozentin)
- Anselm Haak (Dozent)
- Marius Hagemann (2x Tutor)
- Alexander Hengstmann (2x Tutor)
- Tolga Tel (2x Tutor)
- Aura Sofia Lohr (Tutorin)
- Julian Lorenz (Tutor)
- Melvin Kallmayer (Tutor)
- Julian Mende (Tutor)
- Timo Mertin (Tutor)
- Jonas Strauch (Tutor)
- Marc Viel (Tutor)
Klausur
- Klausur: 22.02.2022 · Klausuraufgaben · Musterlösung
- Nachklausur: 05.04.2022 · Klausuraufgaben · Musterlösung
- Weitere Hinweise zur Klausur finden Sie ganz oben in Moodle.
Ähnliche Kurse
- Algorithms and Data Structures II von Inge Li Gørtz (DTU Copenhagen).
- Algorithm Design von Kevin Wayne (Princeton University).
- Algorithms and Models of Computation von Jeff Erickson (University of Illinois)
- Algorithms von Jeff Erickson (University of Illinois)
- Eine vorherige Iteration von ALGO2 wurde im WiSe-2020 (Prof. Meyer) angeboten, wofür Videos aus Präcoronazeiten zusammengeschnitten wurden.