\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\rank}{\textnormal{rank}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \) zur Kursübersicht

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.