• Begrüßung, Überblick (Video 11 min, mit Smartplayer, MP4-Datei 19 MByte), Folien. Zum Vergleich: Vorlesungsinhalt vom letzten Jahr
• Ablauf der Vorlesung (Video 3 min, mit Smartplayer, MP4-Datei 17 MByte)
• Ablauf der Übungen (Video 2 min, mit Smartplayer, MP4-Datei 3 MByte)
• Überblick über vergleichsbasierte Sortieralgorithmen (Wiederholung) (Video 23:30 min, mit Smartplayer, MP4-Datei 32 MByte), Folien
  • Sortieren durch Vergleichen (Bubblesort)
  • Sortieren durch Einfügen
  • Sortieren durch Auswahl
  • Quicksort
  • Sortieren durch Verschmelzen (mergesort)
• Asymptotische Laufzeitanalyse, O-Notation (Wiederholung) (Video 15:30 min, mit Smartplayer, MP4-Datei ohne Quizfrage 20 MByte)
• Analyse von Quicksort mit zufälliger Pivotauswahl (Video 19 min, mit Smartplayer, MP4-Datei ohne Quizfragen 31 MByte)

• Topologisches Sortieren (Folien)
  • Problemdefinition und Beispiel (Video 15 min, mit Smartplayer, MP4-Datei 19 MByte)
  • Charakterisierungssatz (Video 5 min, mit Smartplayer, MP4-Datei 7 MByte)
  • Implementierung (Video 16:30 min, mit Smartplayer, MP4-Datei 23 MByte)
  • verbesserte Implementierung (Video 12 min, mit Smartplayer, MP4-Datei 16 MByte)
  • Auswahl der Datenstrukturen; Laufzeit und Speicherplatz (Video 16 min, mit Smartplayer, MP4-Datei 20 MByte)
    • Programm TopoSort.java
    • Man benötigt für dieses Programm auch die Klasse IntReader.java zum Einlesen ganzer Zahlen
    • Das Gleiche in Python3: topoSort.py und intReader.py; eine mehr Python-artige Variante: topoSort-mit-push-und-pop.py

• Abstrakte Datentypen, Folien
• Spezifikation abstrakter Datentypen (Video 13:30 min, mit Smartplayer, MP4-Datei 17 MByte)
  • verbale Spezifikation
  • modellierende Spezifikation. Beispiel: Mengen (Video 10 min, mit Smartplayer, MP4-Datei 13 MByte)
  • algebraische Spezifikation. Beispiel: Mengen (Video 17 min, mit Smartplayer, MP4-Datei ohne Quizfragen 21 MByte)
    • Beweis von Eigenschaften durch algebraische Manipulation
    • Referenzimplementierung direkt aus der Spezifikation in Haskell (Menge.hs, Protokoll der Haskell-Sitzung, Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)

