Materialseiten AuD

Kapitel 3: Suche in Graphen

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.

Vorlesung 5

Datum: Mittwoch, 13.11.2019
Inhalt: Verbindungen und Zusammenhang in Graphen
Folien: HIER (PDF, 36MB)
Notizen: HIER (PDF, 1.0MB)
Weitere Links:
Wikipedia-Seite: Erdös-Zahl
Paul Erdös bei Google Scholar
Digital Bibliography & Library Project: Paul Erdös
The Erdös Number Project
Erdös-Zahlen einiger berühmter Leute
Can I give you my number?
Kennzeichen mit Erdös-Zahl
Erdös-Zahlen-Rechner (Auf "Collaboration Distance" klickens; dann am besten Nachnamen eingeben und aus Liste auswählen. Benutzt nur Artikel in MathSciNet, also eine eingeschränkte Datenbasis)
Imaginary Erdös numbers (youtube-Video)
Wikipedia-Seite: Kevin Bacon
Wikipedia-Seite: Kevin-Bacon-Zahl
Internet Movie Database: Kevin Bacon
Das Orakel von Kevin Bacon
Wikipedia-Seite: Kleine-Welt-Netzwerke
Ein bisschen mehr dazu
Der xkcd-Comic zu Erdös - man beachte den Text, wenn man den Mauszeiger über das Bild schiebt.
Kickstarter-Projekt - ein Film über Erdös und Bacon.
Music Map - eine visuelle Darstellung, bei der die Kanten im Graphen unterschiedliche Länge haben, die dem Abstand entspricht.

Große Übung 1

Datum: Donnerstag, 14.11.2019
Inhalt: Organisation, Beweistechniken
Folien: HIER
Merkzettel Beweise: HIER

Vorlesung 6

Datum: Dienstag, 19.11.2019
Inhalt: Graphenscanalgorithmus; Zusammenhangskomponenten
Folien: Folien (PDF, 6 MB; ACHTUNG! Ohne Animationen.)
Notizen: HIER (PDF, 1.0MB)
Weitere Links:
Wikipedia-Seite: Zusammenhang von Graphen
Wikipedia-Seite: Aufspannende Bäume
Das Problem aus "Good Will Hunting: Bäume zählen

Vorlesung 7

Datum: Mittwoch, 20.11.2019
Inhalt:; Warteschlange und Stapel; Breiten- und Tiefensuche; Datenstrukturen für die Codierung von Graphen
Folien: Folien ohne Animationen der BFS- und DFS-Beispiele (PDF, 15 MB)
Animationen der BFS- und DFS-Beispiele (PDF, 2 MB)
Quiz: Quiz-Fragen und Ergebnisse (PDF, 10 MB)
Weitere Links:
Wikipedia-Seite: Warteschlangen
Interaktive Visualisierung von Warteschlange
Wikipedia-Seite: Stapelspeicher (Stack)

NEU! Visualisierung: Suche in Graphen
Interaktive Visualisierung von Stack
Interaktive Visualisierung von Breitensuche
Wikipedia-Seite: Breitensuche
Interaktive Visualisierung von Tiefensuche
Wikipedia-Seite: Tiefensuche
Der verteilte "Welle"-Algorithmus aus der Vorlesung
Eine technische Version des Verfahrens im Netzwerkkontext: Flooding
Allgemeiner: Verteilte Algorithmen

Vorlesung 8

Datum: Dienstag, 26.11.2019
Inhalt: Adjazenzliste
Notizen: HIER (PDF, 1.8MB)
Weitere Links:
Wikipedia-Seite: Inzidenzmatrix
(Die englischen Seiten sind auch einen Blick wert!)
Wikipedia-Seite: Adjazenzmatrix ( Englische Version)

Vorlesung 9

Datum: Mittwoch, 27.11.2019
Inhalt: Wachstum von Funktionen; O-Notation
Notizen: HIER (PDF, 1.0MB)
Weitere Links:
Wikipedia-Seite: Spieltheorie
Wikipedia-Seite: Gefangenendilemma
Die tanzenden Roboter
Die Theorie dahinter

(Für Tonspur auf Bild klicken - und über den Unterschied von t^2 und 2^t nachdenken: Der Aufwand vervierfacht sich nicht nur, sondern quadriert sich!) Wikipedia zum Ersten Weltkrieg
Wikipedia zur Spanischen Grippe
Wikipedia zur Pest
Wikipedia zur asymptotischen Notation
Noch ein anderer Zugang: Grenzwert des Verhältnisses der Funktionen zum Vergleich (Auch hier die Warnung: Das dient nur der Vertiefung, lieber ignorieren als davon verwirren lassen!)
Theta für Dummies: Ein Forumthread, der gar nicht so schlecht ist (wenn man bewusst darüber nachdenkt)

Große Übung 2

Datum: Donnerstag, 28.11.2019
Inhalt: Tiefen-/Breitensuche, Asymptotisches Wachstum
Notizen: HIER
Tipps zu Laufzeiten: HIER

Vorlesung 10

Datum: Dienstag, 03.12.2019
Inhalt: Adjazenzliste; Laufzeit von Breiten- und Tiefensuche
Notizen: HIER (PDF, 1.5MB)
Quiz: HIER (PDF, 1.9MB)
Weitere Links:

Wikipedia-Seite: Adjazenzliste (Englische Version)

Vorlesung 11

Datum: Mittwoch, 04.12.2019
Inhalt: Eigenschaften von Breiten- und Tiefensuche; Kapitelzusammenfassung
Folien: HIER (PDF, 15MB)
Notizen: HIER (PDF, 1.5MB)
Graphenscan, BFS, DFS im IDEA-Projekt
Wikipedia zu Online-Algorithmen
Ski Rental: ein besonders eingängiges Online-Problem
Liedtext
Das Lied im Original
Ein bisschen zu vollständiger Induktion

Weiterfürende Themen zu Graphenalgorithmen