Algorithmen & Datenstrukturen
Wintersemester 2001/2002

Veranstaltung: 01824/01825 (Vorlesung mit Praktikum)
Vorbesprechung: keine
Termin: Dienstag, 14 Uhr ct, der prakt. Teil nach Vereinbarung
Beginn: 1te Woche
Ort: Inf II, Raum 324
Dozent: Martin Steffen

Zur Vollständigkeit halber: die zentralen Daten zur Vorlesung im Univis

Der Entwurf und die effiziente Implementierung von Datenstrukturen und zugehöriger Algorithmen zu ihrer Manipulation gehört, unabhängig von Anwendung und Programmiersprache, zum unverzichtbaren Handwerkszeug jeden Programmierers.

Der Kurs behandelt verschiedene grundlegende und immer wiederkehrende statische, dynamische und rekursive Datenstrukturen und ihre Implementierung, wie beispielsweise Arrays, Listen, Stacks, Queues, verschiedene Arten von Bäumen, Hashstrukturen, Graphen ... Hand in Hand mit den Daten werden ausgewählte fundamentale Algorithmen wie Suchen, Sortieren und Traversieren und andere mehr behandelt. Schließlich soll die Vorlesung einen Einblick in allgemeine Problemlösungsstrategien wie "`Divide-and-Conquer"', Backtracking, u.a. geben.

Der Kurs legt besonderen Wert auf die praktische Umsetzung und Implementierung der vorgestellten Algorithmen in den begleitenden Übungen.



1   Organisatorisches

1.1   Anmeldung und Rechnerzugang

Zur Teilnahme bietet es sich an, sich einen account an der Uni zu verschaffen. Die Anmeldung passiert seit diesem Semester

online
Siehe auch die Hinweise der RGB zum Thema.

