Lehr- und Lernform: Vorlesung 2 SWS Übung 2 SWS Zeitlicher Arbeitsaufwand: 180 Stunden Dauer des Moduls: ein Semester 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 Algorithmennachweisen 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. Häufigkeit des Angebots: jedes Wintersemester.