Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
Dozenten: Jun.-Prof. Dennis Hofheinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
All content for Algorithmen 1, SS2016, Vorlesung is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
Dozenten: Jun.-Prof. Dennis Hofheinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016
Algorithmen 1, SS2016, Vorlesung
1 hour 22 seconds
9 years ago
18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016
18 |
0:00:00 Starten
0:00:06 Erinnerung VL 20.06.2016
0:02:10 Erinnerung: analoger Algorithmus
0:03:25 Dijkstra: Implementierung?
0:08:39 Prioritätsliste
0:10:22 Implementierung ≈ BFS mit PQ statt FIFO
0:15:06 Beispiel
0:17:27 Dijkstra: Laufzeit
0:26:20 Analyse im Mittel
0:28:34 Monotone ganzzahlige Prioritätslisten
0:29:57 Negative Kosten
0:30:33 Beginn Übung 9
0:30:39 Roadmap
0:30:59 Organisatorisches
0:31:37 Aufgabe 3
0:32:26 Breitensuche (Wie war das nochmal...)
0:34:48 Breitensuche für nicht zusammenhängende, ungerichtete Graphen
0:35:41 Breitensuche in DAGs für nicht zusammenhängende Graphen
0:38:08 Dijkstras Algorithmus
0:40:56 Bidirektionale Suche
0:45:09 Bidirektionale Suche - Definitionen
0:46:14 Bidirektionale Suche - Vorgehen
0:46:20 Pingo! Was sind gute Abbruchstrategien?
0:49:19 Abbruchstrategie (1)
0:53:36 Abbruchstrategie (2)
0:54:13 Beispiel
0:55:02 Bemerkungen
0:56:01 Graph-Datenstruktur
0:56:07 Pingo! Wie schnell wird eine Routing-Anfrage?
0:57:54 Speedup Techniques
0:59:38 Mehr davon?
Algorithmen 1, SS2016, Vorlesung
Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
Dozenten: Jun.-Prof. Dennis Hofheinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
