• Algorithmen 1, Vorlesung, SS 2019
• Algorithmen 2, WS 2018/19
• Softwaretechnik 1, Vorlesung, SS 2017
• Softwaretechnik 1, Vorlesung, SS 2019
• Softwaretechnik 1, Vorlesung, SS 2021

Algorithmen 1, Vorlesung, SS 2019

Algorithmen 1, Vorlesung, SS 2019

Beschreibung:

• 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)

Lehrinhalt:

• 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

Videos:

• 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 (Teile und Herrsche Ansatz)
• 05: Laufzeitanalyse, Rekurrenzen, Master Theorem, Folgen als Felder und Listen
• 06: Folgen, Verkettete Listen, Unbeschränkte Felder, Account-Methode
• 07: Stapel, Warteschlangen, Hashing, Kollisionen
• 08: Skip List, Amortisierte Liste, Aggregat Methode, Hotlist, Duplikaterkennung
• 09: Kollisionen, Universelles Hashing, Kryptographische Hashfunktionen, Einfache Sortieralgorithmen
• 10: Einfache Sortieralgorithmen, Sortieren durch Mischen, Quicksort
• 11: Halbrekursive Implementierung, Quicksort vs. Mergesort, Ganzzahliges Sortieren
• 12: Adaptives Sortieren, Insertion Sort, Natural Merge Sort, Split Sort
• 13: Prioritätslisten, Binäre Heaps, Adressierbare Prioritätslisten
• 14: Sortierte Folgen, Binäre Baumsuche, Naives Einfügen, Initialisierung
• 15: Bucket Sort Spezial, Bucket Queue, Binary Radix Heap
• 16: Locate, Graphen, Kantenfolgenrepräsentation, Adjazenzfelder
• 17: Kantenfolgenrepräsentation, Adjazenzfelder, Adjazenzlisten, Adjazenz-Matrix, Graph-Traversierung
• 18: Dijkstras Algorithmus, Graph-Traversierung, Kürzeste Wege, Tiefensuche
• 19: Dijkstras Algorithmus, Korrektheit,Bellman-Ford Algorithmus, Kante relaxieren
• 20: Bellman-Ford Algorithmus, Transit-Node Routing
• 21: Jarnik-Prim/Kruskals-Algorithmus
• 22: Generische Optimierungsansätze
• 23: Dijkstras- und Bellmann Ford Algorithmus, Minimale Spannbäume, Steinerbäume

Algorithmen 2, WS 2018/19

Algorithmen 2, WS 2018/19

Videos:

• 01: Algorithm Theory
• 02: Datenstrukturen, Pairung Heaps, Fibonacci Heaps, Union-by-Rank
• 03: Gray-/JouleSort, Pairing Heaps, Dijkstra’s Algorithmmus
• 04: Dijkstra’s Algorithmus, Radix-Heaps, Bucket-Queue, Lufzwit Dijkatra, Fibanacci Heaps
• 05: Monotone ganzzahlige Prioritätslisten, Radix-Heaps, Knotenpotenziale
• 06: DFS, Bucket Queues, Analyse für MST
• 07: Schrumpfgraph, SCC Berechnung, Linear programming, Residual Graph, Ford Fulkerson Algorithm
• 08: Ford Fulkerson Algorithm, Blocking Flows, Dijkstras Algorithmus, Floyd Warshall
• 09: Ford Fulkerson, Dinitz Algorithm,blocking flows, Dinitz analysis, Pre-flow-push algorithms
• 10: Preflow-Push Algorithms, Pratial Correctness, FIFO Preflow push, Residualgraph
• 11:Ford Fulkerson Algorithm, Blocking Flows, Random Graphs, FIFO Preflow push
• 12: Randomisierte Algorithmen, Cuckoo Hashing, Space Efficient Cuckoo Hashing
• 13: Cuckoo Hashing, Das Sekundärspeichermodell, Mittelgroße PQs, Analyse – I/Os
• 14: Spannbäume, Matching, Monte Carlo Simulation, Matrix-Matrix Multiplikation, Coupon Collector
• 15: Der Approximationsfaktor, Pseudopolynomielle Algorithmen, 9 Fixed-Parameter-Algorithmen
• 16: Naive tiefenbeschränkte Suche, Kernbildung für Vertex Cover, Parallele Algorithmen,
• 17: Analyse paralleler Algorithmen, Hyperwürfelalgorithmus, Paralleles Sortieren
• 18: Paralleles Sortieren, Parallele Algorithmen, Parametrisierte Algorithmen
• 19: Geometrische Algorithmen, Streckenschnitt, Überlappungen
• 20: Streckenschnitt, Konvexe Hülle, Geometrische Methoden, Übung
• 21: Kleinste einschließende Kugel, Wavelet Tree
• 22: Wavelet Tree, Onlinealgorithmen, Paging
• 23: Strings sortieren, Suffixe sortieren, Knuth-Morris-Pratt
• 24: Suffix-Baum, Alphabet-Modell, Übung
• 25: Suffixtabellen, Differenzenüberdeckungen, LCP-Array, Textkompression
• 26: LCP-Array, Lempel-Ziv Kompression, Burrows-Wheeler-Transformation
• 27: SAT Solving, Union-find merging, Graph Contraction, Label Propagation
• 28: Übung: In-place Multikey Quicksort, Partitionierung, Suffix-Array, LCP-Array
• 29: Algorithm Engineering, Fortgeschrittene Datenstrukturen, Fortgeschrittene Graphenalgorithmen
• 30: Approximationsalgorithmen, Pseudopolynomielle Algorithmen, Hyperwürfelalgorithmus

