Qualifikationsziele
Die Studierenden können wesentliche Datenstrukturen benennen sowie beschreiben, welche Datenstrukturen für welche Aufgaben geeignet sind. Sie können Kriterien für die Laufzeitbetrachtung aufzählen und in Algorithmen identifizieren. Sie können Such- und Sortieralgorithmen erklären und gegenüberstellen sowie Algorithmen hinsichtlich ihrer Komplexität klassifizieren. Studierende können vorhandenen Code interpretieren und bestehende Algorithmen implementieren. Sie sind in der Lage, sich eigenständig mit den Algorithmen zu beschäftigen und mit ihrer Hilfe eigeständig kleinere Probleme zu lösen.
Inhalte
- Datenstrukturen (Arrays, Listen, Bäume, Hash-Tabelle, Heap)
- Komplexität und asymptotische Aufwandsabschätzung, Landau-Symbole
- Entwurfsmethoden (Divide and Conquer, Greedy, Dynamische Programmierung, Branch and
- Bound Verfahren)
- Suchverfahren (Lineare Suche, Binäre Suche, Interpolationssuche, Suchbäume, Hashverfahren)
- Sortierverfahren (SelektionSort, MergeSort, QuickSort, Heapsort, Radixsort)
- Graphalgorithmen (Breitensuche, Tiefensuche, Minimaler Spannbaum, kürzeste Wege, TSP, Pla-
- narität, Färbungen, maximaler Fluss)
- Suchen in Texten: Knuth-Morris-Pratt, Boyer-Moore, Komprimierung von Texten
- Lehrperson: Bernhard Breil