|
|
| Line 1: |
Line 1: |
| == <div style="font-weight:bold;font-size:107%;text-align:center;">Vorlesung Algorithmen und Datenstrukturen</div>==
| | [[mögliche neue Startseite - Variante 1]] |
| | |
| 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===
| |
| *<div style="font-weight:bold;">[[Übungsaufgaben]] <span style="background-color:red"><- Neue Positionierung!</span></div>
| |
| *[[Klausur und Nachprüfung]]
| |
| *[[Leistungsnachweise]]
| |
| *[[Übungsbetrieb]]
| |
| *[[Prüfungsvorbereitung]]
| |
| *[[Literatur]]
| |
| | |
| ===Gliederung der Vorlesung===
| |
| | |
| <!------------->
| |
| # Kap.: [[Einführung]] (17.4.2012) - [[Gliederung der Vorlesung#Einführung|(detailliertere Beschreibung)]]
| |
| #* Def. von Alg. & Dat., Geschichte // Fund. Alg. & Dat. // Python-Grundlagen
| |
| <!------------->
| |
| # Kap.: [[Container]] (19.4.2012) - [[Gliederung der Vorlesung#Container|(detailliertere Beschreibung)]]
| |
| #* Anford. von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen & Intervalle (Ranges)
| |
| <!------------->
| |
| # Kap.: [[Sortieren]] (24. und 26.4.2012) - [[Gliederung der Vorlesung#Sortieren|(detailliertere Beschreibung)]]
| |
| #* Spez. des Sortierprob. // Selection, Insertion, Merge & Quick Sort und seine Varianten // Vergl. der Anz. der ben. Schritte // Laufzeitmessung in Python
| |
| <!------------->
| |
| # Kap.: [[Korrektheit]] (3. und 8.5.2012) - [[Gliederung der Vorlesung#Korrektheit|(detailliertere Beschreibung)]]
| |
| #* Def. von Korrektheit, Alg.-Spezifikation // Korrektheitsbew. vs. Test. // Vor- & Nachbed., Invar., Prog. by contract // test, exec. paths, unit test, exceptions & exept. handling in python
| |
| <!------------->
| |
| # Kap.: [[Effizienz]] (10. und 15.5.2012) - [[Gliederung der Vorlesung#Effizienz|(detailliertere Beschreibung)]]
| |
| #* Laufzeit & Opt. // Laufzeit vs. Kompl. // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Kompl.
| |
| <!------------->
| |
| # Kap.: [[Suchen]] (22. und 24.5.2012) - [[Gliederung der Vorlesung#Suchen|(detailliertere Beschreibung)]]
| |
| #* Lin. & Bin. Suche in sort. Arrays // Medianprob. // Suchb., balanz. Bäume // selbst-balanz. Bäume, Rotationen // Komplex. der Suche
| |
| <!------------->
| |
| # Kap.: [[Prioritätswarteschlangen]] (29.5.2012) - [[Gliederung der Vorlesung#Prioritätswarteschlangen|(detailliertere Beschreibung)]]
| |
| #* Heap-Datenstruktur // Einfüge- & Löschoperat. // Heapsort // Kompl. des Heaps
| |
| <!------------->
| |
| # Kap.: [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) - [[Gliederung der Vorlesung#Hashing und assoziative Arrays|(detailliertere Beschreibung)]]
| |
| #* Implem. assoz. Arrays mit Bäumen // Hashing & Hashfkten // Implem. assoz. Arrays als Hashtabelle mit lin. Verkettung bzw. mit offener Adressierung // Anwendung des Hashings zur String-Suche: Rabin-Karp-Algorithmus
| |
| <!------------->
| |
| # Kap.: [[Iteration versus Rekursion]] (12.6.2012) - [[Gliederung der Vorlesung#Iteration versus Rekursion|(detailliertere Beschreibung)]]
| |
| #* Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rekurs. Formeln mittels Master- & Substitutionsmeth.
| |
| <!------------->
| |
| # [[Generizität]] (14.6.2012) - [[Gliederung der Vorlesung#Generizität|(detailliertere Beschreibung)]]
| |
| #* Abstrakte Datentypen, Typspez. // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Algeb. Konzepte & Zahlendatentypen // operator overloading in python
| |
| <!------------->
| |
| # Kap.: [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) - [[Gliederung der Vorlesung#Graphen und Graphenalgorithmen|(detailliertere Beschreibung)]]
| |
| #* Einführung // Graphendat., Adjazenzlisten & -matrizen // Gerichtete, ungerichtete, vollständige, planare, duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gew. Graphen // Min. Spannbaum // Kürze. Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Prob. des H.-reisenden, exakte Alg. (erschöpf. Suche, Branch-and-Bound-Meth.) & Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s durch gericht. 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--->
| |
| <!------------->
| |
| # Kap.: [[Randomisierte Algorithmen]] (3. und 5.7.2012) - [[Gliederung der Vorlesung#Randomisierte Algorithmen|(detailliertere Beschreibung)]]
| |
| #* Zufallszahlen, Zyklenlänge, Pitfalls // Zufallszahlengen.: linear congruential generator, Mersenne Twister // Random. vs. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Random. Quicksort // Bsp.e für Monte Carlo: Randomisierte Lösung des k-SAT Prob. // RANSAC-Alg., Erfolgswahrsch., Vergleich mit analyt. Optimierung (Meth. der kleinsten Quadrate)
| |
| <!------------->
| |
| # Kap.: [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012) - [[Gliederung der Vorlesung#Greedy-Algorithmen und Dynamische Programmierung|(detailliertere Beschreibung)]]
| |
| #* Prinz., Aufwandsred. in Entscheidungsbäumen // bereits bek. Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Sched. Prob. & Weighted Interval Sched. Prob. // Bew. der Optimalität beim Sched. Prob.: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dyn. Programmierung
| |
| <!------------->
| |
| # Kap.: [[NP-Vollständigkeit]] (17. und 19.7.2012) - [[Gliederung der Vorlesung#NP-Vollständigkeit|(detailliertere Beschreibung)]]
| |
| #* die Klassen P & NP // NP-Vollständigkeit & Problemreduktion
| |
| <!------------->
| |
| # Kap.: Reserve und/oder Wiederholung (24. und 26.7.2012)
| |
| | |
| ==Sonstiges==
| |
| * [[Gnuplot| Gnuplot Kurztutorial]]
| |
