Gliederung der Vorlesung

Einführung

(17.4.2012)

Definition von Algorithmen und Datenstrukturen, Geschichte
Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
Fundamentale Datenstrukturen: Zahlen, Container, Handles
Python-Grundlagen

Container

(19.4.2012)

Anforderungen von Algorithmen an Container
Einteilung der Container
Grundlegende Container: Array, verkettete Liste, Stack und Queue
Sequenzen und Intervalle (Ranges)

Sortieren

(24. und 26.4.2012)

Spezifikation des Sortierproblems
Selection Sort und Insertion Sort
Merge Sort
Quick Sort und seine Varianten
Vergleich der Anzahl der benötigten Schritte
Laufzeitmessung in Python

Korrektheit

(3. und 8.5.2012)

Definition von Korrektheit, Algorithmen-Spezifikation
Korrektheitsbeweise versus Testen
Vor- und Nachbedingungen, Invarianten, Programming by contract
Testen, Execution paths, Unit Tests in Python
Ausnahmen (exceptions) und Ausnahmebehandlung in Python

Effizienz

(10. und 15.5.2012)

Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
Laufzeit versus Komplexität
Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
Bester, schlechtester, durchschnittlicher Fall
Amortisierte Komplexität

Suchen

(22. und 24.5.2012)

Lineare Suche
Binäre Suche in sortierten Arrays, Medianproblem
Suchbäume, balancierte Bäume
selbst-balancierende Bäume, Rotationen
Komplexität der Suche

Prioritätswarteschlangen

(29.5.2012)

Heap-Datenstruktur
Einfüge- und Löschoperationen
Heapsort
Komplexität des Heaps

Hashing und assoziative Arrays

(31.5.und 5.6.2012)

Implementation assoziativer Arrays mit Bäumen
Hashing und Hashfunktionen
Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus

Iteration versus Rekursion

(12.6.2012)

Typen der Rekursion und ihre Umwandlung in Iteration
Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode

Generizität

(14.6.2012)

Abstrakte Datentypen, Typspezifikation
Required Interface versus Offered Interface
Adapter und Typattribute, Funktoren
Beispiel: Algebraische Konzepte und Zahlendatentypen
Operator overloading in Python

Graphen und Graphenalgorithmen

(19. bis 28.6.2012)

Einführung
Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
Gerichtete und ungerichtete Graphen
Vollständige Graphen
Planare Graphen, duale Graphen
Pfade, Zyklen
Tiefensuche und Breitensuche
Zusammenhang, Komponenten
Gewichtete Graphen
Minimaler Spannbaum
Kürzeste Wege, Best-first search (Dijkstra)
Most-Promising-first search (A*)
Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten

Randomisierte Algorithmen

(3. und 5.7.2012)

Zufallszahlen, Zyklenlänge, Pitfalls
Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
Randomisierte vs. deterministische Algorithmen
Las Vegas vs. Monte Carlo Algorithmen
Beispiel für Las Vegas: Randomisiertes Quicksort
Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)

Greedy-Algorithmen und Dynamische Programmierung

(10. und 12.7.2012)

Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung

NP-Vollständigkeit

(17. und 19.7.2012)

die Klassen P und NP
NP-Vollständigkeit und Problemreduktion

Reserve und/oder Wiederholung

(24. und 26.7.2012)