Algorithmen und Datenstrukturen
Mitteilungen
Die Klausureinsicht zu der Vorlesung "Algorithmen und Datenstrukturen" findet am 10. November 2016 von 09:00 bis 12:00 Uhr im Raum Z 1050 (Zusebau) statt.
Die Klausurergebnisse von "Algorithmen und Datenstrukturen" sind im System eingetragen und über die Thoska Karte abrufbar.
Die Ergebnisse der Bonusklausur "Algorithmen und Datenstrukturen" können Sie in der Übung bzw. im Sekretariat des Institut TI erfragen.
Wenn Sie Gefallen an den in dieser Vorlesung besprochenen Themen gefunden haben, empfehlen wir einen Blick in die Themenliste für das Proseminar "Algorithmen und Komplexität" für Bachelorstudierende im kommenden Wintersemester.
Evaluation der Übung (Stefan Walzer)
Alte Klausuren
Zur Klausurvorbereitung beachten Sie bitte folgende alte Klausuren:
Algorithmen und Datenstrukturen (neu)
- Klausur SS2015
Algorithmen und Datenstrukturen (alt)
- Klausur SS2014
- Klausur SS2013 (nur AuD)
- Klausur SS2012
- Klausur SS2011
- Klausur SS2010
Effiziente Algorithmen (mündliche Prüfung)
- Fragenkatalog mit Beispielfragen
Vorlesungsfolien
1. Teil (AuD)
1. Einführung und Grundlagen
2. Fundamentale Datentypen und Datenstrukturen
3. Binärbäume
4. Suchbäume
5. Hashverfahren
6. Sortieralgorithmen
Druckversion
Blätterversion
[Stand: 19.05.2016]
7. Graphen, Digraphen, Breitensuche
2. Teil (EA + AuD)
8. Divide-and-Conquer-Algorithmen
8/FFT. Schnelle Fourier-Transformation
9. Tiefensuche
10. Greedy-Algorithmen
11. Greedy-Algorithmen für Graphprobleme
12. Dynamische Programmierung
Übungsblätter
1. Teil (AuD)
Übungsblatt 1
Lösung Aufgabe 2d
Übungsblatt 5
Lösung Aufgaben 2, 4
[Stand: 18.05.16]
2. Teil (EA + AuD)
Übungsblatt 11 / Lösung Aufgabe 4
Praktikumsanleitungen
Hausaufgabe
Aufgaben
Praktikum 0
Materialien [Stand: 08.04.2016]
Mögliche Lösung
Termine
Vorlesung:
Donnerstag, 15:00 - 16:30 Uhr, HU-Hs, Prof. M. Dietzfelbinger
Freitag, 13:00 - 14:30 Uhr, HU-Hs
Übungen:
Dienstag, 09:00 - 10:30 Uhr, Sr K 2026, C. Mattern
Mittwoch, 09:00 - 10:30 Uhr, Sr HU 202, C. Mattern
Mittwoch, 11:00 -12:30 Uhr, Sr HU 210, C. Mattern
Praktikum:
Donnerstag (G), 17:00 Uhr, LdV-Hs 2, C. Mattern
Inhalt
1. Teil:
- Spezifikation von Berechnungsproblemen und von abstrakten Datentypen
- Analyse von Algorithmen (Korrektheitsbeweise für iterative und rekursive Verfahren, Laufzeitbegriff, O-Notation, Laufzeitanalyse, Methoden für die Analyse von Laufzeit und Korrektheit)
- Grundlegende Datenstrukturen (Listen, Stacks, Queues, Bäume)
- Binäre Suchbäume, Mehrwegsuchbäume, balancierte Suchbäume (AVL- und/oder Rot-Schwarz-Bäume, B-Bäume)
- Einfache Hashverfahren, universelles Hashing
- Sortierverfahren: Quicksort, Heapsort, Mergesort, Radixsort. Untere Schranke für Sortieren
- Priority Queues mit der Implementierung als Binärheaps
2.Teil:
- Divide-and-Conquer: Multiplikation ganzer Zahlen, Matrixmultiplikation, Master-Theorem, Quickselect, Schnelle Fourier-Transformation
- Grundbegriffe der Graphentheorie, Datenstrukturen für Graphen (Adjazenzmatrix, Kantenliste, Adjazenzlisten, Adjazenzarrays). Durchmustern von Graphen: Breitensuche, Tiefensuche, Zusammenhangskomponenten, Entdecken von Kreisen, topologische Sortierung, starke Zusammenhangskomponenten
- Greedy-Strategie: Teilbares Rucksackproblem, Schedulingprobleme, Huffman-Kodierung, Kürzeste Wege 1: Algorithmus von Dijkstra, Minimale Spannbäume (Algorithmus von Kruskal, Union-Find), Algorithmus von Jarnik/Prim, randomisierter Algorithmus für minimale Schnitte
- Dynamische Programmierung: Editierdistanz, Ganzzahliges Rucksackproblem (mit/ohne Wiederholungen), Kürzeste Wege 2: Algorithmus von Floyd-Warshall, Kürzeste Wege 3: Algorithmus von Bellman-Ford, das Problem des Handlungsreisenden
Literatur
Neben den Vorlesungsfolien empfehlen wir folgende Literatur:
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd Edition, MIT Press, 2009 (auch deutsche Ausgabe verfügbar)
- Mehlhorn, Sanders: Algorithms and Data Structures, The Basic Toolbox, Springer-Verlag, 2008
- Ottmann und Widmayer: Algorithmen und Datenstrukturen, 5. Auflage, Spektrum Akad. Verlag 2012
- Sedgewick: Algorithmen, Addison-Wesley, 2002
Für den zweiten Teil der Vorlesung empfehlen wir weiterhin:
- Dasgupta, Papadimitriou, Vazirani, Algorithms, McGraw-Hill, 2007
- Kleinberg, Tardos, Algorithm Design, Pearson Education, 2005
- Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001
- Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003
Elementare Einführungen:
- Güting, Dieker: Datenstrukturen und Algorithmen, B.G. Teubner Verlag, 2004
- Weicker, Weicker: Algorithmen und Datenstrukturen, Springer-Vieweg, 2013