Theoretische Informatik II - Sommersemester 2024
Stundenplan
| Datum | Inhalt |
|---|---|
| Mittwoch, 5. Juni 2024 | Einen LR-Parser in Java implementieren. |
| Dienstag, 4. Juni 2024 | Kontextfreie Grammatiken: Ableitungen, Ableitungsbäume, LR-Parsen per Hand. |
| Mittwoch, 29. Mai 2024 | Reguläre Ausdrücke. |
| Dienstag, 28. Mai 2024 | Die Grenzen regulärer Sprachen. Untere Schranken durch paarweise unterscheidbare Wortpräfixe. |
| Mittwoch, 22. Mai 2024 | Reguläre Grammatiken, nichtdeterministische endliche Automaten und wie man die in einen regulären umwandelt. |
| Dienstag, 21. Mai 2024 | Lehrfrei |
| Mittwoch, 15. Mai 2024 | Reguläre Sprachen, endliche Automaten. |
| Dienstag, 14. Mai 2024 | Formale Sprachen und Grammatiken. |
| Mittwoch, 17. April 2024 | Untere Schranke $\Omega(2^n/n)$ für Boolesche Schaltkreise durch Abzählen (Shannon's Counting Argument).
Lyupanovs obere Schranke $O(2^n/n)$. Da bin ich nicht fertiggeworden und bin
später zu folgender Erkenntnis gekommen:
|
| Dienstag, 16. April 2024 | Kapitel 1.5: Monotone Schaltkreise für Majority. Einen naiven,
der ausnutzt, dass
\begin{align*}
\sum_{i=1}^n x_i \geq a \Longleftrightarrow \exists 0 \leq b \leq a:
\sum_{j=1}^{\floor{n/2}} x_j \geq b \wedge
\sum_{k=\floor{n/2}+1}^b x_k \geq a-b \ .
\end{align*}
Der Schaltkreis hat aber leider Tiefe $\Theta(\log^2 n)$ und superpolynomielle Größe.
Valiants randomisierte Konstruktion. Rekursive randomisierte Majority-Konstruktion. Analyse, wie die Erfolgswahrscheinlichkeit ansteigt. Zum Schluss Union-Bound. |
| Mittwoch, 10. April 2024 | Kapitel 1.5: Schaltkreise für Majority. Tiefe $O(\log n)$ und Größe $O(n)$ mit dem 3-for-2-Trick. Einführung in monotone Schaltkreise (Kapitel 1.4). Rekursive Top-Down-Konstruktion. |
| Dienstag, 9. April 2024 | Kapitel 1.3: Binäraddierer. Effiziente Carry-Lookahead-Konstruktion mit Hilfe der Binärintervalle. |
| Mittwoch, 3. April 2024 | Boolesche Schaltkreise. Tiefe, Größe, Fan-in. Wahrheitstabellen. Jede Boolesche Funktion hat einen Booleschen Schaltkreis. |
| Dienstag, 2. April 2024 | Begrüßung, Vorstellung, Übersicht. Zum Schluss das Spiel Nim und die optimale Strategie. |
