Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
No edit summary |
|||
| Line 52: | Line 52: | ||
=== Gliederung der Vorlesung === | === Gliederung der Vorlesung === | ||
<!-------------> | <!-------------> | ||
# [[Einführung]] ( | # [[Einführung]] (17.4.2012) | ||
#* Definition von Algorithmen und Datenstrukturen, Geschichte | #* Definition von Algorithmen und Datenstrukturen, Geschichte | ||
#* Fundamentale Algorithmen: create, assign, copy, swap, compare etc. | #* Fundamentale Algorithmen: create, assign, copy, swap, compare etc. | ||
| Line 58: | Line 58: | ||
#* Python-Grundlagen | #* Python-Grundlagen | ||
<!-------------> | <!-------------> | ||
# [[Container]] ( | # [[Container]] (19.4.2012) | ||
#* Anforderungen von Algorithmen an Container | #* Anforderungen von Algorithmen an Container | ||
#* Einteilung der Container | #* Einteilung der Container | ||
| Line 64: | Line 64: | ||
#* Sequenzen und Intervalle (Ranges) | #* Sequenzen und Intervalle (Ranges) | ||
<!-------------> | <!-------------> | ||
# [[Sortieren]] ( | # [[Sortieren]] (24. und 26.4.2012) | ||
#* Spezifikation des Sortierproblems | #* Spezifikation des Sortierproblems | ||
#* Selection Sort und Insertion Sort | #* Selection Sort und Insertion Sort | ||
| Line 72: | Line 72: | ||
#* Laufzeitmessung in Python | #* Laufzeitmessung in Python | ||
<!-------------> | <!-------------> | ||
# [[Korrektheit]] ( | # [[Korrektheit]] (3. und 8.5.2012) | ||
#* Definition von Korrektheit, Algorithmen-Spezifikation | #* Definition von Korrektheit, Algorithmen-Spezifikation | ||
#* Korrektheitsbeweise versus Testen | #* Korrektheitsbeweise versus Testen | ||
| Line 79: | Line 79: | ||
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | #* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | ||
<!-------------> | <!-------------> | ||
# [[Effizienz]] ( | # [[Effizienz]] (10. und 15.5.2012) | ||
#* 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 86: | Line 86: | ||
#* Amortisierte Komplexität | #* Amortisierte Komplexität | ||
<!-------------> | <!-------------> | ||
# [[Suchen]] ( | # [[Suchen]] (22. und 24.5.2012) | ||
#* Lineare Suche | #* Lineare Suche | ||
#* Binäre Suche in sortierten Arrays, Medianproblem | #* Binäre Suche in sortierten Arrays, Medianproblem | ||
| Line 93: | Line 93: | ||
#* Komplexität der Suche | #* Komplexität der Suche | ||
<!-------------> | <!-------------> | ||
# [[Prioritätswarteschlangen]] ( | # [[Prioritätswarteschlangen]] (29.5.2012) | ||
#* Heap-Datenstruktur | #* Heap-Datenstruktur | ||
#* Einfüge- und Löschoperationen | #* Einfüge- und Löschoperationen | ||
| Line 99: | Line 99: | ||
#* Komplexität des Heaps | #* Komplexität des Heaps | ||
<!-------------> | <!-------------> | ||
# [[Hashing und assoziative Arrays]] ( | # [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) | ||
#* Implementation assoziativer Arrays mit Bäumen | #* Implementation assoziativer Arrays mit Bäumen | ||
#* Hashing und Hashfunktionen | #* Hashing und Hashfunktionen | ||
| Line 105: | Line 105: | ||
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus | #* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus | ||
<!-------------> | <!-------------> | ||
# [[Iteration versus Rekursion]] ( | # [[Iteration versus Rekursion]] (12.6.2012) | ||
#* Typen der Rekursion und ihre Umwandlung in Iteration | #* Typen der Rekursion und ihre Umwandlung in Iteration | ||
#* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode | #* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode | ||
<!-------------> | <!-------------> | ||
# [[Generizität]] ( | # [[Generizität]] (14.6.2012) | ||
#* Abstrakte Datentypen, Typspezifikation | #* Abstrakte Datentypen, Typspezifikation | ||
#* Required Interface versus Offered Interface | #* Required Interface versus Offered Interface | ||
| Line 116: | Line 116: | ||
#* Operator overloading in Python | #* Operator overloading in Python | ||
<!-------------> | <!-------------> | ||
# [[Graphen und Graphenalgorithmen]] ( | # [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) | ||
#* Einführung | #* Einführung | ||
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | #* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | ||
| Line 143: | Line 143: | ||
<!---#* Approximation von Geraden---> | <!---#* Approximation von Geraden---> | ||
<!-------------> | <!-------------> | ||
# [[Randomisierte Algorithmen]] (3. und | # [[Randomisierte Algorithmen]] (3. und 5.7.2012) | ||
#* Zufallszahlen, Zyklenlänge, Pitfalls | #* Zufallszahlen, Zyklenlänge, Pitfalls | ||
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister | #* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister | ||
| Line 152: | Line 152: | ||
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate) | #* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate) | ||
<!-------------> | <!-------------> | ||
# [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und | # [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012) | ||
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen | #* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen | ||
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra | #* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra | ||
| Line 158: | Line 158: | ||
#* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung | #* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung | ||
<!-------------> | <!-------------> | ||
# [[NP-Vollständigkeit]] ( | # [[NP-Vollständigkeit]] (17. und 19.7.2012) | ||
#* die Klassen P und NP | #* die Klassen P und NP | ||
#* NP-Vollständigkeit und Problemreduktion | #* NP-Vollständigkeit und Problemreduktion | ||
<!-------------> | <!-------------> | ||
<!-----# [[Quantum computing]] (17.7. | <!-----# [[Quantum computing]] (17.7.2012)----> | ||
== Übungsaufgaben == | == Übungsaufgaben == | ||
Revision as of 19:37, 10 April 2012
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.
Klausur und Nachprüfung
Orte und Termine werden noch bekanntgegeben.
Leistungsnachweise
Für alle Leistungsnachweise ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Im einzelnen können erworben werden:
- ein unbenoteter Übungsschein, falls jemand nicht an der Klausur teilnimmt bzw. die Klausur nicht bestanden wurde.
- ein benoteter Übungsschein (Magister mit Computerlinguistik im Nebenfach, Physik Diplom)
- ein Klausurschein (Magister mit Computerlinguistik im Hauptfach)
- ein Leistungsnachweis über 9 Leistungspunkte (B.A. Computerlinguistik - alte Studienordnung)
- ein Leistungsnachweis über 8 Leistungspunkte (B.Sc. Informatik, B.A. Computerlinguistik - neue Studienordnung)
- ein Leistungsnachweis über 7 Leistungspunkte (B.Sc. Physik).
Übungsbetrieb
- Termine der Übungsgruppen:
- Mo 11:00 - 13:00 Uhr, INF 350 (Otto-Meyerhof-Zentrum, Seiteneingang), Raum 014 (Tutor: Rahul Nair, [mailto:])
- 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, neu: INF 327, Raum SR 5 (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, so aktuell, wie von den Tutoren an mich übermittelt -- UK)
- Zur Klausur wird zugelassen, wer mindestens 50% 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).
Prüfungsvorbereitung
Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay Quizfragen erstellt.
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, einschließlich Graphenalgorithmen)
- T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
- Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)
Gliederung der Vorlesung
- Einführung (17.4.2012)
- Definition von Algorithmen und Datenstrukturen, Geschichte
- Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
- Fundamentale Datenstrukturen: Zahlen, Container, Handles
- Python-Grundlagen
- Container (19.4.2012)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
- Sortieren (24. und 26.4.2012)
- 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 (3. und 8.5.2012)
- 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 (10. und 15.5.2012)
- 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
- Suchen (22. und 24.5.2012)
- 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 (29.5.2012)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Hashing und assoziative Arrays (31.5.und 5.6.2012)
- Implementation assoziativer Arrays mit Bäumen
- Hashing und Hashfunktionen
- Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
- Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
- Iteration versus Rekursion (12.6.2012)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
- Generizität (14.6.2012)
- Abstrakte Datentypen, Typspezifikation
- Required Interface versus Offered Interface
- Adapter und Typattribute, Funktoren
- Beispiel: Algebraische Konzepte und Zahlendatentypen
- Operator overloading in Python
- Graphen und Graphenalgorithmen (19. bis 28.6.2012)
- Einführung
- Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
- Gerichtete und ungerichtete Graphen
- Vollständige Graphen
- Planare Graphen, duale Graphen
- Pfade, Zyklen
- 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
- Randomisierte Algorithmen (3. und 5.7.2012)
- 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)
- Greedy-Algorithmen und Dynamische Programmierung (10. und 12.7.2012)
- 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
- NP-Vollständigkeit (17. und 19.7.2012)
- die Klassen P und NP
- NP-Vollständigkeit und Problemreduktion
Ü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) sowie Musterlösungen für Aufgabe 1 und Aufgabe 2
- 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) und Musterlösung
- Experimente zur Effektivität von Unit Tests
- Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
- Übung (Abgabe 15.5.2008) und Musterlösung
- Theoretische Aufgaben zur Komplexität
- Amortisierte Komplexität von array.append()
- Optimierung der Matrizenmultiplikation
- Übung (neuer Abgabetermin 29.5.2008) und Musterlösung
- Implementation und Analyse eines Binärbaumes
- Anwendung: einfacher Taschenrechner
- Übung (Abgabe 5.6.2008) und Musterlösung
- Treap-Datenstruktur: Verbindung von Suchbaum und Heap
- Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File die-drei-musketiere.txt. Die Zeichenkodierung in diesem File ist Latin-1.)
- Suche mit linearer Komplexität
- Übung (Abgabe 12.6.2008) und Musterlösung
- Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration
- Übung (Abgabe 19.6.2008) und Musterlösung
- Elementare Graphenaufgaben: Aufstellen von Adjazenzmatrizen und Adjazenzlisten, planare Graphen
- Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche
- Übung (Abgabe 26.6.2008)
- Fortgeschrittene Graphenaufgaben: Erzeugen einer perfekten Hashfunktion, Routenplaner (Dazu benötigen Sie das File entfernungen.txt. Die Zeichenkodierung in diesem File ist Latin-1.)
- Übung (Abgabe 3.7.2008) und Musterlösung sowie schöne Visualisierung der Ballungsgebiete von Thorben Kröger
- Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Problem des Handelsreisenden (Eine neue Version der Datei entfernungen.txt ist verfügbar. Dank an Sven Ebser, Joachim Schleicher und Thorben Kröger für Hilfe bei der Verbesserung der Datei.)
- Übung (Abgabe 10.7.2008)
- Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File bundesliga-paarungen-08-09.txt.)
- Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File noisy-circles.txt.)
- Übung (Achtung: Abgabe bereits am Mittwoch, 16.7.2008)
- Greedy-Algorithmen und Dynamische Programmierung
