Algorithmen und Datenstrukturen (Wintersemester 2007/2008)

Dozent: Prof. Dr. Matthias O. Franz
Vorlesung: Dienstags, 8:00-9:30, Hörsaal F023
Übungen: Donnerstags, 9:45-11:15 bzw. 11:30-13:00, Hörsaal G149
Offizielle Vorlesungsseite: Modulseiten Fakultät für Informatik

Die Vorlesung führt in eines der Kerngebiete der Informatik ein: klassische Algorithmen und Datenstrukturen. Im ersten Block werden Suchverfahren behandelt (elementare Suchverfahren, Hashing, Suchbäume, Heaps), im zweiten Graphenalgorithmen (topologisches Sortieren, kürzeste Wege, minimale aufspannende Bäume, Netzwerkflüsse, Zusammenhangskomponenten). Im dritten, kleineren Teil werden Textsuche und, wenn genug Zeit verbleibt, geometrische Algorithmen besprochen. Das Gelernte wird in den Übungen auf konkrete Problemstellungen in C++-Anwendungen umgesetzt.

Ziele:

• Klassische Algorithmen und Datenstrukturen verstehen und anwenden können
• In der Lage sein, abstrakte Beschreibungen von Algorithmen in eine konkrete Programmiersprache - hier C++ - umzusetzen
• Einfache Laufzeitabschätzungen durchzuführen

Voraussetzung:

Erfolgreiche Teilnahme bei Programmiertechnik 2 bei Prof. Dr. Bittel. In den Übungen wird auf einige der dort erarbeiteten Codebausteine zurückgegriffen. Die Vorlesung baut auf die in Programmiertechnik 2 behandelten Themen Komplexitätsanalyse, Sortieralgorithmen und Bäume auf.

Vorlesungsplan

B-Bäume

Datum, Titel	Themen	Material
02.10.2007 Einleitung	Übersicht Suchverfahren: Einleitung und Problemstellung Elementare Suchverfahren: lineare und binäre Suche	Folien Aufgabenblatt 1 Person.h, Kleine Personaldaten-Anwendung, Wörterbuch Deutsch-Englisch, Kleine Wörterbuch-Anwendung Programmierrichtlinien Arbeiten mit der C++-Standardbibliothek (O.Bittel) Probleme beim Übersetzen von Templates (O.Bittel)
09.10.2007 Hashverfahren I	Hashfunktion Hashverfahren mit Verkettung	Folien
16.10.2007 Hashverfahren II 18.10. Abgabe Blatt 1, Aufg. 1, 2, 3 und 6a, b	Offene Hashverfahren Dynamische Hashverfahren
23.10.2007 Binäre Suchbäume	Bäume: Begriffe, Eigenschaften und Traversierung Binäre Suchbäume Gefädelte Suchbäume	Folien Beispielprogramm für binären Suchbaum mit Löschen in searchMinR (O. Bittel)
30.10.2007 Ausgeglichene Bäume I	AVL-Bäume	Folien
06.11.2007 Ausgeglichene Bäume II 08.11. Abgabe Blatt 1, Aufg. 4 und 6c	Treaps Splay-Bäume	Folien
13.11.2007 B-Bäume	B-Bäume 2-3-4-Bäume Schwarz-Rot-Bäume Binäre Bäume	Folien
20.11.2007 Einführung Graphen 22.11. Abgabe Blatt 1, Aufg. 5 und 6d	Einführung und Definitionen Datenstrukturen Elementare Algorithmen	Folien Aufgabenblatt 2 Karte von London Verbindungsdaten Scotland Yard
27.11.2007 Kürzeste Wege in Graphen I	Topologisches Sortieren Kürzeste Wege in ungerichteten Graphen Kürzeste Wege in Distanzgraphen	Folien
04.12.2007 Kürzeste Wege in Graphen II 06.12. Abgabe Blatt 2, Aufg. 1	Gewichtete Digraphen Netzpläne Alle kürzesten Wege in gewichteten Digraphen	Folien
11.12.2007 Minimal aufspannende Bäume	Algorithmus von Prim Algorithmus von Kruskal Vereinigung und Suchen von disjunkten Mengen	Folien
18.12.2007 Flüsse in Netzwerken 20.12. Abgabe Blatt 2, Aufg. 2	Flüsse in Netzwerken Zusammenhangskomponenten	Folien Klausur Wintersemester 2005/2006 Klausur Sommersemester 2006 Musterlösung Sommersemester 2006 (O. Bittel)
08.01.2008 Vorrangswarteschlangen 10.12. Abgabe Blatt 2, Aufg. 3	Elementare Implementierungen Binäre Heaps Index-Heaps Binomial Queues	Folien Aufgabenblatt 3
15.01.2008 Textsuche	Naiver Algorithmus Knuth-Morris-Pratt-Algorithmus Karp-Rabin-Algorithmus	Folien
22.01.2007 Wiederholung und Vorrechnen von Klausuraufgaben 24.01. Abgabe Blatt 3