• Stückweise konstante Funktionen (Folien, Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
  • Beispielprogramm, Formulierung mit Generatoren und dem yield-Ausdruck in Python. (Video 18:30 min, mit Smartplayer, MP4-Datei 22 MByte)
  • Python-Programm StueckweiseKonstant_mit_Generator.py (Video 9 min, mit Smartplayer, MP4-Datei ohne Quizfrage 11 MByte)
  • flexiblere Handhabung der Intervallgrenzen; erweiterte Zahlenordnung, Python-Klasse Number_extended.py (Video 13 min, mit Smartplayer, MP4-Datei ohne Quizfrage 16 MByte)
• Nachtrag zur Analyse von Quicksort:
  • Arten der Algorithmenanalyse (Folien, Video 10 min, mit Smartplayer, MP4-Datei 13 MByte)

• Spezifikation von abstrakten Datentypen: Vor- und Nachbedingungen (Folien, Video 10 min, mit Smartplayer, MP4-Datei ohne Quizfrage 13 MByte)
• Beispiel: Menge durch eine Feld konstanter Länge implementiert: SmallIntSet.java (Programm mit Anmerkungen, Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfrage 15 MByte)
• Abstraktionsfunktion
• Darstellungsinvarianten der Implementierung von Datenstrukturen (Video 17 min, mit Smartplayer, MP4-Datei 22 MByte)
• Nebenbedingungen (Zusatzrestriktionen)
• Korrektheit der Implementierung von abstrakten Datentypen
• Einsatz beim Korrektheitsbeweis auf höherer Ebene (Video 4 min, mit Smartplayer, MP4-Datei 5 MByte)
• Unterstützung für Datenabstraktion in verschiedenen Programmiersprachen (Video 5 min, mit Smartplayer, MP4-Datei 6 MByte)

• Wörterbuch als abstrakter Datentyp (dictionary, Map) (Folien, Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)
  • Wörterbuchoperationen: Einfügen, Suchen, Löschen
• Wiederholung: binäre Bäume und Suchbäume (Video 10 min, mit Smartplayer, MP4-Datei 11 MByte)
  • ausgeglichene und entartete Bäume
• Höhenbalancierte Bäume (AVL-Bäume) (Folien, Video 11 min, mit Smartplayer, MP4-Datei ohne Quizfrage 12 MByte)
  • Rotationen und Doppelrotationen (Video 17 min, mit Smartplayer, MP4-Datei 20 MByte)
  • Einfügen
  • Löschen (Video 14 min, mit Smartplayer, MP4-Datei ohne Quizfragen 16 MByte)
• Erweiterte Suchabfragen in Suchbäumen. Beispiel: Rang (Video 7 min, mit Smartplayer, MP4-Datei 9 MByte)

• Skip-Listen (Folien)
  • Einfügen und Löschen (Video 20 min, mit Smartplayer, MP4-Datei ohne Quizfragen 24 MByte)
  • Analyse der Suchzeit (Video 8 min, mit Smartplayer, MP4-Datei 10 MByte)
  • Erwartungswert der Höhe H einer Skipliste (Video 8 min, mit Smartplayer, MP4-Datei 9 MByte, Ausarbeitung vom Vorjahr), partielle Summation

• a-b-Bäume, insbesondere 2-3-Bäume (Folien, Video 8 min, mit Smartplayer, MP4-Datei 10 MByte)
  • Einfügen und Löschen (Video 15 min, mit Smartplayer, MP4-Datei ohne Quizfrage 19 MByte)
  • Erweiterungen
  • B-Bäume für externen Speicher (Video 4 min, mit Smartplayer, MP4-Datei 5 MByte)
• untere Schranken für Wörterbuchoperationen (Folien)
  • Bitvektoren (Video 8 min, mit Smartplayer, MP4-Datei 9 MByte)
  • vergleichsbasierte Algorithmen (Video 11 min, mit Smartplayer, MP4-Datei 13 MByte)
    • Sortieren, Entscheidungsbäume

• Digitale Suchbäume (tries) zum Speichern von Zeichenketten (Folien, Video 13 min, mit Smartplayer, MP4-Datei 17 MByte)
• komprimierte digitale Suchbäume (Video 11 min, mit Smartplayer, MP4-Datei ohne Quizfragen 14 MByte)
• Suffixbäume, Aufbau und Anwendungen (Video 13 min, mit Smartplayer, MP4-Datei ohne Quizfrage 16 MByte)

• Teilwortsuche (Folien)
  • naiver Algorithmus (Video 20 min, mit Smartplayer, MP4-Datei ohne Quizfragen 24 MByte)
  • Definition der Verschiebefunktion
  • Algorithmus von Knuth-Morris-Pratt (1977) (Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)
  • Berechnung der Verschiebefunktion (Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)
  • Hintergrund und Entstehung des Algorithmus (Video 8 min, mit Smartplayer, MP4-Datei 8 MByte)
• Teilwortsuche: Algorithmus von Boyer und Moore (Video 11 min, mit Smartplayer, MP4-Datei 14 MByte)

• Fingerabdrücke nach Rabin-Karp (Folien)
  • Grundidee, Interpretation einer Zeichenkette als Zahl (Video 11:30 min, mit Smartplayer, MP4-Datei 14 MByte)
  • Restklassenbildung (Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfragen 16 MByte)
  • Auswahl des Moduls, Analyse (Video 14 min, mit Smartplayer, MP4-Datei ohne Quizfrage 16 MByte)
• Textsuche mit endlichen Automaten (Video 8 min, mit Smartplayer, MP4-Datei 9 MByte)
• Graphenalgorithmen (Folien)
  • Wiederholung der Grundbegriffe (Video 13 min, mit Smartplayer, MP4-Datei 16 MByte)
  • Speicherung von Graphen im Computer: Adjazenzmatrix und Adjazenzliste
  • Breitensuche, Breitensuchbaum (Video 24 min, mit Smartplayer, MP4-Datei 30 MByte)
  • Tiefensuche, Tiefensuchbaum (Folien, Video 20 min, mit Smartplayer, MP4-Datei 24 MByte)

• kürzeste Wege, der Algorithmus von Dijkstra (Folien)
  • Simulation von Breitensuche, der kürzeste-Wege-Baum (Video 17 min, mit Smartplayer, MP4-Datei 22 MByte)
  • Korrektheit (Video 7 min, mit Smartplayer, MP4-Datei 8 MByte)
  • Reduktion auf O(n²) Laufzeit (Video 22 min, mit Smartplayer, MP4-Datei 26 MByte)
  • Implementierung mit Prioritätswarteschlangen (Video 10 min, mit Smartplayer, MP4-Datei 13 MByte)
• Halden (Folien)
  • Die binäre Halde mit Speicherung in einem Feld (Video 16 min, mit Smartplayer, MP4-Datei ohne Frage 20 MByte)
  • rudmentäre Python-Klasse Halde mit den Operationen einfügen und entferneMin
  • Prioritätswarteschlange  als abstrakter Datentyp (Video 19 min, mit Smartplayer, MP4-Datei 24 MByte)
  • Implementierung als Halde mit Zugriffshenkeln: Halde.py
  • Algorithmus von Dijkstra unter Verwendung dieser Prioritätswarteschlange: Dijkstra.py

• kürzeste Spannbäume (Folien)
  • Aufgabenstellung (Video 10:30 min, mit Smartplayer, MP4-Datei ohne Frage 15 MByte)
  • Bäume in der Informatik und in der Graphentheorie (Video 6:30 min, mit Smartplayer, MP4-Datei ohne Quizfragen 8 MByte)
  • der gierige Algorithmus (Algorithmus von Kruskal) (Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
  • Korrektheit (Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
  • Reduktion von gleichen Kantengewichten auf den Fall verschiedener Kantengewichte durch Stören der Kosten (Video 8 min, mit Smartplayer, MP4-Datei 8 MByte)
  • Nachbemerkung über Sonderfälle
• das UNION-FIND-Problem (Folien)
  • Vereinigung nach Größe (Video 14 min, mit Smartplayer, MP4-Datei 18 MByte)
  • Erwähnt: Pfadverkürzung und die inverse Ackermannfunktion α(n) (Video 14 min, mit Smartplayer, MP4-Datei 15 MByte)

• kürzeste Spannbäume (Folien)
  • der Algorithmus von Prim für kürzeste Spannbäume (Video 13 min, mit Smartplayer, MP4-Datei 16 MByte)
  • der Algorithmus von Borůvka (1926) (Video 8 min, mit Smartplayer, MP4-Datei 10 MByte)
• Hash-Tabellen und gestreute Speicherung (Folien, Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)
  • Multiplikative Hashfunktion (Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfrage 14 MByte)
  • Behandlung von Kollisionen: Verkettete Listen
  • Behandlung von Kollisionen: offene Adressierung, lineares Sondieren (Video 5:30 min, mit Smartplayer, MP4-Datei 6 MByte)
  • Kuckuckshashing (Video 6 min, mit Smartplayer, MP4-Datei 7 MByte)

• Hashtabellen (Folien)
  • Analyse von multiplikativem Hashing (Video 19 min, mit Smartplayer, MP4-Datei 23 MByte)
  • alternative multiplikative Hashfunktionen mit Primzahlen (Video 3 min, mit Smartplayer, MP4-Datei 3 MByte)
  • Hashcodes für längere Schlüssel (Video 11 min, mit Smartplayer, MP4-Datei 13 MByte)
  • Nachbemerkungen (Video 12 min, mit Smartplayer, MP4-Datei 17 MByte)
    • Hashcodes mit Primzahlen
    • Hashcodes variabler Länge mit Polynomen
    • zum Vergleich: Fingerabdruck beim Rabin-Karp-Verfahren zur Teilwortsuche
    • eingebauter hashCode() in Java, siehe Java-Spezifikation, Funktion hash() in Python
    • böswille Wahl von Schlüsseln, siehe denial-of-service via hash algorithm collision
    • kryptographische Hashfunktionen
  • Analyse von Kuckuckshashing (Folien)
    • Wahrscheinlichkeit für Neuaufbau (Video 26 min, mit Smartplayer, MP4-Datei ohne Quizfragen 30 MByte)
    • Kodierungsargument
    • Erwartete Einfügezeit ohne Neuaufbau (Video 18 min, mit Smartplayer, MP4-Datei 22 MByte)
    • Implementierung: Markierung, Draufgängertum
• Ergänzung/Nachtrag/Wiederholung: Multiplikative Inverse modulo m, erweiterter Euklidischer Algorithmus (Folie, Video 10 min, mit Smartplayer, MP4-Datei ohne Quizfrage 13 MByte)

• Systematisches Durchsuchen von Lösungsbäumen/Backtracking (Folie)
  • Das Acht-Damen-Problem (Video 14 min, mit Smartplayer, MP4-Datei 19 MByte)
  • Verbesserte Suche (Video 8:30 min, mit Smartplayer, MP4-Datei 12 MByte)
• Die Klasse P der in Polynomialzeit lösbaren Probleme (Folien)
  • Algorithmische Probleme, Eingabe, Ausgabe (Video 8 min, mit Smartplayer, MP4-Datei 10 MByte)
  • Rechnermodelle: RAM (Registermaschine), Turingmaschine (Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
• Polynomielle Reduzierbarkeit zwischen Problemen (Turing-Reduzierbarkeit): A <_P B (Video 13 min, mit Smartplayer, MP4-Datei ohne Quizfrage 17 MByte)
• Beispiel: Hamiltonkreis <_P Rundreiseproblem (Video 7 min, mit Smartplayer, MP4-Datei 8 MByte)

• Das Erfüllbarkeitsproblem (Satisfiability, SAT) (Folien, Video 14 min, mit Smartplayer, MP4-Datei 17 MByte)
• Graphenfärbung
• Reduktion: Färbbarkeit <_P SAT
• Entscheidungsprobleme, Karp-Reduktion (Video 6 min, mit Smartplayer, MP4-Datei 7 MByte)
• Die Klasse NP, Entscheidungsprobleme, Zertifikatskriterium (Folien, Video 10 min, mit Smartplayer, MP4-Datei 13 MByte)
• NP-schwere und NP-vollständige Probleme (Video 11 min, mit Smartplayer, MP4-Datei 14 MByte)
• Bedeutung der NP-Schwerheit
• Satz von Cook/Levin: SAT ist NP-schwer (Video 10 min, mit Smartplayer, MP4-Datei 13 MByte)

• Beispiel einer Reduktion: SAT <_P 3-Färbbarkeit (Folien, Video 20 min, mit Smartplayer, MP4-Datei ohne Quizfrage 26 MByte)
• Zusammenfassung: NP-Schwerheit, NP, Reduktion
• 3-SAT (Video 6 min, mit Smartplayer, MP4-Datei 8 MByte)
• Listen variabler Länge, amortisierte Analyse (Folien, Video 16 min, mit Smartplayer, MP4-Datei 20 MByte)
• Effizienz von Listenoperationen in Python (Video 5 min, mit Smartplayer, MP4-Datei 7 MByte)
• Mengen und Wörterbücher als abstrakte Datentypen in Java (die Collection- und Map-Klassen), Quellcode
• dynamische Speicherverwaltung, Stapel und Halde, garbage collection (Folien, Video 18 min, mit Smartplayer, MP4-Datei 22 MByte)
• Radix-Sort zum Sortieren von kurzen Daten (Folie, Video 14 min, mit Smartplayer, MP4-Datei 18 MByte)

• Optimale präfixfreie Kodes (Folien, Video 12 min, mit Smartplayer, MP4-Datei 15 MByte)
  • der Algorithmus von Huffman (Video 16 min, mit Smartplayer, MP4-Datei 19 MByte)
  • die Kraft-McMillan'sche Ungleichung (Video 3:30 min, mit Smartplayer, MP4-Datei 4 MByte)
  • Ergänzung: Beweis der Kraft-McMillan'schen Ungleichung für eindeutig entzifferbare Kodes
    • Nachtrag von der 29. Vorlesung: Video zum Beweis 15 min, mit Smartplayer, MP4-Datei 19 MByte)
• Optimale Suchbäume (Folien, Video 17 min, mit Smartplayer, MP4-Datei 22 MByte)
  • dynamische Programmierung (Video 13 min, mit Smartplayer, MP4-Datei 18 MByte)
  • Implementierungen in Python: optSuchbaum.py
  • Zurückverfolgen der Lösung (abspeichern oder neu berechnen)
• Variante: unsystematisches Lösen der Teilprobleme und Tabellieren der Ergebnisse (Merken, memoization) zur Vermeidung von Mehrfachberechnungen (Video 6 min, mit Smartplayer, MP4-Datei ohne Quizfrage 9 MByte)

• Algorithmus von Dantzig für kürzeste Wege mit negativen Kantengewichten (Folien, Video 28 min, mit Smartplayer, MP4-Datei 35 MByte)
• Editierabstand (Folien, Video 22 min, mit Smartplayer, MP4-Datei ohne Quizfrage 27 MByte)
• Dynamische Programmierung und Wege in azyklischen Graphen (Video 12 min, mit Smartplayer, MP4-Datei 17 MByte)

Geometrische Algorithmen:

• konvexe Hülle: Problemdefinition (Folien, Video 7 min, mit Smartplayer, MP4-Datei 9 MByte)
  • konvexe Hülle einer sortierten Punktmenge in linearer Zeit (inkrementeller Algorithmus), Video 14 min, mit Smartplayer, MP4-Datei 18 MByte
  • Laufzeit (Video 4 min, mit Smartplayer, MP4-Datei 5 MByte)
• Orientierungstest (Video 18 min, mit Smartplayer, MP4-Datei 23 MByte)
• Punkt in Polygon (Folien, Video 8 min, mit Smartplayer, MP4-Datei ohne Quizfragen 10 MByte)
  • Sonderfälle (Video 14 min, mit Smartplayer, MP4-Datei 17 MByte)
• Probleme der Gleitkommarechnung

• dichtestes Punktpaar, teile und herrsche (Folien, Video 24 min, mit Smartplayer, MP4-Datei 30 MByte)
• Dynamische Programmierung; das Rundreiseproblem (Folien, Video 16 min, mit Smartplayer, MP4-Datei 20 MByte)

• Übersicht über Algorithmenentwurfsprinzipien: (keine Folien) Video 9:30 min, mit Smartplayer, MP4-Datei 14 MByte)
  • teile und herrsche
    • siehe 1.Vorlesung (Sortieren, 7. Abschnitt) Video 23:30 min, mit Smartplayer, MP4-Datei 32 MByte), Folien
    • siehe 22. Vorlesung (dichtestes Punktpaar)
  • dynamische Programmierung
    • siehe z.B. 19. Vorlesung (optimaler Suchbaum), 20. Vorlesung (Edit-Abstand), 22. Vorlesung (Rundreiseproblem)
  • systematisches Durchsuchen von Lösungsbäumen (backtracking)
    • siehe 16. Vorlesung (Acht-Damen-Problem)
  • gierige Algorithmen (greedy)
    • siehe 13. Vorlesung (kürzeste Spannbäume, Algorithmus von Kruskal)
  • lokale Optimierung, steilster Abstieg
  • heuristische Suchverfahren (z. B. Simulated annealing, genetische Algorithmen, Tabusuche, Ameisenalgorithmen)
• Näherungslösung, Approximationsalgorithmen (Folien, Video 9:30 min, mit Smartplayer, MP4-Datei 12 MByte)
• lokale Optimierung, steilster Abstieg (Video 22 min, mit Smartplayer, MP4-Datei 28 MByte)
  • Zielfunktion, Nachbarschaftsrelation
• heuristische Suche: Simulated annealing (Video 19 min, mit Smartplayer, MP4-Datei 24 MByte)

• Analyse von Stellungsspielen (Folien)
  • Zweipersonen-Nullsummenspiele mit vollständiger Information, Spielgraph (Video 14:30 min, mit Smartplayer, MP4-Datei ohne Quizfrage 17 MByte)
  • Min-Max-Algorithmus, optimale Spielstrategie (Video 13:30 min, mit Smartplayer, MP4-Datei ohne Quizfragen 17 MByte)
  • Exkurs: Optimale Strategie für Tic-Tac-Toe (Video 8 min, mit Smartplayer, MP4-Datei ohne Quizfrage 14 MByte)
  • heuristische Bewertungsfunktion (Video 32 min, mit Smartplayer, MP4-Datei 40 MByte)
  • α-β-Suche

• randomisierte Auswahl des k-kleinsten Elements (Folien, ...)
  • Quickselect (Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)
  • Analyse (Video 15 min, mit Smartplayer, MP4-Datei 17 MByte)
• Nachtrag zur 10. Vorlesung: deterministische 2-Wege-Kellerautomaten und das Teilwortproblem (Folien)
  • direkte Simulation (Video 13:30 min, mit Smartplayer, MP4-Datei 17 MByte)
  • gegliederte Simulation, Abkürzung durch Merken (Video 18 min, mit Smartplayer, MP4-Datei 21 MByte)

• Fallstudie: das 15-Spiel (Folien, Video 27 min, mit Smartplayer, MP4-Datei 39 MByte)
  • Größen der Schichten, Lösungsprogramm
  • Programm 15-Spiel.py
• heuristische Suche mit dem Algorithmus A* (Video 16 min, mit Smartplayer, MP4-Datei ohne Quizfrage 20 MByte)
  • Folien zur Veranschaulichung des Algorithmus (von Prof. Mulzer)
  • Eigenschaften von heuristischen Funktionen (Video 14 min, mit Smartplayer, MP4-Datei 18 MByte)
  • Anwendung auf das 15-Spiel (Video 14 min, mit Smartplayer, MP4-Datei ohne Quizfrage 21 MByte)
  • Programm 15-Spiel-H.py

• längste monoton aufsteigende Teilfolge (Folien, Video 13:30 min, mit Smartplayer, MP4-Datei 16 MByte)
  • Beschleunigung: Bereichsabfragen (Video 9 min, mit Smartplayer, MP4-Datei ohne Quizfrage 11 MByte)
  • Vereinfachung: invertierte Fragestellung (Video 14 min, mit Smartplayer, MP4-Datei 17 MByte)
• Fallstudie: Nonogramme (Folien, Video 15 min, mit Smartplayer, MP4-Datei 22 MByte)
  • Feststellen des Fortschritts (Video 7 min, mit Smartplayer, MP4-Datei 11 MByte)

• Rückblick: randomisierte Algorithmen und Datenstrukturen (keine Folien). Video 6 min, mit Smartplayer, MP4-Datei 10 MByte
• Fallstudie: der Grintsch (Folien)
  • Einführung (Video 11 min, mit Smartplayer, MP4-Datei 12 MByte)
  • Zeitschritte, Rekursion, Normalisierung (Video 15 min, mit Smartplayer, MP4-Datei ohne Quizfrage 18 MByte)
  • Diskretisierung im Raum, Eindeutigkeit der Lösung (Video 15 min, mit Smartplayer, MP4-Datei 19 MByte)
  • Iterationslösung (Video 15 min, mit Smartplayer, MP4-Datei 22 MByte)
  • Zweipersonenspiel (Video 12 min, mit Smartplayer, MP4-Datei 17 MByte)

• Fallstudie: der Grintsch (Fortsetzung), Folien
  • Visualisierung des Spielablaufs (Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfrage 18 MByte)
  • Bewegung des Grintsches, merkwürdige Phänomene (Video 9 min, mit Smartplayer, MP4-Datei 14 MByte)
  • Rechengenauigkeit, Erklärung für merkwürdige Lösungen (Video 5 min, mit Smartplayer, MP4-Datei 8 MByte)
  • Monotonie der Wertefunktion auf Kreisen, Beschleunigung des Programmes, optimale Lösung des ursprünglichen Problems (Video 19 min, mit Smartplayer, MP4-Datei 23 MByte)
    • Programm Grintsch.py aus der Vorlesung
    • beschleunigtes Programm mit Abkürzungen
  • Beweis der Monotonie (Video 10 min, mit Smartplayer, MP4-Datei 15 MByte)
• diskrete Ereignissimulation (Folie, Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)
• Beweis der Kraft-McMillan'schen Ungleichung (Nachtrag zur 19. Vorlesung, Folien, Video 15 min, mit Smartplayer, MP4-Datei 19 MByte)
  • schriftliche Ausarbeitung: Beweis der Kraftschen Ungleichung für eindeutig entzifferbare Kodes

• Fallstudie: die optimale Stadt (Folien, Zeitschriftenartikel)
  • Eigenschaften einer optimalen Stadt (Video 13 min, mit Smartplayer, MP4-Datei 18 MByte)
  • dynamische Programmierung, Definition der Teilprobleme mit zusätzlichen Parametern (Video 11 min, mit Smartplayer, MP4-Datei 16 MByte)
  • Vorwärtsmodus (Video 12 min, mit Smartplayer, MP4-Datei 19 MByte)
  • Programm optimal_town.py