• Überblick: Qualifikationsziele
• Organisatorisches: Vorlesung und Übung
• Überblick über vergleichsbasierte Sortieralgorithmen (Wiederholung)
  • Sortieren durch Vergleichen (Bubblesort)
  • Sortieren durch Einfügen
  • Sortieren durch Auswahl
  • Quicksort
  • Sortieren durch Verschmelzen (mergesort)
• Asymptotische Laufzeitanalyse, O-Notation (Wiederholung). Ω-Notation (untere Schranken), Θ-Notation

Aufzeichnung 90 min. Passwort: Bubblesort123

• Teile und herrsche (divide-and-conquer)
• O-Notation
  • Rekursion T(n)=O(n)+T(l)+T(n−l)
  • Rekursion T(n)=O(n)+T(⌊n/2⌋)+T(⌈n/2⌉)

Aufzeichnung 86 min, Passwort T(n)istO(n^2)

• Topologisches Sortieren
• Charakterisierung der Existenz einer topologischen Sortierung
• Verschiedene Implementierungen. Lineare Laufzeit O(m+n)

Aufnahme 85 min, Passwort TopoSort1

• Topologisches Sortieren:
  • Auswahl der Datenstrukturen
  • Implementierungen in Python und Java
    • 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
  • Zusammenhang mit Graphenproblemen
• O-Notation als Einbahngleichungen
• Quicksort mit randomisierter Pivotauswahl

Aufnahme 92 min, Passwort random.Quicksort3

• Abstrakte Datentypen
• Spezifikation abstrakter Datentypen
  • verbale Spezifikation
  • modellierende Spezifikation. Beispiel: Mengen
  • algebraische Spezifikation. Beispiel: Mengen
    • Beweis von Eigenschaften durch algebraische Manipulation
    • Referenzimplementierung direkt aus der Spezifikation in Haskell (Menge.hs)

Aufnahme 73 min (Anfang fehlt), Passwort Menge123

• Stückweise konstante Funktionen
  • Spezifikation
  • Verschmelzen; Generatorfuktionen und der yield-Ausdruck in Python.
  • Python-Programm StueckweiseKonstant_mit_Generator.py
  • flexiblere Handhabung der Intervallgrenzen; erweiterte Zahlenordnung, Python-Klasse Number_extended.py

Aufnahme 71 min (Anfang fehlt), Passwort Verschmel2en

• Spezifikation von abstrakten Datentypen: Vor- und Nachbedingungen. Beispiel Mengenoperationen
• Beispiel: Menge durch eine Feld konstanter Länge implementiert: SmallIntSet.java
• Abstraktionsfunktion
• Darstellungsinvarianten der Implementierung von Datenstrukturen
• Nebenbedingungen (Zusatzrestriktionen)
• Korrektheit der Implementierung von abstrakten Datentypen
• Einsatz beim Korrektheitsbeweis auf höherer Ebene
• Unterstützung für Datenabstraktion in verschiedenen Programmiersprachen
  • Schnittstellen (interfaces) in Java; abstrakte Klassen
  • Vor- und Nachbedingungen in Eifel 
  • design by contract

Aufnahme 87 min, Passwort Abstrakt1onsfunktion

• Wörterbuch als abstrakter Datentyp (dictionary, map)
• Wörterbuchoperationen: Einfügen, Suchen, Löschen
• geordnetes Wörterbuch
• Wiederholung: binäre Bäume und Suchbäume
  • ausgeglichene und entartete Bäume
• Höhenbalancierte Bäume (AVL-Bäume)
  • Rotationen und Doppelrotationen
  • Einfügen

Aufnahme (1. Teil 24 min, 2. Teil 64 min), Passwort Höhenunterschiednur1

• Löschen in AVL Bäumen
• geordnetes Wörterbuch
• erweiterte Suchabfragen in Suchbäumen. z.B. Rangabfragen und inverse Rangabfragen
  • zusätzliche Attribute in den Knoten
• 2-3-Bäume, a-b-Bäume

Aufnahme 83 min, Passwort 2-3-Baum

• a-b-Bäume
  • Varianten, B-Bäume für externen Speicher
