Der Stundenplan dient als Tagebuch, um festzuhalten, was wir tatsächlich in den Vorlesungen gemacht haben. Hier kündige ich auch an, welche Übungsaufgaben Sie bis zum nächsten Termin anschauen sollten.
| Dienstag, 9. Dezember Nachmittag (9. Woche, KW 50) |
Rasmus Eder hält Übung. |
| Dienstag, 9. Dezember Vormittag (9. Woche, KW 50) |
Das PRAM-Modell etwas formaler und wie man es in Schaltkreise umwandelt. Dass also
PRAM-Algorithmen und Schaltkreise äquivalent sind, wenn man nur parallele Zeit
$O(\log^k n)$ und $O(n^k)$ Prozessoren haben will und einen der genaue Wert von $k$ nicht
interessiert.
Turingmaschinen mit beschränktem Platz. Eins addieren als Beispielproblem, das ohne zusätzlichen Platz geht (lustigerweise sowohl für eine links-nach-rechts- und eine rechts-nach-links-Schreibweise). |
| Dienstag, 2. Dezember Nachmittag (8. Woche, KW 49) |
Perfekte Matchings berechnen. Isolation Lemma. |
| Dienstag, 2. Dezember Vormittag (8. Woche, KW 49) |
Determinanten berechnen und Matrizen invertieren. |
| Dienstag, 25. November Nachmittag (7. Woche, KW 48) |
Starke Zusammenhangskomponenten auf Arbitrary CRCW PRAM. Randomisiertes Verschmelzen . |
| Dienstag, 25. November Vormittag (7. Woche, KW 48) |
Graphen. Darstellungen, Adjazenzlisten berechnen. Zusammenhangskomponenten mit Umfärbungsvorschlag, Pointer-Jumping. |
| Dienstag, 18. November Nachmittag (6. Woche, KW 47) |
Rasmus Eder hält Übung. |
| Dienstag, 18. November Vormittag (6. Woche, KW 47) |
Coles paralleler Mergesort-Algorithmus. |
| Dienstag, 11. November Nachmittag (5. Woche, KW 46) |
Valiants merge in $O(\log \log n)$ und warum das nicht so ganz stimmt. Verschiedene RPAM-Modelle. Maximum in $O(\log \log n)$ parallelen Vergleichsschritten. |
| Dienstag, 11. November Vormittag (5. Woche, KW 46) |
Sortiernetzwerke. Sortieren auf einer PRAM: merge in $O(\log n)$ Zeitschritten mittels binärer Suche für jedes Element. Sortieren in $O(\log^2 n)$. |
| Dienstag, 4. November Nachmittag (4. Woche, KW 45) |
Übung. |
| Dienstag, 4. November Vormittag (4. Woche, KW 45) |
Crashkurs in Wahrscheinlichkeitsrechnung. Wahrscheinlichkeitsräume, Ergebnisse, Ereignisse. Formel für $\Pr[A \cup B]$; Unabhängigkeit. Markov- und Tschebyschoff-Ungleichung an folgendem Beispiel: wenn man 600 mal würfelt und $X$ die Anzahl ist, wie oft man eine Sechs gewürfelt hat, was ist dann $\Pr[X \geq 300]$? Leider nicht mehr zur Chernhoff-Schranke gekommen... |
| Dienstag, 28. Oktober Nachmittag (3. Woche, KW 44) |
Listensuffixsummen mit $O(\log n)$ Zeit und $O(n)$ Arbeit: wie man in $O(1)$ eine
unabhängige Menge der Größe $\Theta(n)$ konstruiert. Warum es nicht wirklich klar ist,
ob ein schlafender Prozessor was kostet. Der Algorithmus von Anderson und Miller:
man verteilt auf $n / \log n$ Prozessoren jeweils $\log n$ Knoten der Liste (so,
wie sie im Speicher liegen, nicht so, wie sie in der Liste vorkommen).
Dauer, bis alle fertig sind, Chernoff-Schranke von Wikipedia gespickt.
Offene Frage: Was, wenn die Elemente der Liste nicht schön in den ersten $n$ Speicherzellen liegen, sondern beispielsweise in einem $O(n^2)$ großen Speicher wild verteilt liegen? Wie kann man dann jedem Prozessor $\log n$ Eelemente zuordnen? Dominik Scheders spontane Gedanken dazu: die Schwierigkeit gibt es ja bei jedem Problem. Wenn wir also $n$ Datensätze auf $n^2$ Speicherzellen verstreut liegen haben und dann $n$ Prozessoren, die nicht wissen, wo die liegen, dann müsste man die ja erst einmal irgendwie finden. Vielleicht vernünftige Grundannahme: wenn unser Problem aus $n$ Datensätzen besteht, dann gibt es auch einen Bereich aus $O(n)$ Speicherzellen, der sie enthält und den wir a priori kennen. Ich lasse mich aber gerne vom Gegenteil überzeugen und ein plausibles Szenario zeigen, wo das nicht so gegeben ist. |
| Dienstag, 28. Oktober Vormittag (3. Woche, KW 44) |
Kurze Wiederholung der Präfixsumme. Das ganze nicht als Schaltkreis betrachten, sondern sich Prozessoren vorstellen, die Daten rumschicken / speichern. Dann Listenpräfixsummen (bzw. Listensuffixsummen), bei denen die Daten als verkettete Liste gegeben ist und nicht als Array. Pointer Jumping: $O(\log n)$ Zeit und $O(n \log n)$ Arbeit. |
| Dienstag, 21. Oktober 2025 Nachmittag (2. Woche, KW 43) |
Ramus Eder hält Übung. |
| Dienstag, 21. Oktober Vormittag (2. Woche, KW 43) |
Kurze Einführung. Parallele Berechnung von $\min$. Großteil der Zeit für Binäraddierer mit Carry-Lookahead. Dann das gleiche nochmal als rekursive Konstruktion für Präfixsumme. Abstraktion: Präfixsummen mit assoziativem Operator $\circ$. |
| Dienstag, 13. Oktober 2025 (1. Woche, KW 42) |
Keine Veranstaltung in der 42. Kalenderwoche. |
| Dienstag, 13. Oktober 2025 (1. Woche, KW 42) |
Keine Veranstaltung in der 42. Kalenderwoche. |