Algorithmen und Datenstrukturen
Vorlesung im Sommersemester 2015
Professor Ulf Leser
Die Vorlesung behandelt klassische Themen aus den Bereichen Algorithmen und Datenstrukturen. Betrachtete Probleme sind z.B. Sortieren, Suchen in Strings, Listen, und Bäumen, Patternmatching und Wegesuchen in Graphen. Die verschiedenen Verfahren werden ausführlich dargestellt und in ihrer Komplexität analysiert. An ausgewählten Beispielen werden Korrektheitsbeweise durchgeführt. Durch die Vorlesung lernen Studierende grundlegende Algorithmen, effiziente Datenstrukturen und eine Reihe von Entwurfstechniken kennen und sind in der Lage, für ein gegebenes algorithmisches Problem verschiedene Lösungsansätze bzgl. ihrer Effizienz zu beurteilen und den am besten geeigneten Ansatz auszuwählen.
Die erste Vorlesung findet am Montag, den 13.4.2015, statt.
Die Vorlesung wird durch eine Übung begleitet. Die Einschreibung in GOYA erfolgt ausschließlich über die Übungen.
Voraussetzungen
Voraussetzung für den Besuch sind gute Kenntnisse in Java.
Prüfungen
Das Modul wird mit einer Klausur abgeschlossen. Voraussetzung zur Zulassung ist die Erreichung von mindestens 50% der Punkte in der Übung. Die Klausurtermine sind:
- 11.8.2015, 11-14 Uhr
- 15.9.2015, 11-14 Uhr
Der Termin für die Klausureinsicht der ersten Klausur ist:
- 27.8.2015, 11-13 Uhr, RUD 25, 3.113
Anrechnung
Das Modul (Vorlesung + Übung) kann angerechnet werden für
- Monobachelor Informatik (typischerweise im zweiten Semester, 9 SP)
- Monobachelor INFOMIT (typischerweise im zweiten Semester, 9 SP)
- Kombibachelor Informatik, Kern- und Zweitfach (typischerweise im vierten Semester, 9 SP)
- Für einige Fächer auch im Beifach Informatik
Literatur zur Vorlesung
- Ottmann, Widmayer: Algorithmen und Datenstrukturen, Spektrum Verlag
- Saake, Sattler: Algorithmen und Datenstrukturen (mit Java), dpunkt.Verlag
- Sedgewick: Algorithmen in Java: Teil 1 - 4, Pearson Studium
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
Themen der Vorlesung
Die Folien werden hier jeweils nach der Vorlesung als PDF erhältlich sein.
- Einführung
- Maschinenmodell und O-Notation
- (Abstrakte) Datentypen
- MaySubArray - ein Problem, viele Lösungen
- Listen
- Anwendungen von Listen
- Sortieren: Einfache Verfahren und untere Schranke
- Merge Sort und Quick Sort (Korrigierte Fassung, 19.5.15)
- Radix Sort und Bucket Sort (Korrigierte Fassung, 19.5.15)
- Suchen und Selektieren (Korrigierte Fassung, 3.6.15)
- Selbst-Organisierende Listen
- Amortisierte Analyse (von SOLs)
- Priority Queues
- (Overflow) Hashing
- Open Hashing (Korrigierte Fassung, 22.6.15)
- Suchbäume
- AVL-Bäume
- Optimale Suchbäume; Tries (Korrigierte Fassung, 5.7.15)
- Graphen - Einführung
- Transitive Hülle, Floyd-Warshall und starke Zusammenhangskomponenten
- Minimal Spanning Trees
Interessante Links
- Intuitive Erklärungen vieler (eher einfacher) Algorithmen
- Sorting as Dancing: Eindrucksvolle Demonstration elementarer Sortierverfahren
- Buch von Sedgewick, R.,"Algorithms in Java", als ebook
- Umfassende und gute Erklärung zur Amortisieren Analyse mit einer Vielzahl weiterer Beispiele