Parallele Algorithmen, Vorlesung, WS17/18

Karlsruher Institut für Technologie (KIT)
  • 0.0 (0)
  • COURSES
Parallele Algorithmen, Vorlesung, WS17/18

Inhalt der Vorlesung: - Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit, Berechnungskomplexität, 'schwere' Probleme, O-Notation, Mastertheorem - Alphabete, Wörter, formale Sprachen, endliche Akzeptoren, kontextfreie Grammatiken - induktive/rekursive Definitionen, vollständige und strukturelle Induktion, Hüllenbildung - Relationen und Funktionen - Graphen - Syntax und Semantik für Aussagenlogik Weiterführende Literatur - Goos: Vorlesungen über Informatik, Band 1, Springer, 2005 - Abeck: Kursbuch Informatik I, Universitätsverlag Karlsruhe, 2005 Ziel: Der/die Studierende soll - grundlegende Definitionsmethoden erlernen und in die Lage versetzt werden, entsprechende Definitionen zu lesen und zu verstehen. - den Unterschied zwischen Syntax und Semantik kennen. - die grundlegenden Begriffe aus diskreter Mathematik und Informatik kennen und die Fähigkeit haben, sie im Zusammenhang mit der Beschreibung von Problemen und Beweisen anzuwenden. Dozent: Dr. Sebastian Stüker |  Karlsruher Institut für Technologie (KIT), Institut für Anthropomatik und Robotik | Vorlesungsaufzeichnung: http://webcast.kit.edu

  1. 02/01/2018 · VIDEO

    13: Parallele Algorithmen, Vorlesung, WS 2017/18, 29.01.2018

    13 | 0:00:00 Starten 0:00:36 Was wissen wir über die Jobs? 0:02:32 Was wissen wir über die Prozessoren? 0:05:44 Zufälliges Zuordnen 0:07:08 Work Stealing 0:10:58 Backtracking over Transition Functions 0:12:02 An Abstract Model: Tree Shaped Computations 0:17:37 Splitting Stacks 0:21:27 Other Problem Categories 0:27:01 Limits of the Model 0:29:35 Receiver Initiated Load Balancing 0:31:40 Random Polling 0:41:11 Synchronous Random Polling 0:45:21 Analysis 0:51:22 Bounding Idleness 0:57:08 A Simplified Algorithm 1:03:22 Many Consecutive Splits 1:05:49 Many Processors 1:09:03 Superliner Speedup 1:15:12 Static vs Dynamic LB 1:18:35 MapReduce in 10 Minutes

    1h 27m

  2. 01/23/2018 · VIDEO

    12: Parallele Algorithmen, Vorlesung, WS 2017/18, 22.01.2018

    12 | 0:00:00 Starten 0:00:10 Parallele Prioritätslisten 0:02:03 Branch-and-Bound 0:05:17 Einfache Probabilistische Eigenschaften 0:08:11 Parallele Realisierung II 0:09:58 Randomisierte Selektion 0:15:14 Parallele Implementierung 0:21:11 Implementierung IBM SP-2 m=2^24 0:23:27 Implementierung Cray T3D, m=2^24 0:26:07 Lastverteilung 0:30:25 Kostenmaß 0:34:35 Was wissen wir über die Jobs und die Prozessoren? 0:37:26 Ein ganz einfaches Modell 0:51:04 Atomare Jobs 0:58:56 Beispiel Mandelbrotmenge 1:02:56 Angenäherte Berechnung 1:05:56 Code 1:08:31 Statische Äpfelverteilung 1:13:01 Zufälliges Zuordnen 1:19:42 Parallelisierung der Zuordnungsphase 1:21:34 Pseudorandom Permutations 1:24:37 Das Master-Worker-Schema 1:28:22 Größe der Teilprobleme

    1h 30m

  3. 01/18/2018 · VIDEO

    11: Parallele Algorithmen, Vorlesung, WS 2017/18, 15.01.2018

    11 | 0:00:00 Starten 0:00:14 Finding lightest incident edges 0:01:19 Pseudotrees - Rooted Trees 0:03:00 Randomized Linear Time Algorithm 0:04:24 Parallel Filter Kruskal 0:05:40 Parallele Prioritätlisten 0:10:34 Naive Implementierung 0:11:30 Branch-and-Bound 0:25:18 Sequentielles Branch-and-Bound 0:35:27 Paralleles Branch-and-Bound 0:38:20 Analyse 0:52:09 Der Algorithmus von Karp und Zhang 1:01:47 Einfache Probabilistische Eigenschaften 1:04:01 Parallele Realisierung I 1:16:04 Parallele Realisierung II

    1h 27m

  4. 01/11/2018 · VIDEO

    10: Parallele Algorithmen, Vorlesung, WS 2017/18, 08.01.2018

    10 | 0:00:00 Starten 0:00:10 Minimum Spannung Trees 0:03:06 Selecting and Discarding MST Edges 0:09:01 Kruskal's Algorithm 0:12:41 Edge Contraction 0:16:29 Finding lightest incident edges 0:24:06 Structure of Resulting Components 0:28:51 Pseudotrees -> Rooted Trees 0:31:07 Rooted Trees -> Rooted Stars by Doubling 0:32:43 Contraction 0:42:36 Recursion 0:45:21 Analysis 0:52:10 Randomized Linear Time Algorithm 0:55:08 Parallel Filter Kruskal 1:05:43 Running Time: Random graph with 2^16 nodes 1:09:12 More on Parallel MST

    1h 10m

  5. 12/19/2017 · VIDEO

    09: Parallele Algorithmen, Vorlesung, WS 2017/18, 18.12.2017

    09 | 0:00:00 Starten 0:00:10 Datenaustausch bei unregelmäßigen Nachrichtenlängen 0:02:02 Der Vogel-Strauß-Algorithmus 0:05:41 h-Relation 0:07:37 Offline h-Relationen im duplex Modell 0:17:17 Offline h-Relationen im Simplex-Modell 0:22:08 How Helper Hasten h-Relations 0:23:02 Ein ganz simpler Fall 0:24:53 Zwei Dreiecke 0:31:25 Reduktion h-Relation =>(h/2) 2-Relationen 0:33:06 Offline h-Relationen im duplex Modell 0:36:24 ""-Relationen routen für gerade p 0:39:24 Zwei Ungerade Kreise mit >= 3 Knoten 0:43:16 Offene Probleme 0:50:39 Ein einfacher verteilter Algorithmus - Der Zweiphasenalgorithmus 0:53:54 Abstrakte Beschreibung 1:00:40 Offene Probleme zum nichtpräemptiven offline Algorithmus 1:02:07 Zusammenfassung: All-to-All 1:04:26 Noch allgemeinere kollektive Kommunikation: Multicommodity Multicasting

    1h 7m

  6. 12/12/2017 · VIDEO

    08: Parallele Algorithmen, Vorlesung, WS 2017/18, 11.12.2017

    08 | 0:00:00 Starten 0:01:52 Kollektive Kommunikation 0:05:06 All-to-all Personalized Communication 0:08:09 Der 1-Faktor-Algorithmus 0:14:46 Datenaustausch bei unregelmäßigen Nachrichtenlänge 0:17:42 Ein einfacher verteilter Algorithmus- Der Zweiphasenalgorithmus 0:33:27 List Ranking 0:42:37 Motivation II 0:45:26 Doubling using CREW PRAM, n=p 0:55:37 Entfernung unabhängiger Teilmengen 1:13:01 Finden unabhängiger Teilmengen 1:20:05 Neuere Implementierungsergebnisse 1:22:45 Minimum Spanning Trees 1:25:09 The Jarník-Prim Algorithm

    1h 29m

  7. 12/07/2017 · VIDEO

    07: Parallele Algorithmen, Vorlesung, WS 2017/18, 04.12.2017

    07 | 0:00:00 Starten 0:00:10 Analyse von Sample Sort 0:07:27 Samples Sortieren 0:07:46 Mehrwegemischen 0:12:51 Multisequence Selection 0:16:24 Splitter Selection 0:19:44 Verteilte Multisequence Selection 0:30:41 CRCW Sortieren in logarithmischer Zeit 0:35:50 Beispiel 0:37:54 Kollektive Kommunikation 0:39:18 Präfixsummen 0:41:29 Einfache Pipeline 0:42:41 Hyperwürfelalgorithmus 0:57:22 Analyse 0:58:35 Pipeline-Binärbaum-Präfixsummen 1:10:07 23-Präfixsummen 1:10:33 Analyse 1:10:56 Verallgemeinerung 1:11:17 Gossiping 1:20:02 Analyse 1:21:25 All-to-all Personalized Communication 1:25:04 Analyse, Telefonmodell

    1h 33m

  8. 11/28/2017 · VIDEO

    06: Parallele Algorithmen, Vorlesung, WS 2017/18, 27.11.2017

    06 | 0:00:00 Starten 0:00:25 Schnelles ineffizientes Ranking 0:02:41 Sortieren größerer Datenmengen 0:02:48 Zurück zum schnellen Ranking 0:04:42 Verallgemeinerung für m >>p nach schema F? 0:10:01 Distributed memory parallel quicksort 0:10:16 Load Balance 0:24:28 Die gute Nachricht: 0:32:19 Bessere Lastbalanceierung? 0:35:32 Multi-Pivot Verfahren 0:42:23 Analyse 0:49:20 Lemma2. 0:50:46 Lemma 1:06:48 Chernoff-Schranke 1:15:21 Analyse von Sample Sort 1:30:48 Sample Sortieren

    1h 31m
