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: Dienstag, 13.11.2018
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.

Vorlesung 6

Datum: Mittwoch, 14.11.2018
Inhalt: Graphenscanalgorithmus; Zusammenhangskomponenten; Warteschlange und Stapel
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
Wikipedia-Seite: Warteschlangen
Wikipedia-Seite: Stapelspeicher (Stack)

Vorlesung 7

Datum: Dienstag, 20.11.2018
Inhalt: Breiten- und Tiefensuche; Datenstrukturen für die Codierung von Graphen
Folien: Folien mit Animationen der BFS- und DFS-Beispiele (PDF, 15 MB)
Notizen: HIER (PDF, 1.0MB)
Weitere Links:
Wikipedia-Seite: Breitensuche
Wikipedia-Seite: Tiefensuche
Der verteilte "Welle"-Algorithmus aus der Vorlesung
Eine technische Version des Verfahrens im Netzwerkkontext: Flooding
Allgemeiner: Verteilte Algorithmen

Wikipedia-Seite: Inzidenzmatrix
(Die englischen Seiten sind auch einen Blick wert!)
Wikipedia-Seite: Adjazenzmatrix ( Englische Version)

Vorlesung 8

Datum: Mittwoch, 21.11.2018
Inhalt: Adjazenzliste
Notizen: HIER (PDF, 1.8MB)
Weitere Links:
Wikipedia-Seite: Adjazenzliste (Englische Version)

Vorlesung 9

Datum: Dienstag, 27.11.2018
Inhalt: Wachstum von Funktionen; Laufzeit von Breiten- und Tiefensuche
Notizen: HIER (PDF, 1.0MB)
Folien: HIER (PDF, 2.1MB)
Weitere Links:
Wikipedia-Seite: Adjazenzliste (Englische Version)

(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
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 10

Datum: Mittwoch, 28.11.2018
Inhalt: Eigenschaften von Breiten- und Tiefensuche; Kapitelzusammenfassung
Folien: HIER (PDF, 4.5MB)
Notizen: HIER (PDF, 1.5MB)
Weitere Links:

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

Große Übung 4

Datum: Donnerstag, 29.11.2018
Inhalt: Tiefen-/Breitensuche, O-Notation
Notizen: HIER
Tipps zu Laufzeiten: HIER

Weiterfürende Themen zu Graphenalgorithmen