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) - (detailliertere Beschreibung)
   • Spez. des Sortierprob. // 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) - (detailliertere Beschreibung)
   • 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) - (detailliertere Beschreibung)
   • 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) - (detailliertere Beschreibung)
   • Heap-Datenstruktur // Einfüge- und Löschoperationen // Heapsort // Komplexität des Heaps
8. Hashing und assoziative Arrays (31.5.und 5.6.2012) - (detailliertere Beschreibung)
   • Implementation assoziativer Arrays mit Bäumen // Hashing und Hashfunktionen // Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierun // Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
9. Iteration versus Rekursion (12.6.2012) - (detailliertere Beschreibung)
   • Typen der Rekursion und ihre Umwandlung in Iteration // Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
10. Generizität (14.6.2012) - (detailliertere Beschreibung)
    • 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) - (detailliertere Beschreibung)
    • Einführung // Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen // Gerichtete und ungerichtete Graphen // Vollständige Graphen // Planare Graphen, duale Graphen // Pfade, Zykle // 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) - (detailliertere Beschreibung)
    • 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) - (detailliertere Beschreibung)
    • 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) - (detailliertere Beschreibung)
    • 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