\( \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, 11. Dezember 2025
(9. Woche, KW 50)
Mittwoch, 10. Dezember 2025
(9. Woche, KW 50)		 Kürzeste Wege, wenn auch negative Kosten erlaubt sind: der Bellman-Ford-Algorithmus.
Donnerstag, 4. Dezember 2025
(8. Woche, KW 49)		 Nochmals: Kosaraju-Sharir. Dann Breitensuche. Graphen mit Kantenkosten und Dijkstras Algorithmus.
Mittwoch, 3. Dezember 2025
(8. Woche, KW 49)		 Tologische Sortierung per Tiefensuche. Starke Zusammenhangskomponenten und Kosaraju-Sharir.
Donnerstag, 27. November 2025
(7. Woche, KW 48)		 Zyklen finden. Zusammenhangskomponenten.
Mittwoch, 26. November 2025
(7. Woche, KW 48)		 Graphen. Definitionen. Tiefensuche, Erreichbarkeit.
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.