Suche in Graphen ist eine grundlegende Fragestellung. Die zugehörigen Strukturen und Methoden bieten zugleich einen Einstieg in weiterführende Themen. Zudem kann man sehen, wie die Wahl von Datenstrukturen den Ablauf eines Algorithmus beeinflussen kann.
Termine:
- Vorlesung 5 am 11.11.20 (11:30 Uhr): Zusammenhang in Graphen
- Übung 3 am 12.11.20 (11:30 Uhr): Beweistechniken (Teil 2)
- Vorlesung 6 am 17.11.20 (09:45 Uhr): Graphenscan
- Vorlesung 7 am 18.11.20 (11:30 Uhr): Breiten- und Tiefensuche
- Vorlesung 8 am 24.11.20 (09:45 Uhr): Adjazenzliste
- Vorlesung 9 am 25.11.20 (11:30 Uhr): Wachstum von Funktionen
- Übung 4 am 26.11.20 (11:30 Uhr): BFS/DFS, Asymptotisches Wachstum
- Vorlesung 10 am 01.12.20 (09:45 Uhr): Wiederholung
- Vorlesung 11 am 02.12.20 (11:30 Uhr): Eigenschaften von BFS/DFS
Vorlesungen
-
Vorlesung 11
In dieser Vorlesung schließen wir das Kapitel 3 ab und schauen noch einmal auf verschiedene Eigenschaften von Breiten- und Tiefensuche. -
Vorlesung 10
In dieser Vorlesung analysieren wir die Laufzeit der Breiten- und der Tiefensuche. -
Übung 4
In dieser Übung haben wir uns Beispiele für Tiefen- und Breitensuche angesehen und uns mit dem Wachtum von Funktionen beschäftigt. -
Vorlesung 9
In dieser Vorlesung gibt es eine Einführung in das Wachstum von Funktionen und die O-Notation. -
Vorlesung 8In dieser Vorlesung werden weitere Datenstrukturen für Graphen wie die Adjazenz- und die Inzidenzmatrix vorgestellt.
-
Vorlesung 7
In dieser Vorlesung stellen wir grundlegende Datenstrukturen wie Warteschlangen und Stapel vor. Zusätzlich werden Breiten- und Tiefensuche behandelt sowie Datenstrukturen für die Codierung von Graphen. -
Vorlesung 6
In dieser Vorlesung wird der Graphenscanalgorithmus vorgestellt um Zusammenhangskomponenten in Graphen zu finden. -
Übung 3
In dieser Übung betrachten wir eine neue Beweistechnik: Die vollständige Induktion. -
Vorlesung 5
In dieser Vorlesung werden einige weitere Konzepte in Graphen vorgestellt. Dabei geht es vornehmlich um Verbindugen und Zusammenhang.