Logbuch Theoretische Informatik 1 - Winter 2019/20
13.02.2020:
Materialien und weitere Lektüre:
Branch & Bound, allgemeines Verfahren, Rucksackproblem: Startlösung mit dynamischer Programmierung, Bounding-Schritt mit fraktionaler Greedy-Heuristik; TSP: Startlösung mit Nearest-Insertion Heuristik, Bounding-Schritt mit Held-Karp Schranke. Aufgaben zu dynamischer Programmierung und NP-Vollständigkeit- Folien Kapitel Exakte Algorithmen (Seiten 17-32)
- Skript: Abschnitt 9.3
- Applet zur Nearest-Insertion Heuristik beim TSP
11.02.2020:
Materialien und weitere Lektüre:
Wiederholung Turingmaschine und NP-Vollständigkeit. Backtracking, Beispiel Backtracking KNF-SAT, Beispiel Backtracking Subset-Sum, Branch & Bound, allgemeines Verfahren- Folien Kapitel Exakte Algorithmen (Seiten 9-20)
- Skript: Abschnitte 9.2, 9.3
- Backtracking im Graphenfärbungsproblem
06.02.2020:
Materialien und weitere Lektüre:
Wiederholung Entwurfsmethoden. Evolutionäre Algorithmen, Crossoveroperatoren für verschiedene Lösungsräume. Exakte Algorithmen, parametrisierte Komplexität, exakter Algorithmus für das Vertex-Cover Problem, Backtracking- Folien Kapitel Lokale Suche (Seiten 27-28)
- Folien Kapitel Exakte Algorithmen (Seiten 1-8)
- Skript: Abschnitte 8.3, 9, 9.1
04.02.2020:
Materialien und weitere Lektüre:
Wiederholung Laufzeitanalyse, Kürzeste Wege und Minimale Spannbäume. Lokale Suche in variabler Tiefe, Minimum Balanced Cut Problem, Metropolis Algorithmus, Simulated Annealing, Video für das TSP, Evolutionäre Algorithmen, Initialisierung, Selektion zur Reproduktion, Selektion zur Ersetzung, Mutationsoperatoren für verschiedene Lösungsräume- Folien Kapitel Lokale Suche (Seiten 9-26)
- Skript: Abschnitte 8.1, 8.2, 8.3
- Simulated Annealing für das TSP
30.01.2020:
Lokale Suche, k-Flip-Nachbarschaft, Beispiele Simplex-Algorithmus und Gradientenabstieg,
Wiederholung Sortieren, Laufzeitanalyse, Tiefen- und Breitensuche
- Folien Kapitel Lokale Suche (Seiten 1-8)
- Skript: Abschnitte 8, 8.1
28.01.2020:
Rekursive Aufzählbarkeit, L und L rekursiv aufzählbar ⇒ beide entscheidbar,
rekursive Aufzählbarkeit von Grammatiken und
Axiomensystemen, Gödelscher Unvollständigkeitssatz,
Zusammenfassung, Wiederholung Sortieren
- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 49-63)
- Wiederholungsfragen Entscheidbarkeit
- Wiederholungsfragen Sortieren
- Skript: Abschnitte 12, 12.1, 12.3
23.01.2020:
Reduktionen, unentscheidbare Probleme/Sprachen: Universelle
Sprache, Halteproblem, spezielles Halteproblem (mit leerer
Eingabe), Satz von Rice, rekursive Aufzählbarkeit, L und
L rekursiv aufzählbar ⇒ beide entscheidbar,
rekursive Aufzählbarkeit von Grammatiken und Axiomensystemen
- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 33-54)
- Skript: Abschnitte 11.3, 11.4, 12
21.01.2020:
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, universelle
Turing-Maschine, Diagonalsprache und ihr Komplement als
unentscheidbare Sprachen
- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 1-32)
- Skript: Abschnitte 10, 10.1, 10.2, 11, 11.1 und 11.2
17.12.2019:
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
12.12.2019:
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, Rucksackproblem
- Folien Kapitel Approximationsalgorithmen (Seiten 1-15)
- Wiederholungsfragen P und NP (Seiten 13-17)
- Skript: Abschnitte 7 und 7.1
10.12.2019:
Satz von Cook und Levin, Masterreduktion
L ≤p KNF-SAT für jedes Problem L
∈ NP. Approximationsalgorithmen, Einführung und
Definitionen
- Folien Kapitel NP-Vollständigkeit (Seiten 44-57)
- Folien Kapitel Approximationsalgorithmen (Seiten 1-6)
- Wiederholungsfragen P und NP (Seiten 8-12)
- Skript: Abschnitte 6.1 und 7
05.12.2019:
Probleme: Independent Set (IS), Vertex Cover (VC), Set Cover
(SC), Gerichteter Hamiltonscher Kreis (DHC), Hamiltonscher
Kreis (HC), Travelling Salesperson Problem (TSP), Längster Weg (LW).
Polynomielle Reduktionen: CLIQUE ≤p IS ≤p VC ≤p SC
DHC ≤p HC ≤p TSP, HC ≤p LW.
- Folien Kapitel NP-Vollständigkeit (Seiten 18-43)
- Wiederholungsfragen P und NP (Seiten 5-7)
- Skript: Abschnitte 6.2.2 und 6.2.4
03.12.2019:
Wiederholung 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: 2-SAT, CLIQUE.
Polynomielle Reduktionen: KNF-SAT ≤p 3-SAT ≤p CLIQUE
2-SAT in P
- Folien Kapitel Die Klassen P und NP (Seiten 32-39)
- Folien Kapitel NP-Vollständigkeit (Seiten 1-17)
- Wiederholungsfragen P und NP (Seiten 1-4)
- Skript: Abschnitte 5.3, 6.1 und 6.2.1
28.11.2019:
Schwierige Probleme, 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, polynomielle Reduktion
- Folien Kapitel Die Klassen P und NP (Seiten 4-32)
- Wiederholungsfragen Entwurfsmethoden (Seiten 13-15)
- Skript: Abschnitte 5, 5.1, 5.2 und Definition 5.7
26.11.2019:
RNA Sekundärstruktur, dynamische Programmierung, Laufzeit O(n3), Lineare Programmierung, Definition lineares Programm, Beispiel,
geometrische Interpretation, bipartites Matching und integrale Ecken, Schwierige Probleme
- Folien Kapitel Entwurfsmethoden (Seiten 90-108)
- Folien Kapitel Die Klassen P und NP (Seiten 1-6)
- Wiederholungsfragen Entwurfsmethoden (Seiten 9-12)
- Skript: Abschnitte 4.3.4, 4.4, 4.5 und 5
21.11.2019:
All-Pairs-Shortest-Path (Algorithmus von Floyd, Orakel: Enthält ein kürzester u-v-Weg den Knoten i?, Laufzeit O(n3)),
paarweises Alignment (Definition, Orakel mit Alignment von Präfixen, Laufzeit O(nm) für zwei Strings mit Längen n und m, Beispiel)
RNA Sekundärstruktur, Formalisierung (keine engen Kurven, keine kreuzenden Paarungen, komplementäre Basispaare)
- Folien Kapitel Entwurfsmethoden (Seiten 72-93)
- Wiederholungsfragen Entwurfsmethoden (Seiten 6-8)
- Skript: Abschnitte 4.3.2, 4.3.3 und 4.3.4
19.11.2019:
TSP (Teilprobleme L(k,S), Rekursionsgleichung, Lösung mit Laufzeit O(n² 2n), Beispiel), gewichtetes Intervall-Scheduling (Orakel, Teilprobleme opt(i),
Rekursionsgleichung, Lösung mit Laufzeit O(n log n)), All-Pairs-Shortest-Path (Bellman-Ford Algorithmus, Orakel: Erste
Kante eines kürzesten u-v-Weges?, Laufzeit O(n²m))
- Folien Kapitel Entwurfsmethoden (Seiten 55-71)
- Wiederholungsfragen Laufzeitanalyse und Rekusionsgleichungen (Seiten 10-12)
- Wiederholungsfragen Entwurfsmethoden (Seiten 4-5)
- Beispiel zur dynamischen Programmierung für TSP
- Skript: Abschnitte 4.3, 4.3.1 und 4.3.2
14.11.2019:
Huffman-Codes (Huffman-Baum, Struktureigenschaften (innere Knoten Grad 2, zu codierende Zeichen an
Blättern, seltenste Zeichen sind Geschwister auf maximaler Tiefe),
Greedy-Algorithmus, Laufzeit O(n log n)), Divide and Conquer,
schnelle Multiplikation von Zahlen und Matrizen, Dynamische Programmierung, Orakel-Ansatz, TSP (Orakel, Teilprobleme L(k,S),
Rekursionsgleichung)
- Folien Kapitel Entwurfsmethoden (Seiten 19-55)
- Wiederholungsfragen Laufzeitanalyse und Rekusionsgleichungen (Seiten 7-9)
- Wiederholungsfragen Entwurfsmethoden (Seiten 1-3)
- Skript: Abschnitte 4.1.2, 4.2.1, 4.2.2, und 4.3
12.11.2019:
Entwurfsmethoden, Greedy-Algorithmen für Intervall-Scheduling (frühe Terminierungszeiten
zuerst, Beweis der Optimalität, Umsetzung mit Laufzeit O(n log n)), Minimierung maximaler
Verspätung (frühe Fristen zuerst (earliest deadline
first), Beweis der der Optimalität, Laufzeit O(n log n)),
Huffman-Codes
- Folien Kapitel Entwurfsmethoden (Seiten 1-23)
- Wiederholungsfragen Graphalgorithmen (Seiten 7-9)
- Wiederholungsfragen Laufzeitanalyse und Rekusionsgleichungen (Seiten 4-6)
- Skript: Abschnitte 4.1.2 und 4.2
07.11.2019:
Minimale Spannbäume, Algorithmus von Jarnik-Prim-Dijkstra (Laufzeit O((n+m) log n) mit binären
Heaps, Analogie zum Dijkstra-Algorithmus für kürzeste
Wege), Algorithmus von Kruskal (Laufzeit O(n + m log n) mit Union-Find Datenstruktur)
- Folien Kapitel Graphalgorithmen (Seiten 37-55)
- Wiederholungsfragen Graphalgorithmen (Seiten 4-6)
- Wiederholungsfragen Laufzeitanalyse und Rekusionsgleichungen (Seiten 1-3)
- Skript: Abschnitt 3.3
05.11.2019:
Das Single-Source-Shortest-Path Problem, Bindfadenmodell, Algorithmus von Dijkstra (Korrektheit, Laufzeit O((n+m) log n) mit binären Heaps)
Minimale Spannbäume, Anwendungen (Netzwerkdesign, Heuristik für das Travelling Salesman Problem),
Optimalitätskriterium: S-kreuzende Kanten mit minimalem Wert
- Folien Kapitel Graphalgorithmen (Seiten 18-39)
- Wiederholungsfragen Graphalgorithmen (Seiten 1-3)
- Skript: Abschnitte 3.2 und 3.3
31.10.2019:
Wiederholung Sample Sort, Graphen, Tiefensuche in ungerichteten Graphen mit Anwendungen
Tiefensuche in gerichteten Graphen mit Anwendungen,
Breitensuche
- Folien Kapitel Graphalgorithmen (Seiten 1-17)
- Wiederholungsfragen Sortieren (Seiten 19-20)
- Skript: Abschnitte 3.1.1 und 3.1.2
29.10.2019:
Wiederholung Externspeicher und Radixsort, untere Schranke Ω(n log n) für worst-case Laufzeit von
vergleichsorientierten Sortieralgorithmen; Message Passing Interface, Sample Sort für Parallelrechner
mit p Kernen in Zeit O(n/p log2 n) (wenn p ≤
n1/3)
24.10.2019:
Sortieren im Externspeicher (einfach: Θ(n/B log2 n/B) Speicherzugriffe, verbessert: Θ(n/B logM/B n/B) Zugriffe); 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)
- Folien Kapitel Sortieren (Seiten 57-61, 69-79)
- Wiederholungsfragen Sortieren (Seiten 8-11)
- Skript: Abschnitte 2.3 und 2.5
- Distribution Counting und Radixsort
22.10.2019:
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))
- Folien Kapitel Sortieren (Seiten 42-56)
- Wiederholungsfragen Sortieren (Seiten 4-7)
- Skript: Abschnitte 2.2.1, 2.2.2, 2.2.3 und 2.3 (bis Seite 27)
- Sound of Sorting psychedelisch
17.10.2019:
Selection Sort (worst- und best-case Laufzeit
Θ(n²)), Insertion Sort (worst- und 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-45)
- Wiederholungsfragen Sortieren (Seiten 1-3)
- Skript: Abschnitte 2.1, 2.2 und 2.2.1
- Sound of Sorting schwarz-weiß
15.10.2019:
Einführung, Wiederholung (asymptotische Notation,
Rekursionsgleichungen), Sortierproblem, Bubble Sort (worst-case
Laufzeit Θ(n²), erwartete Laufzeit Θ(n²)), Selection Sort (worst- und best-case Laufzeit
Θ(n²))
- Folien Kapitel Sortieren (Seiten 1-26)
- Skript: Abschnitte 1 und 2.1
- Animation und Code
- Animation und Code (2)