Neue Startseite: Difference between revisions
From Alda
Jump to navigationJump to search
(nur erstellt) |
(1. Versuch (Verlinkung auf Unterseiten mit Hash funktioniert noch nicht)) |
||
| Line 1: | Line 1: | ||
== Vorlesung Algorithmen und Datenstrukturen == | == Vorlesung Algorithmen und Datenstrukturen == | ||
Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2012 | Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2012 | ||
Die Vorlesung findet ''' | Die Vorlesung findet '''Dienstags''' und '''Donnerstags''' jeweils um 14:15 Uhr in INF 227 (KIP), HS 2 statt. | ||
[[Klausur und Nachprüfung]] | |||
[[Leistungsnachweise]] | |||
[[Übungsbetrieb]] | |||
[[Prüfungsvorbereitung]] | |||
[[Literatur]] | |||
[[Gliederung der Vorlesung]] | |||
<!-------------> | <!-------------> | ||
# [[Einführung]] (17.4.2012) | # [[Einführung]] (17.4.2012) --> [[Gliederung der Vorlesung#Einführung|<detailliertere Beschreibung>]] | ||
#* | #* Def. von Algorithmen und Datenstrukturen, Geschichte // Fundamentale Algo. und Dat. // Python-Grundlagen | ||
<!-------------> | <!-------------> | ||
# [[Container]] (19.4.2012) | # [[Container]] (19.4.2012) [[Gliederung der Vorlesung#Container|detailliertere Beschreibung]] | ||
#* Anforderungen von | #* Anforderungen von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen und Intervalle (Ranges) | ||
<!-------------> | <!-------------> | ||
# [[Sortieren]] (24. und 26.4.2012) | # [[Sortieren]] (24. und 26.4.2012) | ||
| Line 168: | Line 125: | ||
# Reserve und/oder Wiederholung (24. und 26.7.2012) | # 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. | (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. | ||
| Line 181: | Line 138: | ||
#* Entwicklung eines Gewinnalgorithmus für ein Spiel | #* Entwicklung eines Gewinnalgorithmus für ein Spiel | ||
#* Bonus: Dynamisches Array mit verringertem Speicherverbrauch | #* Bonus: Dynamisches Array mit verringertem Speicherverbrauch | ||
# [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5.2012) | # [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5.2012) und [[Media:Uebung-3-Musterlösung.pdf|Musterlösung]] | ||
#* Experimente zur Effektivität von Unit Tests | #* Experimente zur Effektivität von Unit Tests | ||
#* Bestimmung von Pi mit dem Algorithmus von Archimedes | #* Bestimmung von Pi mit dem Algorithmus von Archimedes | ||
| Line 189: | Line 146: | ||
#* Amortisierte Komplexität von array.append() | #* Amortisierte Komplexität von array.append() | ||
#* Optimierung der Matrizenmultiplikation | #* Optimierung der Matrizenmultiplikation | ||
# [[Media:Uebung-5.pdf|Übung]] (31.5.2012) <!------ und [[Media:muster_blatt5.pdf|Musterlösung]] ----> | |||
# [[Media: | |||
#* Implementation und Analyse eines Binärbaumes | #* Implementation und Analyse eines Binärbaumes | ||
#* Anwendung: einfacher Taschenrechner | #* Anwendung: einfacher Taschenrechner | ||
<!------------ | <!------------ | ||
# [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6. | # [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6.2012) und [[Media:muster_blatt6.pdf|Musterlösung]] | ||
#* Treap-Datenstruktur: Verbindung von Suchbaum und Heap | #* Treap-Datenstruktur: Verbindung von Suchbaum und Heap | ||
#* Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | #* Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | ||
#* Suche mit linearer Komplexität | #* Suche mit linearer Komplexität | ||
<!------------ | <!------------ | ||
# [[Media:Übung-7.pdf|Übung]] (Abgabe 12.6. | # [[Media:Übung-7.pdf|Übung]] (Abgabe 12.6.2012) und [[Media:muster_blatt7.pdf|Musterlösung]] | ||
#* Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration | #* Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration | ||
<!------------ | <!------------ | ||
# [[Media:Übung-8.pdf|Übung]] (Abgabe 19.6. | # [[Media:Übung-8.pdf|Übung]] (Abgabe 19.6.2012) und [[Media:muster_blatt8.pdf|Musterlösung]] | ||
#* Elementare Graphenaufgaben: Aufstellen von Adjazenzmatrizen und Adjazenzlisten, planare Graphen | #* Elementare Graphenaufgaben: Aufstellen von Adjazenzmatrizen und Adjazenzlisten, planare Graphen | ||
#* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche | #* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche | ||
<!------------ | <!------------ | ||
# [[Media:Übung-9.pdf|Übung]] (Abgabe 26.6. | # [[Media:Übung-9.pdf|Übung]] (Abgabe 26.6.2012) | ||
#* Fortgeschrittene Graphenaufgaben: Erzeugen einer perfekten Hashfunktion, Routenplaner (Dazu benötigen Sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/entfernungen.txt entfernungen.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | #* Fortgeschrittene Graphenaufgaben: Erzeugen einer perfekten Hashfunktion, Routenplaner (Dazu benötigen Sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/entfernungen.txt entfernungen.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | ||
<!------------ | <!------------ | ||
# [[Media:Übung-10.pdf|Übung]] (Abgabe 3.7. | # [[Media:Übung-10.pdf|Übung]] (Abgabe 3.7.2012) und [[Media:loesung_blatt10.pdf|Musterlösung]] sowie schöne [[Media:ballungsgebiete.pdf|Visualisierung der Ballungsgebiete]] von Thorben Kröger | ||
#* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Problem des Handelsreisenden (Eine <font color=red>neue Version</font> der Datei [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/entfernungen.txt entfernungen.txt] ist verfügbar. Dank an Sven Ebser, Joachim Schleicher und Thorben Kröger für Hilfe bei der Verbesserung der Datei.) | #* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Problem des Handelsreisenden (Eine <font color=red>neue Version</font> der Datei [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/entfernungen.txt entfernungen.txt] ist verfügbar. Dank an Sven Ebser, Joachim Schleicher und Thorben Kröger für Hilfe bei der Verbesserung der Datei.) | ||
<!------------ | <!------------ | ||
# [[Media:Übung-11.pdf|Übung]] (Abgabe 10.7. | # [[Media:Übung-11.pdf|Übung]] (Abgabe 10.7.2012) | ||
#* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/bundesliga-paarungen-08-09.txt bundesliga-paarungen-08-09.txt].) | #* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/bundesliga-paarungen-08-09.txt bundesliga-paarungen-08-09.txt].) | ||
#* Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/noisy-circles.txt noisy-circles.txt].) | #* Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/noisy-circles.txt noisy-circles.txt].) | ||
<!------------- | <!------------- | ||
# [[Media:Übung-12.pdf|Übung]] (<font color=red>Achtung: Abgabe bereits am Mittwoch, 16.7. | # [[Media:Übung-12.pdf|Übung]] (<font color=red>Achtung: Abgabe bereits am Mittwoch, 16.7.2012</font>) | ||
#* Greedy-Algorithmen und Dynamische Programmierung | #* Greedy-Algorithmen und Dynamische Programmierung | ||
<!----------------> | <!----------------> | ||
[[Sonstiges]] | |||
Revision as of 01:38, 27 May 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.
- Einführung (17.4.2012) --> <detailliertere Beschreibung>
- Def. von Algorithmen und Datenstrukturen, Geschichte // Fundamentale Algo. und Dat. // Python-Grundlagen
- Container (19.4.2012) detailliertere Beschreibung
- Anforderungen von Alg. an Container // Einteilung der Container // Grundleg. Container // 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
- Reserve und/oder Wiederholung (24. und 26.7.2012)
(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.
- Übung (Abgabe 24.4.2012) und Musterlösung
- Python-Tutorial
- Sieb des Eratosthenes
- Wert- und Referenzsemantik
- Dynamisches Array
- Ü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
- Ü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
- Übung (Abgabe Montag 21.5.2012)
- Theoretische Aufgaben zur Komplexität
- Amortisierte Komplexität von array.append()
- Optimierung der Matrizenmultiplikation
- Übung (31.5.2012)
- Implementation und Analyse eines Binärbaumes
- Anwendung: einfacher Taschenrechner
