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. Der Termin der Abschlussklausur wird noch bekannt gegeben. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!)
Leistungsnachweise
- Für alle Leistungsnachweise sind die erfolgreiche Teilnahme an den Übungen und das Bestehen der schriftlichen Prüfung erforderlich.
- Es kann ein benoteter Übungsschein oder
- für Informatiker: ein Leistungsnachweis über 8 Leistungspunkte nach ECTS (European Credit Transfer System, vgl. Modulhandbuch B.Sc. Angewandte Informatik) oder
- für Physiker: ein Leistungsnachweis über 7 Leistungspunkte nach ECTS (vgl. Modulhandbuch B.Sc. Physik) erworben werden.
Übungsbetrieb
- Termine der Übungsgruppen:
- Mo 11:00 - 13:00 Uhr, INF 350 (Otto-Meyerhof-Zentrum, Seiteneingang), Raum 014 (Tutor: Rahul Nair)
- Di 11:00 - 13:00 Uhr, INF 350 (Otto-Meyerhof-Zentrum, Seiteneingang), Raum 014 (Tutor: Thomas Gerlach, gerlach@kip.uni-heidelberg.de)
- Mi 14:00 - 16:00 Uhr, INF 328, Raum SR 17B (im ersten OG, Tutor: Christoph Sommer)
- Do 14:00 - 16:00 Uhr, INF 294, Raum -113 (im Untergeschoss, Tutor: Daniel Kondermann, daniel.kondermann@iwr.uni-heidelberg.de)
- Könnte man die E-Mail-Adressen hier nochmal dazuschreiben? Danke!
- Übungsaufgaben (Übungszettel mit Abgabetermin, Musterlösungen)
- aktueller Punktestand (PDF, anonymisiert)
- Zur Klausur wird zugelassen, wer mindestens 60% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen. Es gibt verschiedene Möglichkeiten, Zusatzpunkte zu erlangen (Bonusaufgaben, Anfertigung der Wiki-Seiten, gute Mitarbeit in den Übungen).
Literatur
- R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
- J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil)
- T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung
- Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)
Gliederung der Vorlesung
(Übersicht 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
- Sortieren ohne Schlüsselvergleich, Bucket Sort
- Selection Sort und Insertion 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)
- Lineare Suche
- Binäre Suche in sortierten Arrays, Medianproblem
- 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)
- Prinzip
- Beispiele für Dynamische Programmierung
- 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 11: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.
- Ü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
- Suche mit linearer Komplexität
- Ü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
