{"id":10607,"date":"2020-01-29T10:11:50","date_gmt":"2020-01-29T10:11:50","guid":{"rendered":"http:\/\/blog.bachi.net\/?p=10607"},"modified":"2021-12-29T13:28:25","modified_gmt":"2021-12-29T13:28:25","slug":"kit-webcast","status":"publish","type":"post","link":"https:\/\/blog.bachi.net\/?p=10607","title":{"rendered":"KIT Webcast"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBPQNK4lG23kJSqxSQQhuud7\">Algorithmen 1, Vorlesung, SS 2019<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBP4f2HwiN3d7kn2KW3_5cG-\">Algorithmen 2, WS 2018\/19<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBN-QTjtWl4oNOu5qStyvMRz\">Softwaretechnik 1, Vorlesung, SS 2017<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBPvbQjgHABO1rp6Oo3zZsMf\">Softwaretechnik 1, Vorlesung, SS 2019<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBNW7ei5VKKEw4p4MSOcjwX5\">Softwaretechnik 1, Vorlesung, SS 2021<\/a><\/li>\n<\/ul>\n<h3>Algorithmen 1, Vorlesung, SS 2019<\/h3>\n<p><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBPQNK4lG23kJSqxSQQhuud7\">Algorithmen 1, Vorlesung, SS 2019<\/a><\/p>\n<p>Beschreibung:<\/p>\n<ul>\n<li>Ergebnis\u00fcberpr\u00fcfung (Checkers) und Zertifizierung<\/li>\n<li>Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert<\/li>\n<li>Grundbegriffe des Algorithm Engineering<\/li>\n<li>Effektive Umsetzung verketteter Listen<\/li>\n<li>Unbeschr\u00e4nkte Arrays, Stapel, und Warteschlangen<\/li>\n<li>Hashtabellen: mit Verkettung, linear probing, universelles Hashing<\/li>\n<li>Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort<\/li>\n<li>Selektion: quickselect<\/li>\n<li>Priorit\u00e4tslisten: bin\u00e4re Heaps, addrssierbare Priorit\u00e4tslisten<\/li>\n<li>Sortierte Folgen\/Suchb\u00e4ume: Wie unterst\u00fctzt man alle wichtigen Operationen in logarithmischer Zeit<\/li>\n<li>Graphen (Repr\u00e4sentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,&#8230;), K\u00fcrzeste Wege: Dijkstra&#8217;s Algorithmus, Bellman\n<li>Ford    Algorithmus, Minimale Spannb\u00e4ume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)<\/li>\n<li>Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)<\/li>\n<\/ul>\n<p>Lehrinhalt:<\/p>\n<ul>\n<li>Grundbegriffe des Algorithm Engineering<\/li>\n<li>Asymptotische Algorithmenanalyse (worst case, average case, probabilistisch,  amortisiert)<\/li>\n<li>Datenstrukturen z. B. Arrays, Stapel, Warteschlangen und Verkettete Listen<\/li>\n<li>Hashtabellen<\/li>\n<li>Sortieren: vergleichsbasierte Algorithmen (z.B. quicksort, insertionsort), untere Schranken, Linearzeitalgorithmen (z.B. radixsort)<\/li>\n<li>Priorit\u00e4tslisten<\/li>\n<li>Sortierte Folgen,Suchb\u00e4ume und Selektion<\/li>\n<li>Graphen (Repr\u00e4sentation, Breiten-\/Tiefensuche, K\u00fcrzeste Wege, Minimale Spannb\u00e4ume)<\/li>\n<li>Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)<\/li>\n<li>Geometrische Algorithmen<\/li>\n<\/ul>\n<p>Videos:<\/p>\n<ul>\n<li>01: Algorithmik, Langzahl-Multiplikation, Addition, Pseudocode<\/li>\n<li>02: Schulalgorithmus, O-Kalk\u00fcl, Karatsuba-Ofman-Multiplikation<\/li>\n<li>03: Korrektheit von Algorithmen, Asymptotische Laufzeiten<\/li>\n<li>04: O-Kalk\u00fcl, Invarianten, Laufzeiten (Teile und Herrsche Ansatz)<\/li>\n<li>05: Laufzeitanalyse, Rekurrenzen, Master Theorem, Folgen als Felder und Listen<\/li>\n<li>06: Folgen, Verkettete Listen, Unbeschr\u00e4nkte Felder, Account-Methode<\/li>\n<li>07: Stapel, Warteschlangen, Hashing, Kollisionen<\/li>\n<li>08: Skip List, Amortisierte Liste, Aggregat Methode, Hotlist, Duplikaterkennung<\/li>\n<li>09: Kollisionen, Universelles Hashing, Kryptographische Hashfunktionen, Einfache Sortieralgorithmen<\/li>\n<li>10: Einfache Sortieralgorithmen, Sortieren durch Mischen, Quicksort<\/li>\n<li>11: Halbrekursive Implementierung, Quicksort vs. Mergesort, Ganzzahliges Sortieren<\/li>\n<li>12: Adaptives Sortieren, Insertion Sort, Natural Merge Sort, Split Sort<\/li>\n<li>13: Priorit\u00e4tslisten, Bin\u00e4re Heaps, Adressierbare Priorit\u00e4tslisten<\/li>\n<li>14: Sortierte Folgen, Bin\u00e4re Baumsuche, Naives Einf\u00fcgen, Initialisierung<\/li>\n<li>15: Bucket Sort Spezial, Bucket Queue, Binary Radix Heap<\/li>\n<li>16: Locate, Graphen, Kantenfolgenrepr\u00e4sentation, Adjazenzfelder<\/li>\n<li>17: Kantenfolgenrepr\u00e4sentation, Adjazenzfelder, Adjazenzlisten, Adjazenz-Matrix, Graph-Traversierung<\/li>\n<li>18: Dijkstras Algorithmus, Graph-Traversierung, K\u00fcrzeste Wege, Tiefensuche<\/li>\n<li>19: Dijkstras Algorithmus, Korrektheit,Bellman-Ford Algorithmus, Kante relaxieren<\/li>\n<li>20: Bellman-Ford Algorithmus, Transit-Node Routing<\/li>\n<li>21: Jarnik-Prim\/Kruskals-Algorithmus<\/li>\n<li>22: Generische Optimierungsans\u00e4tze<\/li>\n<li>23: Dijkstras- und Bellmann Ford Algorithmus, Minimale Spannb\u00e4ume, Steinerb\u00e4ume<\/li>\n<\/ul>\n<h3>Algorithmen 2, WS 2018\/19<\/h3>\n<p><a href=\"https:\/\/www.youtube.com\/playlist?list=PLfk0Dfh13pBP4f2HwiN3d7kn2KW3_5cG-\">Algorithmen 2, WS 2018\/19<\/a><\/p>\n<p>Videos:<\/p>\n<ul>\n<li>01: Algorithm Theory<\/li>\n<li>02: Datenstrukturen, Pairung Heaps, Fibonacci Heaps, Union-by-Rank<\/li>\n<li>03: Gray-\/JouleSort, Pairing Heaps, Dijkstra&#8217;s Algorithmmus<\/li>\n<li>04: Dijkstra&#8217;s Algorithmus, Radix-Heaps, Bucket-Queue, Lufzwit Dijkatra, Fibanacci Heaps<\/li>\n<li>05: Monotone ganzzahlige Priorit\u00e4tslisten, Radix-Heaps, Knotenpotenziale<\/li>\n<li>06: DFS, Bucket Queues, Analyse f\u00fcr MST<\/li>\n<li>07: Schrumpfgraph, SCC Berechnung, Linear programming, Residual Graph, Ford Fulkerson Algorithm<\/li>\n<li>08: Ford Fulkerson Algorithm, Blocking Flows, Dijkstras Algorithmus, Floyd Warshall<\/li>\n<li>09: Ford Fulkerson, Dinitz Algorithm,blocking flows, Dinitz analysis, Pre-flow-push algorithms<\/li>\n<li>10: Preflow-Push Algorithms, Pratial Correctness, FIFO Preflow push, Residualgraph<\/li>\n<li>11:Ford Fulkerson Algorithm, Blocking Flows, Random Graphs, FIFO Preflow push<\/li>\n<li>12: Randomisierte Algorithmen, Cuckoo Hashing, Space Efficient Cuckoo Hashing<\/li>\n<li>13: Cuckoo Hashing, Das Sekund\u00e4rspeichermodell, Mittelgro\u00dfe PQs, Analyse &#8211; I\/Os<\/li>\n<li>14: Spannb\u00e4ume, Matching, Monte Carlo Simulation, Matrix-Matrix Multiplikation, Coupon Collector<\/li>\n<li>15: Der Approximationsfaktor, Pseudopolynomielle Algorithmen, 9 Fixed-Parameter-Algorithmen<\/li>\n<li>16: Naive tiefenbeschr\u00e4nkte Suche, Kernbildung f\u00fcr Vertex Cover, Parallele Algorithmen,<\/li>\n<li>17: Analyse paralleler Algorithmen, Hyperw\u00fcrfelalgorithmus, Paralleles Sortieren<\/li>\n<li>18: Paralleles Sortieren, Parallele Algorithmen, Parametrisierte Algorithmen<\/li>\n<li>19: Geometrische Algorithmen, Streckenschnitt, \u00dcberlappungen<\/li>\n<li>20: Streckenschnitt, Konvexe H\u00fclle, Geometrische Methoden, \u00dcbung<\/li>\n<li>21: Kleinste einschlie\u00dfende Kugel, Wavelet Tree<\/li>\n<li>22: Wavelet Tree, Onlinealgorithmen, Paging<\/li>\n<li>23: Strings sortieren, Suffixe sortieren, Knuth-Morris-Pratt<\/li>\n<li>24: Suffix-Baum, Alphabet-Modell, \u00dcbung<\/li>\n<li>25: Suffixtabellen, Differenzen\u00fcberdeckungen, LCP-Array, Textkompression<\/li>\n<li>26: LCP-Array, Lempel-Ziv Kompression, Burrows-Wheeler-Transformation<\/li>\n<li>27: SAT Solving, Union-find merging, Graph Contraction, Label Propagation<\/li>\n<li>28: \u00dcbung: In-place Multikey Quicksort, Partitionierung, Suffix-Array, LCP-Array<\/li>\n<li>29: Algorithm Engineering, Fortgeschrittene Datenstrukturen, Fortgeschrittene Graphenalgorithmen<\/li>\n<li>30: Approximationsalgorithmen, Pseudopolynomielle Algorithmen, Hyperw\u00fcrfelalgorithmus<\/li>\n<\/ul>\n<h3>Algorithmen 2, Vorlesung, WS 2019\/20<\/h3>\n<p>Videos:<\/p>\n<ul>\n<li>01: Rolle der Algorithmik, Algorithm Engineering, Algorithm Libraries<\/li>\n<li>02: Experimental Methodology, Adressierbare Priorit\u00e4tenlisten, Pairing Heaps<\/li>\n<li>03: Fortgeschrittene Datenstrukturen, Binomialb\u00e4ume, Fortgeschrittene Graphenalgorithmen<\/li>\n<li>04: Binomialb\u00e4ume, Radix-Heaps, deleteMin-Operationen<\/li>\n<li>05: All-Pairs Shortest Paths, Knotenpotentiale, Routenplanung<\/li>\n<li>06: Repr\u00e4sentation offener Komponenten, \u00dcbung: Spezielle Priority Queues, Radix Heaps<\/li>\n<li>07: Maximum Flows and Matchings, s-t Cuts, Ford Fulkerson Algorithm, Dinitz Algorithm<\/li>\n<li>08: Computer Blocking Flows, \u00dcbung: K\u00fcrzeste-Wege-Suche, Bidirektionale Suche, A*-Suche<\/li>\n<li>09: Ford Fulkerson Algorithm, Level Function, Partial Correctness, FIFO Preflow push<\/li>\n<li>10: Flows and Matchings, MFIFO Modified FIFO Selection Rule, Timings: CG 1, CG2, AMO<\/li>\n<li>11: Randomisierte Algorithmen: Sort Checking, Hashing; Externe Algorithmen<\/li>\n<li>12: Externe Algorithmen: Externe Priorit\u00e4tslisten, \u00dcbung: Potentialmethode, preflow-push Algorithmus<\/li>\n<li>13: Approximationsalgorithmen: Approximationsfaktor; Pseudopolynomielle Algorithmen<\/li>\n<li>14: Fixed-Parameter-Algorithmen, Naive tiefenbeschr\u00e4nkte Suche, Kernbildung f\u00fcr Vertex Cover, \u00dcbung<\/li>\n<li>15: Fixed-Parameter-Algorithmen, Parallele Algorithmen, Hyperw\u00fcrfelalgorithmus<\/li>\n<li>16: Paralleles Sortieren: Anf\u00e4nger- und Theoretiker-Parallelisierung, Mehrwegmischen, \u00dcbung<\/li>\n<li>17: Geometrische Algorithmen, \u00dcbung: Approximationsalgorithmen, Parametrisierte Algorithmen<\/li>\n<li>18: Streckenschnitt, 2D Konvexe H\u00fclle, Kleinste einschlie\u00dfende Kugel, 2D Bereichssuche<\/li>\n<li>19: Bitvektoren, \u00dcbung: Geometrische Algorithmen, Bitvektoren, 2D Range Queries, Linienschnitt<\/li>\n<li>20: Onlinealgorithmen, Paging algorithms, Conservative algorithms, Randomized algorithms<\/li>\n<li>21: Stringology (Zeichenkettenalgorithmen): Strings sortieren, Knuth-Morris-Pratt, Border-Array<\/li>\n<li>22: Stringology: Notation, Suffixe sortieren, Suffixbaum, \u00dcbung: Online Algorithmen<\/li>\n<li>23: SA mit Pr\u00e4fix Verdopplung, Rekursion, COBS<\/li>\n<li>24: LCP-Array, Verlustfreie Textkompression, \u00dcbung: in-place Multikey Quicksort, LCP-Array<\/li>\n<li>25: Datenkompression, Lempel-Ziv Kompression, Burrows Wheeler Transformation, Backward Search<\/li>\n<li>26: Efficient Document Retrieval on General Sequences<\/li>\n<li>27: Pairing Heaps, Bucket Queue, Residual Graph, Randomisierte Algorithmen<\/li>\n<li>28: Approximationsalgorithmen, Fixed-Parameter-Algorithmen, Parallele Algorithmen, Stringology<\/li>\n<\/ul>\n<h3>Theoretische Grundlagen der Informatik, Vorlesung, WS 2019\/20<\/h3>\n<p>Videos:<\/p>\n<ul>\n<li>01: Formale Sprachen, Regul\u00e4re Sprachen, Regul\u00e4re Ausdr\u00fccke, Endliche Automaten<\/li>\n<li>02: Kontextfreie Grammatiken, Nichtderterministische endliche Automaten, Potenzmengenkonstruktion<\/li>\n<li>03: Entfernen von \u025b\u200b-\u00dcberg\u00e4ngen, Satz von Kleene, Pumping-Lemma f\u00fcr regul\u00e4re Sprachen<\/li>\n<li>04: Pumping-Lemma f\u00fcr regul\u00e4re Sprachen, Verallgemeinertes Pumping-Lemma, \u00c4quivalenzklassenautomat<\/li>\n<li>05: \u00c4quivalenz, Rechtsinvarianz und Index, Satz von Nerode, Registermaschine, Turingmaschine<\/li>\n<li>06: Turing-Maschine, berechenbar\/totalrekursiv, G\u00f6delnummer, Diagonalsprache<\/li>\n<li>07: Satz von Rice, Post&#8217;sches Korrespondenzproblem, Kodierungsschemata, Entscheidungsproblem<\/li>\n<li>08: Nichtdeterministische Turingmaschine, Polynomiale Transformation, Satz von Cook<\/li>\n<li>09: Die Probleme 3SAT, 2SAT, MAX2SAT, CLIQUE, COLOR und EXACT COVER<\/li>\n<li>10: Die Probleme SUBSET SUM, PARTITION und KNAPSACK, Polynomielle Hierarchie, Suchprobleme<\/li>\n<li>11: Problem INTEGER PROGRAMMING, Pseudopolynomiale Algorithmen, Absolute Approximationsalgorithmen<\/li>\n<li>12: Metrisches TSP, Approximationsschemata, Maximierungsprobleme, Optimierungsprobleme<\/li>\n<li>13: Grammatiken, Chomsky-Hierarchie<\/li>\n<li>14: Pumping-Lemma und Ogden\u00b4s Lemma f\u00fcr kontextfreie Sprachen, Eigenschaften kontextfreier Sprachen<\/li>\n<li>15: Eigenschaften kontextfreier Sprachen, Greibach-Normalform, Kellerautomaten<\/li>\n<li>16: Kellerautomaten, Greibach-Normalform, Sprache der korrekten Rechenwege<\/li>\n<li>17: Informationstheorie, Entropie, Kodierungsb\u00e4ume, Laufl\u00e4ngenkodierung<\/li>\n<li>18: Parit\u00e4tscodes, Kreuzsicherung, Block-Codes, Hamming-Distanz und Fehlerkorrektur<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>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\u00fcberpr\u00fcfung (Checkers) und Zertifizierung Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert Grundbegriffe des Algorithm Engineering Effektive Umsetzung verketteter Listen [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-10607","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts\/10607","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10607"}],"version-history":[{"count":7,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts\/10607\/revisions"}],"predecessor-version":[{"id":12870,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts\/10607\/revisions\/12870"}],"wp:attachment":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}