|
|
| (18 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Vorlesung Algorithmen und Datenstrukturen ==
| | (Diese Varianten erfahren eventuell noch ein paar Modifikationen, falls der Professor die Neugestaltung der Startseite akzeptiert. |
| | Bitte schreibt auf der Seite "diskussion" (zweiter Tab auf der Seite), wie euch einzelne Varianten gefallen und welche Änderungen gewünscht werden.) |
|
| |
|
| 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.
| | [[mögliche neue Startseite - Variante 1]] |
|
| |
|
| [[Klausur und Nachprüfung]] | | [[mögliche neue Startseite - Variante 2]] |
|
| |
|
| [[Leistungsnachweise]] | | [[mögliche neue Startseite - Variante 3]] (noch nicht fertig) |
| | |
| [[Übungsbetrieb]]
| |
| | |
| [[Prüfungsvorbereitung]]
| |
| | |
| [[Literatur]]
| |
| | |
| | |
| [[Gliederung der Vorlesung]]
| |
| | |
| <!------------->
| |
| # [[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) [[Gliederung der Vorlesung#Container|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
| |
| <!------------->
| |
| <!---#* 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]] (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)
| |
| | |
| [[Ü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.
| |
| | |
| # [[Media:Übung-1.pdf|Übung]] (Abgabe 24.4.2012) und [[Media:Uebung-1-Musterloesung.pdf|Musterlösung]]
| |
| #* Python-Tutorial
| |
| #* Sieb des Eratosthenes
| |
| #* Wert- und Referenzsemantik
| |
| #* Dynamisches Array
| |
| # [[Media:Uebung-2.pdf|Übung]] (Abgabe 3.5.2012) und [[Media:Uebung-2-Musterloesung.pdf|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
| |
| # [[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
| |
| #* Bestimmung von Pi mit dem Algorithmus von Archimedes
| |
| #* Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
| |
| # [[Media:Uebung-4.pdf|Übung]] (Abgabe '''Montag''' 21.5.2012) <!------------ und [[Media:Musterloesung_4.pdf|Musterlösung]] ---->
| |
| #* Theoretische Aufgaben zur Komplexität
| |
| #* Amortisierte Komplexität von array.append()
| |
| #* Optimierung der Matrizenmultiplikation
| |
| # [[Media:Uebung-5.pdf|Übung]] (31.5.2012) <!------ und [[Media:muster_blatt5.pdf|Musterlösung]] ---->
| |
| #* Implementation und Analyse eines Binärbaumes
| |
| #* Anwendung: einfacher Taschenrechner
| |
| <!------------
| |
| # [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6.2012) und [[Media:muster_blatt6.pdf|Musterlösung]]
| |
| #* 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.)
| |
| #* Suche mit linearer Komplexität
| |
| <!------------
| |
| # [[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
| |
| <!------------
| |
| # [[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
| |
| #* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche
| |
| <!------------
| |
| # [[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.)
| |
| <!------------
| |
| # [[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.)
| |
| <!------------
| |
| # [[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].)
| |
| #* 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.2012</font>)
| |
| #* Greedy-Algorithmen und Dynamische Programmierung
| |
| <!---------------->
| |
| | |
| [[Sonstiges]]
| |
