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

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

Daten[Bearbeiten | Quelltext bearbeiten]

Vortragende Ami Paz, Nils Morten Kriege
ECTS 6,00 / 4,00
Aufgezeichnet Ja
Letzte Abhaltung 2022S
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


Inhalt[Bearbeiten | Quelltext bearbeiten]

Es ging um Distributed Algorithms. Das 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.

Dabei ging es im 2022S 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)
  • Allgemeine Graphentheorie
  • CONGEST model (zB. BFS, All-pairs shortest paths, Wave, APSP, Diameter-Approximations, Cycle detection, ...)
  • Diameter-Approximations, Lower bounds, ...
  • Kurze Einführung in Parallel Computing (SIMD, MISD, Memory models incl. Parallel RAM, ...)
  • CLIQUE Model (incl. Routing; example Matrix multiplication, ...)

Ablauf[Bearbeiten | Quelltext bearbeiten]

Es gibt normale Vorlesungssessions (2x pro Woche, ohne Anwesenheitspflicht), die auch aufgezeichnet wurden. Dort werden die Vorlesungsfolien vorgetragen. Man sollte sich die Vorlesung unbedingt anschauen (notfalls die Aufzeichnung), ohne Vorlesung versteht man wahrscheinlich nicht besonders viel.

Desweiteren gibt es 2 Hausübungen. Da geht es jeweils entweder darum, die Laufzeit eines Algorithmus' zu beweisen, einen neuen Algorithmus zu finden bzw. einen bestehenden so anzupassen, dass er auf eine geänderte Topologie / mit bestimmten Constraints funktioniert.

Die beiden Hausübungen sind quasi unendlich schwer. Alle Leute, mit denen ich gesprochen habe, hatte absolut keine Ahnung, was sie hier eigentlich tun. Interessanterweise waren viele der Lösungen dann trotzdem richtig, auch wenn man sich gedacht hat, dass das so niemals stimmen kann. Man kreuzt im Moodle an, welche Beispiele man gelöst hat; dann gibt es Sessions, wo man aufgerufen wird und seine Lösung präsentieren muss (in diesen Sessions gibt es Anwesenheitspflicht).

Zusätzlich gibt es noch ein Projekt, das man zu zweit machen muss. Dabei wählt man ein Paper aus einer Liste aus und soll dann hier irgendetwas verbessern. Z.B. dass es in einem anderen Modell funktioniert o.ä. Seine Ergebnisse muss man dann auch am Ende des Semesters präsentieren.

Am Semesterende gibt es noch eine mündliche Prüfung, die zur Hälfte zum Vorlesungsstoff und zur Hälfte ums Projekt geht.

Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]

  • Mathematische Beweise (informell)
  • Gute graphentheoretische Kenntnisse von Vorteil
  • Kenntnisse von Randomized Algorithms

Dh. ich würde dringend 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]

  • 25% machen die Hausübungen aus
  • 25% das Projekt
  • 50% die mündliche Prüfung über Vorlesungsstoff und Projekt

Achtung: Das Projekt ist unbedingte Voraussetzung - ohne Projekt kann man auch nicht zur Prüfung antreten und ist automatisch negativ!

Wir sind uns nicht sicher, aber glauben, dass bei den Hausübungen der Versuch, das Beispiel zu lösen, zählt, sodass man dann dafür die Punkte bekommt. Das macht es vermutlich einfacher, die LV zu bestehen, weil man auch für unfertig und falsch gelöste Beispiele vermutlich Punkte bekommt. Ganz sicher sind wir uns hier aber nicht.

Dauer der Zeugnisausstellung[Bearbeiten | Quelltext bearbeiten]

Semester Letzte Leistung Zeugnis
SS22 27.06.2022 27.07.2022 4 Wochen

Zeitaufwand[Bearbeiten | Quelltext bearbeiten]

Ziemlich hoch. Für mich war es wohl die schwerste Lehrveranstaltung, die ich je versucht habe.

Unterlagen[Bearbeiten | Quelltext bearbeiten]

noch offen

Tipps[Bearbeiten | Quelltext bearbeiten]

  • Sofort mitlernen, sonst kommt man nicht weit.
  • Am besten das Projekt mit jemandem machen, den/die man kennt und der/die die LV auch fertig machen wird! Meine Projektpartnerin hat die Lehrveranstaltung geschmissen, wodurch ich das Projekt alleine machen hätte müssen - und die LV letztlich auch geschmissen habe.

Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]

Die Lehrenden sind extrem nett und erklären bei Fragen auch so lange, wie man nachfragt. Nachdem das Thema für uns Studierende so aber neu war, ist es uns trotzdem schwer gefallen, die Inhalte zu verstehen. Ich habe jedoch keine Ahnung, wie man das verbessern könnte ...