Neue Startseite: Difference between revisions
From Alda
Jump to navigationJump to search
(Test ob verhashte Verlinkung mit präparierter Seite funktioniert) |
(Erste hoffentlich vollständig funktionierende Version im Bereich Skript) |
||
| Line 15: | Line 15: | ||
<!-------------> | <!-------------> | ||
# [[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 | #* Def. von Algorithmen und Datenstrukturen, Geschichte // Fundamentale Algo. und Dat. // Python-Grundlagen | ||
<!-------------> | <!-------------> | ||
# [[Container]] (19.4.2012) [[Gliederung der Vorlesung#Container|detailliertere Beschreibung]] | # [[Container]] (19.4.2012) - [[Gliederung der Vorlesung#Container|(detailliertere Beschreibung)]] | ||
#* Anforderungen von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen und Intervalle (Ranges) | #* 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) - [[Gliederung der Vorlesung#Sortieren|(detailliertere Beschreibung)]] | ||
#* Spezifikation des | #* Spezifikation des Sortierprob. | ||
#* Selection Sort und Insertion Sort | #* Selection Sort und Insertion Sort | ||
#* Merge Sort | #* Merge Sort | ||
| Line 29: | Line 29: | ||
#* Laufzeitmessung in Python | #* Laufzeitmessung in Python | ||
<!-------------> | <!-------------> | ||
# [[Korrektheit]] (3. und 8.5.2012) | # [[Korrektheit]] (3. und 8.5.2012) - [[Gliederung der Vorlesung#Korrektheit|(detailliertere Beschreibung)]] | ||
#* Definition von Korrektheit, Algorithmen-Spezifikation | #* Definition von Korrektheit, Algorithmen-Spezifikation | ||
#* Korrektheitsbeweise versus Testen | #* Korrektheitsbeweise versus Testen | ||
| Line 36: | Line 36: | ||
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | #* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | ||
<!-------------> | <!-------------> | ||
# [[Effizienz]] (10. und 15.5.2012) | # [[Effizienz]] (10. und 15.5.2012) - [[Gliederung der Vorlesung#Effizienz|(detailliertere Beschreibung)]] | ||
#* 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 43: | Line 43: | ||
#* Amortisierte Komplexität | #* Amortisierte Komplexität | ||
<!-------------> | <!-------------> | ||
# [[Suchen]] (22. und 24.5.2012) - | # [[Suchen]] (22. und 24.5.2012) - [[Gliederung der Vorlesung#Suchen|(detailliertere Beschreibung)]] | ||
#* Lineare Suche | #* Lineare Suche | ||
#* Binäre Suche in sortierten Arrays, Medianproblem | #* Binäre Suche in sortierten Arrays, Medianproblem | ||
| Line 50: | Line 50: | ||
#* Komplexität der Suche | #* Komplexität der Suche | ||
<!-------------> | <!-------------> | ||
# [[Prioritätswarteschlangen]] (29.5.2012) | # [[Prioritätswarteschlangen]] (29.5.2012) - [[Gliederung der Vorlesung#Prioritätswarteschlangen|(detailliertere Beschreibung)]] | ||
#* Heap-Datenstruktur | #* Heap-Datenstruktur | ||
#* Einfüge- und Löschoperationen | #* Einfüge- und Löschoperationen | ||
| Line 56: | Line 56: | ||
#* Komplexität des Heaps | #* Komplexität des Heaps | ||
<!-------------> | <!-------------> | ||
# [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) | # [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) - [[Gliederung der Vorlesung#Hashing und assoziative Arrays|(detailliertere Beschreibung)]] | ||
#* Implementation assoziativer Arrays mit Bäumen | #* Implementation assoziativer Arrays mit Bäumen | ||
#* Hashing und Hashfunktionen | #* Hashing und Hashfunktionen | ||
| Line 62: | Line 62: | ||
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus | #* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus | ||
<!-------------> | <!-------------> | ||
# [[Iteration versus Rekursion]] (12.6.2012) | # [[Iteration versus Rekursion]] (12.6.2012) - [[Gliederung der Vorlesung#Iteration versus Rekursion|(detailliertere Beschreibung)]] | ||
#* 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]] (14.6.2012) | # [[Generizität]] (14.6.2012) - [[Gliederung der Vorlesung#Generizität|(detailliertere Beschreibung)]] | ||
#* Abstrakte Datentypen, Typspezifikation | #* Abstrakte Datentypen, Typspezifikation | ||
#* Required Interface versus Offered Interface | #* Required Interface versus Offered Interface | ||
| Line 73: | Line 73: | ||
#* Operator overloading in Python | #* Operator overloading in Python | ||
<!-------------> | <!-------------> | ||
# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) | # [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) - [[Gliederung der Vorlesung#Graphen und Graphenalgorithmen|(detailliertere Beschreibung)]] | ||
#* Einführung | #* Einführung | ||
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | #* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | ||
| Line 100: | Line 100: | ||
<!---#* Approximation von Geraden---> | <!---#* Approximation von Geraden---> | ||
<!-------------> | <!-------------> | ||
# [[Randomisierte Algorithmen]] (3. und 5.7.2012) | # [[Randomisierte Algorithmen]] (3. und 5.7.2012) - [[Gliederung der Vorlesung#Randomisierte Algorithmen|(detailliertere Beschreibung)]] | ||
#* Zufallszahlen, Zyklenlänge, Pitfalls | #* Zufallszahlen, Zyklenlänge, Pitfalls | ||
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister | #* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister | ||
| Line 109: | Line 109: | ||
#* 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 12.7.2012) | # [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012) - [[Gliederung der Vorlesung#Greedy-Algorithmen und Dynamische Programmierung|(detailliertere Beschreibung)]] | ||
#* 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 115: | Line 115: | ||
#* 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]] (17. und 19.7.2012) | # [[NP-Vollständigkeit]] (17. und 19.7.2012) - [[Gliederung der Vorlesung#NP-Vollständigkeit|(detailliertere Beschreibung)]] | ||
#* die Klassen P und NP | #* die Klassen P und NP | ||
#* NP-Vollständigkeit und Problemreduktion | #* NP-Vollständigkeit und Problemreduktion | ||
Revision as of 01:27, 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.
Organisation
Gliederung der Vorlesung
- 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) - (detailliertere Beschreibung)
- Spezifikation des Sortierprob.
- 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) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Hashing und assoziative Arrays (31.5.und 5.6.2012) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
- Generizität (14.6.2012) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- 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) - (detailliertere Beschreibung)
- 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