Wir bitten um schriftliche (per email Anmeldung für den Kurs und um die Angabe folgender Daten:

1.2   Scheinkriterium

Für den Schein sind 50% der Punkte zu erreichen. Wer einen benoteten Schein braucht oder will, bekommt ihn nach einer zusätzlichen mündlichen Prüfung am Ende des Kurses. Was die gestellten Programmieraufgaben betrifft, so gehen folgende Punkte in die Bewertung ein:
  1. (selbstverständlich) Korrektheit der Lösung, daneben aber auch
  2. sinnvolle Kommentierung des Kodes, Effizienz und Sauberkeit der Lösung. Ferner soll für jedes Programm eine
  3. Kurzbeschreibung der Lösung abgegeben werden.

1.3   Abgabe

Die Übungen werden in Zweiergruppen gelöst. Die Gruppeneinteilung befindet sich hier. Der verbindliche Abgabetermin ist jeweils auf dem Übungszettel angegeben. Die Lösungen sollen per email abgegeben werden, und zwar an ms@informatik.uni-kiel.de. Dabei gilt: Bei der Abgabe ist es erforderlich, ein einfaches Makefile mit beizufügen, für die erste Aufgabe beispielsweise könnte das Auspacken der abgegebenen Lösung folgende Struktur besitzen:

 /home/<.....>/uebung1:
  total 11
  drwxr-xr-x   2         512 Nov  4 08:56 .
  drwxr-xr-x   3         512 Nov  2 21:40 ..
  -rw-r--r--   1        1634 Nov  2 21:36 Readme
  -rw-r--r--   1        1159 Nov  2 20:23 mergesort.c
  -rw-r--r--   1          90 Oct 30 17:21 mergesort.h
  -rw-r--r--   1        2353 Nov  2 21:12 sorttest.c
  -rw-r--r--   1         224 Nov  4 08:55 Makefile
Ein einfaches Makefiles (im Falle von C) zu diesem Übungszettel könnte eventuell entsprechend so aussehen: 
######################################### Kommentare mit ``#''

CC = gcc      ## Definition einer Variable

########

all: mergesort test
        true

test: sorttest.o mergesort.o
        $(CC) sorttest.o mergesort.o -o sorttest

sorttest.o: sorttest.c
        $(CC) -c sorttest.c

mergesort.o: mergesort.c mergesort.h
        $(CC) -c mergesort.c

clean:
        \rm -f mergesort mergesort.o sorttest.o sorttest
Zur Erklärung: ein Makefile ist eine Datei mit eben diesem Namen Makefile, welches einem hilft, (vor allem) Übersetzungen zu steuern. Das Makefile besteht aus einer Reihe von Einträgen. Die Namen zu Beginn jedes Eintrags heißen ``targets'' und was in der folgenden Zeile steht, wird bei einem make <target> ausgeführt, beispielsweise
make clean
in diesem Beispiel räumt mittes eines rm die generierten Dateien wieder auf. Der Aufruf von
make all
führt ein true aus (den erfolgreichen, nichtstuenden Befehl), das heißt, für sich genommen tut es erstmal nichts, aber bevor es true ausführt, wird vorher noch ein make mergesort und make test gemacht, denn die Einträge in der Zeile nach dem Ziel, also hier nach all, sind Abhängigkeiten, die zunächst ausgeführt werden.

Defaultmäßig wird bei einem bloßen
make
das erste Ziel ausgeführt (in dem Beispiel ist es also analog zu make all). Typische, oft verwendete Ziele sind, wie in dem Beispiel sieht, make all und make clean für ``Alles in der richtigen Reihenfolge übersetzen'' zum Beispiel bei uns, alle Aufgaben einer Serie, und make clean ``Alles aufräumen'', natürlich nicht die Quelldateien, sondern nur das, was durch Kompilation erzeugt wurde.

Man kann noch sehr viel mehr mit Makefiles machen, für uns reicht dieser simple Gebrauch, damit ich bei der Korrektur nicht lange suchen muß, welchen Kompiler ich mit welchen Optionen auf welches File anwenden muß. Bei Bedarf: weitere Informationen zu gnu's make finden sich hier.

1.4   Nachbereitung

Mal schauen ...



2   Unterlagen

2.1   Folien

Als Unterlagen stellen wir die Vorlesungsfolien ins Netz, sie enthalten das meiste des Vorlesungsstoffes (bis auf z.B. einige Bilder):

Folien    zum Papiersparen 4fach verkleinert     als HTML-Dokument

2.2   Aufgaben

Es wird meistens jede Woche einen Übungszettel geben, die Abgabe in der Regel am Donnerstag drauf.

Zettel      Thema      Ausgabedatum
Übung 1      Sortieren      24. Oktober
Übung 2      Heaps/Sortieren/Rekursion & Iteration      30. Oktober
Übung 3      Divide & Conquer, Rekursion und Iteration      13. November
Übung 4      Sortieren. Suchbäume      27. November
Übung 5      Rot/Schwarzbäume      4. Dezember
Übung 6      Graphen      8. Januar
Übung 7      Graphen, Spannbäume      29. Januar

2.3   Zettel und ähnliches

Zettel      Thema      Ausgabedatum
Handout 1      Organisatorisches      24. Oktober

2.4   Sonstiges

Einige der vorgestellten Algorithmen habe ich in Ocaml implementiert; den Code kann man sich hier anschauen.

3   Literatur

In der Hauptsache stützt sich die Vorlesung auf [CLR90], ein umfangreiches, modernes Standardwerk zum Thema. Ein weiteres, nicht ganz so schwergewichtiges Buch ist [Ski97]. Es zeichnet sich dadurch aus, daß es zu jedem Problem auch auf praktische Anwendungen und bekannte Implementierungen verweist. Daneben stellt der Autor eine sehr gute Webseite zu dem Buch zur Verfügung.

Weitere, bekannte und empfehlenswerte Bücher zum Thema sind beispielsweise [AHU89], [Koz92], [Sed88] oder [Sed90], und [Wir86].

4   Links

Hier ein paar mehr oder minder ungeordnete Links zum Thema.

References

[AHU89]
Alfred Aho, John E. Hopcroft, and Jeffrey Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1989.

[CLR90]
Thomas H. Cormen, Charles E. Leierson, and Ronald L. Rivest. An Introduction to Algorithms. MIT Press, 1990.

[Koz92]
Dexter C. Kozen. The Design and Analysis of Algorithms. Springer, 1992.

[Sed88]
R. Sedgewick. Algorithms. Addison-Wesley, 2 edition, 1988.

[Sed90]
Robert Sedgewick. Algorithms in C. Addison-Wesley, 1990.

[Ski97]
Steven S. Skiena. The Algorithm Design Manual. Springer, Telos, 1997.

[Wir86]
Niklaus Wirth. Algorithmen und Datenstrukturen. B. G. Teubner, 1986.
Pages last (re-)generated January 29, 2002
This document was translated from LATEX by HEVEA.