See All (13)

About

Inhalt der Vorlesung: - Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit, Berechnungskomplexität, 'schwere' Probleme, O-Notation, Mastertheorem - Alphabete, Wörter, formale Sprachen, endliche Akzeptoren, kontextfreie Grammatiken - induktive/rekursive Definitionen, vollständige und strukturelle Induktion, Hüllenbildung - Relationen und Funktionen - Graphen - Syntax und Semantik für Aussagenlogik Weiterführende Literatur - Goos: Vorlesungen über Informatik, Band 1, Springer, 2005 - Abeck: Kursbuch Informatik I, Universitätsverlag Karlsruhe, 2005 Ziel: Der/die Studierende soll - grundlegende Definitionsmethoden erlernen und in die Lage versetzt werden, entsprechende Definitionen zu lesen und zu verstehen. - den Unterschied zwischen Syntax und Semantik kennen. - die grundlegenden Begriffe aus diskreter Mathematik und Informatik kennen und die Fähigkeit haben, sie im Zusammenhang mit der Beschreibung von Problemen und Beweisen anzuwenden. Dozent: Dr. Sebastian Stüker |  Karlsruher Institut für Technologie (KIT), Institut für Anthropomatik und Robotik | Vorlesungsaufzeichnung: http://webcast.kit.edu

Information

More From Karlsruher Institut für Technologie

  • Einführung in die Geophysik 1, WS17/18, Vorlesung
    Courses
    Courses

    Updated 02/05/2018

  • IEEE International Conference on Robotics and Automation, 2013
    Courses
    Courses

    Updated 01/31/2014

  • Transport Phenomena in the Biosphere
    Courses
    Courses

    Updated 02/05/2018

  • Internationales Forum am ZAK
    Courses
    Courses

    Updated 06/25/2020

  • The Karlsruhe Institute of Technology (KIT)
    Courses
    Courses

    Updated 12/03/2013

  • KIT Campus – Studieren und mehr | 2014
    Courses
    Courses

    Updated 09/19/2014

  • CAD tutorial in Mechanical Design, WT13/14
    Courses
    Courses

    Updated 11/28/2013

To listen to explicit episodes, sign in.

Stay up to date with this show

Sign in or sign up to follow shows, save episodes, and get the latest updates.
Select a country or region

Africa, Middle East, and India

Asia Pacific

Europe

Latin America and the Caribbean

The United States and Canada