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

Die Vorlesung findet mittwochs um 11:15 Uhr in INF 227, HS 2 und donnerstags um 11:15 Uhr in INF 308, HS 2 statt.

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: Algebraische 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. Bei Abgabe bis zum folgenden Montag 10:00 Uhr werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

1. Übung (Abgabe 17.4.2008)
   • Python-Tutorial
   • Sieb des Eratosthenes
   • Wert- und Referenzsemantik
2. Übung (Abgabe 24.4.2008)
   • Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von Problemgröße)
   • Entwicklung eines effizienten Algorithmus: Bruchfestigkeit von Gläsern
3. Übung (Abgabe 2.5.2008)
   • Experimente zur Effektivität von Unit Tests
   • Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
4. Übung (Abgabe 8.5.2008)
   • Theoretische Aufgaben zur Komplexität
   • Amortisierte Komplexität von array.append()
   • Optimierung der Matrizenmultiplikation
5. Übung (Abgabe 15.5.2008)
   • Implementation und Analyse eines Binärbaumes
   • Anwendung: einfacher Taschenrechner
6. Übung (Abgabe 23.5.2008)
   • Treap-Datenstruktur: Verbindung von Suchbaum und Heap
   • Anwendung: Worthäufigkeiten
7. Übung (Abgabe 29.5.2008)
   • Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration
8. Übung (Abgabe 5.6.2008)
   • Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen, Benutzer-definierte Zahlentypen
9. Übung (Abgabe 12.6.2008)
   • Elementare Graphenaufgaben (Adjazenzlisten aufschreiben, Beweis e <= 3n-6 für planare Graphen, Zyklen eines vollständigen Graphen)
   • Implementation einer Graphklasse
   • Iteratoren für Tiefensuche und Breitensuche
10. Übung (Abgabe 19.6.2008)
    • Anwendung: Weg aus einem Labyrinth
    • Anwendung: Erzeugen einer perfekten Hashfunktion
11. Übung (Abgabe 26.6.2008)
    • Anwendung: Routenplaner
    • Beispiele für Divide and Conquer: pow-Funktion
    • Beispiel für Methode der kleinsten Quadrate: Approximation von Kreisen
12. Übung (Abgabe 3.7.2008)
    • Naiver (deterministischer) und randomisierter Primzahltest, Laufzeitvergleich
    • RANSAC für Kreise
13. Übung (Abgabe 10.7.2008)
    • Theoretische und praktische Aufgaben zur dynamische Programmierung
14. Übung (Abgabe 17.7.2008)
    • Sudoku-Löser