Datenstrukturen und Algorithmen (SS 2007)

Peter Rossmanith

Bereich

4+2 SWS Pflichtvorlesung für den Bachelorstudiengang Informatik

Zeit und Ort

Vorlesung dienstags und freitags 14:00-15:30 Uhr im Audimax
Fragestunde, neuer Termin: montags 14:00-15:30 Uhr im AH II

Voraussetzungen

Stoff der Vorlesung "Programmierung" sowie Grundkenntnisse in Mathematik.

Klausur am 09.10.

Die vorläufigen Ergebnisse stehen fest. Sie hängen am Lehrgebiet aus (Gebäude E2, Raum 6103) und können innerhalb des RWTH-Netzes auch hier eingesehen werden.

Eine Klausureinsicht wird am Dienstag, den 16.10.2007 gewährt. Sie findet von 9:00 bis 10:00 Uhr im Raum E2-6103 statt. Update: Aufgrund der Überschneidung mit Vorlesungen des dritten Semesters (Informatik Bachelor) bieten wir auch einen zweiten Termin an: 16.10.2007, 16:00 bis 17:00 Uhr, Raum E2-6103.

Studierende des Diplom-Studiengangs Informatik, die sich zur mündlichen Ergänzungsprüfung anmelden möchten (und dürfen), mögen sich während der Klausureinsicht an uns wenden oder sich schnellstmöglichst bei Joachim Kneis anmelden.

Nach der Wiederholungsklausur (pdf) haben wir wieder Lösungsvorschläge (pdf) erstellt.

Achtung: Aufgrund der Umstellung auf Bachelor/Master und der veränderten Klausurzyklen mußte das ZPA nach eigenen Angaben Zwangsanmeldungen für die Studiengänge Computermathematik, Lehramt Informatik sowie Werkstoffinformatik vornehmen, damit die betroffenen Studierenden überhaupt an der Wiederholungsklausur teilnehmen konnten. Ein Nichterscheinen führt bei diesen Studiengängen deshalb selbstverständlich nicht zum Verlust eines Versuchs.

Klausur vom 31.07.

Nach der Klausur haben wir Lösungsvorschläge (pdf) und eine Liste typischer Fehler (pdf) zusammengestellt.

Ein paar Statistiken gibt es hier.

Übung

Die Java-Programme zu den Aufgaben kann man hier erhalten und hier gibt es Dokumentation, Java-Quellen und Visualisierungen von vielen unserer Algorithmen.

Die Tutoren Felix, Fernando und Michael haben eine eigene Erklärung zum Themengebiet Amortisierte Analyse (PDF) verfasst. Lesen!

Das von uns bestellte Buch Hacker's Delight ist mittlerweile im Handapparat der Vorlesung angekommen und freut sich auf neugierige Blicke.

Auf mehrfachen Wunsch verweisen wir hiermit auf das Java-Applet für Simulated Annealing und TSP.

Inhalt

Die Vorlesung stellt grundlegende Datenstrukturen und Algorithmen vor. Einerseits wird ein Katalog wichtiger Algorithmen detailliert vorgestellt, wobei Wert auf das intuitive Verständis des Algorithmus, die formalen Beweise seiner Korrektheit und auf die Analyse seiner Laufzeit und Gebrauch anderer Ressourcen gelegt wird. Andererseits werden allgemeine Techniken zum Entwurf neuer Datenstrukturen und Algorithmen vorgestellt.

Nach dem Genuß dieser Vorlesung sollen folgende wichtige Kenntnisse erworben worden sein: Die Fähigkeit, eine für ein Problem geeignete Datenstruktur aus einem grossen Katalog zu wählen und zu implementieren. Aktives, detailliertes Kennen der wichtigsten Algorithmen und Datenstrukturen sowie die Fähigkeit, geeignete Algorithmen in der Literatur zu finden. Selbstständiges Entwerfen und Analysieren neuer Datenstrukturen und Algorithmen anhand der wichtigsten Entwurfstechniken.

Ein grober Inhaltsüberblick sieht so aus:

Ein Skript wird begleitend herausgegeben (im Augenblick sind noch ein paar technische Probleme zu lösen). Hier ist ein erster Teil. Das Skript ist noch recht unvollständig, kann aber auch im vollständigen Zustand nicht Sekundärliteratur vollständig ersetzen. Die ersten beiden Bücher unten sind zu diesem Zweck sehr empfohlen. Hier gibt es die ersten Folien (auch als pdf und mit vier Folien auf einer Seite). Auf besonderen Wunsch sind hier noch die vollständigen Overlays aller Folien gesammelt, um z.B. DFS nachzuvollziehen. Jetzt gibt es auch noch die letzten Folien aus der letzten Vorlesung zu Simulated Annealing.

Literatur

Buch Introduction to Algorithms.
Buch Algorithmen und Datenstrukturen.
Buch The Art of Computer Programming.

Peter Rossmanith