Übersicht
Veranstaltungsart: Vorlesung + Übung (Bachelor)
Credits: 4V + 2Ü, 8 LP
Turnus: Jedes Wintersemester
Empfohlenes Semester:
3. Fachsemester
3. Fachsemester
Prüfung: Klausur (120 Minuten)
Sprache: Deutsch
Inhalt
Ziel der Vorlesung ist eine Einführung in Algorithmen und Datenstrukturen für Sortierverfahren, zur Verwaltung von Mengen und für Graphalgorithmen. Themenauswahl:
- Sortierverfahren und Verwandtes
- Mergesort, Heapsort, Quicksort, Selektion, Rekursions(un)gleichungen (Mastertheorem), Untere Schranken, Multiplikation großer Zahlen, Sortieren durch Zählen, Radix-Sortieren, Sortiernetzwerke (paralleles Sortieren)
- Verwaltung von Mengen
- Binäre Heaps, Fibonacci Heaps, AVL-Bäume, (a,b)-Bäume, Hashing, Union-Find-Problem
- Graphalgorithmen
- Tiefensuche, Topologisches Sortieren, Zusammenhangskomponenten, Kürzeste Wege (Bellman-Ford, Dijkstra), Minimale Spannbäume (Kruskal, Prim)
- NP-Vollständigkeit