LS 2

Home
Teaching (German)
Winter 04/05
Sommer 04
Diplomarbeiten (pdf)
Frühere Semester
Service
Travel
Staff
Contact
Private

External Links

Universität Dortmund
Computer Science Faculty
Collab. Research Center 531
Collab. Research Center 475
Research Cluster 1126
Student Advisory

Datenstrukturen

im Wintersemester 2001/2002

Prof. Dr. Ingo Wegener




Informationen zur Vorlesung

  • Vorlesungstermine
    Aufgrund der hohen zu erwartenden Hörerzahl wird die Vorlesung zweimal gehalten.

    Vorlesung A
    Wochentag Uhrzeit Hörsaal
    Montag 14-16 Uhr HG 1/HS 6
    Mittwoch 08-10 Uhr HG 1/HS 6
    360 Sitzplätze
    		          
    Vorlesung B
    Wochentag Uhrzeit Hörsaal
    Dienstag 08-10 Uhr EF 50/HS 1
    Donnerstag 10-12 Uhr EF 50/HS 1
    420 Sitzplätze

    Die erste Vorlesung findet am 15.10.2001 bzw. 16.10.2001 statt.

  • Skript
    Das überarbeitete Vorlesungsskript (ca. 160 Seiten) ist ab sofort im Skriptenverkauf erhältlich. Den Hörern der Vorlesung steht auch auch eine "elektronische Version" zur Verfügung.

    Fehlerliste als PDF-Datei

  • Foliensammlung
    Einige handschriftliche Folien aus der Vorlesung stehen hier als JPEG-Dateien bereit. Die Folien aus je einem Kapitel sind zu komprimierten Archiven zusammengefasst. (Hinweis: Die Folien mit den Hinweisen zur Prüfungsvorbereitung sind bei Kapitel 5 einsortiert.)

    Folien zu Kapitel 1 (Kap1.tgz)
    Folien zu Kapitel 2 (Kap2.tgz)
    Folien zu Kapitel 3 (Kap3.tgz)
    Folien zu Kapitel 4 (Kap4.tgz)
    Folien zu Kapitel 5 (Kap5.tgz)

    Entpacken z. B. mit: gtar -xvzf Kap1.tgz

  • "OBDD-Zeichner"
    Auf der Seite http://niikaan.fdl.cc.mn.us/obdd/obddps.html kann man boolesche Ausdrücke eingeben und erhält das zugehörige reduzierte OBDD als Graph visualisiert. Die Variablenreihenfolge ist x1, x2, x3, ... Zur Erläuterung der Syntax schaue man sich die Beispiele unter http://niikaan.fdl.cc.mn.us/obdd/ an.

  • Vorlesungsinhalt
    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 Gewinn bringend 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 Erfolg versprechend sind. Dieses Lernziel ist natürlich ohne eine selbständige Bearbeitung der Übungsaufgaben nicht erreichbar.

    Zu der Vorlesung gibt es das oben erwähnte Skript. 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, OBDDs)
    3. Dynamische Dateien (Hashing, Skiplisten, Suchbäume, 2-3-Bäume, Bayer-Bäume, AVL-Bäume)
    4. Sortieren
    5. Entwurfsmethoden für effiziente Algorithmen (Greedy-Algorithmen, dynamische Programmierung, lokale Suche, Backtracking, Branch-and-bound, Divide-and-conquer)




Informationen zu den Übungen