?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