Theoretische Informatik I - WS2024/25
Eine der Säulen der Informatik - in Theorie und Praxis - ist die Algorithmik. Die Vorlesung führt in das Gebiet ein.
Eingangs werden Such- und Sortieralgorithmen behandelt. Während die binäre Suche zu ersteren zählt, sind Mergesort, Heapsort und Quicksort als Beispiele für Sortieralgorithmen zu nennen.
Nach einer Einführung in die O-Notation werden verschiedene Datenstrukturen, beispielsweise Stacks, Queues, binäre Suchbäume, B-Bäume oder Rot-Schwarz-Bäume, vorgestellt.
Auch arithmetische Algorithmen, wie die schnelle Matrix-Exponentiation oder die schnelle Multiplikation, werden eingeführt.
Abschließend nehmen die Graphalgorithmen einen relativ breiten Raum der Vorlesung ein. Bei diesen geht es um das systematische Aufsuchen aller Knoten eines beliebigen, gerichteten oder ungerichteten Graphen. Als die beiden hauptsächlichen Lösungswege werden die Breitensuche und die Tiefensuche behandelt. Ferner werden verschiedene Verfahren für die Bestimmung kürzester Wege und von minimalen Spannbäumen in Graphen betrachtet. Netzwerkflüsse werden ebenfalls eingeführt.
Vorlesungen:
- Mittwoch 9:15 - 10:45 Uhr (Prof. Dr. Scheder, A12.346 (alt: 1/346))
- Donnerstag 15:30 - 17:00 Uhr (Prof. Dr. Scheder, A12.346 (alt: 1/346))
Übungen:
- Dienstag 7:30 - 9:00 Uhr (J. Tantow, A11.006 (alt: 1/B006))
- Mittwoch 7:30 - 9:00 Uhr (J. Tantow, A11.006 (alt: 1/B006))
- Freitag 13:45 - 15:15 Uhr (S. Schulze, A11.006 (alt: 1/B006))