Main Page

Getting started

• Wiki Editierhilfe (Wiki-Syntax usw.)
• MediaWiki Manual (für Administratoren)
• Sandbox (zum ungefährlichen Ausprobieren von Änderungen)

Vorlesung Algorithmen und Datenstrukturen

Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2008

Organisatorisches (9.4.2008)

• Übungsbetrieb
• Scheinbedingungen, Credit points
• Klausurtermin

Gliederung der Vorlesung (als PDF mit Übungsthemen)

1. Einführung (9.4.2008)
   • Definition von Algorithmen und Datenstrukturen, Geschichte
   • Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
   • Fundamentale Datenstrukturen: Zahlen, Container, Handles
   • Python-Grundlagen
2. Container (10.4.2008)
   • Anforderungen von Algorithmen an Container
   • Einteilung der Container
   • Grundlegende Container: Array, verkettete Liste, Stack und Queue
   • Sequenzen und Intervalle (Ranges)
3. Sortieren (16. und 17.4.2008)
   • Spezifikation des Sortierproblems
   • Selection Sort
   • Merge Sort
   • Quick Sort und seine Varianten
   • Vergleich der Anzahl der benötigten Schritte
   • Laufzeitmessung in Python
4. Korrektheit (23. und 24.4.2008)
   • 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
5. Effizienz (24. und 30.4.2008)
   • Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
   • Laufzeit versus Komplexität
   • Komplexitätsklassen
   • Bester, schlechtester, durchschnittlicher Fall
   • Amortisierte Komplexität
6. Suchen (7. und 8.5.2008)
   • Binäre Suche in sortierten Arrays
   • Suchbäume
   • balancierte Bäume
   • selbst-balancierende Bäume, Rotationen
   • Komplexität der Suche
7. Prioritätswarteschlangen (14.5.2008)
   • Heap-Datenstruktur
   • Einfüge- und Löschoperationen
   • Heapsort
   • Komplexität des Heaps
8. Dictionaries (15.5.2008)
   • Implementation mit Bäumen
   • Hashing
   • Implementation als Hashtabelle
9. Iteration versus Rekursion (21.5.2008)
   • Typen der Rekursion und ihre Umwandlung in Iteration
   • Iteratoren
10. Generizität (28.und 29.5.2008)
    • Abstrakte Datentypen, Typspezifikation
    • Required Interface versus Offered Interface
    • Adapter und Typattribute, Funktoren
    • Beispiel: Algabraische Konzepte und Zahlendatentypen
    • Operator overloading in Python
11. Graphen und Graphenalgorithmen (4. bis 12.6.2008)
    • Einführung
    • Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
    • Gerichtete und ungerichtete Graphen
    • Vollständiger Graph
    • Pfade, Zyklen
    • Tiefensuche und Breitensuche
    • Zusammenhang, mehrfacher Zusammenhang, Komponenten
    • Gewichtete Graphen
    • Minimaler Spannbaum
    • Kürzeste Wege, Best-first search (Dijkstra)
    • Most-Promising-first search (A*)
12. Prinzipien des Algorithmenentwurfs (18.6.2008)
    • Repetition
    • Orthogonale Zerlegung des Problems
    • Hierarchische Zerlegung der Daten (Divide and Conquer)
    • Randomisierung
    • Optimierung, Zielfunktionen
    • Systematisierung von Algorithmen aus der bisherigen Vorlesung
13. Analytische Optimierung (19.6.2008)
    • Methode der kleinsten Quadrate
    • Approximation von Geraden
14. Randomisierte Algorithmen (25. und 26.6.2008)
    • Zufallszahlen, Zyklenlänge, Pitfalls
    • Zufallsverteilungen, Box-Muller Transformation
    • Randomisierte vs. deterministische Algorithmen
    • Las Vegas vs. Monte Carlo Algorithmen
    • Beispiel für Las Vegas: Randomisiertes Quicksort
    • Beispiele für Monte Carlo: randomisierte Integration, randomisierter Primzahltest
    • RANSAC-Algorithmus, Erfolgswahrscheinlichkeit
15. Greedy-Algorithmen (2.7.2008)
    • Prinzip
    • Bedingung für Optimalität
    • Beispiele für Greedy-Algorithmen
16. Dynamische Programmierung (3. und 9.7.2008)
17. Erschöpfende Suche (10. und 16.7.2008)
    • Beispiele: u.a. Problem des Handlungsreisenden
    • Exponentielle Komplexität, NP-Vollständigkeit
    • Approximation bei NP-vollständigen Problemen
18. Quantum computing (17.7.2008)

Übungsaufgaben

(im PDF Format)