Logbuch Algorithmen und Datenstrukturen 2 - Winter 2022/23
Fragestunde -- 07.02.2023:
NP-Vollständigkeit, Reduktion allgemeines Schema, Facility Location (FL) Problem, Reduktion VC ≤p FL, Maximum Matching in allgemeinen Graphen (MATCH), Reduktion MATCH ≤p IS, Satz von Rice, Beispiele.Vorlesung 23 -- 01.02.2023:
Materialien und weitere Lektüre:
Branch & Cut, Beispiel M-TSP. Lokale Suche, k-Flip-Nachbarschaft, Beispiele Simplex-Algorithmus und Gradientenabstieg, Vertex Cover. Lokale Suche mit variabler Tiefe, Minimum Balanced Cut und TSP.- Folien Kapitel Exakte Algorithmen (Seiten 24-27)
- Folien Kapitel Lokale Suche (Seiten 1-11)
- Skript: Abschnitte 9.3.1, 8, 8.1
Vorlesung 22 -- 31.01.2023:
Wiederholung NP-Vollständigkeit, Wiederholung Backtracking, Beispiel Subset-Sum. Branch & Bound, allgemeines Verfahren, Rucksackproblem: Startlösung mit dynamischer Programmierung, Bounding-Schritt mit fraktionaler Greedy-HeuristikDie Vorlesung konnte aufgrund von technischen Problemen leider nicht aufgezeichnet werden.
Materialien und weitere Lektüre:- Folien Kapitel Exakte Algorithmen (Seiten 8-23)
- Wiederholungsfragen Asymptotik und NP-Vollständigkeit (Seiten 6-9)
- Skript: Abschnitte 9.2, 9.3
Vorlesung 21 -- 26.01.2023:
Materialien und weitere Lektüre:
Wiederholung: LP Dualität, Laufzeitanalyse, Turing Maschine. Exakte Algorithmen, parametrisierte Komplexität, exakter Algorithmus für das Vertex-Cover Problem, Backtracking, Beispiel Backtracking KNF-SAT- Folien Kapitel Exakte Algorithmen (Seiten 1-14)
- Wiederholungsfragen Flüsse und LPs (Seiten 6-8)
- Wiederholungsfragen Asymptotik und NP-Vollständigkeit (Seiten 1-5)
- Skript: Abschnitte 9, 9.1, 9.2
Vorlesung 20 -- 24.01.2023:
Materialien und weitere Lektüre:
Lineare Programmierung, Matching-LP hat nur integrale Ecken, Vertex Cover LP hat u.U. fraktionale optimale Ecke. Dualität, Konstruktion des dualen LPs, Repräsentation in Matrix-Vektor Notation, Schwache und starke Dualität. Wiederholung Sortieren- Folien Kapitel Flüsse und Lineare Programmierung (Seiten 63-81)
- Wiederholungsfragen Sortieren (2) (Seiten 4-8)
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 29.4
Vorlesung 19 -- 19.01.2023:
Materialien und weitere Lektüre:
Wiederholung perfektes Matching mit minimalen Kosten, Reduzierte Kosten und kompatible Preise, Algorithmus am Beispiel. Lineare Programme, Formulierung, geometrische Interpretation, Algorithmen für lineare Programme, Formulierung als lineares Programm: Maximaler Fluss, bipartites Matching mit maximalem Gewicht- Folien Kapitel Flüsse und Lineare Programmierung (Seiten 52-63)
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 29, 29.1, 29.2
- Kleinberg, Tardos. Algorithm Design. Kapitel 7.13
Vorlesung 18 -- 17.01.2023:
Materialien und weitere Lektüre:
Wiederholung Flüsse, Maximum Matching und Minimum Vertex Cover in bipartiten Graphen, Perfektes bipartites Matching mit minimalen Kosten, Fluss-Algorithmus mit kürzesten augmentierenden Pfaden, optimale Matchings erzeugen keine negativen Kreise im Restnetzwerk, Algorithmus erzeugt keine negativen Kreise, reduzierte Kosten und Einsatz von Dijkstra's Algorithmus.- Folien Kapitel Flüsse und Lineare Programmierung (Seiten 38-51)
- Wiederholungsfragen Flüsse und LPs (Seiten 4-5)
- Kleinberg, Tardos. Algorithm Design. Kapitel 7.13
Vorlesung 17 -- 12.01.2023:
Materialien und weitere Lektüre:
Matching, Definitionen, Matching in bipartiten Graphen, Reduktion auf maximale Flüsse, Beweis der Optimalität. Vertex Cover in bipartiten Graphen, Reduktion auf minimale Schnitte, Beweis der Optimalität. Wiederholung Sortieren- Folien Kapitel Flüsse und Lineare Programmierung (Seiten 26-37)
- Wiederholungsfragen Flüsse und LPs (Seiten 1-3)
- Wiederholungsfragen Sortieren (2) (Seiten 1-4)
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 26.3
- Kleinberg, Tardos. Algorithm Design. Kapitel 7.5
Vorlesung 16 -- 10.01.2023:
Materialien und weitere Lektüre:
Flüsse, Flussnetzwerk, s-t-Schnitte, Max-Flow Min-Cut, Restnetzwerk, Ford-Fulkerson Algorithmus zur Berechnung maximaler Flüsse und minimaler Schnitte, Laufzeitanalyse, Edmonds-Karp-Variante mit polynomieller Laufzeit- Folien Kapitel Flüsse und Lineare Programmierung (Seiten 1-25)
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 26, 26.1, 26.2
- Kleinberg, Tardos. Algorithm Design. Kapitel 7, 7.1, 7.2, 7.3
Vorlesung 15 -- 13.12.2022:
Materialien und weitere Lektüre:
Rucksackproblem: volles Approximationsschema mit Austauschbeziehung zwischen Approximationsfaktor und Laufzeit, Vertex Cover: Matching-Heuristik ist 2-approximativ, Gewichtetes Vertex Cover: Lineare Programmierung und Runden ist 2-approximativ.- Folien Kapitel Approximationsalgorithmen (Seiten 15-28)
- Wiederholungsfragen Approximationsalgorithmen (Seiten 1-3)
- Skript: Abschnitte 7.2 und 7.3
Vorlesung 14 -- 08.12.2022:
Materialien und weitere Lektüre:
Approximationsalgorithmen, Einführung und Definitionen, Metrisches TSP (2-Approximation mit Spannbaum-Heuristik, 3/2-Approximation mit Christofides' Algorithmus), On-line Makespan Scheduling: Greedy Algorithmus ist 2-approximativ, Off-line Makespan Scheduling: Sortierter-Greedy-Algorithmus ist 3/2-approximativ- Folien Kapitel Approximationsalgorithmen (Seiten 6-14)
- Wiederholungsfragen Entscheidbarkeit (Seiten 3-5)
- Skript: Abschnitte 7 und 7.1
Vorlsung 13 -- 06.12.2022:
Materialien und weitere Lektüre:
Wiederholung Satz von Rice, Rekursive Aufzählbarkeit, L und L rekursiv aufzählbar ⇒ beide entscheidbar, rekursive Aufzählbarkeit von Grammatiken und Axiomensystemen, Gödelscher Unvollständigkeitssatz, Zusammenfassung. Approximationsalgorithmen, Einführung und Definitionen, Metrisches TSP (2-Approximation mit Spannbaum-Heuristik)- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 49-63)
- Folien Kapitel Approximationsalgorithmen (Seiten 1-6)
- Wiederholungsfragen Entscheidbarkeit (Seiten 1-3)
- Skript: Abschnitte 12, 12.1, 12.3 und 7
Vorlesung 12 -- 01.12.2022:
Materialien und weitere Lektüre:
Gödelnummer, universelle Turing-Maschine, Diagonalsprache und ihr Komplement als unentscheidbare Sprachen, Reduktionen, unentscheidbare Probleme/Sprachen: Universelle Sprache, Halteproblem, spezielles Halteproblem (mit leerer Eingabe), Satz von Rice- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 24-48)
- Wiederholungsfragen Entscheidbarkeit/Berechenbarkeit (Seite 1)
- Skript: Abschnitte 11.2, 11.3, und 11.4
Vorlesung 11 -- 29.11.2022:
Materialien und weitere Lektüre:
Satz von Cook und Levin, Masterreduktion L ≤p KNF-SAT für jedes Problem L ∈ NP.
Berechenbarkeit von Funktionen, Entscheidbarkeit von Problemen, Mächtigkeit der Turing-Maschine und des Begriffs der Entscheidbarkeit, Klasse PSPACE, probabilistische und Quanten-Turingmaschinen, Unentscheidbarkeit, Existenz unentscheidbarer Sprachen durch Abzählen, Gödelnummer- Folien Kapitel NP-Vollständigkeit (Seiten 52-57)
- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 1-26)
- Wiederholungsfragen P und NP (Seiten 13-17)
- Skript: Abschnitte 6.1, 10, 10.1, 10.2, 11 und 11.1
Vorlesung 10 -- 24.11.2022:
Materialien und weitere Lektüre:
Probleme: Gerichteter Hamiltonscher Kreis (DHC), Hamiltonscher Kreis (HC), Travelling Salesperson Problem (TSP), Längster Weg (LW).
Polynomielle Reduktionen: DHC ≤p HC ≤p TSP, HC ≤p LW.
Satz von Cook und Levin, Masterreduktion L ≤p KNF-SAT für jedes Problem L ∈ NP.- Folien Kapitel NP-Vollständigkeit (Seiten 30-52)
- Wiederholungsfragen P und NP (Seiten 9-12)
- Skript: Abschnitte 6.2.4 und 6.1
Vorlesung 9 -- 22.11.2022:
Materialien und weitere Lektüre:
Probleme: CLIQUE, Independent Set (IS), Vertex Cover (VC), Set Cover (SC)
Polynomielle Reduktionen: 3-SAT ≤p CLIQUE ≤p IS ≤p VC ≤p SC
2-SAT in P- Folien Kapitel NP-Vollständigkeit (Seiten 10-29)
- Wiederholungsfragen P und NP (Seiten 5-8)
- Skript: Abschnitte 6.2, 6.2.1 und 6.2.2
Vorlesung 8 -- 17.11.2022:
Wiederholung Klasse P, Klasse NP enthält alle Entscheidungsprobleme mit effizienter nichtdeterministischer Berechnung der Entscheidung, polynomielle Reduktion, Transitivität der Reduktion, NP-Härte vs. NP-Vollständigkeit, L NP-hart ⇔ alle Probleme K ∈ NP sind auf L reduzierbar - oder mind. ein NP-hartes L' ist auf L reduzierbar, NP-Vollständigkeit von 3-SAT
Probleme: KNF-SAT, 3-SAT.
Polynomielle Reduktionen: KNF-SAT ≤p 3-SAT
Materialien und weitere Lektüre:- Folien Kapitel Die Klassen P und NP (Seiten 23-39)
- Folien Kapitel NP-Vollständigkeit (Seiten 1-9)
- Wiederholungsfragen P und NP (Seiten 1-4)
- Skript: Abschnitte 5.2 und 5.3
Vorlesung 7 -- 15.11.2022:
Materialien und weitere Lektüre:
Modell der (deterministischen) Turing-Maschine, effiziente Berechnung als polynomielle worst-case Laufzeit auf einer deterministischen Turing-Maschine, Klasse P enthält alle Entscheidungsprobleme mit effizienter Berechnung der Entscheidung, Beispiele für Probleme in P, Modell der nichtdeterministischen Turing-Maschine, Klasse NP enthält alle Entscheidungsprobleme mit effizienter nichtdeterministischer Berechnung der Entscheidung- Folien Kapitel Die Klassen P und NP (Seiten 1-25)
- Wiederholungsfragen Sortieren (Seiten 15-18)
- Skript: Abschnitte 5, 5.1 und 5.2
Vorlesung 6 -- 03.11.2022:
Materialien und weitere Lektüre:
Sample Sort in Zeit O(n/p log2 n) (wenn p ≤ n1/3), Zusammenfassung Sortieren.
Schwierige Probleme.- Folien Kapitel Sortieren (Seiten 82-89)
- Folien Kapitel Die Klassen P und NP (Seiten 1-9)
- Wiederholungsfragen Sortieren (Seiten 12-16)
- Skript: Abschnitte 2.6, 2.7 und 5
Vorlesung 5 -- 01.11.2022:
Materialien und weitere Lektüre:
Wiederholung Auswahlproblem, untere Schranke für vergleichsorientierte Verfahren; verbessertes Sortieren von ganzen Zahlen (Distribution Counting in Laufzeit O(n+m), Radixsort in Laufzeit O(L(n+b)) mit Basis b und Anzahl L der Stellen); Message Passing Interface, Sample Sort für Parallelrechner mit p Kernen- Folien Kapitel Sortieren (Seiten 70-85)
- Wiederholungsfragen Sortieren (Seiten 8-11)
- Skript: Abschnitte 2.5 und 2.6
- Distribution Counting und Radixsort
Vorlesung 4 -- 27.10.2022:
Materialien und weitere Lektüre:
Nicht-rekursiver Mergesort, Sortieren im Externspeicher (einfach: Θ(n/B log2 n/B) Speicherzugriffe, verbessert: Θ(n/B logM/B n/B) Zugriffe); untere Schranke Ω(n log n) für worst-case Laufzeit von vergleichsorientierten Sortieralgorithmen- Folien Kapitel Sortieren (Seiten 58-69)
- Skript: Abschnitte 2.3 und 2.4
- Sound of Sorting psychedelisch
Vorlesung 3 -- 25.10.2022:
Materialien und weitere Lektüre:
Quicksort (erwartete Laufzeit Θ(n log n) bei uniform zufälliger Eingabepermutation, warum liegt eine Teilfolge nach einem Rekursionsaufruf immer noch in zufälliger Reihenfolge?, gleiche Analyse für beliebige Eingabe aber uniform zufällige Wahl des Pivotelements.); Auswahlproblem (randomisiert mit erwarteter Laufzeit O(n), deterministisch in Laufzeit O(n)), Mergesort (worst-, best- und average-case Θ(n log n))Vorlesung 2 -- 20.10.2022:
Materialien und weitere Lektüre:
Insertion Sort (worst-case Laufzeit Θ(n²), best-case Laufzeit Θ(n)), Wiederholung Heapsort, Quicksort (rekursive Implementierung, sequentielle Implementierung, Stackgröße), worst-case Laufzeit Θ(n²), best-case Laufzeit Θ(n log n), erwartete Laufzeit Θ(n log n) bei uniform zufälliger Eingabepermutation- Folien Kapitel Sortieren (Seiten 25-46)
- Wiederholungsfragen Sortieren (Seiten 1-3)
- Skript: Abschnitte 2.1, 2.2 und 2.2.1
- Sound of Sorting schwarz-weiß
Vorlesung 1 -- 18.10.2022:
Materialien und weitere Lektüre:
Einführung, Wiederholung (asymptotische Notation, Rekursionsgleichungen), Sortierproblem, Bubble Sort (worst-case Laufzeit Θ(n²), erwartete Laufzeit Θ(n²)), Selection Sort (worst- und best-case Laufzeit Θ(n²)), Insertion Sort (worst-case Laufzeit Θ(n²)), Wiederholung Heapsort- Folien Kapitel Sortieren (Seiten 1-31)
- Skript: Abschnitte 1 und 2.1
- Animation und Code
- Animation und Code (2)