\( \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}} \)

Theoretische Informatik I - Stundenplan

Donnerstag, 20. November 2025
(6. Woche, KW 47)		 Polynome multiplizieren: Schulmethode, Karatsuba, schnelle Fourier-Transformation.
Mittwoch, 19. November 2025
(6. Woche, KW 47)		 Feiertag.
Donnerstag, 13. November 2025
(5. Woche, KW 46)		 Karatsuba-Multiplikation.
Mittwoch, 12. November 2025
(5. Woche, KW 46)		 Arithmetische Operationen: drei_hoch(n) in Python. Laufzeitmessung. Theoretische Analyse. fast_exp(base, exponent) mit Laufzeitanalyse (teilweise). Schulmethode für Multiplikation. Laufzeit $O(n^2)$.
Donnerstag, 6. November 2025
(4. Woche, KW 45)		 Deterministisches Selektieren: Median of medians. Kurze Einführung in $O$-Notation.
Mittwoch, 5. November 2025
(4. Woche, KW 45)		 Untere Schranken für vergleichsbasierte Sortieralgorithmen: $\log_2(n!)$. Dann Quickselect: Implementierung und Analyse mit den Indikatorvariablen.
Donnerstag, 30. Oktober 2025
(3. Woche, KW 44)		 Laufzeitanalyse mit Indikatorvariablen und Summenabschätzung: $2\ln(2) n \log_2(n)$.
Mittwoch, 29. Oktober 2025
(3. Woche, KW 44)		 Quicksort: Implementierung, Laufzeitmessung. Quicksort-Baum. Nachfahre / Vorgägner im Baum, erwartete Tiefe. Grobe Abschätzung der erwarteten Tiefe ($5.2 \log_2(n)$, glaube ich)
Donnerstag, 23. Oktober 2025
(2. Woche, KW 43)		 Johannes Tantow hält Vorlesung. Thema: Heapsort.
Mittwoch, 22. Oktober 2025
(2. Woche, KW 43)		 Sortieralgorithmen: naive wie Selectionsort und gute wie Mergesort. Analyse mit Binärbaum (Level, Vergleiche pro Knoten und dann pro Level zählen).
Donnerstag, 16. Oktober 2025
(1. Woche, KW 42)		 Binäre Suche implemtieren; Schleifeninvariante; formale Analyse der Anzahl der Zugriffe; Bit-Größe einer natürlichen Zahl, die zwei äquivalenten Formeln $\ceil{\log(n+1)}$ und $\floor{\log n} + 1$. Informationstheoretische Interpretation von $\ceil{\log(n+1)}$: der Ausdruck $n+1$ ist die Anzahl der möglichen Antworten $-1, 0, 1, 2, 3, \dots, n-1$.
Mittwoch, 15. Oktober 2025
(1. Woche, KW 42)		 Binäre Suche mit Browser-App und als Zweipersonenspiel. Maximum in einem unimodalen Array finden als App und als Spiel.