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 & Datenstrukturen, Geschichte // Fundamentale Algo. & Dat. // Python-Grundlagen
2. Container (19.4.2012) - (detailliertere Beschreibung)
   • Anforderungen von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen & Intervalle (Ranges)
3. Sortieren (24. und 26.4.2012) - (detailliertere Beschreibung)
   • Spez. des Sortierprob. // Selection, Insertion, Merge & Quick Sort und seine Varianten // Vergl. der Anz. der ben. Schritte // Laufzeitmessung in Python
4. Korrektheit (3. und 8.5.2012) - (detailliertere Beschreibung)
   • Def. von Korrektheit, Alg.-Spezifikation // Korrektheitsbew. vs. Test. // Vor- & Nachbed., Inv., Programming by contract // test, execution paths, unit test, exceptions & Ausnahmebehandlung in Python
5. Effizienz (10. und 15.5.2012) - (detailliertere Beschreibung)
   • Laufzeit & Optimierung // Laufzeit vs. Komplexität // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Komplexität
6. Suchen (22. und 24.5.2012) - (detailliertere Beschreibung)
   • Lin. -, Binäre Suche in sort. Arrays // Medianproblem // Suchbäume, balancierte Bäume // selbst-balancierende Bäume, Rotationen // Komplex. der Suche
7. Prioritätswarteschlangen (29.5.2012) - (detailliertere Beschreibung)
   • Heap-Datenstruktur // Einfüge- und Löschoperat. // Heapsort // Kompl. des Heaps
8. Hashing und assoziative Arrays (31.5.und 5.6.2012) - (detailliertere Beschreibung)
   • Impl. assoz. Arrays mit Bäumen // Hashing & Hashfunktionen // Impl. assoz. Arrays als Hashtabelle mit lin. Verkettung bzw. mit offener Adressierung // Anwendung des Hashings zur String-Suche: Rabin-Karp-Algorithmus
9. Iteration versus Rekursion (12.6.2012) - (detailliertere Beschreibung)
   • Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rek. Formeln mittels Master- & Substitutionsmeth.
10. Generizität (14.6.2012) - (detailliertere Beschreibung)
    • Abstrakte Datentypen, Typspezifikation // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Alg. Konz. & Zahlendatentypen // Operator overloading in Python
11. Graphen und Graphenalgorithmen (19. bis 28.6.2012) - (detailliertere Beschreibung)
    • Einführung // Graphendatenstrukturen, Adjazenzlisten & Adjazenzmatrizen // Gerichtete & ungerichtete & vollständige & planare & duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gewichtete Graphen // Minimaler Spannbaum // Kürzeste Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Problem des Handlungsreisenden, exakte Alg. (erschöpfende Suche, Branch-and-Bound-Methode) und Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s 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. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Randomisiertes Quicksort // Bsp.e für Monte Carlo: Randomisierte Lösung des k-SAT Prob. // RANSAC-Alg., Erfolgswahrsch., Vergleich mit analyt. Optimierung (Meth. der kleinsten Quadrate)
13. Greedy-Algorithmen und Dynamische Programmierung (10. und 12.7.2012) - (detailliertere Beschreibung)
    • Prinzipien, Aufwandsred. in Entscheidungsbäumen // bereits bekannte Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Scheduling Prob. und Weighted Interval Sched. Prob. // Bew. der Optimalität beim Sched. Prob.: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dyn. Programmierung
14. NP-Vollständigkeit (17. und 19.7.2012) - (detailliertere Beschreibung)
    • die Klassen P und NP // NP-Vollständigkeit & 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