• Überblick
• Ü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)
• Analyse von Quicksort mit randomisierter Pivotauswahl

• Topologisches Sortieren
  • 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
• Laufzeit und Speicherplatz

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

• stückweise konstante Funktionen. Beispielprogramm StueckweiseKonstant.py
• elegantere Formulierung mit Generatoren und dem yield-Ausdruck in Python. StueckweiseKonstant_mit_Generator.py
• flexiblere Handhabung der Intervallgrenzen; erweiterte Zahlenordnung, Python-Klasse Number_extended.py

• Spezifikation von abstrakten Datentypen: Vor- und Nachbedingungen
• Abstraktionsfunktion; Darstellungsinvarianten der Implementierung von Datenstrukturen
• Korrektheit der Implementierung von abstrakten Datentypen
• Beispiel: Menge durch eine Feld konstanter Länge implementiert: SmallIntSet.java
• Unterstützung für Datenabstraktion in verschiedenen Programmiersprachen
• Wörterbuch als abstrakter Datentyp (dictionary, Map)
• Wörterbuchoperationen
• Wiederholung: binäre Bäume und Suchbäume

• Höhenbalancierte Bäume (AVL-Bäume)
• Rotationen und Doppelrotationen
• Einfügen
• Löschen

• Erweiterte Suchabfragen in Suchbäumen. Beispiel: Rang
• Skip-Listen: Analyse; Einfügen und Löschen

• Erwartungswert der Höhe H einer Skipliste (Ausarbeitung), partielle Summation
• a-b-Bäume, insbesondere 2-3-Bäume

• Digitale Suchbäume (tries) zum Speichern von Zeichenketten
• Präfix und Suffix
• komprimierte digitale Suchbäume
• Suffixbäume

• Graphen
  • Wiederholung der Grundbegriffe
  • Speicherung von Graphen im Computer: Adjazenzmatrix und Adjazenzliste

Probeklausur, 90 Minuten

• Teilwortsuche mit Hilfe der Verschiebefunktion: Algorithmus von Knuth-Morris-Pratt
• Berechnung der Verschiebefunktion

• Teilwortsuche: Algorithmus von Boyer und Moore
• Fingerabdrücke nach Rabin-Karp: Grundidee, Darstellung einer Zeichenkette als Zahl

• Fingerabdrücke: Rabin-Karp
• Textsuche mit endlichen Automaten
• Graphenalgorithmen
  • Tiefensuche, Tiefensuchbaum

• Graphenalgorithmen
  • Tiefensuche
• kürzeste Wege, der Algorithmus von Dijkstra; Korrektheit und Laufzeit
• der kürzeste-Wege-Baum

• Prioritätswarteschlange als abstrakter Datentyp; Zugriffszeiger zur Angabe von gespeicherten Elementen
• Implementierung einer Prioritätswarteschlange als Halde mit Zugriffshenkeln: Halde.py

• Implementierung einer Prioritätswarteschlange als Halde mit Zugriffshenkeln: Halde.py
• Algorithmus von Dijkstra unter Verwendung dieser Prioritätswarteschlange; Dijkstra.py
• kürzeste Spannbäume, der gierige Algorithmus
• Bäume in der Informatik und in der Graphentheorie
• Reduktion auf den Fall verschiedener Knotengewichte durch Stören der Kosten

• das UNION-FIND-Problem; Vereinigung nach Größe. Erwähnt: die inverse Ackermannfunktion α(n)
• der Algorithmus von Prim für kürzeste Spannbäume
• der Algorithmus von Borůvka (1926)

• Hash-Tabellen und gestreute Speicherung;
• Behandlung von Kollisionen: Verkettete Listen, offene Adressierung, lineares Sondieren
• Kuckuckshashing

• Analyse von Kuckuckshashing
• Codierungsargument

• gute Hash-Funktionen
• Hashcodes
• Erwähnung: kryptographische Hashfunktionen

• Systematisches Durchsuchen von Lösungsbäumen/Backtracking: Das Acht-Damen-Problem
• Die Klasse P der in Polynomialzeit lösbaren Probleme
• Polynomielle Reduzierbarkeit zwischen Problemen (Turing-Reduzierbarkeit): A <_P B
• Hamiltonkreis <_P Rundreiseproblem

• Das Erfüllbarkeitsproblem (Satisfiability, SAT)
• Graphenfärbung
• Reduktion: Färbbarkeit <_P SAT
• Die Klasse NP, Entscheidungsprobleme, Zertifikatskriterium
• NP-schwere und NP-vollständige Probleme
• Bedeutung der NP-Schwerheit

• Beispiele von Reduktionen: SAT <_P 3-Färbbarkeit
• 3-SAT
• Listen variabler Länge, amortisierte Analyse

• Effizienz von Listenoperationen in Python
• Mengen und Wörterbücher als abstrakte Datentypen in Java (die Collection- und Map-Klassen), Quellcode
• dynamische Speicherverwaltung, Stapel und Halde, garbage collection
• Radix-Sort zum Sortieren von kurzen Daten
• Optimale präfixfreie Kodes

• Optimale Kodes, der Algorithmus von Huffman
• Optimale Suchbäume

Nachtrag: Beweis der Kraftschen Ungleichung für eindeutig entzifferbare Kodes

• Optimale Suchbäume, dynamische Programmierung
• Implementierungen in Python: optSuchbaum.py
• Variante: unsystematisches Lösen der Teilprobleme und Tabellieren der Ergebnisse (memoization) zur Vermeidung von Mehrfachberechnungen
• Rückverfolgung der Lösung (abspeichern oder neu berechnen)
• Algorithmus von Dantzig für kürzeste Wege mit negativen Kantengewichten

• Editierabstand
• randomisierte Auswahl des k-kleinsten Elements, Quickselect
• Geometrische Algorithmen:
• konvexe Hülle einer sortierten Punktmenge in linearer Zeit (inkrementeller Algorithmus)

• dichtestes Punktpaar, teile und herrsche
• Dynamische Programmierung; das Rundreiseproblem

• Nachtrag: Orientierungstest
• Punkt in Polygon
• Probleme der Gleitkommarechnung
• Übersicht über Algorithmenentwurfsprinzipien:
  • teile und herrsche
  • dynamische Programmierung
  • systematisches Durchsuchen von Lösungsbäumen (backtracking)
  • gierige Algorithmen (greedy)
  • heuristische Suchverfahren
  • lokale Optimierung, steilster Abstieg, heuristische Suchverfahren (z. B. Simulated annealing, genetische Algorithmen)
• lokale Optimierung, steilster Abstieg
• heuristische Suche: Simulated annealing, Zielfunktion, Nachbarschaftsrelation

• längste monoton aufsteigende Teilfolge
• Analyse von Zwei-Personen-Spielen, Min-Max-Algorithmus, α-β-Suche