Inhalte:
Die Studierenden erhalten detaillierte Kenntnisse über höheren Datenstrukturen und effizienten Algorithmen, die diese Datenstrukturen verwenden. Ein Teil der Lehrveranstaltung beschäftigt sich mit der Komplexität von "Standard"-Operationen auf höheren Datenstrukturen. Bei diesen Operationen handelt es sich z.B. um das Einfügen, das Löschen oder das Suchen eines Elements in eine Menge von Elementen. Kennt man erst mal die Komplexität der Operationen, dann kann man hieraus auf Einsatzgebiete schließen, in der die Datenstruktur effizient verwendbar ist. Die Datenstrukturen, die in dem Modul behandelt werden sind:

• Höhenbalancierte Suchbäume: AVL-Bäume, (a-b)-Bäume, Rot-Schwarz-Bäume
• Selbstorganisierende Listen und Bäume: Splay Trees
• Heaps: Binomial Heaps, Fibonacci Heaps

Ein weiteres Themengebiet des Moduls sind spezielle Problemklasse, für die effiziente Lösungsmöglichkeiten vorgestellt werden. Das Modul beschäftigt sich z.B. mit dem Problem der Selektion, mit planaren Graphen, mit dem Matching-Problem und dem Flussproblem. In diesem Zusammenhang wird auch auf die Möglichkeit der Verwendung paralleler Algorithmen eingegangen.

AVL-Baum

Rot-Schwarz-Baum

Binärer Suchbaum

Qualifikationsziele:
Mit Hilfe der erworbenen Kenntnisse können die Studierenden die Effizienz der besprochenen Datenstrukturen in spezifischen Einsatzgebieten bewerten. Durch die Betrachtung verschiedener Problemklassen werden einige Einsatzgebiete für die vorgestellten Datenstrukturen besprochen, so dass den Studierenden eine Übertragung in weitere Einsatzgebiete erleichtert wird. Die Studierenden erhalten im Rahmen dieses Moduls aber auch einen Eindruck von den Grenzen der Lösungsmöglichkeiten durch bekannte Algorithmen und Datenstrukturen.

Voraussetzung für die Teilnahme:
Der Studierende benötigt die Kenntnisse der Module: Grundlagen der Informatik, Grundlagen der Programmierung, Maschinenorientiertes Programmieren, Keine Teilnahmebeschränkung

Geschätzter studentischer Arbeitsaufwand (workload):
3 ECTS-LP (90 Stunden)

Beschreibung der Lehr- und Lernformen:
Seminaristischer Unterricht (4-stündig)

Häufigkeit des Angebots:
Das Modul dauert ein Trimester und wird jeweils im Herbsttrimester ab dem 2. Studienjahr angeboten. Das Modul wird pro Studienjahr einmal angeboten.