• Digitale Suchbäume (tries) zum Speichern von Zeichenketten
• komprimierte digitale Suchbäume
• Suffixbäume, Aufbau und Anwendungen

Aufnahme 68 min (Anfang fehlt), Passwort Suffixbaum123

• untere Schranken für Wörterbuchoperationen
  • vergleichsbasierte Algorithmen
    • Sortieren, Entscheidungsbäume
  • vergleichsbasierte Datenstrukturen
  • nicht vergleichsbasierte Datenstrukturen (und Sortieralgorithmen)
    • Bitvektoren, digitale Suchbäume, (Hashtabellen), (bucketsort, radixsort)
• Teilwortsuche
  • Algorithmus von Knuth-Morris-Pratt (Python-Programm)

Aufzeichnung 90 min, Passwort Bitvektor-01001

• Teilwortsuche
  • Algorithmus von Knuth-Morris-Pratt, Berechnung der Verschiebefunktion
  • Algorithmus von Boyer-Moore
  • Fingerabdrücke nach Rabin-Karp
    • Auswahl des Moduls
  • Textsuche mit endlichen Automaten

Aufnahme 88 min, Passwort Hash4unktion

• Graphenalgorithmen
  • Wiederholung der Grundbegriffe
  • Speicherung von Graphen im Computer: Adjazenzmatrix und Adjazenzliste
  • Erreichbarkeit
  • Breitensuche, Breitensuchbaum
  • Nicht explizit gespeicherte Graphen bei der Lösungssuche in der künstlichen Intelligenz

Aufnahme 86 min, Passwort gemeinsame5chlangeQ

• Tiefensuche, Tiefensuchbaum
• kürzeste Wege, der Algorithmus von Dijkstra
  • Simulation von Breitensuche, der kürzeste-Wege-Baum
  • Korrektheit
  • Reduktion auf O(n²) Laufzeit
  • Implementierung mit Suchbäumen und Prioritätswarteschlangen
  • Prioritätswarteschlange  als abstrakter Datentyp

Aufzeichnung 90 min, Passwort Tiefensuc4e

• Halden
  • Die binäre Halde mit Speicherung in einem Feld
  • rudmentäre Python-Klasse Halde mit den Operationen einfügen und entferneMin
  • Prioritätswarteschlange  als abstrakter Datentyp
  • Implementierung als Halde mit Zugriffshenkeln: Halde.py
  • Algorithmus von Dijkstra unter Verwendung dieser Prioritätswarteschlange: Dijkstra.py
• kürzeste Spannbäume
  • Aufgabenstellung
  • der gierige Algorithmus (Algorithmus von Kruskal)
  • Korrektheit

teilweise Aufzeichnung 68 min, Passwort Kruskal123

• kürzeste Spannbäume (Fortsetzung)
  • Reduktion von gleichen Kantengewichten auf den Fall verschiedener Kantengewichte durch Stören der Kosten
  • Nachbemerkung über Sonderfälle
• das UNION-FIND-Problem
  • Vereinigung nach Größe
  • Erwähnt: Pfadverkürzung und die inverse Ackermannfunktion α(n)

Aufzeichnung 89 min, Passwort Ackermann1alpha

• 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)
  • Python-Programm 8Damen.py
• 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)
• Graphenfärbung (GRAPHCOL) und die Entscheidungsvariante (Färbbarkeit GRAPHCOL-E)
• Reduktion: Färbbarkeit <_P SAT
• Entscheidungsprobleme, Karp-Reduktion
• Die Klasse NP, Entscheidungsprobleme, Zertifikatskriterium
• NP-schwere und NP-vollständige Probleme
• Bedeutung der NP-Schwerheit
• Satz von Cook/Levin: SAT ist NP-schwer
• Beweis der NP-Schwerheit durch Reduktion

Aufnahme 84 min, Passwort Weihnachten2021