Algorithmen 2, Vorlesung, WS 2019/20

Videos:

• 01: Rolle der Algorithmik, Algorithm Engineering, Algorithm Libraries
• 02: Experimental Methodology, Adressierbare Prioritätenlisten, Pairing Heaps
• 03: Fortgeschrittene Datenstrukturen, Binomialbäume, Fortgeschrittene Graphenalgorithmen
• 04: Binomialbäume, Radix-Heaps, deleteMin-Operationen
• 05: All-Pairs Shortest Paths, Knotenpotentiale, Routenplanung
• 06: Repräsentation offener Komponenten, Übung: Spezielle Priority Queues, Radix Heaps
• 07: Maximum Flows and Matchings, s-t Cuts, Ford Fulkerson Algorithm, Dinitz Algorithm
• 08: Computer Blocking Flows, Übung: Kürzeste-Wege-Suche, Bidirektionale Suche, A*-Suche
• 09: Ford Fulkerson Algorithm, Level Function, Partial Correctness, FIFO Preflow push
• 10: Flows and Matchings, MFIFO Modified FIFO Selection Rule, Timings: CG 1, CG2, AMO
• 11: Randomisierte Algorithmen: Sort Checking, Hashing; Externe Algorithmen
• 12: Externe Algorithmen: Externe Prioritätslisten, Übung: Potentialmethode, preflow-push Algorithmus
• 13: Approximationsalgorithmen: Approximationsfaktor; Pseudopolynomielle Algorithmen
• 14: Fixed-Parameter-Algorithmen, Naive tiefenbeschränkte Suche, Kernbildung für Vertex Cover, Übung
• 15: Fixed-Parameter-Algorithmen, Parallele Algorithmen, Hyperwürfelalgorithmus
• 16: Paralleles Sortieren: Anfänger- und Theoretiker-Parallelisierung, Mehrwegmischen, Übung
• 17: Geometrische Algorithmen, Übung: Approximationsalgorithmen, Parametrisierte Algorithmen
• 18: Streckenschnitt, 2D Konvexe Hülle, Kleinste einschließende Kugel, 2D Bereichssuche
• 19: Bitvektoren, Übung: Geometrische Algorithmen, Bitvektoren, 2D Range Queries, Linienschnitt
• 20: Onlinealgorithmen, Paging algorithms, Conservative algorithms, Randomized algorithms
• 21: Stringology (Zeichenkettenalgorithmen): Strings sortieren, Knuth-Morris-Pratt, Border-Array
• 22: Stringology: Notation, Suffixe sortieren, Suffixbaum, Übung: Online Algorithmen
• 23: SA mit Präfix Verdopplung, Rekursion, COBS
• 24: LCP-Array, Verlustfreie Textkompression, Übung: in-place Multikey Quicksort, LCP-Array
• 25: Datenkompression, Lempel-Ziv Kompression, Burrows Wheeler Transformation, Backward Search
• 26: Efficient Document Retrieval on General Sequences
• 27: Pairing Heaps, Bucket Queue, Residual Graph, Randomisierte Algorithmen
• 28: Approximationsalgorithmen, Fixed-Parameter-Algorithmen, Parallele Algorithmen, Stringology

Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20

Videos:

• 01: Formale Sprachen, Reguläre Sprachen, Reguläre Ausdrücke, Endliche Automaten
• 02: Kontextfreie Grammatiken, Nichtderterministische endliche Automaten, Potenzmengenkonstruktion
• 03: Entfernen von ɛ​-Übergängen, Satz von Kleene, Pumping-Lemma für reguläre Sprachen
• 04: Pumping-Lemma für reguläre Sprachen, Verallgemeinertes Pumping-Lemma, Äquivalenzklassenautomat
• 05: Äquivalenz, Rechtsinvarianz und Index, Satz von Nerode, Registermaschine, Turingmaschine
• 06: Turing-Maschine, berechenbar/totalrekursiv, Gödelnummer, Diagonalsprache
• 07: Satz von Rice, Post’sches Korrespondenzproblem, Kodierungsschemata, Entscheidungsproblem
• 08: Nichtdeterministische Turingmaschine, Polynomiale Transformation, Satz von Cook
• 09: Die Probleme 3SAT, 2SAT, MAX2SAT, CLIQUE, COLOR und EXACT COVER
• 10: Die Probleme SUBSET SUM, PARTITION und KNAPSACK, Polynomielle Hierarchie, Suchprobleme
• 11: Problem INTEGER PROGRAMMING, Pseudopolynomiale Algorithmen, Absolute Approximationsalgorithmen
• 12: Metrisches TSP, Approximationsschemata, Maximierungsprobleme, Optimierungsprobleme
• 13: Grammatiken, Chomsky-Hierarchie
• 14: Pumping-Lemma und Ogden´s Lemma für kontextfreie Sprachen, Eigenschaften kontextfreier Sprachen
• 15: Eigenschaften kontextfreier Sprachen, Greibach-Normalform, Kellerautomaten
• 16: Kellerautomaten, Greibach-Normalform, Sprache der korrekten Rechenwege
• 17: Informationstheorie, Entropie, Kodierungsbäume, Lauflängenkodierung
• 18: Paritätscodes, Kreuzsicherung, Block-Codes, Hamming-Distanz und Fehlerkorrektur