[Technical Faculty]

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]

Inhalt

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.

Organisatorisches

Anmeldung:

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

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:
  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.
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: 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

    Notizen/Folien (hier zum Papiersparen vierfach verkleinert) ab und zu

Aufgaben

1.     Sortieren 1 25. Oktober, (gegenüber dem ausgedruckten Zettel: die Heap-Aufgabe ist diese Woche noch nicht fällig).
2.     Heaps, Sortieren 1. November
3.     Divide & Conquer, Listen 8. November
4.     Suchbäume 15. November
5.     Rot-Schwarz Bäume 22. November
    kein neuer Übungszettel diese Woche 29. November
6.     Graphen 6. Dezember
    keine neuen Übungszettel 13./20. Dezember
7.     Graphen (2) (oder hier) 3. Januar
8.     Graphen 10. Januar
9.     kürzeste Pfade 17. Januar
10.     Dynamische Programmierung, Zeichenketten 24. Januar

Das Abgabedatum steht auf dem Übungszettel, in der Regel der Donnerstag nach der Ausgabe am Montag in der Vorlesung.

Zettel u. ä.

1.     Organisatorisches 25. Oktober

Literatur

Links

Ein ungeordnete Sammlung von Links


[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