Siehe ZEUS-Webseite für einzelne Termine und weitere Details!
Beschreibung:
Aufbauend auf den Kenntnissen der "Einführung in die strukturierte und objektorientierte Programmierung" (ESOP) ist der Umgang mit Datenstrukturen und Algorithmen größerer Strukturkomplexität zu erlernen. Dabei sollen die Studierenden einen Grundschatz wichtiger Datenstrukturen und Algorithmen kennenlernen und diese nach ihrer algorithmischen Komplexität beurteilen können. Die begleitenden Übungen vertiefen den Vorlesungsstoff und sollen dazu beitragen, eigenständig die Konstruktion und Analyse von Algorithmen durchzuführen. Von den vorgestellten Datenstrukturen bzw. Algorithmen sind einige exemplarisch zu implementieren. Neben diesem Grundziel der Lehrveranstaltung dienen ausgewählte Implementierungsbeispiele des Praktikums dazu, die im ESOP erworbenen Programmierkenntnisse (insbesondere die objektorientierten Konzepte) zu festigen.
Nach Absolvieren von VO und UE können Studierende …
Landau-Symbole definieren und einfache Komplexitätsklassen gegeneinander abgrenzen,
die Komplexität von einfachen Algorithmen bestimmen,
den Fundamentalsatz (Beschleunigen durch Aufteilen) wiedergeben und anwenden,
unterschiedliche Sortierverfahren beschreiben und nutzen,
unterschiedliche Suchverfahren beschreiben und nutzen,
unterschiedliche Hashverfahren beschreiben und nutzen,
Graphen und Bäume definieren und grundlegende Algorithmen (Traversierung, Tiefen/Breitensuche) auf den zugehörigen Datenstrukturen anwenden,
Balancierte Bäume (AVL- und B-Bäume) definieren und zugehörige Algorithmen anwenden,
kürzeste Wege in Graphen (1:n, n:n) und Spannbäume definieren und bestimmen,
unterschiedliche Algorithmen für Stringmatching nennen,
einfache Algorithmen zur Datenkompression, Fehlererkennung- und -korrektur erklären und anwenden und
die Komplexitätsklassen P und NP definieren und das Prinzip der Polynomiellen Reduktion erklären.