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

1. Artikel (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

1. Artikel (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

1. Artikel (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)

1. • Lineare Suche
   • Binäre Suche in sortierten Arrays, Medianproblem
   • Suchbäume, balancierte Bäume
   • selbst-balancierende Bäume, Rotationen
   • Komplexität der Suche
2. Prioritätswarteschlangen (29.5.2012)
   • Heap-Datenstruktur
   • Einfüge- und Löschoperationen
   • Heapsort
   • Komplexität des Heaps
3. 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
4. Iteration versus Rekursion (12.6.2012)
   • Typen der Rekursion und ihre Umwandlung in Iteration
   • Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
5. 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
6. 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
7. 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)
8. 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
9. NP-Vollständigkeit (17. und 19.7.2012)
   • die Klassen P und NP
   • NP-Vollständigkeit und Problemreduktion
10. Reserve und/oder Wiederholung (24. und 26.7.2012)