13 Folgen

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

Parallele Algorithmen, Vorlesung, WS17/18 Karlsruher Institut für Technologie

    • Kurse

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

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

    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

    • 1 Std. 26 Min.
    • video
    12: Parallele Algorithmen, Vorlesung, WS 2017/18, 22.01.2018

    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

    • 1 Std. 29 Min.
    • video
    11: Parallele Algorithmen, Vorlesung, WS 2017/18, 15.01.2018

    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

    • 1 Std. 27 Min.
    • video
    10: Parallele Algorithmen, Vorlesung, WS 2017/18, 08.01.2018

    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

    • 1 Std. 10 Min.
    • video
    09: Parallele Algorithmen, Vorlesung, WS 2017/18, 18.12.2017

    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

    • 1 Std. 7 Min.
    • video
    08: Parallele Algorithmen, Vorlesung, WS 2017/18, 11.12.2017

    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

    • 1 Std. 29 Min.

Top‑Podcasts in Kurse

Mehr von Karlsruher Institut für Technologie