Algorithmen und Datenstrukturen 2

WiSe-2021/22

Overview

Übersicht

Wochenplan

Die Veranstaltung dauert 15 Wochen, die Pläne sind vorläufig:

  1. Einführung und All-Pairs Shortest Paths

  2. Network Flow I: Max-flow min-cut theorem, augmenting paths, Ford-Fulkerson

  3. Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths

  4. Amortisierte Analyse: Dynamische Tabellen, MultiPop Stacks, Splay Trees

  5. Randomisierte Algorithmen I: Contention resolution, Minimum cut

  6. Randomisierte Algorithmen II: Selection, Quicksort

  7. Hartnäckigkeit I: Sprachen, Polynomialzeitreduktionen

  8. Hartnäckigkeit II: P, NP, NP-Vollständigkeit

  9. Recap I

  10. Berechnungsmodelle: Endliche Automaten, Turing-Maschinen, Nicht-Determinismus, starke Church-Turing Hypothese, Word-RAM

  11. Berechenbarkeit: Halteproblem, Satz von Rice

  12. Lineare Programmierung I: Konvexität, Polytope, Simplex-Algorithmus

  13. Lineare Programmierung II: Dualität, Integrale Lineare Programmierung

  14. 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

  15. Recap II

Literatur

Lernziele

Nach der Veranstaltung können die Studierenden:

Außerdem können die Studierenden:

Inhalt

Allgemeines

Vorlesungsteam

Klausur

Ähnliche Kurse