Uni Wien:Distributed and Parallel Algorithms VU (Goranci, Kriege)

Daten

Vortragende	Gramoz Goranci, Nils Morten Kriege, seit 2024S auch: Martin Schirneck
ECTS	6,00 / 4,00
Aufgezeichnet	Nein
Sprache	English
Links	ufind:052114

Zuordnungen

Bachelor Informatik	Modul Parallel Computing (Gebundenes Wahlfach)
Bachelor Informatik	Modul Algorithms (Gebundenes Wahlfach)
Master Informatik	Modul Parallel Computing (Gebundenes Wahlfach)
Master Informatik	Modul Algorithms (Gebundenes Wahlfach)
Master Data Science	Modul Specialisation (Gebundenes Wahlfach)
Master Computational Science	Modul Specialisation (Gebundenes Wahlfach)

Inhalt

Es ging um Distributed Algorithms sowie um Parallel Algorithms.

Distributed Algorithms sind vor allem Algorithmen (und die Theorie dazu), die in Netzwerken (mit verschiedenen Topologien) laufen, wobei jede Node in der Regel nur mit den unmittelbaren Nachbarn kommunizieren kann. Das Modell dazu ist relativ abstrakt.

Dabei ging es im 2023S insbesondere um folgende Themen:

• Algorithmen für Colorings - also quasi das Einfärben des Netzwerks mit einem distributed Algorithm; u.a.:
  • P3C
  • P3CRand
  • P3CBit
  • Lower bounds für 2- und 3-coloring
• Maximal independent set (MIS)
• LOCAL model (incl. Diameter und die Algorithmen in diesem Modell, u.a. BDColor)
• CONGEST model (zB. BFS, All-pairs shortest paths, Wave, APSP, Diameter-Approximations, Cycle detection, ...)
• Allgemeine Graphentheorie
• Diameter-Approximations, Lower bounds, ...
• Graph spanners
• Spectral sparsifiers
• Kurze Einführung in Parallel Computing (SIMD, MISD, Memory models incl. Parallel RAM, ...)
• Parallel Algorithms - also quasi, wie man unter der Annahme, dass man unendlich viele Prozesse hat, Algorithmen parallelisiert und analysiert
• Parallel Graph Algorithms (Prim's Algorithm, Kruskal's Algorithm, Boruvka's Algorithm, ... - alle parallel)

Ablauf

Es gibt normale Vorlesungssessions (2x pro Woche, ohne Anwesenheitspflicht). Diese fanden vor Ort im Seminarraum statt; es gab kein Streaming und keine Aufzeichnung. Für die meisten Inhalte gab es Vorlesungsfolien, für einzelne Themen aber auch nur handgeschriebene Unterlagen (die aber auch auf Moodle gestellt wurden).

Man sollte die Vorlesung idealerweise wirklich besuchen, weil es sonst sehr schwer ist, die Inhalte zu verstehen, vor allem vom ersten Teil.

Es gab 4 Hausübungen, 2 davon zum ersten Teil (distributed Algorithms), 2 für den zweiten Teil (parallel Algorithms). Jede Hausübung macht 10% der Note aus. Oft muss man einen Algorithmus für ein bestimmtes Modell mit einer bestimmten Laufzeit finden, oder die Laufzeit oder Korrektheit beweisen o.ä. Die Hausübungen durften in Gruppen zu maximal 2 Leuten gemacht werden (es musste aber trotzdem jeder seine eigene Lösung abgeben). Sie sind ziemlich schwer. Man bekommt Punkte dafür und die Hausübungen werden an der Tafel von dem jeweiligen Lehrenden vorgezeigt, allerdings werden keine Lösungen veröffentlicht und man bekommt nicht direkt Feedback für seine Lösung (außer wahrscheinlich man fragt explizit danach).

Zusätzlich gibt es noch ein Projekt, das man zu zweit oder alleine machen muss. Dabei wählt man ein Paper aus einer Liste aus und hat dann 3 Möglichkeiten:

• Entweder man fasst das Paper zusammen und präsentiert es (Summary).
• Oder man verbessert etwas/untersucht etwas, was mit dem Thema zu tun hat/... (Research-oriented).
• Oder man implementiert oder testet etwas von seinem Paper (Implementation and Experimental Evaluation).

Das Ergebnis muss man präsentieren (was 25% der Note ausmacht) und außerdem einen Report schreiben (15% der Note).

Es gab keine schriftliche oder mündliche Prüfung, allerdings 2 Quiz via Moodle. Die sind relativ einfach und machen auch nur je 5% der Note aus.

Die LV ist jedenfalls reine Theorie.

Benötigte/Empfehlenswerte Vorkenntnisse

• Mathematische Beweise (informell)
• Gute graphentheoretische Kenntnisse von Vorteil, wird aber an sich wiederholt.
• Kenntnisse von Randomized Algorithms

Dh. ich würde empfehlen, sowohl Uni_Wien:Algorithms_and_Data_Structures_2_VU_(Kriege) als auch Uni_Wien:Advanced_Algorithms_VU_(Hanauer) vorher zu absolvieren, auch wenn das keine unbedingten Voraussetzungen laut Curriculum sind.

Vortrag

siehe Ablauf

Übungen

siehe Ablauf

Prüfung, Benotung

• 40% Exercises (individual work) - also 4 HÜen zu je 10%
• 10% Quizzes (individual work) - 2 Quiz zu je 5%
• 25% Project presentation (individual or group work) - alleine oder zu 2t
• 15% Project report (individual or group work) - alleine oder zu 2t
• 10% Active participation in project discussions (individual work)

Achtung: Das Projekt ist unbedingte Voraussetzung!

Dauer der Zeugnisausstellung

noch offen

Zeitaufwand

Relativ hoch, weil die Materie sehr komplex bzw. abstrakt ist. Für jede Hausübung sollte man je mindestens 2 Tage einplanen, für das Projekt etwas mehr (je nachdem, wie lange man braucht, um das Paper zu verstehen halt).

Unterlagen

noch offen

Tipps

• Am besten das Projekt mit jemandem machen, den/die man kennt und der/die die LV auch fertig machen wird! Also eine verlässliche Person suchen.

Verbesserungsvorschläge / Kritik

• Ein bisschen mehr praktische Anwendungsfälle/Beispiele wären vielleicht nett.

Materialien

Diese Seite hat noch keine Anhänge, du kannst aber neue hinzufügen.