Neue Startseite

Vorlesung Algorithmen und Datenstrukturen

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

Die Vorlesung findet Dienstags und Donnerstags jeweils um 14:15 Uhr in INF 227 (KIP), HS 2 statt.

Organisation

• Klausur und Nachprüfung
• Leistungsnachweise
• Übungsbetrieb
• Prüfungsvorbereitung
• Literatur

Gliederung der Vorlesung

1. Einführung (17.4.2012) -> detailliertere Beschreibung
   • Def. von Algorithmen und Datenstrukturen, Geschichte // Fundamentale Algo. und Dat. // Python-Grundlagen
2. Container (19.4.2012) detailliertere Beschreibung
   • Anforderungen von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen und Intervalle (Ranges)
3. Sortieren (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
4. Korrektheit (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
5. Effizienz (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
6. Suchen (22. und 24.5.2012) -> detailliertere Beschreibung
   • Lineare Suche
   • Binäre Suche in sortierten Arrays, Medianproblem
   • Suchbäume, balancierte Bäume
   • selbst-balancierende Bäume, Rotationen
   • Komplexität der Suche
7. Prioritätswarteschlangen (29.5.2012)
   • Heap-Datenstruktur
   • Einfüge- und Löschoperationen
   • Heapsort
   • Komplexität des Heaps
8. 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
9. Iteration versus Rekursion (12.6.2012)
   • Typen der Rekursion und ihre Umwandlung in Iteration
   • Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
10. 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
11. 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
12. 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)
13. 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
14. NP-Vollständigkeit (17. und 19.7.2012)
    • die Klassen P und NP
    • NP-Vollständigkeit und Problemreduktion
15. Reserve und/oder Wiederholung (24. und 26.7.2012)

Übungsaufgaben

(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei Abgabe bis zum folgenden Montag 11:00 Uhr werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

1. Übung (Abgabe 24.4.2012) und Musterlösung
   • Python-Tutorial
   • Sieb des Eratosthenes
   • Wert- und Referenzsemantik
   • Dynamisches Array
2. Übung (Abgabe 3.5.2012) und Musterlösung
   • Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße)
   • Entwicklung eines Gewinnalgorithmus für ein Spiel
   • Bonus: Dynamisches Array mit verringertem Speicherverbrauch
3. Übung (Abgabe 10.5.2012) und Musterlösung
   • Experimente zur Effektivität von Unit Tests
   • Bestimmung von Pi mit dem Algorithmus von Archimedes
   • Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
4. Übung (Abgabe Montag 21.5.2012)
   • Theoretische Aufgaben zur Komplexität
   • Amortisierte Komplexität von array.append()
   • Optimierung der Matrizenmultiplikation
5. Übung (31.5.2012)
   • Implementation und Analyse eines Binärbaumes
   • Anwendung: einfacher Taschenrechner

Sonstiges