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.
| Freitag, 30. Oktober 2026 (3. Woche, KW 44) |
Listenpräfix bzw. Listensuffix. Pointer Jumping mit $O(\log n)$ Zeit und $O(n \log n)$ Arbeit. Zwei Begriffe von Arbeitskomplexität: die "strenge" $P \cdot T$ und die "liberale" $\sum_{p} \left(\textnormal{Arbeit, die $p$ macht}\right)$. Versuch einer Verbesserung: Prozessoren wählen Zufallsbits und schlafen ein wenn bit[i] = 0 und bit[next[i]] = 1 ist. Überlegung, warum die Behauptung, der Arbeitsaufwand sei $O(n)$ nicht ganz koscher ist. Nochmal etwas ins PRAM-Modell geschaut. |
| Dienstag, 27. Oktober 2026 (3. Woche, KW 44) |
Übung zur Präfixsumme: Blockindex, Blockbeginn, Blocklänge. Best Subinterval. Vier Werte (grün: Optimum generell; rot: bestes, das an linken Rand angrenzt; blau: bestes, das an rechten Rand angrenzt; orange: Gesamtsumme des Intervals). Operator definiert, geschaut, ob der assoziativ ist. Klar: auf den tatsächlich vorkommenden Quadrupeln ist er's. Claude sagt, auch generell assoziativ. |
| Freitag, 23. Oktober 2026 (2. Woche, KW 43) |
Binäraddierer mit Carry generate / propagate. |
| Dienstag, 20. Oktober 2026 (2. Woche, KW 43) |
Allgemeine Einführung. Minimum / Summe auf einem Array. Präfixsummen mit Baum hoch, Baum runter. |
| Freitag, 16. Oktober 2026 (1. Woche, KW 42) |
Keine Veranstaltung. |
| Dienstag, 13. Oktober 2026 (1. Woche, KW 42) |
Keine Veranstaltung. |