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
All content for Parallele Algorithmen, Vorlesung, WS17/18 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
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
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
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
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
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
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
