Algorithmen 2, Vorlesung, WS18/19

Karlsruher Institut für Technologie (KIT)
  • 0.0(0개의 평가)
  • 강의
Algorithmen 2, Vorlesung, WS18/19

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt. Literaturhinweise: - K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox - K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie - R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows - M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications - G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press - R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006. Dozenten: Prof. Dr. Peter Sanders, Dr. Christian Schulz, Dr. Simon Gog, M.Sc. Michael Axtmann | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

  1. 2019. 02. 07. · 비디오

    30: Algorithmen II, Vorlesung, WS 2018/19, 05.02.2019

    30 | 0:00:00 Start 0:00:20 Schrumpfgraph 0:02:39 Approximationsalgorithmen 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:03:57 Viele kleine Jobs 0:04:52 Untere Schranken 0:05:10 Der Approximationsfaktor 0:07:17 Diese Schranke ist bestmöglich 0:07:49 Mehr zu Scheduling 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems 0:08:33 Hamilton Cycle 0:10:07 TSP mit Dreiecksungleichung 0:10:38 2-Approximstion durch minimalen Spannbaum 0:11:16 Pseudopolynomielle Algorithmen 0:12:26 Fully Polynomial Time Approximation Scheme 0:13:31 Fixed Parameter Algorithmen 0:14:49 VERTEX Cover 0:15:05 Fixed parameter tractable 0:16:32 Naive tiefenbeschränkte Suche 0:19:19 Kernbildung für Vertex Cover 0:21:45 Warum Parallelverarbeitung 0:22:58 Modell Nachrichtengekoppelte Parallelrechner 0:23:30 Kostenmodell für Nachrichtenaustausch 0:24:56 Warum kein Multicore-Modell? 0:26:18 Analyse paralleler Algorithmen 0:26:49 Pseudocode 0:27:41 Weniger ist mehr 0:28:10 Hyperwürfel 0:28:56 Hyperwürfelaulgorithmus 0:31:31 Paralleles Quicksort 0:32:00 Theoretiker-Parallelisierung 0:34:01 Onlinealgorithmen 0:34:29 Competitive analysis 0:35:19 A typical online problem: Ski rental 0:36:32 Paging 0:37:48 Comparison of algorithms 0:39:57 Discussion 0:42:00 Stringology 0:43:29 Strings Sortieren 0:47:55 Naives Pattern Matching 0:48:29 Knuth-Morris-Pratt 0:50:27 Volltextsuche von Langsam bis Superschnell 0:51:18 Invertierter Index 0:52:13 Etwas ""Stringology""-Notation 0:53:14 Suffixe Sortieren 0:53:56 Volltextsuche 0:54:45 Suffix-Baum 0:56:22 SA mit Präfix Verdopplung 0:58:05 Ein erster Teile-und-Herrsche-Ansatz 0:58:52 SA berechnen 1:00:42 Rekursion 1:03:52 LCP-Array 1:07:13 Datenkompression 1:08:51 Wörterbasierte Textkompression 1:09:59 Lempel-Ziv Kompression 1:11:29 Burrows Wheeler Transformation 1:14:47 Geometrische Algorithmen 1:15:37 Plane-Sweep-Algorithmen 1:18:08 Verallgemeinerung 1:21:33 Mehr Linienschnitt 1:22:51 Kleine einschließende Kugel

    1시간 27분

  2. 2019. 02. 04. · 비디오

    29: Algorithmen II, Vorlesung, WS 2018/19, 04.02.2019

    29 | 0:00:00 Starten 0:00:10 Inhaltsübersicht 0:03:02 Rolle der Algorithmik 0:03:43 Machine Learning macht das von selbst 0:17:02 Algorithm Theory 0:21:47 Graphenalgorithmen 0:22:20 Laufzeit 0:26:50 Satz 1 0:29:13 Monotone ganzzahlige Prioritätslisten 0:30:15 Bucket Queue 0:33:27 Analyse 0:34:30 All-Pair Shortest Paths 0:35:09 Knotenpotentiale 0:36:07 Algorithmus 0:37:46 Landmarks 0:38:33 Zusammenfassung Kürzeste Wege 0:39:47 Fortgeschrittene Datenstrukturen 0:40:21 Adressierbare Prioritätslisten 0:41:04 Grundlegende Datenstruktur 0:42:44 Pairing Heaps 0:47:06 Union by Rank 0:49:25 Zusammenfassung Datenstrukturen 0:50:45 Anwendung von DFS 0:51:16 Starke Zusammenhangskomponenten 0:54:00 Repräsentation offener Komponenten 0:57:08 Zusammenfassung SCC Berechnung 0:57:34 2 zusammenhängende Komponenten 0:57:47 Mehr DFS basierte Linearzeitalgorithmen 0:58:25 Maximum Flows and Matchings 0:58:31 Definitions: Network 0:59:24 Duality between Flows and Cuts 1:00:01 Applications 1:00:27 Algorithms 1956-now 1:04:27 Residual Graph 1:06:27 Ford Fulkerson Algorithm 1:07:34 Max Flow Min Gut theorem 1:07:41 Bad Example for Ford Fulkerson 1:08:35 Blocking Flows 1:08:58 Dinitz Algorithm 1:09:52 Blocking Flow Analysis 1:11:20 Maximum Cardinality Bipartite Matching 1:13:09 Preflow Push Algorithms 1:14:45 Level Function 1:16:04 FIFO Preflow push 1:17:17 Timings 1:17:24 Zusammenfassung Flows and Matchings 1:17:57 Randomisierte Algorithmen 1:18:11 Here Fast SOace Efficient Hashing 1:18:50 Externe Algorithmen

    1시간 23분

  3. 2019. 01. 31. · 비디오

    28: Algorithmen II, Übung, WS 2018/19, 29.01.2019

    28 | 0:00:00 Start 0:00:08 Übung 11 0:02:04 Themenübersicht 0:02:49 in-place Multikey Quicksort 0:08:18 Partitionierung 0:20:32 Suche mit Suffix-Arrays 0:34:34 Ablauf 0:40:40 Zusammenfassung 0:43:06 LCP-Array 0:52:10 Schnelle Suche mit Suffix-Arrays 0:55:58 Redundante Vergleiche

    1시간 11분

  4. 2019. 01. 29. · 비디오

    27: Algorithmen II, Vorlesung, WS 2018/19, 28.01.2019

    28 | 0:00:00 Start 0:00:05 Einleitung 0:00:28 Dominik Schreiber - SAT Solving and Automated Planning 0:00:41 Overview 0:01:51 The SAT Problem 0:03:39 SAT Solving 0:05:06 Parallel SAT Solving 0:09:30 Automated Planning 0:13:20 SAT-based Planning 0:17:44 Outlook: Future Research and Teaching 0:23:16 Sebastian Lamm - Distributed Connected Components 0:23:45 Connected Components and Applications 0:25:23 Sequential Algorithms 0:26:16 General Framework 0:29:04 All-Reduce (AR) - Algorithm 0:31:14 Union-find merging (UFM) 0:35:26 Graph Contraction (GC) - Algorithm 0:38:21 Label Propagation (LP) 0:40:44 Comparison 0:43:14 Conclusion 0:44:40 Sebastion Schlag - High Quality Hypergraph Partitioning 0:47:24 Applications 0:48:57 Parallel Sparse-Matrix Vector Product (SpM x V) 0:52:09 From SpM x V to Hypergraph Partitioning 0:56:33 How does Hypergraph Partitioning work? 0:59:27 Taxonomy of Hypergraph Partitioning Tools 1:01:07 Why Yet Another Multilevel Algorithm? 1:05:30 Latest Experimental Results 1:08:45 KaHyPar - Karlsruhe Hypergraph Partitioning 1:10:20 Tobias Maier - Parallele Algorithmen - Einschub Shared Memory Datenstrukturen 1:12:12 Concurrent Hash Table 1:17:19 Migration als Lösung 1:20:33 Vergrößern der Hash Tabelle 1:24:09 Deallocation Problem

    1시간 26분

  5. 2019. 01. 24. · 비디오

    26: Algorithmen II, Vorlesung, WS 2018/19, 22.01.2019

    26 | 0:00:00 Start 0:00:05 LCP-Array 0:11:29 Textkompression 0:12:39 Lempel-Ziv Kompression (LZ) 0:30:17 Burrows-Wheeler-Transformation 0:35:48 Burrows-Wheeler-Transformation-- Rücktransformation 0:48:41 Was bringt die BWT? 0:50:52 BWT--Kompression 0:58:13 Suche in BWT 0:59:10 Backward Search 1:12:41 Wavelet Tree Example: Calculate Rank

    1시간 25분

  6. 2019. 01. 22. · 비디오

    25: Algorithmen II, Vorlesung, WS 2018/2019, 21.01.2019

    25 | 0:00:00 Start 0:00:05 Suffix Array Konstruktionsalgorithmen 0:01:30 SA mit Präfix Verdopplung 0:04:27 Suffixtabellen 0:05:56 Ein erster Teile-und-Herrsche-Ansatz 0:07:22 Asymmetrisches Divide-and-Conquer 0:14:36 Rekursion 0:27:05 Least Significant Digit First Radix Sort 0:28:40 Stabiles Ganzzahliges Sortieren 0:30:16 Sortieren: Most Significant Digit Radix Sort 0:33:16 Suffix-Baum 0:36:08 Implementierung: Vergleichs-Operatoren 0:37:40 Verallgemeinerung: Differenzenüberdeckungen 0:46:22 Suche in Suffix Arrays 0:48:49 LCP-Array 1:10:20 Suffix-Baum aus SA und LCP 1:10:40 Datenkompression 1:12:20 THeorie Verlustfreier Textkompression 1:22:46 Wörterbuchbasierte Textkompression

    1시간 26분

  7. 2019. 01. 17. · 비디오

    24: Algorithmen II, Vorlesung und Übung, WS 2018/19, 15.01.2019

    24 | 0:00:00 Start 0:00:07 Stringology 0:02:36 Fragen zur letzten Vorlesung/ Wiederholung 0:08:51 Suffix-Baum 0:13:39 Alphabet-Modell 0:17:31 Suffix Array Konstruktionsalgorithmen 0:19:50 SA mit Präfix Verdopplung 0:36:14 Ein erster Teile-und-Herrsche-Ansatz 0:37:32 SA1 berechnen 0:39:42 Berechne SA0 aus SA1 0:41:12 Asymmetrisches Divide-and-Conquer 0:43:50 Übung 0:43:53 Online Algorithmen 0:46:32 kompetitiver Faktor 0:48:15 Ski Rental Problem 1:00:15 Doubling Strategie 1:01:09 Online Bidding

    1시간 19분

  8. 2019. 01. 15. · 비디오

    23: Algorithmen II, Vorlesung, WS 2018/19, 14.01.2019

    23 | 0:00:00 Start 0:00:05 Competitive analysis 0:01:19 Atypical online problem: ski rental 0:01:50 Paging 0:02:33 Longest Forward Distance is optimal 0:02:50 Comparison of algorithms 0:03:28 Resource augmentation 0:03:41 Competitive ratio 0:03:53 Counting the faults of OPT 0:03:55 Randomized algorithms 0:04:04 Marking Algorithms 0:04:58 Why competitive analysis 0:06:30 Disadvantages of competitive analysis 0:08:35 Stringology 0:10:08 Strings Sortieren 0:19:15 Multikey Quicksort 0:23:21 Ohne Endzeichen 0:31:58 Algorithmen-Übersicht 0:33:11 Vergleich Sequentielle Algorithmen 0:37:40 Naives Pattern Matching 0:43:03 Knuth-Morris-Pratt 0:58:59 Berechnung des Border-Arrays 1:06:06 Volltextsuche von Langsam bis Superschnell 1:11:48 Invertierter Index 1:14:24 Suffixtabellen 1:14:56 Etwas ""Stringology""-Notation 1:16:22 Suffixe Sortieren 1:18:00 Anwendungen 1:19:04 Suffixe Sortieren 1:19:09 Suffix-Baum

    1시간 24분
모두 보기(30개)

    소개

    Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt. Literaturhinweise: - K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox - K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie - R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows - M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications - G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press - R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006. Dozenten: Prof. Dr. Peter Sanders, Dr. Christian Schulz, Dr. Simon Gog, M.Sc. Michael Axtmann | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

    정보

    • 제작진
      Karlsruher Institut für Technologie (KIT)
    • 방송 연도
      2018년 - 2019년
    • 에피소드
      30
    • 등급
      전체 연령 사용가
    • 웹사이트 보기
      Algorithmen 2, Vorlesung, WS18/19

    Karlsruher Institut für Technologie의 콘텐츠 더 보기

    제한된 콘텐츠

    해당 국가 또는 지역에서는 이 에피소드를 웹에서 재생할 수 없습니다.

    무삭제판 에피소드를 청취하려면 로그인하십시오.

    이 프로그램의 최신 정보 받기

    프로그램을 팔로우하고, 에피소드를 저장하고, 최신 소식을 받아보려면 로그인하거나 가입하십시오.
    국가 또는 지역 선택

    아프리카, 중동 및 인도

    아시아 태평양

    유럽

    라틴 아메리카 및 카리브해

    미국 및 캐나다