Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
| Line 58: | Line 58: | ||
#* Laufzeitmessung in Python | #* Laufzeitmessung in Python | ||
<!-------------> | <!-------------> | ||
# [[Korrektheit]] (23. | # [[Korrektheit]] (23. - 30.4.2008) | ||
#* Definition von Korrektheit, Algorithmen-Spezifikation | #* Definition von Korrektheit, Algorithmen-Spezifikation | ||
#* Korrektheitsbeweise versus Testen | #* Korrektheitsbeweise versus Testen | ||
| Line 65: | Line 65: | ||
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | #* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | ||
<!-------------> | <!-------------> | ||
# [[Effizienz]] ( | # [[Effizienz]] (30.4. - 8.5.2008) | ||
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | #* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | ||
#* Laufzeit versus Komplexität | #* Laufzeit versus Komplexität | ||
| Line 72: | Line 72: | ||
#* Amortisierte Komplexität | #* Amortisierte Komplexität | ||
<!-------------> | <!-------------> | ||
# [[Suchen]] ( | # [[Suchen]] (14. und 15.5.2008) | ||
#* Lineare Suche | #* Lineare Suche | ||
#* Binäre Suche in sortierten Arrays, Medianproblem | #* Binäre Suche in sortierten Arrays, Medianproblem | ||
| Line 79: | Line 79: | ||
#* Komplexität der Suche | #* Komplexität der Suche | ||
<!-------------> | <!-------------> | ||
# [[Prioritätswarteschlangen]] ( | # [[Prioritätswarteschlangen]] (21.5.2008) | ||
#* Heap-Datenstruktur | #* Heap-Datenstruktur | ||
#* Einfüge- und Löschoperationen | #* Einfüge- und Löschoperationen | ||
| Line 85: | Line 85: | ||
#* Komplexität des Heaps | #* Komplexität des Heaps | ||
<!-------------> | <!-------------> | ||
# [[Dictionaries]] ( | # [[Dictionaries]] (28.5.2008) | ||
#* Implementation mit Bäumen | #* Implementation mit Bäumen | ||
#* Hashing | #* Hashing | ||
#* Implementation als Hashtabelle | #* Implementation als Hashtabelle | ||
<!-------------> | <!-------------> | ||
# [[Iteration versus Rekursion]] ( | # [[Iteration versus Rekursion]] (29.5.2008) | ||
#* Typen der Rekursion und ihre Umwandlung in Iteration | #* Typen der Rekursion und ihre Umwandlung in Iteration | ||
#* Iteratoren | #* Iteratoren | ||
<!-------------> | <!-------------> | ||
# [[Generizität]] ( | # [[Generizität]] (4. und 5.6.2008) | ||
#* Abstrakte Datentypen, Typspezifikation | #* Abstrakte Datentypen, Typspezifikation | ||
#* Required Interface versus Offered Interface | #* Required Interface versus Offered Interface | ||
| Line 101: | Line 101: | ||
#* Operator overloading in Python | #* Operator overloading in Python | ||
<!-------------> | <!-------------> | ||
# [[Graphen und Graphenalgorithmen]] ( | # [[Graphen und Graphenalgorithmen]] (11. bis 19.6.2008) | ||
#* Einführung | #* Einführung | ||
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | #* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | ||
| Line 114: | Line 114: | ||
#* Most-Promising-first search (A*) | #* Most-Promising-first search (A*) | ||
<!-------------> | <!-------------> | ||
# [[Prinzipien des Algorithmenentwurfs]] ( | # [[Prinzipien des Algorithmenentwurfs]] (25.6.2008) | ||
#* Repetition | #* Repetition | ||
#* Orthogonale Zerlegung des Problems | #* Orthogonale Zerlegung des Problems | ||
| Line 122: | Line 122: | ||
#* Systematisierung von Algorithmen aus der bisherigen Vorlesung | #* Systematisierung von Algorithmen aus der bisherigen Vorlesung | ||
<!-------------> | <!-------------> | ||
# [[Analytische Optimierung]] ( | # [[Analytische Optimierung]] (25.6.2008) | ||
#* Methode der kleinsten Quadrate | #* Methode der kleinsten Quadrate | ||
#* Approximation von Geraden | #* Approximation von Geraden | ||
<!-------------> | <!-------------> | ||
# [[Randomisierte Algorithmen]] ( | # [[Randomisierte Algorithmen]] (26.6. und 2.7.2008) | ||
#* Zufallszahlen, Zyklenlänge, Pitfalls | #* Zufallszahlen, Zyklenlänge, Pitfalls | ||
#* Zufallsverteilungen, Box-Muller Transformation | #* Zufallsverteilungen, Box-Muller Transformation | ||
| Line 135: | Line 135: | ||
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit | #* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit | ||
<!-------------> | <!-------------> | ||
# [[Greedy-Algorithmen]] ( | # [[Greedy-Algorithmen]] (3.7.2008) | ||
#* Prinzip | #* Prinzip | ||
#* Bedingung für Optimalität | #* Bedingung für Optimalität | ||
#* Beispiele für Greedy-Algorithmen | #* Beispiele für Greedy-Algorithmen | ||
<!-------------> | <!-------------> | ||
# [[Dynamische Programmierung]] ( | # [[Dynamische Programmierung]] (9.7.2008) | ||
#* Prinzip | #* Prinzip | ||
#* Beispiele für Dynamische Programmierung | #* Beispiele für Dynamische Programmierung | ||
Revision as of 13:41, 24 April 2008
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, rnair (at) gmx (punkt) de)
- 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, christoph.sommer@iwr.uni-heidelberg.de)
- Do 14:00 - 16:00 Uhr, INF 294, Raum -113 (im Untergeschoss, Tutor: Daniel Kondermann, daniel.kondermann@iwr.uni-heidelberg.de)
- Ü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
- Selection Sort und Insertion Sort
- Merge Sort
- Quick Sort und seine Varianten
- Vergleich der Anzahl der benötigten Schritte
- Laufzeitmessung in Python
- Korrektheit (23. - 30.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 (30.4. - 8.5.2008)
- Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
- Laufzeit versus Komplexität
- Komplexitätsklassen
- Bester, schlechtester, durchschnittlicher Fall
- Amortisierte Komplexität
- Suchen (14. und 15.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 (21.5.2008)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Dictionaries (28.5.2008)
- Implementation mit Bäumen
- Hashing
- Implementation als Hashtabelle
- Iteration versus Rekursion (29.5.2008)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Iteratoren
- Generizität (4. und 5.6.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 (11. bis 19.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 (25.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 (25.6.2008)
- Methode der kleinsten Quadrate
- Approximation von Geraden
- Randomisierte Algorithmen (26.6. und 2.7.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 (3.7.2008)
- Prinzip
- Bedingung für Optimalität
- Beispiele für Greedy-Algorithmen
- Dynamische Programmierung (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) und Musterlösung
- 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 (neuer Abgabetermin 7.5.2008)
- Experimente zur Effektivität von Unit Tests
- Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
- Übung (Abgabe 15.5.2008)
- Theoretische Aufgaben zur Komplexität
- Amortisierte Komplexität von array.append()
- Optimierung der Matrizenmultiplikation
- Übung (Abgabe 23.5.2008)
- Implementation und Analyse eines Binärbaumes
- Anwendung: einfacher Taschenrechner
- Übung (Abgabe 29.5.2008)
- Treap-Datenstruktur: Verbindung von Suchbaum und Heap
- Anwendung: Worthäufigkeiten
- Suche mit linearer Komplexität
- Übung (Abgabe 5.6.2008)
- Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration
- Übung (Abgabe 12.6.2008)
- Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen, Benutzer-definierte Zahlentypen
- Übung (Abgabe 19.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 26.6.2008)
- Anwendung: Weg aus einem Labyrinth
- Anwendung: Erzeugen einer perfekten Hashfunktion
- Übung (Abgabe 3.7.2008)
- Anwendung: Routenplaner
- Beispiele für Divide and Conquer: pow-Funktion
- Beispiel für Methode der kleinsten Quadrate: Approximation von Kreisen
- Übung (Abgabe 10.7.2008)
- Naiver (deterministischer) und randomisierter Primzahltest, Laufzeitvergleich
- RANSAC für Kreise
- Übung (Abgabe 17.7.2008)
- Theoretische und praktische Aufgaben zur dynamische Programmierung
