SoSe 2014













Submodulnummer Veranstaltungsform Name LP SWS / Prüfungsdauer
0086cA.1.4.1 Vorlesung Algorithmen, Datenstrukturen und Datenabstraktion 0 4.0
0086cA.1.4.2 Übung Algorithmen, Datenstrukturen und Datenabstraktion 0 2.0
0086cA.1.4.3 Modulprüfung Algorithmen, Datenstrukturen und Datenabstraktion 9 120 min
Qualifikationsziele: Studentinnen und Studenten können die Grundbegriffe der Algorithmik definieren. Sie wissen, was ein abstrakter Datentyp ist, und verstehen den Unterschied zwischen Spezifikation und Implementierung. Sie kennen die wichtigsten abstrakten Datentypen und die Datenstrukturen zu deren Implementierung und können diese in Bezug auf ihre Eigenschaften beurteilen und geeignet auswählen und einsetzen. Sie können die Korrektheit von Algorithmen nachweisen und die asymptotische Laufzeit von Algorithmen bestimmen. Sie kennen die Definition und verstehen die praktische Bedeutung von NP-Vollständigkeit für die effiziente Lösbarkeit von Problemen.

Inhalte: Die grundlegenden Datenstrukturen Listen, Schlangen, Keller, Bäume; Sortierverfahren (Mergesort, Quicksort, u. a.), Suchverfahren, Auswahlverfahren; Abstrakte Datentypen Prioritätswarteschlange und Wörterbuch und zugehörige Datenstrukturen wie Heaps, Hashtabellen, binäre Suchbäume, B-Bäume u.a.; Algorithmen auf Graphen wie Breiten- und Tiefensuche, topologisches Sortieren, kürzeste Spannbäume, kürzeste Wege; Algorithmen für Zeichenketten; Speicherverwaltung; Allgemeine Lösungsstrategien wie Teile und Herrsche, dynamische Programmierung, Auswählen und Abschneiden, gierige Algorithmen. Mathematische Analyse von Algorithmen bezüglich Laufzeit und Speicherplatz. NP-Vollständigkeit.