Algorithmen 1, SS2017, Vorlesung Karlsruher Institut für Technologie (KIT)
-
- Education
Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:
Ergebnisüberprüfung (Checkers) und Zertifizierung
Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
Grundbegriffe des Algorithm Engineering
Effektive Umsetzung verketteter Listen
Unbeschränkte Arrays, Stapel, und Warteschlangen
Hashtabellen: mit Verkettung, linear probing, universelles Hashing
Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
Selektion: quickselect
Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
Dozenten: Prof. Dr. Jörn Müller-Quade | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
-
- video
23: Algorithmen 1, Vorlesung, SS 2017, 24.07.2017
23 |
0:00:00 Starten
0:00:06 Schnuppervorlesung Sicherheit
0:00:39 Überblick
0:03:10 Ziel
0:04:56 Motivation
0:09:01 Grundidee
0:11:20 Erste Eigenschaften
0:14:56 Überblick RSA
0:21:55 RSA-Schlüsselgenerierung
0:28:49 Korrektheit von RSA
0:38:04 Sicherheit?
0:43:31 Semantische Sicherheit für Public-Key-Verschlüsselung
0:50:04 Äquivalenter Begriff: IND-CPA
0:55:11 Sicherheit von RSA
0:56:43 Weitere Angriff auf RSA
0:59:31 Homomorphie von RSA
1:01:57 RSA-Padding
1:05:57 RSA-OAEP
1:07:17 Sicherheit von RSA-OAEP
1:09:35 Relevanz von RSA (-OAEP)
1:12:20 Mehr über ElGamal
Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:
- Ergebnisüberprüfung (Checkers) und Zertifizierung
- Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
- Grundbegriffe des Algorithm Engineering
- Effektive Umsetzung verketteter Listen
- Unbeschränkte Arrays, Stapel, und Warteschlangen
- Hashtabellen: mit Verkettung, linear probing, universelles Hashing
- Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
- Selektion: quickselect
- Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
- Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
- Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
Literaturhinweise:
Algorithms and Data Structures - The Basic Toolbox, K. Mehlhorn und P. Sanders
Springer 2008
Weiterführende Literatur
Algorithmen - Eine Einführung
T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein, Oldenbourg, 2007
Algorithmen und Datenstrukturen
T. Ottmann und P. Widmayer, Spektrum Akademischer Verlag, 2002
Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen
R. Sedgewick, Pearson Studium 2003
Algorithm Design
J. Kleinberg and É. Tardos, Addison Wesley, 2005
Vöcking et al.
Taschenbuch der Algorithmen, Springer, 2008
Lehrinhalt:
Dieses Modul soll Studierenden grundlegende Algorithmen und Datenstrukturen vermitteln.
Die Vorlesung behandelt unter anderem:
- Grundbegriffe des Algorithm Engineering
- Asymptotische Algorithmenanalyse (worst case, average case, probabilistisch, amortisiert)
- Datenstrukturen z. B. Arrays, Stapel, Warteschlangen und Verkettete Listen
- Hashtabellen
- Sortieren: vergleichsbasierte Algorithmen (z.B. quicksort, insertionsort), untere Schranken, Linearzeitalgorithmen (z.B. radixsort)
- Prioritätslisten
- Sortierte Folgen,Suchbäume und Selektion
- Graphen (Repräsentation, Breiten-/Tiefensuche, Kürzeste Wege, Minimale Spannbäume)
- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
- Geometrische Algorithmen -
- video
22: Algorithmen 1, Vorlesung, SS 2017, 17.07.2017
22 |
0:00:00 Starten
0:01:04 Kap. 13: Zusammenfassung
0:02:22 Zusammenfassung - Datenstrukturen
0:07:39 Zusammenfassung - Algorithmen
0:11:29 Zusammenfassung - Entwurfstechniken I
0:15:46 Zusammenfassung - Entwurfstechniken II
0:20:07 Zusammenfassung - Analysetechniken
0:26:12 Zusammenfassung - weitere Techniken -
- video
21: Algorithmen 1, Übung, SS 2017, 12.07.2017
21 |
0:00:00 Starten
0:00:06 Roadmap Übung
0:00:38 Schwierige Probleme
0:09:30 Erinnerung: Lineare Programme
0:15:36 Erinnerung: Travelling Salesman Problem
0:17:15 Ein ILP für TSP
0:24:57 Heuristiken
0:25:55 Ameisenalgorithmen
0:30:41 Vertex Cover
0:32:22 Approximation
0:34:48 Eine Approximation für Vertex Cover
0:39:05 Metaheuristiken und Nachbarschaften
0:40:20 Nachbarschaftsmetaheuristiken
0:44:43 Lokale Suche für Vertex Cover
0:47:12 Tabu-Suche für Vertex Cover -
- video
20: Algorithmen 1, Vorlesung, SS 2017, 10.07.2017
20 |
0:00:00 Starten
0:03:19 Wdh. Dynamische Programmierung
0:08:34 Algorithmenentwurf mittels dynamischer Programmierung
0:14:18 Anwendungen dynamischer Programmierung
0:17:38 Gegenbeispiel: Teilproblemeigenschaft
0:18:42 Gegenbeispiel: Austauschbarkeit
0:20:53 Systematische Suche
0:23:44 Beispiel: Branch-and-Bound für das Rucksackproblem
0:32:09 Beispielrechnung
0:41:30 Branch-and-Bound - allgemein
0:44:33 Lokale Suche - global denken, lokal handeln
0:47:55 Hill Climbing
0:48:51 Problem: Lokale Optima
0:49:53 Warum die Nachbarschaft wichtig ist
0:53:40 Jenseits von Hill Climbing
1:01:08 Evolutionäre Algorithmen
1:03:50 Zusammenfassung -
- video
19: Algorithmen 1, Vorlesung und Übung, SS 2017, 05.07.2017
19 |
0:00:00 Starten
0:00:06 Kap. 12: Generische Optimierungsansätze
0:01:08 Durchgehendes Beispiel: Rucksackproblem
0:04:07 Black-Box-Löser
0:04:40 Lineare Programmieurng
0:08:09 Beispiel: Kürzeste Wege
0:09:11 Eine Anwendung - Tierfutter
0:10:38 Verfeinerungen
0:11:52 Algorithmen und Implementierungen
0:13:15 Ganzzahlige Lineare Programmierung
0:16:09 Umgang mit (M)ILPs
0:18:39 Optimale Greedy-Algorithmen
0:23:56 Dynamische Programmierung - Aufbau aus Bausteinen
0:31:11 Dynamische Programmieurng
0:47:57 Übung: Kürzeste Wege Algorithmen: Bellman-Ford
0:56:11 Minimale Spannbäume
0:59:32 Steinerbäume
1:07:49 Problem des Handlungsreisenden (TSP) -
- video
18: Algorithmen 1, Vorlesung, SS 2017, 03.07.2017
18 |
0:00:00 Starten
0:00:06 Kap. 11: Minimale Spannbäume
0:03:34 Anwendungen
0:13:56 Der Jarnik-Prim-Algorithmus
0:24:48 Kruskals Algorithmus
1:03:02 Vergleich Jarnik-Prim Kruskal
1:04:09 Mehr MST-Algorithmen
1:06:50 Zusammenfassung