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

Übungsaufgaben

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). Die Abgabe erfolgt am angegebenen Tag bis 10:00 Uhr per Email bei dem jeweiligen Übungsgruppenleiter.

1. Übung (Abgabe 17.4.2008)
   • Python-Tutorial
   • Sieb des Eratosthenes
   • Wert- und Referenzsemantik
2. Übung (Abgabe 24.4.2008)
3. Übung (Abgabe 2.5.2008)
4. Übung (Abgabe 8.5.2008)
5. Übung (Abgabe 15.5.2008)
6. Übung (Abgabe 23.5.2008)
7. Übung (Abgabe 29.5.2008)
8. Übung (Abgabe 5.6.2008)
9. Übung (Abgabe 12.6.2008)
10. Übung (Abgabe 19.6.2008)
11. Übung (Abgabe 26.6.2008)
12. Übung (Abgabe 3.7.2008)
13. Übung (Abgabe 10.7.2008)
14. Übung (Abgabe 17.7.2008)
    • Sudoku-Löser