• Beispiel einer Reduktion: SAT <_P 3-Färbbarkeit
• Zusammenfassung: NP-Schwerheit, NP, Reduktion
• 3-SAT
• Hashtabellen, gestreute Speicherung
  • Behandlung von Kollisionen: Verkettete Listen
  • Behandlung von Kollisionen: offene Adressierung, lineares Sondieren
  • Kuckuckshashing
  • Multiplikative Hashfunktion
  • Verhalten in Abhängigkeit vom Belegungsfaktor α=n/s

Aufnahme 89 min, Passwort Modulo2^w

• • Analyse von multiplikativem Hashing
• Hashtabellen
  • Analyse von multiplikativem Hashing
  • alternative multiplikative Hashfunktionen mit Primzahlen
  • Hashcodes für längere Schlüssel
• Zusatzbemerkungen
  • Hashcodes mit Primzahlen
  • Hashcodes variabler Länge mit Polynomen
  • eingebauter hashCode() in Java, siehe Java-Spezifikation, Funktion hash() in Python, Anforderungen an die hash()-Methode
  • böswille Wahl von Schlüsseln, siehe denial-of-service via hash algorithm collision
  • Gegensatz: kryptographische Hashfunktionen

Teilweise Aufzeichnung 68 min, Passwort Wortlänge32

• Analyse von Kuckuckshashing
  • Kodierungsargument

Aufzeichnung 89 min, Passwort Kuckuck1

• Amortisierte Analyse
  • Listen variabler Länge
  • Umbau von Hashtabellen
  • Laufzeit von Listenoperationen in Python
• dynamische Speicherverwaltung, Stapel und Halde, garbage collection

Aufzeichnung 87 min, Passwort A.append(5)

• Radix-Sort zum Sortieren von kurzen Daten
• Optimale präfixfreie Kodes
  • der Algorithmus von Huffman
  • die Kraft-McMillan'sche Ungleichung (erwähnt)
    (Ergänzung: Beweis der Kraft-McMillan'schen Ungleichung für eindeutig entzifferbare Kodes)

Aufzeichnung 83 min, Passwort Opt1Code

• Mengen und Wörterbücher als abstrakte Datentypen in Java (die Collection- und Map-Klassen)
  • Quellcode, siehe zum Beispiel TreeMap.java
• Optimale Suchbäume
  • dynamische Programmierung
  • 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
• Algorithmus von Dantzig für kürzeste Wege mit negativen Kantengewichten

Aufzeichnung 90 min, Passwort opt1Code

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

• Punkt in Polygon
  • Sonderfälle
• Probleme der Gleitkommarechnung
• dichtestes Punktpaar, teile und herrsche

Aufzeichnung 80 min, Passwort Delta1-Delta2

• dynamische Programmierung; das Rundreiseproblem
• Übersicht über Algorithmenentwurfsprinzipien:
  • teile und herrsche
    • siehe Sortieren, dichtestes Punktpaar
  • dynamische Programmierung
    • siehe optimaler Suchbaum, Edit-Abstand, Rundreiseproblem
  • systematisches Durchsuchen von Lösungsbäumen (backtracking)
    • siehe Acht-Damen-Problem
  • gierige Algorithmen (greedy)
    • siehe 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
• längste aufsteigende Teilfolge
  • dynamische Programmierung, O(n²)
  • mit Bereichsabfragen, O(n log n)
  • Darstellung einer Funktion, O(n log n)

Aufnahme 95 min, Passwort Aufsteigend123

• lokale Optimierung, steilster Abstieg
  • Zielfunktion, Nachbarschaftsrelation
• heuristische Suche: Simulated annealing
• diskrete Ereignissimulation
• randomisierte Auswahl des k-kleinsten Elements: Quickselect

Aufzeichnung 87 min, Passwort: 2OPT-Nachbarschaft

• Fallstudie: Lösen von Nonogrammen
• heuristische Suche mit dem Algorithmus A*
  • Folien zur Veranschaulichung des Algorithmus (von Prof. Mulzer)

Aufzeichnung 87 min, Passwort: A-Stern-1

• größte Paarung:
  • gieriger Algorithmus
  • Näherungslösung
• Rückschau: randomisierte Algorithmen und Datenstrukturen
• Fallstudie: Faltung von RNA-Molekülen

Aufzeichnung 70 min, Passwort: 2Drittel-Approximation