Algorithmen und Datenstrukturen

In dieser Vorlesung sollen Algorithmen für eine Reihe grundlegender Aufgaben wie z.B. Sortieren, Suchen etc. und die dabei verwendeten Datenstrukturen vorgestellt und untersucht werden. Tatsächlich besteht ein enger Zusammenhang zwischen dem Aufbau eines Algorithmus und der Strukturierung der verwendeten Daten. Es stellt sich heraus, dass die verwendete Strukturierung der Daten ganz erheblich den Rechenzeit- und Speicherplatzbedarf eines Algorithmus beeinflusst. Es ist daher erforderlich, bei jedem Entwurf eines Algorithmus eine günstige, die gewünschte Anwendung unterstützende Datenstruktur zu finden. In der Vorlesung sollen folgende Themen behandelt werden:
  1. Einführung: Algorithmen und ihr Rechenzeit- und Speicherplatzbedarf
  2. Felder, Keller und Schlangen
  3. Verkettete Listen
  4. Bäume und Graphen
  5. Suchen und Sortieren
  6. Hashing
  7. Balancierte Bäume
Zur Vorlesung existiert ein Skript. Als einführende und ergänzende Literatur wird auf die folgenden Lehrbücher verwiesen:
A. Aho, J. Hopcroft, J. Ullman:
The Design and Analysis of Computer Algorithms
Addison-Wesley, Reading, MA, 1974.
E. Horowitz, S. Sahni:
Fundamentals of Data Structures in PASCAL
3rd Edition; Computer Science Press, New York, NY, 1990.
J. Martin:
Data Types and Data Structures
Prentice-Hall, Englewood Cliffs, NJ, 1986.
K. Mehlhorn
Datenstrukturen und effiziente Algorithmen 1: Sortieren und Suchen
Teubner-Verlag, Stuttgart, 1986.
K. Mehlhorn
Datenstrukturen und effiziente Algorithmen 2: Graphenalgorithmen und NP-Vollständigkeit
Teubner-Verlag, Stuttgart, 1986.
N. Wirth:
Algorithmen und Datenstrukturen
Teubner-Verlag, Stuttgart, 1975.

Voraussetzungen:

Grundkenntnisse in Informatik etwa im Umfang der Vorlesung "Grundzüge der Informatik I" und fundierte Kenntnisse in einer höheren Programmiersprache, vorzugsweise PASCAL.

Leistungsnachweis:

Durch regelmäßige Bearbeitung der Übungsaufgaben, aktive Teilnahme an den Übungen und Bestehen einer Abschlussklausur oder eines Kolloquiums kann ein Übungsschein erworben werden.