![[Technical Faculty]](../../images/tflogo.gif)
Algorithmen & Datenstrukturen
Vorlesung u. Praktikum für den Ingenieursstudiengang,
Grundstudium, 3tes Semester
Wintersemester 1999/2000
Veranst: 8803/8804 (Vorlesung/Praktikum, 2+2 stündig)
Ort: Haus II, HO 2, Raum 332
Termin: Montag 9-11 und Donnterstag 16-18 Uhr
Vorbesprechung: keine
Beginn: Montag, 25. Oktober 1999
[Inhalt]
[Organisatorisches]
[Unterlagen]
[Handouts]
[Aufgaben]
[Literatur]
[Software]
[Links]
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.
Anmeldung:
Wir bitten um schriftliche (per email)
Anmeldung für den Kurs und um die Angabe folgender Daten:
- Name,
- Email-Adresse
- Semesterzahl
- Matrikelnummer
- Studiengang
Scheinkriterium
Für den Schein sind 50% der Punkte zu erreichen. Wer
einen benoteten Schein braucht, bekommt ihn durch 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:
- (selbstverständlich) Korrektheit der Lösung, daneben aber auch
- sinnvolle Kommentierung des Kodes, Effizienz und
Sauberkeit der Lösung. Ferner soll für jedes Programm eine
- Kurzbeschreibung der Lösung abgegeben werden.
Die verwendete Programmiersprache ist C.
Abgabe
Die Übungen werden in Zweiergruppen gelöst. Für
Rechnerzugang ist pro Benuzter eine Unterschrift unter
eine Wohlverhaltenserklärung erfoderlich. 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
{rhu,ms}@informatik.uni-kiel.de. Dabei gilt:
- Die Abgabe erfolgt per Übungszettel, d.h., bei mehreren
Aufgaben pro Zettel müssen diese zusammen in einer Mail gesendet werden.
- Das Subject der Mail muß die Nummer der Übungszettels und
Namen/Gruppe enthalten.
- Falls die Lösung aus mehreren Dateien besteht: bitte als
Paket verschicken, also ``taren'' oder mime-encoded.
Ideal bei mehreren Aufgaben ist es, 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 Info.txt
-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
Eine einfaches Makefile zu diesem Übungszettel könnte entsprechend so
aussehen:
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
Nachbereitung:
...
Unterlagen
Aufgaben
Das Abgabedatum steht auf dem Übungszettel, in der Regel
der Donnerstag nach der Ausgabe am Montag in der Vorlesung.
Zettel u. ä.
Literatur
- Thomas H. Cormen and Charles E. Leierson and Ronald L. Rivest,
Introduction to Algorithms. MIT-press, 1990.
- 1000-seitiges Standardwerk
-
Steven S. Skiena
The Algorithm Design
Manual, Springer-Verlag, 1998
- nicht ganz so
schwergewichtig wie [CLR90], gute Algorithmen- und Problemsammlung,
einschließlich Referenzen erhältlicher Implementierungen
und Tools! empfehlenswerte, gut geordnete Webseite zum Buch
Links
Ein ungeordnete Sammlung von Links
- Kurse und Kursmaterialien
- Zwei Sammlungen (hier
und hier von
Uni-Kursen zum Thema (sowohl für Undergraduates und Fortgeschrittene)
-
Vorlesungsskripten der TU-München vergleichbaren Veranstaltungen
(Grundlegende Algorithmen, Effiziente Algorithmen und Datenstrukturen)
- Ein
Skript zum Thema Graphen und ihre Algorithmen
- Mathematik & Mathematiker
- Sonstige Materialsammlungen und weitere Startpunkte in Netz
- Web-Server
- ein
``Kombinatorik''-Server:
gibt einem Aufzählungen von kombinatorischer Datenstrukturen
verschiedener Art an (Permutationen, verschiedene Arten von
B"aumen, Graphen etc.)
-
interaktive Bibliothek von Zahlenserien
[Inhalt]
[Organisatorisches]
[Unterlagen]
[Handouts]
[Aufgaben]
[Literatur]
[Software]
[Links]
Bei Fragen, email an {rhu|ms}@informatik.uni-kiel.de (Ralf Huuck, Martin Steffen)
Maintained by:
Martin Steffen
Last modified: Wed Apr 11 07:47:33 MET DST 2001