KIT Lehre und Wissen
Algorithmen 1 — twenty-three lectures from KIT, 2019.Algorithmen 1. Twenty-three lectures in German from KIT.
2019 · 23 lectures · 28.1 h2018 · 23 lectures · 29.3 h2017 · 23 lectures · 27.9 h2016 · 25 lectures · 31.6 h2015 · 26 lectures · 30.8 h2014 · 25 lectures · 33.6 h2013 · 25 lectures · 33.6 h
Algorithmen 1 · 23 lectures
01: Algorithmik, Langzahl-Multiplikation, Addition, Pseudocode
02: Schulalgorithmus, O-Kalkül, Karatsuba-Ofman-Multiplikation
03: Korrektheit von Algorithmen, Asymptotische Laufzeiten
04: O-Kalkül, Invarianten, Laufzeiten
05: Laufzeitanalyse, Rekurrenzen, Master Theorem
06: Folgen, Verkettete Listen, Unbeschränkte Felder
07: Stapel, Warteschlangen, Hashing, Kollisionen
08: Skip List, Amortisierte Liste, Aggregat Methode, Hotlist
09: Kollisionen, Universelles Hashing
10: Einfache Sortieralgorithmen, Sortieren durch Mischen
11: Halbrekursive Implementierung, Quicksort vs. Mergesort
12: Adaptives Sortieren, Insertion Sort, Natural Merge Sort
13: Prioritätslisten, Binäre Heaps
14: Sortierte Folgen, Binäre Baumsuche, Naives Einfügen
15: Bucket Sort Spezial, Bucket Queue, Binary Radix Heap
16: Locate, Graphen, Kantenfolgenrepräsentation, Adjazenzfelder
17: Kantenfolgenrepräsentation, Adjazenzfelder, Adjazenzlisten
18: Dijkstras Algorithmus, Graph-Traversierung, Kürzeste Wege
19: Dijkstras Algorithmus, Korrektheit,Bellman-Ford
20: Bellman-Ford Algorithmus, Transit-Node Routing
21: Jarnik-Prim/Kruskals-Algorithmus
22: Generische Optimierungsansätze
23: Dijkstras- und Bellmann Ford AlgorithmusAlgorithmen 1 · 23 lectures
01: Rekursiver Algorithmus, Karatsuba-Ofman-Algorithmus
02: Pseudocode, Programmanalyse, Master-Theorem, Graphen, Bäume
03: Effizienz von Algorithmen, Invarianten, Karatsuba-Ofman
04: P und NP, Listenglieder, verkettete Listen
05: Felder, Stapel und Schlange, Hashtabellen
06: Hashtabellen, Wahrscheinlichkeitstheorie
07: Skip Lists, Amortisierte Analyse, Hotlist
08: Universelles Hashing, Sortieren durch Mischen
09: Quicksort, Harmonische Summe
10: Sortieren, Quickselect, Quantifiziertes Chaos
11: Einfügen, Binärer Heap, Heapsort, Prioritätslisten
12: Sortierte Folgen, Binäre Suche, Priority Queues
13: Sortierte Folgen, Binäre Baumsuche, Items, Einfügen
14: Graphen, Kantenfolgenrepräsentation, Adjazenzfelder
15: Breitensuche, DFS-Baum
16: Graphen, Handshaking Lemma, Adjazenz- und Inzidenzmatrix
17: Kürzeste Wege, Dijkstra Algorithmus, Laufzeitanalyse
18: Dijkstra Algorithmus, Bellman-Ford-Algorithmus
19: Minimale Spannbäume, Generische Optimierungsansätze
20: MST, Pfadkompression, lineare Programmierung
21: Dijkstra Beispiel, Bellman Ford Algorithmus, MST
22: Dynamische Programmierung, Branch and Bound, Lokale Suche
23: Generische Optimierungsansätze, StaisfiabilityAlgorithmen 1 · 23 lectures
01: Ziffernmultiplikation, Schulmultiplikation
02: Karatsuba-Ofman Multiplikation, Algorithmenanalyse
03: Übung: Eingabegröße und Laufzeit, Asymptotische Notationen
04: Form Follows Function, Listenklasse, Felder
05: Stapel und Schlangen, Hashing, Übung: Listen
06: Hashtabellen, Anwendungen, Kollisionen
07: Verkettete lineare Suche, Hashtabellen für assoziative
08: Sortieren durch Mischen, Baumbasierte Sortier-Darstellung
09: Quicksort: Zufälliger Pivot, Harmonische Summe, Übung
10: Halbrekursive Implementierung, Quicksort vs. Mergesort
11: Heap-Algorithmus, Binärer Heap, Heapsort, Übung
12: Adressierbare Prioritätslisten, Sortierte Folgen
13: Dynamische Sortierte Folgen, Naives Einfügen
14: Repräsentation von Graphen, Adjazenzfelder
15: Tiefensuche, DFS-Baum, Topologische Sortierung
16: Dijkstras Algorithmus, Prioritätsliste
17: Kürzeste Wege, Transit-Node Routing, Übung
18: Minimale Spannbäume, Der Jarnik-Prim-Algorithmus
19: Generische Optimierungsansätze, Lineare Programmierung
20: Dynamische Programmierung, Branch-and-Bound, Hill Climbing
21: Übung: Ameisenalgorithmen, Vertex Cover
22 : Zusammenfassung: Datenstrukturen, Algorithmen
23: Schnuppervorlesung SicherheitAlgorithmen 1 · 25 lectures
01: Algorithmik, Ziffernmultiplikation, Rekursion
02: Langzahlmultikplikation, Algorithmenanalyse
03: Pseudocode, Programmanalyse, Graphalgorithmus
04: Folgen als Felder und Listen, Listenklasse
05: Felder, Arrays, Amortisierte Analyse, Stapel
06: Hashing, Kollisionen, Verkettete Listen
07: Hashing, Wahrscheinlichkeitstheorie
08: Hashing, Sortieren
09: Sortieren, Insertion Sort, Merge Sort
10: Mergesort, Quicksort
11: Selection, Quickselect, bucket sort, Quicksort
12: Array-Implementierung, Kd Schlüssel, Sortieren
13: Adressierbare Prioritätslisten, Adressierbare Binäre Heaps
14: Binäre Suchbäume, locate(k), Suchbäume, Items, Einfügen
15: Adjazenzfelder, Adjazenzlisten, Adjazenz-Matrix
16: Graphentraversierung, Breitensuche, Tiefensuche
17: DFS, Topologische Sortierung, Kürzeste Weg
18: Dijkstra, Prioritätsliste, Roadmap, Breitensuche
19: Negative Kosten, Bellman-Ford, Kürzeste Wege
20: MST, MSF, Cut Property, Cycle Property
21: Union-Find Datenstruktur, Pfadkompression, Jarník-Prim
22: Greedy-Algorithmen, Rucksackproblem
23: Branch-and-Bound, Hill Climbing, Parallele Algorithmen
24: Entwurfstechniken, Algorithmentheorie, Arrays, Hashing
25: Binäre Heaps, Binäre Suchbäume, Kürzeste WegeAlgorithmen 1 · 26 lectures
01: Einführung, Langzahlmultiplikation
02: Grundlagen, Master-Theorem
03: Graphen, Folgen, doppelt verkettete Listen
04: Arrays, amortisierte Analyse, Übung
05: Unbeschränkte Felder, Amortisierte Analyse
06: Karatsuba-Ofman, Rekurrenzen, Amortisierte Analyse
07: Hashing, hashtabellen, Kollisionsauflösung
08: Verketten, Kryptographische Hashfunktionen
09: Sortieren & Co, Formaler, Quicksort
10: Quicksort, Größerer Basisfall, Halbrekursive, Roadmap
11: Quickselect, Auswahl, Array-Implementierung
12: Prioritätslisten, deleteMin, Binärer Heap
13: Binärer Heap, Sortierte Folgen, Abgrenzung, locate(k)
14: Sortierte Folgen, Abgrenzung, Suchbäume balancieren
15: (a,b)-Bäume, Initialisierung, Einfügen und Entfernen
16: Repräsentation von Graphen, Adjazenzfelder
17: Graphtraversierung, Breitensuche, Tiefensuche
18: DFS-Baum, Kürzeste Wege, Dijkstras Algorithmus
19: Bellmann-Ford-Algorithums, Zyklische Graphen
20: Straßennetzwerke, Minimale Spannbäume
21: Union-Find Datenstruktur, Generische Optimierungsansätze
22: Dynamische Programmierung
23: Systematische Suche, Branch-and-Bound, Hill Climbing
24: Parallele Algorithmen, PRAM-Modelle
25: PRAM-Algorithmen, Algorithmus UCH, Listen, Felder
26: Effizienz von Algorithmen, Invarianten, QuicksortAlgorithmen 1 · 25 lectures
01: Organisatorisches
02: Einführung: Algorithmenanalyse, Maschinenmodell RAM
03: Folgen, Felder, Listen, Übung
04: Folgen, Felder, Listen: Verkettete Listen
05: Armortisierte Analyse, Übung
06: Amortisierte Analyse, Hashing (Streuspeicherung)
07: Hashing mit verketteten Listen, Universelles Hashing
08: Verketten: Lineare Suche, Sortieren
09: Sortieren: Sortieren durch Mischen, Quicksort, Übung
10: Quicksort
11: Quicksort, Selection, Ganzzahliges Sortieren, Übung
12: Prioritätslisten: Binäre Heaps
13: Prioritätslisten, Sortierte Folgen, Übung
14: Sortierte Folgen: Binäre Suchbäume, Erweiterte Suchbäume
15: Suchbäume balancieren, Übung
16: Graphtravesierung: Breitensuche, Tiefensuche, Übung
17: Breitensuche, Tiefensuche, Kürzeste Wege
18: Kürzeste Wege: Zyklische Graphen
19: Techniken für Routenplanung
20: Minimale Spannbäume: MST-Kanten, Jarník-Prim Algorithmus
21: Minimale Spannbäume, Gastvortrag (Vitaly Osipov)
22: Black-Box-Löser, Greedy-Algorithmen
23: Systematische Suche, Branch-and-Bound, Lokale Suche
24: Branch-and-Bound, Lokale Suche, Evolutionäre Algorithmen
25: Zusammenfassung: EntwurfstechnikenAlgorithmen 1 · 25 lectures
01: Algorithmus, Datenstruktur, Addition, Pseudocode
02: Schulmultiplikation, Algorithmen-Entwurfsmuster
03: Design by Contract, Graphen, Kürzeste Wege
04: Listenglieder, dummy header, die Listenklasse
05: Form follows Function, Einfach verkettete Listen
06: Kürzen, Amortisierte Analyse, Stapel und Schaltungen, FIFO
07: Hashtabellen, zufällige Hash-Funktionen, Binärzähler
08: einfache universelle Familie , Hashing mit linearer Suche
09: Sortieren durch Mischen, Untere Schranken
10: unbounded Hashtables, Rehash
11: Quickselect, Auswahlproblem, Eimersortieren, Rekurrenzen
12: Binärer Heap – Konstruktion, Heapsort
13: Sortierte Folgen, Heap und Suchbaum, Vollständiger Binärbaum
14: Suchbäume balancieren, Initialisierung, Locate, Einfügen
15: Entfernen, Graphenrepräsentation, Adjazenzfelder
16: Adjazenz-Matrix, Zusammenhangstest für Intervallgraphen
17: DFS Baum, Klassenklassifizierung bei DFS, Kürzeste Wege
18: Korrektheit, Prioritätsliste, Laufzeit, negative Kosten
19: Distanz zu einem Zielknoten, Routenplanung
20: Kruskals-Algorithmus, Union-Find Datenstruktur
21: Anwendung Negative Kreise, Contraction Hierarchies
22: Ganzzahlige lineare Programmierung
23: Branch-and-Bound, lokale Suche, Evolutionäre Algorithmen
24: Entwurfstechniken, Analysetechniken
25: sortierte Folgen, Adjazenz-Matrix, Azyklische Graphen











