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.
Vorlesung 5
- Datum: Mittwoch, 09.11.2016
- Inhalt: Verbindungen und Zusammenhang in Graphen
- Folien: HIER (PDF, 36MB)
- Notizen: HIER (PDF, 1.0MB)
- Weitere Links:
Wikipedia-Seite: Erdös-Zahl
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.
Vorlesung 6
- Datum: Dienstag, 15.11.2016
- Inhalt: Graphenscanalgorithmus; Zusammenhangskomponenten; Warteschlange und Stapel; Breiten- und Tiefensuche
- Folien:
Folien (PDF, 24 MB; ACHTUNG! Ohne Animationen.)
Folien mit Animationen der BFS- und DFS-Beispiele (PDF, 67 MB)
- Weitere Links:
Wikipedia-Seite: Zusammenhang von Graphen
Wikipedia-Seite: Aufspannende Bäume
Das Problem aus "Good Will Hunting: Bäume zählen
Wikipedia-Seite: Breitensuche
Wikipedia-Seite: Tiefensuche
Wikipedia-Seite: Warteschlangen
Wikipedia-Seite: Stapelspeicher (Stack)
Der verteilte "Welle"-Algorithmus aus der Vorlesung
Eine technische Version des Verfahrens im Netzwerkkontext: Flooding
Allgemeiner: Verteilte Algorithmen
Vorlesung 7
- Datum: Mittwoch, 16.11.2016
- Inhalt: Datenstrukturen für die Codierung von Graphen
- Notizen: HIER (PDF, 1.0MB)
- Weitere Links:
Wikipedia-Seite: Repräsentation von Graphen im Computer (Achtung! Die englischen Seiten zum Thema sind deutlich besser!)
Wikipedia-Seite: Inzidenzmatrix
Wikipedia-Seite: Adjazenzmatrix
Wikipedia-Seite: Adjazenzliste
Vorlesung 8
- Datum: Dienstag, 22.11.2016
- Inhalt: Wachstum von Funktionen
- Notizen: HIER (PDF, 1.0MB)
- Weitere Links:
Wikipedia zur asymptotischen Notation
Sehr detaillierte Skriptnotizen zu Landau-Symbolen (Das ist *viel* detaillierter und tiefer als wir es brauchen)
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)
Vorlesung 9
- Datum: Mittwoch, 23.11.2016
- Inhalt: Laufzeit von Breiten- und Tiefensuche
- Notizen: HIER (PDF, 1.0MB)
- Weitere Links:
(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!)
Große Übung 3
- Datum: Donnerstag, 24.11.2016
- Inhalt: Komplexität
- Folien: HIER
Vorlesung 10
- Datum: Dienstag, 29.11.2016
- Inhalt: Eigenschaften von Breiten- und Tiefensuche; Kapitelzusammenfassung
- Notizen: HIER (PDF, 2.5MB)
- Folien: HIER (PDF, 8.5MB)
- Weitere Links:
Wikipedia zu Online-Algorithmen
Ski Rental: ein besonders eingängiges Online-Problem
Liedtext
Das Lied im Original
Ein bisschen zu vollständiger Induktion