Algorithmen und Datenstrukturen (ESE)
Entwurf, Analyse und Umsetzung von Algorithmen (IEMS)
Junior-Prof. Dr. Olaf Ronneberger
Diese Vorlesung führt grundlegende Algorithmen und Datenstrukturen ein. Sie lernen, den Ressourcenverbrauch (insbesondere Laufzeit) eines gegebenen Programms zu analysieren, sowohl theoretisch (asymptotische Analyse) also auch praktisch (konkrete Laufzeitabschätzung). Ebenso lernen Sie die Optimalität eines Programms beurteilen, sowohl theoretisch (untere Schranken) als auch praktisch (läuft das Programm so schnell wie es könnte).
| Vorlesungen: (2 SWS) |
Donnerstags 10-12, Raum: 101 SR 00-010/14 |
| Übungen: (1 SWS) |
Montags, 13-14, Raum: 101 SR 00-010/14 (nach Bedarf) Kontakt: Claudius Korzen |
| Beginn: | Donnerstag, 23.10.2013 |
| ECTS-Punkte: | ESE: 4; IEMS: 6 |
| Semester lt Studienplan: | ESE: 3 |
| Klausur: | Freitag, 27.2.2015, 16.00 - 18.00 Uhr, "Kinohörsaal" unter der Mensa (Gebäude 082 Raum HS 00-006) PDF der Klausur mit Musterlösung & Bewertungsschlüssel |
| Voraussetzungen: | Grundlegende Kenntnisse in einer objekt-orientieren höheren Programmiersprache (Java oder C++) |
| Links: |
|
Übungen
| No | Ausgabe | Abgabe (ESE) | Abgabe (IEMS) | Materialien & Links |
|---|---|---|---|---|
| 1 | 22.10.2014 | 30.10.2014 | 13.11.2014 |
Insertion Sort; Heaps; Daphne, SVN, Jenkins uebungsblatt-01.pdf |
| 2 | 30.10.2014 | 6.11.2014 | 20.11.2014 |
Induktionsbeweise, Implementation Heapsort uebungsblatt-02.pdf |
| 3 | 6.11.2014 | 13.11.2014 | 27.11.2014 |
O-Notation, Theta und Omega uebungsblatt-03.pdf, Aufzeichnung der Uebungsstunde am 17.11.: Uebung_AlgoDatESE+IEMS_03.mp4 |
| 4 | 13.11.2014 | 20.11.2014 | 4.12.2014 |
assoziative Arrays, häufigster Städtename uebungsblatt-04.pdf, und allCountries.zip (269MB). Code aus der Vorlesung: spike.cpp, Makefile |
| 5 | 20.11.2014 | 27.11.2014 | 11.12.2014 |
universelles Hashing uebungsblatt-05v2.pdf (update vom 22.11.2014 in rot), Ergebnistabelle Hashing |
| 6 | 27.11.2014 | 4.12.2014 | 18.12.2014 |
PriorityQueue implementieren uebungsblatt-06.pdf PriorityQueueItem_PseudoCode.h PriorityQueue_PseudoCode.h |
| 7 | 4.12.2014 | 11.12.2014 | 8.1.2015 |
Dynamic Array implementieren, amortisierte Analyse uebungsblatt-07.pdf DynamicArrayTest.cpp DynamicArray.h DynamicArray.cpp DynamicArrayMain.cpp DynamicArrayTest.java DynamicArray.java DynamicArrayMain.java MagicSystem.java |
| 8 | 11.12.2014 | 18.12.2014 | 15.1.2015 |
Cache-Effizienz uebungsblatt-08.pdf Code dazu: ArraySumMain.java |
| 9 | 18.12.2014 | 8.1.2015 | 22.1.2015 |
Master-Theorem uebungsblatt-09.pdf |
| 10 | 8.1.2015 | 15.1.2015 | 29.1.2015 |
Binary Search Tree implementieren uebungsblatt-10.pdf vorlesung-10.zip (Beispiel-Code für eine doppelt verkettete Liste) BinarySearchTreeNode.H (Pseudo-Code-Vorlage für die Übungsaufgabe) BinarySearchTree.H |
| 11 | 15.1.2015 | 22.1.2015 | 5.2.2015 |
Beweis O(n) für (4,9) Bäume uebungsblatt-11.pdf |
| 12 | 22.1.2015 | 29.1.2015 | 12.2.2015 |
Graph-Klasse, Largest Connected Component uebungsblatt-12.pdf Graph.H (Pseudocode-Vorlage), code_vorlesung_12.zip (Code aus der Vorlesung) saarland.graph (16MB), Ergebnistabelle LCC |
| 13 | 29.1.2015 | 5.2.2015 | 19.2.2015 |
Dijkstra's Algorithmus uebungsblatt-13.pdf bawue_bayern.zip (102MB), Ergebnistabelle Dijkstra's Algorithmus |
| 14 | 5.2.2015 | 12.2.2015 | 19.2.2015 (nur 2 Wochen Bearbeitungszeit, damit die Musterlösungen rechtzeitig zur Klausurvorbereitung online gestellt werden können) |
Dynamische Programmierung, Editierdistanz uebungsblatt-14.pdf Code aus der Vorlesung aol-query-log.zip (8.6MB), Ergebnistabelle Editierdistanz |
Vorlesungen
| No | Datum | Themen | Folien | Aufzeichnungen (je ca. 105MB) |
|---|---|---|---|---|
| 1 | Do, 23.10.2014 | Einführung, Organisatorisches, Sortieren | Vorlesung_AlgoDatESE+IEMS_01.pdf, Vorlesung_AlgoDatESE+IEMS_01_handout.pdf | Vorlesung_AlgoDatESE+IEMS_01.mp4 |
| 2 | Do, 30.10.2014 | Laufzeitanalyse MinSort und HeapSort, Induktionsbeweise | Vorlesung_AlgoDatESE+IEMS_02.pdf | Vorlesung_AlgoDatESE+IEMS_02.mp4 |
| 3 | Do, 06.11.2014 | O-Notation, Theta, Omega | Vorlesung_AlgoDatESE+IEMS_03.pdf | Vorlesung_AlgoDatESE+IEMS_03.mp4 |
| 4 | Do, 13.11.2014 | Mittlere Laufzeit, Assoziative Arrays aka Maps | Vorlesung_AlgoDatESE+IEMS_04.pdf | Vorlesung_AlgoDatESE+IEMS_04.mp4 |
| 5 | Do, 20.11.2014 | Wie baut man eine Hash Map, universelles Hashing | Vorlesung_AlgoDatESE+IEMS_05.pdf | Vorlesung_AlgoDatESE+IEMS_05.mp4 |
| 6 | Do, 27.11.2014 | Hashing Kollisionsbehandlung, Prioritätswarteschlangen | Vorlesung_AlgoDatESE+IEMS_06.pdf | Vorlesung_AlgoDatESE+IEMS_06.mp4 |
| 7 | Do, 04.12.2014 | Dynamische Felder und amortisierte Analyse | Vorlesung_AlgoDatESE+IEMS_07.pdf | Vorlesung_AlgoDatESE+IEMS_07.mp4 |
| 8 | Do, 11.12.2014 | Cache-Effizienz, "Teile und Herrsche" | Vorlesung_AlgoDatESE+IEMS_08.pdf | Vorlesung_AlgoDatESE+IEMS_08.mp4 |
| 9 | Do, 18.12.2014 | Teile und Herrsche, Mastertheorem | Vorlesung_AlgoDatESE+IEMS_09.pdf | Vorlesung_AlgoDatESE+IEMS_09.mp4 |
| 10 | Do, 08.01.2015 | Verkettete Listen, binäre Suchbäume | Vorlesung_AlgoDatESE+IEMS_10.pdf | Vorlesung_AlgoDatESE+IEMS_10.mp4 |
| 11 | Do, 15.01.2015 | Balancierte Suchbäume | Vorlesung_AlgoDatESE+IEMS_11.pdf | Vorlesung_AlgoDatESE+IEMS_11.mp4 |
| 12 | Do, 22.01.2015 | Graphen, Breitensuche, Tiefensuche, Zusammenhangskomponenten | Vorlesung_AlgoDatESE+IEMS_12.pdf | Vorlesung_AlgoDatESE+IEMS_12.mp4 |
| 13 | Do, 29.01.2015 | Kürzeste Wege, Dijkstras Algorithmus | Vorlesung_AlgoDatESE+IEMS_13.pdf (Update 2.3.2015: Folie 23) | Vorlesung_AlgoDatESE+IEMS_13.mp4 |
| 14 | Do, 05.02.2015 | Editierdistanz, dynamisches Programmieren | Vorlesung_AlgoDatESE+IEMS_14.pdf | Vorlesung_AlgoDatESE+IEMS_14.mp4 |
| 15 | Do, 12.02.2015 | Evaluation, Klausur, Vorstellung Arbeitsgruppe | Vorlesung_AlgoDatESE+IEMS_15.pdf | Vorlesung_AlgoDatESE+IEMS_15.mp4 |
last changed: 2015-01-21 by Olaf Ronneberger