Main Page
From Alda
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
Gliederung der Vorlesung (als PDF mit Übungsthemen)
- 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
- Container (10.4.2008)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
- 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
- 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
- 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
- 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
- Prioritätswarteschlangen (14.5.2008)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Dictionaries (15.5.2008)
- Implementation mit Bäumen
- Hashing
- Implementation als Hashtabelle
- Iteration versus Rekursion (21.5.2008)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Iteratoren
- 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
- 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*)
- 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
- Analytische Optimierung (19.6.2008)
- Methode der kleinsten Quadrate
- Approximation von Geraden
- 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
- Greedy-Algorithmen (2.7.2008)
- Prinzip
- Bedingung für Optimalität
- Beispiele für Greedy-Algorithmen
- Dynamische Programmierung (3. und 9.7.2008)
- 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
- 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.
- Übung (Abgabe 17.4.2008)
- Python-Tutorial
- Sieb des Eratosthenes
- Wert- und Referenzsemantik
- Übung (Abgabe 24.4.2008)
- Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von Problemgröße)
- Entwicklung eines effizienten Algorithmus: Bruchfestigkeit von Gläsern
- Übung (Abgabe 2.5.2008)
- Experimente zur Effektivität von Unit Tests
- Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
- Übung (Abgabe 8.5.2008)
- Theoretische Aufgaben zur Komplexität
- Amortisierte Komplexität von array.append()
- Optimierung der Matrizenmultiplikation
- Übung (Abgabe 15.5.2008)
- Implementation und Analyse eines Binärbaumes
- Anwendung: einfacher Taschenrechner
- Übung (Abgabe 23.5.2008)
- Treap-Datenstruktur: Verbindung von Suchbaum und Heap
- Anwendung: Worthäufigkeiten
- Übung (Abgabe 29.5.2008)
- Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration
- Übung (Abgabe 5.6.2008)
- Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen, Benutzer-definierte Zahlentypen
- Ü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
- Übung (Abgabe 19.6.2008)
- Anwendung: Weg aus einem Labyrinth
- Anwendung: Erzeugen einer perfekten Hashfunktion
- Ü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
- Übung (Abgabe 3.7.2008)
- Naiver (deterministischer) und randomisierter Primzahltest, Laufzeitvergleich
- RANSAC für Kreise
- Übung (Abgabe 10.7.2008)
- Theoretische und praktische Aufgaben zur dynamische Programmierung
- Übung (Abgabe 17.7.2008)
- Sudoku-Löser
