AD

Algorithmen und Datenstrukturen (AD)

Aktuelles

Aktuelle (WiSe 13/24) AD-Seite: [1]

Inhalt

AD bietet sowohl eine theoretische als auch eine praktische Sicht auf Algorithmen und Datenstrukturen.

Im theoretischen Teil wird gezeigt, wie Algorithmen generell zu bewerten sind. Dazu wird auf Problemangemessenheit, Zeit- und Platzkomplexität, sowie Echtzeitfähigkeit eingegangen. Natürlich muss zusätzlich auch die Vollständigkeit und Korrektheit des Algorithmus geprüft werden können. Um die Komplexität zu bewerten werden abstrakte Rechnermodelle eingeführt, die es erlauben, die Komplexität von Algorithmen in Bezug auf Zeit und Platzbedarf einzuschätzen. Somit ist es möglich, rekursive und iterative Algorithmen zu bewerten und untere und obere Schranken für den Aufwand zu geben.

Im zweiten Teil werden verschiedene Typen von Datenstrukturen betrachten und nützliche Algorithmen auf diesen. Als erstes sollen lineare Datenstrukturen (Arrays, Listen, Stapel, Schlangen) und dazugehörige Algorithmen (Suchen, Sortieren, Hash-Indizierung) behandelt werden. Darauf folgen dann hierarchische Datenstrukturen (Bäume, Graphen) und Algorithmen die diese verwenden (Suchbäume, balancierte Bäume, Durchlaufen von Graphen). Zuletzt werden nichtdeterministische Suchprobleme thematisiert, dazu gehören die Suche in Bäumen und Graphen, Suchstrategien, Optimierungsprobleme (kürzester Weg, dynamische Programmierung, A*).

Allgemeines zur Lehrveranstaltung

• Modulart: Pflichtmodul
• Referenzsemester: 3
• Leistungspunkte: 6

Lehrveranstaltungsform

• 3 SWS Vorlesung
• 1 SWS Übung

Voraussetzungen

• Verbindlich: keine
• Empfohlen: SE I, DM, FGI

Materialien

• Studentisches Skript aus dem WS16/17: [2] (von Kim 5wittenb)