15: Algorithmen 1, Vorlesung, SS 2018, 11.06.2018

Autor

Carsten Sinz

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

15 |
0:00:00 Starten
0:00:09 Organisatorisches
0:03:12 Randbemerkung zu WWDC 2018
0:05:32 Rückblick Vorlesung 06.06.
0:07:56 Überblick heutige Vorlesung
0:08:18 Adjazenz-Matrix
0:08:52 Pfade zählen mittels LA
0:09:38 Graphentheorie und LA
0:15:39 Zusammenhangstest für Intervallgraphen
0:18:18 Beispiel
0:19:52 Graphenpräsentation: Zusammenfassung
0:21:30 Graph-Traversierung
0:23:14 Graphtraversierung als Kantenklassifizierung
0:26:23 Breitensuche
0:31:57 Repräsentation des Baumes
0:41:59 Repräsentation von Q und Q' mittels FIFO
0:45:45 Tiefensuche
0:47:04 Tiefensuchschema für G=(V,E)
0:52:43 DFS-Baum
1:00:08 DFS-Nummerierung
1:03:55 Fertigstellungszeit
1:06:03 Kantenklassifizierung bei DFS
1:07:47 Fertigstellungszeit
1:08:58 Topologishce Sortierung
1:13:38 Topologisches Sortieren mittels DFS
1:16:50 Starke Zusammenhangskomponenten
1:21:17 MehrDFS-basierte Linearzeitalgorithmen
1:22:37 BFS vs. DFS

Laufzeit (hh:mm:ss)

01:24:36

Serie

Algorithmen 1, Vorlesung, SS 2018

Publiziert am

18.06.2018

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz