Logbuch Theoretische Informatik 1 - Winter 2017/18
08.02.2018:
Materialien und weitere Lektüre:
Zwei-Personen-Spiele, Spielbaum, Minimax-Auswertung, α-β-Suche, Größenordnungen beim Schach; Aufgaben zu Linearen Programmen, Entscheidbarkeit, NP-Vollständigkeit, dynamische Programmierung- Folien Kapitel Exakte Algorithmen (Seiten 37-45)
- Skript: Abschnitt 9.4
- Vier Gewinnt
06.02.2018:
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; Branch & Cut für ganzzahlige Programmierung, TSP: Cutting mit Subtour-Eliminierungsconstraints; Wiederholung Turingmaschine und NP-Vollständigkeit- Folien Kapitel Exakte Algorithmen (Seiten 17-36)
- Skript: Abschnitt 9.3
- Applet zur Nearest-Insertion Heuristik beim TSP
01.02.2018:
Materialien und weitere Lektüre:
Simulated Annealing für das Travelling Salesman Problem, Exakte Algorithmen, parametrisierte Komplexität, exakter Algorithmus für das Vertex-Cover Problem, Backtracking, Beispiel Backtracking KNF-SAT, Beispiel Backtracking Subset-Sum, Wiederholung Entwurfsmethoden- Folien Kapitel Exakte Algorithmen (Seiten 1-16)
- Skript: Abschnitte 9, 9.1, 9.2
- Simulated Annealing für das TSP
- Backtracking im Graphenfärbungsproblem
30.01.2018:
Materialien und weitere Lektüre:
Lokale Suche in variabler Tiefe, Minimum Balanced Cut Problem, Metropolis Algorithmus, Simulated Annealing, Evolutionäre Algorithmen, Initialisierung, Selektion zur Reproduktion, Selektion zur Ersetzung, Mutations- und Crossoveroperatoren für verschiedene Lösungsräume, Wiederholung Kürzeste Wege und Minimale Spannbäume- Folien Kapitel Lokale Suche (Seiten 9-28)
- Skript: Abschnitte 8.1, 8.2, 8.3
25.01.2018:
Materialien und weitere Lektüre:
Wiederholung Sortieren, Tiefen- und Breitensuche, Laufzeitanalyse, Lokale Suche, k-Flip-Nachbarschaft, Beispiele Simplex-Algorithmus und Gradientenabstieg, Lokale Suche in variabler Tiefe- Folien Kapitel Lokale Suche (Seiten 1-10)
- Skript: Abschnitte 8, 8.1
23.01.2018:
Materialien und weitere Lektüre:
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, Lokale Suche, k-Flip-Nachbarschaft- Folien Kapitel Lokale Suche (Seiten 1-4)
- Folien Kapitel Entscheidbarkeit und Berechenbarkeit (Seiten 49-63)
- Wiederholungsfragen Entscheidbarkeit
- Skript: Abschnitte 12, 12.1, 12.3, 8
18.01.2018:
Materialien und weitere Lektüre:
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
16.01.2018:
Materialien und weitere Lektüre:
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
21.12.2017:
Materialien und weitere Lektüre:
Approximationsalgorithmen, Vertex Cover: Matching-Heuristik ist 2-approximativ, Gewichtetes Vertex Cover: Lineare Programmierung und Runden ist 2-approximativ, Besprechung von Teilen der Nachklausur WS 2009/10- Folien Kapitel Approximationsalgorithmen (Seiten 22-28)
- Wiederholungsfragen Approximationsalgorithmen
- Nachklausur WS 2009/10
- Skript: Abschnitt 7.3
19.12.2017:
Materialien und weitere Lektüre:
Approximationsalgorithmen, On-line Makespan Scheduling: Greedy Algorithmus ist 2-approximativ, Off-line Makespan Scheduling: Sortierter-Greedy-Algorithmus ist 3/2-approximativ, Rucksackproblem: volles Approximationsschema mit Austauschbeziehung zwischen Approximationsfaktor und Laufzeit, Vertex Cover: Matching-Heuristik ist 2-approximativ- Folien Kapitel Approximationsalgorithmen (Seiten 8-25)
- Skript: Abschnitte 7, 7.1 und 7.2
14.12.2017:
Materialien und weitere Lektüre:
Satz von Cook und Levin, Masterreduktion L ≤p KNF-SAT für jedes Problem L ∈ NP; Approximationsalgorithmen, Einführung und Definitionen, Metrisches TSP (2-Approximation mit Spannbaum-Heuristik, 3/2-Approximation mit Christofides' Algorithmus), On-line Makespan Scheduling, Greedy Algorithmus- Folien Kapitel NP-Vollständigkeit (Seiten 46-57)
- Folien Kapitel Approximationsalgorithmen (Seiten 1-10)
- Wiederholungsfragen Polynomielle Reduktionen (II), Satz von Cook und Levin
- Skript: Abschnitte 6.1, 7 und 7.1
12.12.2017:
Materialien und weitere Lektüre:
Probleme: Gerichteter Hamiltonscher Kreis (DHC), Hamiltonscher Kreis (HC), TSP, Längster Weg (LW). Polynomielle Reduktionen: DHC ≤p HC ≤p TSP und 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-57)
- Wiederholungsfragen Polynomielle Reduktionen (I)
- Skript: Abschnitte 6.2.4 und 6.1
07.12.2017:
Materialien und weitere Lektüre:
Probleme: 2-SAT, CLIQUE, Independent Set (IS), Vertex Cover (VC), Set Cover (SC).
Polynomielle Reduktionen: KNF-SAT ≤p 3-SAT ≤p CLIQUE ≤p IS ≤p VC ≤p SC
2-SAT in P- Folien Kapitel NP-Vollständigkeit (Seiten 1-29)
- Wiederholungsfragen Turing-Maschinen, Reduktion KNF-SAT ≤p 3-SAT
- Skript: Abschnitte 6.2.1 und 6.2.2
05.12.2017:
Materialien und weitere Lektüre:
Wiederholung Klasse P, Modell der nichtdeterministischen Turing-Maschine, 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- Folien Kapitel Die Klassen P und NP (Seiten 22-39)
- Folien Kapitel NP-Vollständigkeit (Seiten 1-9)
- Wiederholungsfragen Asymptotische Notation (I), Laufzeitanalyse (IV), Turing-Maschine
- Skript: Abschnitte 5.2, 5.3 und Satz 6.2
- LEGO Turing Maschine
30.11.2017:
Materialien und weitere Lektüre:
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- Folien Kapitel Die Klassen P und NP (Seiten 1-22)
- Wiederholungsfragen APSP, Alignment, Sekundärstruktur
- Skript: Abschnitte 5, 5.1 und 5.1.1
28.11.2017:
Materialien und weitere Lektüre:
RNA Sekundärstruktur, Formalisierung (keine engen Kurven, keine kreuzenden Paarungen, komplementäre Basispaare), dynamische Programmierung, Laufzeit O(n3), Lineare Programmierung, Definition lineares Programm, Beispiel, geometrische Interpretation, bipartites Matching und integrale Ecken- Folien Kapitel Entwurfsmethoden (Seiten 89-108)
- Wiederholungsfragen APSP und Paarweises Alignment
- Skript: Abschnitte 4.3.4, 4.4 und 4.5
23.11.2017:
Materialien und weitere Lektüre:
All-Pairs-Shortest-Path (Bellman-Ford Algorithmus, Orakel: Erste Kante eines kürzesten u-v-Weges?, Laufzeit O(n²m); Algorithmus von Floyd, Orakel: Enthält ein kürzester u-v-Weg den Knoten i?, Laufzeit O(n³)), paarweises Alignment (Definition, Orakel mit Alignment von Präfixen, Laufzeit O(nm) für zwei Strings mit Längen n und m, Beispiel)- Folien Kapitel Entwurfsmethoden (Seiten 65-88)
- Wiederholungsfragen Gewichtetes Intervall-Scheduling und APSP
- Skript: Abschnitte 4.3.2 und 4.3.3
21.11.2017:
Materialien und weitere Lektüre:
Dynamische Programmierung, Orakel-Ansatz, TSP (Orakel, 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)- Folien Kapitel Entwurfsmethoden (Seiten 47-69)
- Wiederholungsfragen Laufzeitanalyse (III), Huffman-Codes, Dynamische Programmierung
- Beispiel zur dynamischen Programmierung für TSP
- Skript: Abschnitte 4.3, 4.3.1 und 4.3.2
16.11.2017:
Materialien und weitere Lektüre:
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- Folien Kapitel Entwurfsmethoden (Seiten 19-49)
- Wiederholungsfragen Rekursionsgleichungen und Scheduling
- Skript: Abschnitte 4.1.2 und 4.2
14.11.2017:
Materialien und weitere Lektüre:
Wiederholung Union-Find Datenstruktur (Union-Schritt bzgl. kleinerer Tiefe oder weniger Knoten), 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))- Folien Kapitel Entwurfsmethoden (Seiten 1-18)
- Wiederholungsfragen Laufzeitanalyse (II) und Minimale Spannbäume
- Skript: Abschnitte 4.1 und 4.1.1
09.11.2017:
Materialien und weitere Lektüre:
Minimale Spannbäume, Anwendungen (Netzwerkdesign, Heuristik für das Travelling Salesman Problem), Optimalitätskriterium: S-kreuzende Kanten mit minimalem Wert, 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 31-54)
- Wiederholungsfragen Laufzeitanalyse (I) und Kürzeste Wege
- Skript: Abschnitt 3.3
07.11.2017:
Materialien und weitere Lektüre:
Tiefensuche in gerichteten Graphen mit Anwendungen, Breitensuche, das Single-Source-Shortest-Path Problem, Bindfadenmodell, Algorithmus von Dijkstra (Korrektheit, Laufzeit O((n+m) log n) mit binären Heaps)- Folien Kapitel Graphalgorithmen (Seiten 11-30)
- Wiederholungsfragen Sample Sort und Tiefensuche
- Skript: Abschnitte 3.1.1, 3.1.2 und 3.2
02.11.2017:
Materialien und weitere Lektüre:
Message Passing Interface, Sample Sort für Parallelrechner mit p Kernen in Zeit O(n/p log2 n) (wenn p ≤ n1/3), Graphen, Tiefensuche in ungerichteten Graphen mit Anwendungen- Folien Kapitel Sortieren (Seiten 80-87)
- Folien Kapitel Graphalgorithmen (Seiten 1-10)
- Wiederholungsfragen Externspeicher und Radixsort
- Skript: Abschnitte 2.6, 2.7 und 3.1.1
26.10.2017:
Materialien und weitere Lektüre:
Wiederholung Auswahlproblem (deterministisch Laufzeit O(n)), 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; 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 Ziffern)24.10.2017:
Materialien und weitere Lektüre:
Wiederholung Quicksort (average-case, warum liegt eine Teilfolge nach einem Rekursionsaufruf immer noch in zufälliger Reihenfolge?); Auswahlproblem (randomisiert mit erwarteter Laufzeit O(n), deterministisch in Laufzeit O(n)), Mergesort (worst-, best- und average-case Θ(n log n)), Sortieren im Externspeicher (einfach mit Θ(n/B log2 n/B) Speicherzugriffen, verbessert mit Θ(n/B logM/B n/B) Zugriffen)19.10.2017:
Materialien und weitere Lektüre:
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, gleiche Analyse für beliebige Eingabe aber uniform zufällige Wahl des Pivotelements.- Folien Kapitel Sortieren (Seiten 25-46)
- Wiederholungsfragen Bubblesort
- Skript: Abschnitte 2.1, 2.2 und 2.2.1
- Sound of Sorting
17.10.2017:
Materialien und weitere Lektüre:
Einführung, Wiederholung (asymptotische Notation, Rekursionsgleichungen), Sortierproblem, Bubble Sort (worst-case Laufzeit Θ(n²), erwartete Laufzeit Θ(n²))- Folien Kapitel Sortieren (Seiten 1-24)
- Skript: Abschnitte 1 und 2.1
- Animation und Code