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

Aus VoWi
Zur Navigation springen Zur Suche springen
Ähnlich benannte LVAs (Materialien):

Daten[Bearbeiten | Quelltext bearbeiten]

Vortragende Gramoz Goranci, Nils Morten Kriege
ECTS 6,00 / 4,00
Aufgezeichnet Nein
Sprache English
Links ufind:052114 , Homepage
Zuordnungen
Bachelor Informatik Wahlmodul Parallel Computing
Bachelor Informatik Wahlmodul Algorithms
Master Informatik Wahlmodul Parallel Computing
Master Informatik Wahlmodul Algorithms
Master Data Science
Master Computational Science Wahlmodul Specialisation


Inhalt[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

siehe Ablauf

Übungen[Bearbeiten | Quelltext bearbeiten]

siehe Ablauf

Prüfung, Benotung[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

noch offen

Zeitaufwand[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

noch offen

Tipps[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

  • 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.