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
27 July 2017, 7:30 am