Main Page

From Alda
Jump to navigationJump to search

Getting started

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.

  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