Datenstrukturen

Grundvorlesung mit Übungen, WS 1999/2000

Hanno Lefmann

Neu:Inhalte

[Termine] [Zusammenfassung] [Skript] [Übungen] [Lösungen]

Termine

Wann? Wo? Wer?
Vorlesungen: Mo 14.15 - 16.00 HGI, HS6 Hanno Lefmann
Mi 8.15 - 10.00 HGI, HS2 Hanno Lefmann
Übungen: Mo 8.00 - 10.00 GB IV, R 318 Alexander Gülich
Mo 10.00 - 12.00 C rechts Haiseung Yoo
Mo 12.00 - 14.00 GB IV, R 013 Stefan Droste
Mo 12.00 - 14.00 GB IV, R 318 Haiseung Yoo
Mo 16.00 - 18.00 GB IV, R 013 Alexander Gülich
Di 8.00 - 10.00 C rechts Markus Müller-Olm
Di 10.00 - 12.00 GB IV, R 318 Markus Müller-Olm
Di 14.00 - 16.00 GB IV, R 013 Benjamin Drisch
Do 8.00 - 10.00 C rechts Hamza Tatlitürk
Do 10.00 - 12.00 C rechts Benjamin Drisch
Do 12.00 - 14.00 C rechts Markus Wiebe
Do 16.00 - 18.00 GB IV, R 113 Stefan Droste
Fr 8.00 - 10.00 C rechts Hamza Tatlitürk
Fr 10.00 - 12.00 C rechts Markus Wiebe

Zusammenfassung

Die Grundvorlesung "Datenstrukturen" behandelt grundlegende Datenstrukturen und Entwurfsmethoden für effiziente Algorithmen. Die erworbenen Kenntnisse und Fähigkeiten können in praktisch allen Teilbereichen der Informatik gewinnbringend eingesetzt werden.

Die Vorgehensweise ist problemorientiert, d.h. Methoden und Techniken werden exemplarisch an ausgewählten Problemen (die wichtig und interessant sind) vorgestellt und erläutert. Die Effizienz der Datenstrukturen und Algorithmen wird jeweils analysiert.

Das Lernziel besteht nicht nur darin, den jeweils vorgestellten Lehrstoff zu verarbeiten, sondern darüber hinaus sollen die Zuhörerinnen und Zuhörer die Fähigkeit erwerben, die Techniken auf andere Probleme eigenständig anwenden zu können und für Probleme entscheiden zu können, welche Methoden erfolgversprechend sind. Dieses Lernziel ist natürlich ohne eine selbständige Bearbeitung der Übungsaufgaben nicht erreichbar.

Zu der Vorlesung wird es ein Skript geben. Zur Vorbereitung ist ein Schmökern in den Lehrbüchern über Datenstrukturen und Algorithmen hilfreich. Zur Orientierung werden die Inhalte der Vorlesung stichwortartig aufgelistet.

1. Typische Beispielprobleme, Rechnermodelle, Komplexitätsmaße.

2. Grundlegende Datenstrukturen (Arrays, Listen, Mengen, Bäume, Graphen, UNION-FIND).

3. Sortieren.

4. Dynamische Daten (Hashing, Skip Lists, Suchbäume, 2-3-Bäume, Bayer-Bäume, AVL-Bäume).

5. Entwurfsmethoden für effiziente Algorithmen (Greedy Algorithmen, Dynamische Programmierung, Lokale Suche, Backtracking, Branch-and-Bound, Divide-and-Conquer).

6. Algorithmische Geometrie.

Skript

Grundlage der Vorlesung ist das Vorlesungsskript "Datenstrukturen" von Ingo Wegener aus dem WS 1996/97. Der Ausdruck des Skripts ist am Fachbereich mit dem Kommando lprdoc oder xlpr möglich. Der Dokumentname ist "daten-ws96".

Übungen

Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche am 18. Oktober 1999.

Lösungen

Und hier die Lösung der Weihnachtsaufgabe von Blatt 11 (besser bekannt als die "Marzipanbrotaufgabe"). Mitsamt der besten Abgaben! (gezipptes Postscript), (PDF)

[Lehrstuhl 2] [Fachbereich Informatik] [Universität Dortmund]

Letzte Änderung: 19.6.2000