Theoretische Informatik I, Wintersemester 2026/27- Stundenplan
| Montag, 16. November 2026 (6. Woche, KW KW 47) |
Polynome multiplizieren mit schneller Fourier-Transformation. |
| Donnerstag, 12. November 2026 (5. Woche, KW 46) |
Karatsuba-Multiplikation |
| Montag, 9. November 2026 (5. Woche, KW 46) |
Fibonacci-Zahlen berechnen, rekursiv and interativ. Warum suggeriert unsere Laufzeitmessung für die iterative Version eine Laufzeit von $O(n^2)$ und nicht $O(n)$? Schnelle Matrix-Exponentiation. |
| Donnerstag, 5. November 2026 (4. Woche, KW 45) |
Untere Schranke für vergleichsbasiertes Sortieren. O-Notation. Sachen wie $\sum_{i=1}^n i^2 \in \Theta(n^3)$ oder ${n \choose k} \in \Theta(n^k)$. |
| Montag, 2. Oktober 2026 (4. Woche, KW 45) |
Median-of-Medians-Algorithmus. Rekursionen der Form $T(n) \leq T(\alpha n) + T(\beta n) + n$ lösen. |
| Donnerstag, 29. Oktober 2026 (3. Woche, KW 44) |
Selektieren: Naiv mit Sortieren und nachschauen. Maximum in $n$ Schritten. Zweitgrößtes Element $n + \log n$ Schritten. Quickselect und einigermaßen genaue Laufzeitanalyse. |
| Montag, 26. Oktober 2026 (3. Woche, KW 44) |
Quicksort: Implementierung, Laufzeitmessung. Quicksort-Baum. Nachfahre / Vorfahre im Baum, Indikatorvariable $A_{x,y}$. Erwartete Abschätzung der erwarteten Anzahl an Vergleichen ($2 \ln(n)$, glaube ich). |
| Donnerstag, 22. Oktober 2026 (2. Woche, KW 43) |
Effiziente Sortieralgorithmen. Mergesort: Implementierung, Laufzeitmessung. Analyse mit Binärbaum. Heapsort: Heap als Datenstruktur. Einfügen, Löschen. Implementierung als Array (an Tafel, nicht als Code). |
| Montag, 19. Oktober 2026 (2. Woche, KW 43) |
Naive Sortieralgorithmuen: Selectionsort. Laufzeitmessung. Laufzeitanalyse. Die Summe $1 + ... + (n-1)$. Falsche Vermutung: Selectionsort vergleicht jedes Paar von Elementen genau einmal. In Wirklichkeit kann ein Paar mehrmals verglichen werden (Übungsaufgabe: wie oft?) und es können sogar Paare fehlen (Übungsaufgabe: wie viele?) |
| Donnerstag, 15. Oktober 2026 (1. Woche, KW 42) |
Binäre Suche: group testing ($n$ Personen; $k$ davon haben eine Infektion; effizientes Testen, indem man mehrere Proben zu Batches zusammenwirft, testet, und dann alle Personen, die in einer positiven Batch waren, individuell test. Unimodale Arrays, obere Schranke. |
| Montag, 12. Oktober 2026 (1. Woche, KW 42) |
Binäre Suche mit Browser-App und als Zweipersonenspiel. Johannes Tantow hält Vorlesung. |