Algorithmen und Datenstrukturen 2

ALGO2 · 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

  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. Approximationsalgorithmen: LP-Dualität, Greedy, Vertex-Cover, Set Cover.

  15. Parametrisierte Algorithmen: Bounded Search Trees, Kernelisierung.

Literatur

Lernziele

Nach der Veranstaltung können die Studierenden:

Außerdem können die Studierenden:

Inhalt

Allgemeines

Vorlesungsteam

Ähnliche Kurse

Klausur