sync

26 files changed, 1341 insertions, 39 deletions

diff --git a/notes/algo/main.pdf b/notes/algo/main.pdf
deleted file mode 100644
index 857e3e3..0000000
--- a/notes/algo/main.pdf
+++ /dev/null
diff --git a/notes/mathe2/exam.pdf b/notes/mathe2/exam.pdf
new file mode 100644
index 0000000..222c5d6
--- /dev/null
+++ b/notes/mathe2/exam.pdf
diff --git a/notes/mathe2/examtitle.tex b/notes/mathe2/examtitle.tex
index 5419f39..0c648a8 100644
--- a/notes/mathe2/examtitle.tex
+++ b/notes/mathe2/examtitle.tex
@@ -9,10 +9,6 @@
 		\textbf{Marvin Borner}
 
 		\vfill
-		\includegraphics[width=0.4\textwidth]{ochs_logo}\\
-		\vfill
-
-		\includegraphics[width=0.4\textwidth]{uni_logo}\\
 		Sommersemester 2022
 	\end{center}
 \end{titlepage}
diff --git a/notes/mathe2/main.pdf b/notes/mathe2/main.pdf
index 7f7ad91..f4af5d6 100644
--- a/notes/mathe2/main.pdf
+++ b/notes/mathe2/main.pdf
diff --git a/notes/mathe2/title.tex b/notes/mathe2/title.tex
index 2a33392..d06190d 100644
--- a/notes/mathe2/title.tex
+++ b/notes/mathe2/title.tex
@@ -9,15 +9,9 @@
 		\textbf{Marvin Borner}
 
 		\vfill
-		\includegraphics[width=0.4\textwidth]{ochs_logo}\\
-		\vfill
 
 		Vorlesung gehalten von\\
-		\textbf{Peter Ochs}
-
-		\vspace{0.8cm}
-
-		\includegraphics[width=0.4\textwidth]{uni_logo}\\
+		\textbf{Peter Ochs}\\
 		Sommersemester 2022
 	\end{center}
 \end{titlepage}
diff --git a/notes/mathe3/exam.md b/notes/mathe3/exam.md
new file mode 100644
index 0000000..87c1539
--- /dev/null
+++ b/notes/mathe3/exam.md
@@ -0,0 +1,345 @@
+---
+author: Marvin Borner
+date: "`\\today`{=tex}"
+lang: de-DE
+pandoc-latex-environment:
+  bem-box:
+  - bem
+  bsp-box:
+  - bsp
+  proof-box:
+  - proof
+  visu-box:
+  - visu
+toc-title: Inhalt
+---
+
+```{=tex}
+\newpage
+```
+# Sinnvolle Rechenregeln
+
+## Potenzregeln
+
+-   $a^n\cdot a^m=a^{n+m}$
+-   $a^n\cdot b^n=(a\cdot b)^n$
+-   $(a^n)^m=a^{n\cdot m}$
+-   $\frac{a^n}{b^n}=\left(\frac{a}{b}\right)^n$
+-   $\frac{a^n}{b^m}=a^{n-m}$
+
+## Toll
+
+-   $\sin^2(x)+\cos^2(x)=1$
+
+# Euklidischer Algorithmus
+
+Zur Berechnung des ggT.
+
+::: bsp
+Berechnung von $\ggT(48,-30):$
+`\begin{align*}48&=-1\cdot-30+18\\-30&=-2\cdot18+6\\18&=3\cdot6+0\end{align*}`{=tex}
+
+$\ggT(48,-30)=6$
+:::
+
+TODO: kgV mit Primfaktorzerlegung
+
+# Erweiterter Euklidischer Algorithmus
+
+Zur Berechnung von $s,t$, da:
+$$0\ne a,b\in\Z\implies\exists s,t\in\Z:\ggT(a,b)=sa+tb$$ ggT
+gleichsetzen, rückwärts einsetzen und je ausmultiplizieren.
+
+::: bsp
+Mit vorigem Beispiel:
+`\begin{align*}6&=-30+2\cdot18\\&=-30+2\cdot(48+1\cdot-30)\\&=2\cdot48+3\cdot-30\end{align*}`{=tex}
+:::
+
+TODO: Polynome.
+
+# Inverse prüfen
+
+$$a\in\Z_n\text{ invertierbar}\iff\ggT(a,n)=1$$ $a^{-1}$ ist dann $s$
+aus $sa+tn=1$ des EEA.
+
+# Zykel
+
+-   zyklische Gruppe, von $a$ erzeugt:
+    $\langle a\rangle\defeq\{a^n\mid n\in\Z\}$
+
+# Fundamentalsatz
+
+Mit $2\le n\in\N$ gibt es endlich viele paarweise verschiedene
+$p_1,...,p_k\in\P$ und $e_1,...,e_k\in\N$, sodass
+$$n=p_1^{e_1}\cdot...\cdot p_k^{e_k}.$$
+
+# Chinesischer Restsatz
+
+Lösen von simultaner Kongruenz.
+
+TODO: Beispiel.
+
+# Reduzibilität
+
+-   TODO: Nullstellen und so
+-   TODO: Mit Primzahlen ez
+
+# Lösen von $a^b\pmod{n}$
+
+-   falls $n$ groß: Primfaktorzerlegung von $n$ und für jeden Faktor
+    durchführen.
+-   Modulo in Potenzen aufnehmen (Trick: $2\pmod{3}=-1$)
+-   Satz von Euler: $a^{\varphi(n)}\equiv1\pmod{n}$
+-   sonst schlau Potenzregeln anwenden
+
+# Eulersche $\varphi$-Funktion
+
+-   $\varphi(p)=p-1$ für $p\in\P$
+-   $\varphi(M)=m_1\cdot...\cdot m_n$ mit $m_i\in\N$ paarweise
+    teilerfremd (bspw. über chinesischen Restsatz)
+-   $\varphi(M)=(p_1-1)p_1^{a_1-1}\cdot...\cdot(p_k-1)p_k^{a_k-1}$, mit
+    Primfaktorzerlegung $M=p_1^{a_1}\cdot...\cdot p_k^{a_k}$
+
+::: bsp
+$\varphi(100)=\varphi(4\cdot5^2)=\varphi(4)\cdot\varphi(5^2)=2\cdot(5-1)\cdot5^{2-1}=40$
+:::
+
+# RSA-Verfahren
+
+Bob (Schlüsselerzeugung)
+
+1.  wählt zwei große $p,q\in\P: p\ne q$ und bildet $n=pq$
+2.  berechnet $\varphi(n)=(p-1)(q-1)$
+3.  wählt $e$ teilerfremd zu $\varphi(n)$
+4.  bestimmt $0<d<\varphi(n)$ mit $e\cdot d\pmod{\varphi(n)}=1$.
+    Verwendet dazu EEA: $ed\pmod{\varphi(n)}$
+5.  Public key: $(e,n)$. Private key: d
+
+Alice (Verschlüsselung)
+
+1.  kodiert Nachricht als Zahl und zerlegt sie anschließend in Blöcke
+    gleicher Länge, sodass jeder Block $m_i$ als Zahl $0\le m_i<n$ ist.
+    Blöcke werden einzeln verschlüsselt. Sei $m$ ein solcher Block.
+2.  berechnet $c=m^e\pmod{n}$
+3.  sendet $c$ an Bob.
+
+Bob (Entschlüsselung)
+
+1.  berechnet $c^d\pmod{n}=m$ für alle Blöcke
+
+::: bsp
+Gegeben $(n,e)=(33,3)$ public key
+
+1.  Verschlüsseln Sie die Nachricht $m=6$.`\newline`{=tex}
+    $c=m^e\pmod{n}=6^3\pmod{33}=3\cdot 6=18$
+2.  Faktorisieren Sie $n=33$, berechnen Sie $\varphi(n)$ und
+    $d$.`\newline`{=tex} $\varphi(n)=2\cdot10=20$, $ed\pmod{20=1}$. Man
+    erkennt $d=7$.
+3.  Entschlüsseln Sie die Nachricht $c=2$:
+    $m=c^d\pmod{n}=2^7\pmod{33}=2^5\cdot2^2\pmod{33}=-4\pmod{33}=29$.
+:::
+
+# Konvergenz
+
+Sei $(x_k)_{k\in\N}$ eine Folge im $\R^n$. $(x_k)_{k\in\N}$ konvergiert
+gegen $a\in\R^n$ ($x_k\to a$ oder $\lim_{k\to\infty}x_k=a$) wenn gilt
+$$\forall\varepsilon>0\ \exists N\in\N\ \forall k\ge N:\|x_k-a\|<\varepsilon.$$
+
+# Eigenschaften von Mengen
+
+-   Sei $x_0\in\R^n,\ \varepsilon>0$.
+    $K_\varepsilon(x_0)=\{x\in\R^n\mid\|x-x_0\|<\varepsilon\}$ heißt
+    offene $\varepsilon$-Kugel um $x_0$.
+-   $D\subseteq\R^n$ **beschränkt**
+    $\defiff\exists K>0:\|x\|<K\quad\forall x\in D$
+-   $U\subseteq\R^n$ **offen**
+    $\defiff\forall x\in U\exists\varepsilon>0:K_\varepsilon(x)\subseteq U$
+-   $A\subseteq\R^n$ **abgeschlossen** $\defiff A^C=\R^n\setminus A$
+    offen
+-   Sei $(x_k)$ Folge in $A\subseteq\R^n$ mit Grenzwert $a\in\R^n$. $A$
+    **abgeschlossen** $\iff a\in A$.
+-   $x\in\R^n$ Randpunkt von
+    $D\subseteq\R^n\defiff K_\varepsilon(x)\cap D\ne\emptyset$ und
+    $K_\varepsilon(x)\cap D^C\ne\emptyset\quad\forall\varepsilon>0$.
+-   $\partial D$ ist die (abgeschlossene) Menge aller Randpunkte von
+    $D$.
+-   $D\subseteq\R^n$ **kompakt** $\defiff$ Jede Folge in $D$ besitzt
+    eine in $D$ konvergente Teilfolge.
+-   $D\subseteq\R^n$ **kompakt** $\iff D$ beschränkt und abgeschlossen.
+-   $\bar{D}\defeq D\cup\partial D$ ist abgeschlossen und heißt
+    **Abschluss** von $D$.
+-   $\mathring{D}\defeq D\setminus\partial D$ ist offen und heißt
+    **Innneres** von $D$.
+
+# Stetigkeit
+
+Sei $f: D\subset\R^n\to\R^m$.
+
+-   $f$ stetig in $a\in D\defiff\lim_{x\to a}f(x)=f(a)$
+-   $f$ stetig auf $D\defiff f\text{ stetig in }a\quad\forall a\in D$
+
+Mit $f: D\subseteq\R^n\to\R^n, v\subseteq f(0)$, $V$ offen:
+$$f\text{ stetig}\iff f^{-1}(V)\text{ offen.}$$
+
+TODO: Stetige Fortsetzbarkeit
+
+## Polarkoordinaten
+
+-   $x=r\cdot\cos(\alpha)$
+-   $y=r\cdot\sin(\alpha)$
+-   statt $(x,y)$ $(r,\alpha)$ gegen $a$ laufen lassen (TODO!)
+
+## Prüfen
+
+-   In Punkt: $\lim_{v\to v_0} f(v)=f(v_0)$
+    -   bspw. mit Polarkoordinaten
+    -   oder mit
+        $0\le|f(x,y)|\le ... \implies \lim_{(x,y)\to(0,0)}f(x,y)=0$
+        -   bspw. x aus Nenner nehmen
+
+# Weierstraß Minimax-Theorem
+
+$f:D\subseteq\R^n\to\R$ stetig, $D$ kompakt.
+
+$\implies\exists x_\star,x^\star\in D: \underbrace{f(x_\star)}_\mathrm{min}\le f(x)\le\underbrace{f(x^\star)}_\mathrm{max}\quad\forall x\in D$
+
+::: bsp
+$f:\R^2\to\R$, $f(x,y)=xy$
+
+$S=\left\{\begin{pmatrix}x\\y\end{pmatrix}\in\R^2\mid x^2+y^2=1\right\}$
+
+$\implies f$ hat Maximum und Minimum auf $S$
+:::
+
+# TODO: Zeug?
+
+# Differenziation
+
+Sei $D\subseteq\R^n$ offen, $f:D\to\R^m$, $f(x)=(f_1(x),...,f_m(x))$ und
+$a=(a_1,...,a_n)^\top\in D$.
+
+-   Jacobimatrix:
+    $$f'(a)\defeq\begin{pmatrix}\frac{\partial f_1}{\partial x_1}(a)&...&\frac{\partial f_1}{\partial x_n}(a)\\\frac{\partial f_m}{\partial x_1}(a)&...&\frac{\partial f_m}{\partial x_n}(a)\\\end{pmatrix}\in\M_{m,n}(\R)$$
+-   Gradient:
+    $$f'(a)^\top=\begin{pmatrix}\frac{\partial f}{\partial x_1}(a)\\\vdots\\\frac{\partial f}{\partial x_n}(a)\end{pmatrix}=:\nabla f(a)=\grad(f(a))\in\R^n$$
+
+Sei $D\subseteq\R^n$ offen, $a\in D$, $f: D\to\R^m$.
+
+-   $f$ heißt in $a\in D$ (total) differenzierbar, wenn $f$ geschrieben
+    werden kann als
+    $$f(x)=\underbrace{f(a)}_{\in\R^m}+\underbrace{A}_{\in\M_{m,n}(\R)}\cdot(\underbrace{x-a}_{\in\R^m})+\underbrace{R(x)}_{\in\R^m},$$
+    wobei $A\in\M_{m,n}(\R)$ und $R: D\to\R^m$ mit
+    $\lim_{x\to a}\frac{R(x)}{\|x-a\|}=0$
+-   $f$ heißt (total) differenzierbar, wenn in jedem Punkt von $D$
+    differenzierbar.
+
+Anderes:
+
+-   $f:D\subseteq\R^n\to\R^m$ differenzierbar in $a\in D$ (D offen)
+    $\implies f$ stetig in $a$.
+-   **Tangentialebene**: $g(x)=f(a)+f'(a)\cdot(x-a)$
+-   $f$ differenzierbar in $a\in D\iff f_i$ differenzierbar in
+    $a\in D\quad\forall i\in\{1,...,n\}$.
+
+## Prüfen
+
+-   ob in Punkt $p$ partiell differenzierbar: partielle Ableitungen
+    bilden
+    -   falls bspw. Fallunterscheidung und $(0,0)$-Punkt: $h$-Definition
+        für $x$/$y$ anwenden
+    -   Richtungsableitung: $f_v(x,y)=\frac{(x+hv_1,0+hv_2)-f(0,0)}{h}$
+-   total differenzierbar
+    -   je partiell ableiten und prüfen ob Ableitungen stetig
+    -   mit Richtungsleitung versuchen Gegenteil zu beweisen (TODO)
+
+# Ableitungsregeln
+
+-   $(g\circ f)'(a)=g'(f(a))\cdot f'(a)$
+-   $(f+g)'(a)=f'(a)+g'(a)$
+-   $(\lambda f)'(a)=\lambda f'(a)$
+-   $(f^\top g)'(a)=f(a)^\top g'(a)+g(a)^\top f'(a)$
+
+TODO: lhopital
+
+Anderes:
+
+-   $\left(\ln x\right)'=\frac 1 x$
+-   $\left(\frac gh\right)'=\frac{h\cdot g'-g\cdot h'}{h^2}$
+-   $\left(\frac{a}{x^k}\right)'=-\frac{ka}{x^{k+1}}$ bzw. unten
+    Kettenregel
+
+# Richtungsableitung
+
+Sei $D\subseteq\R^n$ offen, $f:D\to\R$, $v\in\R^n$ mit $\|v\|=1$.
+
+$f$ heißt in $a\in D$ differenzierbar in Richtung $v$, falls
+$\lim_{h\to0}\frac{f(a+hv)-f(a)}{h}$ exisitert. Der Grenzwert heißt
+Richtungsableitung von $f$ in Richtung $v$ in $a$,
+$\frac{\partial f}{\partial v}(a)$.
+
+# Satz von Schwarz
+
+TODO.
+
+# Definitheit
+
+1.  Partielle Ableitungen
+2.  Gradienten mit $0$ gleichsetzen
+3.  Hessematrix und Punkte einsetzen (falls $x$/$y$ vorhanden)
+4.  Über Eigenwerte oder Determinante bestimmen
+
+## Matrix
+
+Eine symmetrische Matrix $A\in\M_n(\R)$ ist
+
+-   positiv definit $\iff$ $\det(A_k)>0\quad\forall k\in\{1,...,n\}$
+-   negativ definit $\iff$
+    $\det(A_k)\begin{cases}<0&k\text{ ungerade}\\>0&k\text{ gerade}\end{cases}$
+    (-+-+..)
+
+TODO: über Eigenwerte
+
+# Extrema
+
+Sei $D\subseteq\R^n$ offen,
+$f\in\varphi^2(D,\R),\ a\in D,\ \nabla f(a)=0$.
+
+-   $H_f(a)$ positiv definit $\implies$ $a$ Stelle eines lokalen
+    Minimums.
+-   $H_f(a)$ negativ definit $\implies$ $a$ Stelle eines lokalen
+    Maximums.
+-   $H_f(a)$ indefinit $\implies$ $a$ ist Sattelpunkt
+-   Ist $H_f(a)$ positiv/negativ semidefinit, so ist keine Aussage
+    möglich.
+
+# Taylor
+
+-   Taylorpolynom: $T_n(x)=\sum_{k=0}^n\frac{f^{(k)}(x_0)}{k!}(x-x_0)^k$
+-   Satz: $f(x)=T_n(x)+R_n(x)$
+    -   $R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)^{n+1}$
+
+# Höhenlinien
+
+-   $f(x,y)=c$ setzen
+-   nach $y=...$ umformen
+-   entweder verschiedene $c$ einsetzen oder geg. $N_c(f)$
+
+# Implizite Funktionen
+
+TODO.
+
+# Umkehrfunktionen
+
+TODO.
+
+# Lagrange
+
+1.  Nebenbedingung mit $0$ gleichsetzen
+2.  Lagrange-Funktion, bspw.
+    $\mathcal{L}(x,y,\lambda)=f(x,y)+\lambda g(x,y)$ mit $g$
+    Nebenbedingung
+3.  Erste partielle Ableitungen der Lagrange Funktion
+    ($\mathcal{L}_\lambda=g$)
+4.  Ableitungen mit $0$ gleichsetzen und lösen (Additionsverfahren gut)
+5.  Mehrere Ergebnisse dann Extrempunkte
+6.  Definitheit überprüfen (geränderte Matrix TODO?)
diff --git a/notes/mathe3/exam.pdf b/notes/mathe3/exam.pdf
new file mode 100644
index 0000000..5a7079a
--- /dev/null
+++ b/notes/mathe3/exam.pdf
diff --git a/notes/mathe3/examtitle.tex b/notes/mathe3/examtitle.tex
new file mode 100644
index 0000000..cfeb5e4
--- /dev/null
+++ b/notes/mathe3/examtitle.tex
@@ -0,0 +1,16 @@
+\begin{titlepage}
+	\begin{center}
+		\vspace*{1cm}
+
+		{\huge\textbf{Mathematik für Informatik 3}}
+
+		\vspace{0.5cm}
+		{\Large Klausurvorbereitung}\\
+		\textbf{Marvin Borner}
+
+		\vfill
+		Wintersemester 2022/23
+	\end{center}
+\end{titlepage}
+
+\pagebreak\hspace{0pt}\vfill\begin{center}{\Large Dies ist meine WIP Zusammenfassung, welche hauptsächlich mir dienen soll. Ich schreibe außerdem ein inoffizielles Skript, welches auf \url{https://marvinborner.de/mathe3.pdf} zu finden ist.}\end{center}\vfill\hspace{0pt}\pagebreak
diff --git a/notes/mathe3/main.md b/notes/mathe3/main.md
index f695fbd..2845136 100644
--- a/notes/mathe3/main.md
+++ b/notes/mathe3/main.md
@@ -544,7 +544,7 @@ Seien $(R, +, \cdot)$ und $(R',\oplus,\odot)$ Ringe.
 
 ::: bsp
 1.  Boolesche Algebra:
-    $$(\{f,w\}, \texttt{XOR}, 1)\cong ({0,1},\oplus,\odot)$$
+    $$(\{f,w\}, \texttt{XOR}, 1)\cong (\{0,1\},\oplus,\odot)$$
     $\psi(f)=0,\psi(w)=1$. $\psi$ Isomorphismus, falls
     Verknüpfungstafeln übereinstimmen
     `\begin{center}\begin{tabular}{c||c c}\texttt{XOR}&f&w\\\hline f&f&w\\w&w&f\end{tabular}\end{center}`{=tex}
@@ -1165,7 +1165,7 @@ beschränkt.
 
 $f:D\subseteq\R^n\to\R$ stetig, $D$ kompakt.
 
-$\implies\exists x_\star,x^\star\in D: \underbrace{f(x_\star)}_\mathrm{min}\le f(x)\le f(x^\star)_\mathrm{max}\quad\forall x\in D$
+$\implies\exists x_\star,x^\star\in D: \underbrace{f(x_\star)}_\mathrm{min}\le f(x)\le\underbrace{f(x^\star)}_\mathrm{max}\quad\forall x\in D$
 
 ::: proof
 ```{=tex}
@@ -1257,7 +1257,7 @@ $a=(a_1,...,a_n)^\top\in D$.
     $$f'(a)^\top=\begin{pmatrix}\frac{\partial f}{\partial x_1}(a)\\\vdots\\\frac{\partial f}{\partial x_n}(a)\end{pmatrix}=:\nabla f(a)=\grad(f(a))\in\R^n$$
     als Gradienten von $f$ in $a$.
 
-## Geometriche Deutung der partiellen Ableitung
+## Geometrische Deutung der partiellen Ableitung
 
 Sei $f:\R^2\to\R,\ a\in\R^2,\ a=\begin{pmatrix}a_1\\a_2\end{pmatrix}$.
 
@@ -1683,11 +1683,12 @@ $D\subseteq\R$ offen, $f:D\to\R$.
     in jedem Punkt von $D$ partiell differenzierbar ist und alle
     $\frac{\partial f}{\partial x_i}$ ($i\in\{1,...,n\}$) auf $D$ stetig
     sind
--   $f$ heißt 2-mal stetig differezierbar ($f\in\mathcal{C}^2(D)$), wenn
-    $f\in\mathcal{C}^1(D)$ und alle $\frac{\partial f}{\partial x_j}$
-    ($j\in\{1,...,n\}$) $\in\mathcal{C}^1(D)$. Die partielle Ableitung
-    von $\frac{\partial f}{\partial x_j}$ nach $x_k$ wird mit
-    $\frac{\partial^2f}{\partial x_2\partial x_j}$ bezeichnet (partielle
+-   $f$ heißt 2-mal stetig differenzierbar ($f\in\mathcal{C}^2(D)$),
+    wenn $f\in\mathcal{C}^1(D)$ und alle
+    $\frac{\partial f}{\partial x_j}$ ($j\in\{1,...,n\}$)
+    $\in\mathcal{C}^1(D)$. Die partielle Ableitung von
+    $\frac{\partial f}{\partial x_j}$ nach $x_k$ wird mit
+    $\frac{\partial^2f}{\partial x_k\partial x_j}$ bezeichnet (partielle
     Ableitung zweiter Ordnung). Für $k=j$ schreibt man kurz
     $\frac{\partial^2f}{\partial x_j^2}$.
 -   Analog ist $f$ $s$-mal stetig differenzierbar
diff --git a/notes/mathe3/main.pdf b/notes/mathe3/main.pdf
index 4b42dd9..abcbb8d 100644
--- a/notes/mathe3/main.pdf
+++ b/notes/mathe3/main.pdf
diff --git a/notes/mathe3/makefile b/notes/mathe3/makefile
index 36d0026..bfe8b0d 100644
--- a/notes/mathe3/makefile
+++ b/notes/mathe3/makefile
@@ -15,6 +15,14 @@ part:
 	@progress 1 pdflatex
 	@echo done.
 
+exam:
+	@mkdir -p build/
+	@pandoc exam.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/exam.tex --pdf-engine-opt=-shell-escape -H header.tex -B examtitle.tex >/dev/null
+	@(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/exam.tex | grep '^!.*' -A200 --color=always ||true) &
+	@progress 1 pdflatex
+	@cp build/exam.pdf . &>/dev/null
+	@echo done.
+
 clean:
 	@$(RM) -rf build
 
diff --git a/notes/mathe3/title.tex b/notes/mathe3/title.tex
index a10f295..8b583a0 100644
--- a/notes/mathe3/title.tex
+++ b/notes/mathe3/title.tex
@@ -9,17 +9,9 @@
 		\textbf{Marvin Borner}
 
 		\vfill
-		{\Large \textbf{WARNUNG WIP: Fehler zu erwarten!}\\\textbf{Stand: \today, \currenttime}}\\
-		{\large Bitte meldet euch bei mir, falls ihr Fehler findet.}
-		% \includegraphics[width=0.4\textwidth]{zeller_logo}\\
-		\vfill
 
 		Vorlesung gehalten von\\
-		\textbf{Rüdiger Zeller}
-
-		\vspace{0.8cm}
-
-		\includegraphics[width=0.4\textwidth]{uni_logo}\\
+		\textbf{Rüdiger Zeller}\\
 		Wintersemester 2022/23
 	\end{center}
 \end{titlepage}
diff --git a/notes/theo1/exam.md b/notes/theo1/exam.md
new file mode 100644
index 0000000..0b93ea1
--- /dev/null
+++ b/notes/theo1/exam.md
@@ -0,0 +1,335 @@
+---
+author: Marvin Borner
+date: "`\\today`{=tex}"
+lang: de-DE
+pandoc-latex-environment:
+  bem-box:
+  - bem
+  bsp-box:
+  - bsp
+  prob-box:
+  - prob
+  proof-box:
+  - proof
+  visu-box:
+  - visu
+toc-title: Inhalt
+---
+
+```{=tex}
+\newpage
+\renewcommand\O{\mathcal{O}} % IDK WHY
+```
+# Tricks
+
+-   $\log_a(x)=\frac{\log_b(x)}{\log_b(a)}$
+
+# Big-O-Notation
+
+-   $f\in\O(g)$: $f\le g$
+-   $f\in\Omega(g)$: $f\ge g$
+-   $f\in o(g)$: $f<g$
+-   $f\in\omega(g)$: $f>g$
+-   $f\in\Theta(g)$: $f=g$
+
+# Master Theorem
+
+Mit $T(n)=aT(\lceil n/b\rceil)+\O(n^d)$ für $a>0$, $b>1$ und $d\ge0$,
+ist
+$$T(n)=\begin{cases}\O(n^d)&d>\log_ba\\\O(n^d\log_n)&d=log_ba\\\O(n^{log_ba})&d<\log_ba\end{cases}$$
+
+# Bäume
+
+-   Binary Höhe: $\log n$; Binary Anzahl: $\sum_{i=0}^h2^i=2^{h+1}-1$
+-   Heap:
+    -   `Heapify`: rekursiv swap bis Bedingung nicht verletzt:
+        $\O(\log n)$
+    -   `Decrease`: erniedrigen, dann heapify auf node: $\O(\log n)$
+    -   `Increase`: erhöhen, dann rekursiv mit parent swappen bis
+        bedingung nicht verletzt: $\O(\log n)$
+    -   `ExtractMax`: Wurzel mit letzter leaf ersetzen, `heapify(root)`:
+        $\O(\log n)$
+    -   `Insert`: Einfügen an nächster Stelle mit $-\infty$,
+        `Increase(x)` : $\O(\log n)$
+    -   `Build`: Array irgendwie als Baum schreiben, `heapify` auf jedem
+        Knoten von unten nach oben: $\O(n)$
+-   Priority queue: Als heap analog
+
+# Hashing
+
+-   irreversible Reduzierung des Universums
+
+# Graphen
+
+-   Adjazenzmatrix: $a_{ij}=1$ bzw Gewicht wenn Kante von $i$ nach $j$
+    -   für dense
+-   Adjazenzliste: array von Knoten mit Listen von ausgehenden Kanten
+    -   für sparse
+-   Sources: längste finishing time von DFS
+-   Sinks: alle Kanten umdrehen, dann sources finden
+-   SCC: DFS auf umgedrehtem Graph, startend bei ursprünglicher source
+    (`\textrightarrow`{=tex} SCC). Weiter bei restlichen Knoten (nach
+    absteigenden finishing times): $\O(V + E)$
+-   Cycles: durch DFS wenn visited nochmal visited wird
+-   Topological sort: no cycles; DFS und Knoten nach absteigenden
+    finishing times sortieren
+
+## DFS
+
+-   $\O(V+E)$ bzw. $\O(V^2)$ für Matrix
+
+TODO: Anleitung schriftlich
+
+## BFS
+
+-   gleich wie DFS nur queue statt stack
+-   $\O(V+E)$ bzw. $\O(V^2)$ für Matrix
+-   gut für shortest path, einfach jedes Mal distance updaten
+
+## Relaxation
+
+-   anfangs alle $\infty$ außer Start
+
+```{=tex}
+\begin{lstlisting}
+function Relax(u,v)
+    if v.dist > u.dist + w(u, v)
+      v.dist = u.dist + w(u,v)
+      v.$\pi$ = u
+\end{lstlisting}
+```
+## Bellman-Ford
+
+-   $(|V|-1)$-mal alle Kanten relaxen, dann noch einmal alle relaxen
+    (wenn sich was ändert, dann cycle): $\O(V\cdot E)$
+-   in undirected muss in beide Richtungen relaxed werden
+-   blöd für negative Gewichte
+-   geht auch dezentral/asynchron, damit einzelne Knoten sich updaten
+    können
+
+## Dijkstra
+
+-   gierig: nimmt einfach immer die nächstbeste Kante
+-   $\O((V+E)\log V)$ mit min-priority Queues
+-   für PPSP einfach stoppen wenn Knoten erreicht wurde (oder auch
+    bidirektional, dann besser)
+
+## Floyd-Warshall
+
+-   besser für APSP (da Bellmand/Dijkstra je für jeden Vertex ausführen
+    müssten: $\O(V^2\cdot E...)$)
+-   dreimal `for` für Matrix
+
+## A\*
+
+-   wie Dijkstra, nur mit nächstem $d(s,u)+w(u,v)+\pi(v)$ statt
+    $d(s,u)+w(u,v)$ (Heuristik)
+
+## Kruskal
+
+-   für MST
+-   Kanten aufsteigend sortieren; je nächste Kante zu leerem Graph
+    hinzufügen solange kein Zykel entsteht
+-   oder voll toll mit union-find: $\O(E\log V)$
+    -   weil dann Zykelerkennung ez geht und so
+
+## Prim
+
+-   für MST
+-   bei random starten, dann immer nächstbeste Kante hinzufügen (Kreis
+    erweitert sich)
+-   mit priority queue $\O(E\log V)$
+
+# Sortierung
+
+-   **stabil**: wenn gleicher Wert am Ende gleichen Index
+    -   selection: stabil
+    -   insertion: stabil
+    -   heap: instabil
+    -   merge: stabil
+    -   quick: stabil (out-of-place)
+    -   counting: stabil (mit Listen als buckets)
+-   Annahme: konstante Vergleiche
+
+## Selection
+
+-   je kleinstes Element entfernen und in Ausgabe pushen: $\O(n^2)$
+
+## Insertion
+
+-   je Element nach links bewegen bis es kleiner-gleich ist. Dann für
+    nächstes wiederholen: $\O(n^2)$ oder best-case $\O(n)$
+
+## Bubble
+
+-   Paare von hinten durchgehen, je swappen wenn größer: $\O(n^2)$ oder
+    best-case $\O(n)$
+
+## Merge
+
+-   List halbieren, rekursiv beide Listenhälften merge-sorten und
+    mergen: $\O(n\log n)$ weil Master-Theorem
+-   merge sollte nicht kopieren (also doof in funktionalen Sprachen)
+
+## Heap
+
+-   Heap aus Zahlen erstellen, je `ExtractMax` anwenden: $\O(n\log n)$
+    worst und best
+
+## Quick
+
+-   je Pivotelement (e.g. Median) wählen, dann kleiner/größer
+    Pivot-Hälfte rekursiv zusammenfügen: $\O(n^2)$ oder best-case
+    $\O(n)$
+-   durch random Pivotelement ist worst-case $\O(n\log n)$ zu erwarten
+
+## Counting
+
+-   array mit buckets, sortieren nach Schlüsselwert; am Ende concat
+    ausgeben: $\O(K+n)$ - besser als vergleichsbasierte Algorithmen
+
+## Radix
+
+-   Zahlen werden als Strings vom Ende aus durch Counting-Sort sortiert:
+    $\O(d(n+K))$ mit $d$ als Anzahl der Ziffern
+-   block-based: je nochmal $x$ buckets
+
+## Bucket
+
+-   Werte aus Intervall $[i/n,(i+1)/n[$ werden bucket $i$ zugeordnet;
+    dann jeden Bucket mit Insertion sortieren: $\O(n)$ oder worst-case
+    $\O(n\log n)$
+
+# Suchen
+
+## Binary
+
+-   (Array sortiert); `A[n/2]` betrachten, entsprechend in
+    linker/rechter Hälfte weitersuchen: $\O(\log n)$
+
+## Exponential
+
+-   Zweierpotenz-Indizes durchgehen, bei $q<2^i$ binary auf $2^{i-1}$
+    und $2^i$
+
+## Binary tree
+
+-   links $\le$ parent, rechts $\ge$ parent: $\O(\log n)$
+-   rekursiver tree-walk für sort: $\O(n)$
+-   insert wird obv sehr unbalanced: $\O(n)$
+-   delete einfach nächstbestes passendes Element als Substitution
+    suchen: $\O(n)$
+
+### AVL
+
+-   LeftRotation/RightRotation für balancing von Subbäumen (TODO?)
+-   insert/delete: $\O(\log n)$ da balancing $\O(1)$
+
+# Gier
+
+-   einfach immer das nächstbeste nehmen (Heuristiken)
+-   häufig nicht optimal, dafür effizient
+    -   bei Knapsack bspw. doof
+    -   für Dijkstra, Kruskal, Prim aber auch global optimal
+
+## Lokale Suche
+
+-   bei zufälligem Wert starten, lokale Nachbarschaft betrachten.
+    Aufhören, sobald keine bessere Lösung in lokaler Nachbarschaft ist
+-   mit unterschiedlichen Startwerten wiederholen
+-   bei TSP durch swappen eigentlich not too bad (also für TSP obv)
+
+### Simulated annealing
+
+-   am Anfang zu höherer Wahrscheinlichkeit auch schlechtere Lösungen in
+    lokaler Nachbarschaft betrachten (in Abhängigkeit der Differenz)
+-   Wahrscheinlichkeit ist je $e^{-\Delta/T}$
+-   eigentlich ganz cool, aber T muss halt passend gewählt werden
+
+# Dynamik
+
+-   Lösen von Problemen durch Kombination der Teilproblemlösungen
+    (bottom-up vs. top-down)
+
+## Knapsack
+
+-   Dieb\*in will möglichst viel stehlen hehe
+-   Fälle: Objekt $j$ wird nicht eingepackt: $K(V,j)=K(V,j-1)$
+-   Fälle: Objekt $j$ wird eingepackt: $K(V,j)=K(V-vol_j,j-1)+val_j$
+-   bottom-up Array konstruieren mit beiden Fällen und je Maximum nehmen
+-   top-down bspw. durch rekursive Memoization
+-   damit $\O(n\cdot V_\text{total})$ (abhängig von
+    $V\implies\text{Skalierung siehe Approximationsalgorithmen}$)
+
+# Backtracking
+
+-   bspw. toll bei Queen's problem
+-   einfach backtracken im Lösungsbaum wenn Teillösung ungültig
+
+# Branch and Bound
+
+-   bound: untere Schranke bestimmen und mit aktueller Lösung
+    vergleichen
+-   bei TSP ist die untere Schranke bspw. das Gewicht des MST
+-   verbessert nur durchschittliche Laufzeit
+
+# Approximationsalgorithmen
+
+-   Algorithmus finden, der der tatsächlichen Lösung möglichst nahe
+    kommt
+-   Güte von Approximation $A$ mit Instanz $I$ entsprechend
+    $\alpha_A=\max_I\frac{\mathrm A(I)}{\mathrm{OPT}(I)}$
+-   Beispiele
+    -   Set/Vertex cover
+    -   TSP: Zusätzliche Annahme: Dreiecksungleichung. Dann ist lower
+        bound MST und upper bound zweifacher Graph Durchlauf unter
+        Verwendung der Dreiecksungleichung
+        -   damit $\alpha_A\le2$
+    -   Knapsack: Volumina skalieren und inten - Rundungsfehler ergibt
+        entsprechend $\alpha_A$
+
+# Line
+
+-   $\sigma=\sigma_1,...,\sigma_m$ Sequenz unbekannter $\sigma$
+-   `\texttt{opt($\sigma$})`{=tex} sind Kosten des besten offline
+    Algorithmus
+-   `\texttt{A($\sigma$})`{=tex} sind Kosten des online Algorithmus für
+    $\sigma$
+-   **c-kompetitiv**, wenn für $\sigma$ gilt
+    $A(\sigma)\le c\mathrm{opt}(\sigma)$
+
+## Buy-or-rent
+
+-   Wie lange Skifahren? Leihen $50$, kaufen $500$ Euro.
+-   $\sigma_i=1\implies\text{skifahren}$,
+    $\sigma_i=0\implies\text{nicht skifahren}$
+-   $\frac{A(\sigma)}{c\mathrm{opt}(\sigma)}=\frac{50(t-1)+500}{50t}$
+    minimal für $t=10$
+    -   also Ski kaufen nach 10 Tagen
+
+## List-update
+
+-   move-to-front ist am besten
+
+## Dating
+
+-   wie viele Dates bevor Entscheidung?
+-   Kalibrierungsphase mit $t$ Personen; in Phase 2 entscheiden sobald
+    jemand besser als alle aus Phase 1
+-   blabla $t=\frac ne$ also mit ca. 1/3 kalibrieren
+
+# Closest pair of points
+
+-   brute-force ($\O(n^2)$) und sortieren ($\O(n\log n)$) beides nicht
+    optimal
+-   divide and conquer: Raum rekursiv aufteilen, Abstand closest pair je
+    Seite: $\O(n\log n)$
+    -   problem in der Mitte lässt sich 2d elegant lösen
+-   randomisierte Lößung: $\sqrt{n}$ zufällige Punkte und paarweise
+    Abstände
+    -   kleinster Abstand ist $\delta$
+    -   Hashing, Würfel, blabla effizient (TODO?)
+
+# KD-Bäume
+
+TODO.
diff --git a/notes/theo1/exam.pdf b/notes/theo1/exam.pdf
new file mode 100644
index 0000000..04de475
--- /dev/null
+++ b/notes/theo1/exam.pdf
diff --git a/notes/theo1/examtitle.tex b/notes/theo1/examtitle.tex
new file mode 100644
index 0000000..6d77854
--- /dev/null
+++ b/notes/theo1/examtitle.tex
@@ -0,0 +1,16 @@
+\begin{titlepage}
+	\begin{center}
+		\vspace*{1cm}
+
+		{\huge\textbf{Theoretische Informatik 1\bigskip\\Algorithmen und Datenstrukturen}}
+
+		\vspace{0.5cm}
+		{\Large Klausurvorbereitung}\\
+		\textbf{Marvin Borner}
+
+		\vfill
+		Wintersemester 2022/23
+	\end{center}
+\end{titlepage}
+
+\pagebreak\hspace{0pt}\vfill\begin{center}{\Large Dies ist meine WIP Zusammenfassung, welche hauptsächlich mir dienen soll. Ich schreibe außerdem ein inoffizielles Skript, welches auf \url{https://marvinborner.de/algo.pdf} zu finden ist.}\end{center}\vfill\hspace{0pt}\pagebreak
diff --git a/notes/algo/header.tex b/notes/theo1/header.tex
index 3709c26..3709c26 100644
--- a/notes/algo/header.tex
+++ b/notes/theo1/header.tex
diff --git a/notes/algo/main.md b/notes/theo1/main.md
index 88b3e3c..54809bf 100644
--- a/notes/algo/main.md
+++ b/notes/theo1/main.md
@@ -1225,4 +1225,4 @@ function KruskalNaiveMST(V,E,W)
 
 -   sorting $\O(|E|\log|E|)$
 -   check for cycle: $\O(|E|\cdot?)$
-- total: $\O(|E|\log|E|+|E|\cdot?)$
+-   total: $\O(|E|\log|E|+|E|\cdot?)$
diff --git a/notes/theo1/main.pdf b/notes/theo1/main.pdf
new file mode 100644
index 0000000..a61d262
--- /dev/null
+++ b/notes/theo1/main.pdf
diff --git a/notes/theo1/makefile b/notes/theo1/makefile
new file mode 100644
index 0000000..2cacf25
--- /dev/null
+++ b/notes/theo1/makefile
@@ -0,0 +1,31 @@
+VIEW = zathura
+
+all:
+	@mkdir -p build/
+	@pandoc main.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex -B title.tex >/dev/null
+	@(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) &
+	@progress 3 pdflatex
+	@cp build/main.pdf . &>/dev/null
+	@echo done.
+
+part:
+	@mkdir -p build/
+	@pandoc part.md --filter pandoc-latex-environment -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex >/dev/null
+	@(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) &
+	@progress 1 pdflatex
+	@echo done.
+
+exam:
+	@mkdir -p build/
+	@pandoc exam.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/exam.tex --pdf-engine-opt=-shell-escape -H header.tex -B examtitle.tex >/dev/null
+	@(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/exam.tex | grep '^!.*' -A200 --color=always ||true) &
+	@progress 1 pdflatex
+	@cp build/exam.pdf . &>/dev/null
+	@echo done.
+
+clean:
+	@$(RM) -rf build
+
+run: all
+	@clear
+	@$(VIEW) build/main.pdf
diff --git a/notes/algo/title.tex b/notes/theo1/title.tex
index 1b73738..4ed6e46 100644
--- a/notes/algo/title.tex
+++ b/notes/theo1/title.tex
@@ -8,16 +8,10 @@
 		{\Large Inofficial lecture notes}\\
 		\textbf{Marvin Borner}
 
-		% \vfill
-		% \includegraphics[width=0.4\textwidth]{zeller_logo}\\
 		\vfill
 
 		Vorlesung gehalten von\\
-		\textbf{Ulrike von Luxburg}
-
-		\vspace{0.8cm}
-
-		\includegraphics[width=0.4\textwidth]{uni_logo}\\
+		\textbf{Ulrike von Luxburg}\\
 		Wintersemester 2022/23
 	\end{center}
 \end{titlepage}
diff --git a/notes/theo2/header.tex b/notes/theo2/header.tex
new file mode 100644
index 0000000..959df6a
--- /dev/null
+++ b/notes/theo2/header.tex
@@ -0,0 +1,73 @@
+\usepackage{braket}
+\usepackage{polynom}
+\usepackage{amsthm}
+\usepackage{csquotes}
+\usepackage{svg}
+\usepackage{environ}
+\usepackage{mathtools}
+\usepackage{tikz,pgfplots}
+\usepackage{titleps}
+\usepackage{tcolorbox}
+\usepackage{enumitem}
+\usepackage{listings}
+\usepackage{soul}
+\usepackage{forest}
+\usepackage{datetime}
+
+\pgfplotsset{width=10cm,compat=1.15}
+\usepgfplotslibrary{external}
+\usetikzlibrary{arrows,automata,positioning}
+%\usetikzlibrary{calc,trees,positioning,arrows,arrows.meta,fit,shapes,chains,shapes.multipart}
+%\tikzexternalize
+\setcounter{MaxMatrixCols}{20}
+\graphicspath{{assets}}
+
+\newpagestyle{main}{\sethead{\toptitlemarks\thesection\quad\sectiontitle}{}{\thepage}\setheadrule{.4pt}}
+\pagestyle{main}
+
+\newtcolorbox{proof-box}{title=Beweis,colback=green!5!white,arc=0pt,outer arc=0pt,colframe=green!60!black}
+\newtcolorbox{bsp-box}{title=Beispiel,colback=orange!5!white,arc=0pt,outer arc=0pt,colframe=orange!60!black}
+\newtcolorbox{visu-box}{title=Visualisation,colback=cyan!5!white,arc=0pt,outer arc=0pt,colframe=cyan!60!black}
+\newtcolorbox{bem-box}{title=Bemerkung,colback=white,colbacktitle=white,coltitle=black,arc=0pt,outer arc=0pt,colframe=black}
+\newtcolorbox{defi-box}{title=Definition,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black}
+\newtcolorbox{satz-box}{title=Satz,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black}
+
+\newcommand\toprove{\textbf{Zu zeigen: }}
+
+\newcommand\defeq{\mathrel{\vcentcolon=}}
+\newcommand\defiff{\mathrel{\vcentcolon\Longleftrightarrow}}
+
+\newcommand\N{\mathbb{N}}
+\newcommand\R{\mathbb{R}}
+\newcommand\Z{\mathbb{Z}}
+\newcommand\Q{\mathbb{Q}}
+\newcommand\C{\mathbb{C}}
+\renewcommand\P{\mathbb{P}}
+\renewcommand\O{\mathcal{O}}
+\newcommand\pot{\mathcal{P}}
+\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}
+\newcommand{\bigcupdot}{\dot{\bigcup}}
+
+\DeclareMathOperator{\ggT}{ggT}
+\DeclareMathOperator{\kgV}{kgV}
+
+\newlist{abc}{enumerate}{10}
+\setlist[abc]{label=(\alph*)}
+
+\newlist{num}{enumerate}{10}
+\setlist[num]{label=\arabic*.}
+
+\newlist{rom}{enumerate}{10}
+\setlist[rom]{label=(\roman*)}
+
+\makeatletter
+\renewenvironment{proof}[1][\proofname] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse}
+\makeatother
+\def\qedsymbol{\sc q.e.d.} % hmm?
+
+\lstset{
+	basicstyle=\ttfamily,
+	escapeinside={(*@}{@*)},
+	numbers=left,
+	mathescape
+}
diff --git a/notes/theo2/main.md b/notes/theo2/main.md
new file mode 100644
index 0000000..64e7e06
--- /dev/null
+++ b/notes/theo2/main.md
@@ -0,0 +1,477 @@
+---
+author: Marvin Borner
+date: "`\\today`{=tex}"
+lang: de-DE
+pandoc-latex-environment:
+  bem-box:
+  - bem
+  bsp-box:
+  - bsp
+  defi-box:
+  - defi
+  proof-box:
+  - proof
+  satz-box:
+  - satz
+  visu-box:
+  - visu
+toc-title: Inhalt
+---
+
+```{=tex}
+\newpage
+\renewcommand\O{\mathcal{O}} % IDK WHY
+```
+# Reguläre Sprachen und endliche Automaten
+
+## Motivation
+
+-   Eingabe
+-   Verarbeitung (Berechnungen, Zustände)
+-   Ausgabe
+
+## Wörter und Sprachen
+
+::: defi
+Ein *Alphabet* $\Sigma$ sei eine nicht-leere, endliche Menge. Ein *Wort*
+$w$ ist entsprechend eine Folge von Elementen aus $\Sigma$.
+:::
+
+::: bsp
+-   $\Sigma=\{a,...,z\}$, $w=\text{luxburg}$, $|w|=7$
+:::
+
+::: defi
+$\Sigma^n$ ist die Menge aller Wörter der Länge $n$. Die *Kleene'sche
+Hülle* ist $\Sigma^*\defeq\bigcup_{n=0}^\infty\Sigma^n$.
+$\Sigma^+\defeq\bigcup_{n=1}^\infty\Sigma^n$.
+
+*Sprache $L$ über $\Sigma$* ist eine Teilmenge von $\Sigma^*$.
+:::
+
+::: defi
+Eine *Konkatenation* ist eine Aneinanderhängung zweier Wörter $u$ und
+$w$. Eine Konkatenation zweier *Sprachen* $L_1,L_2$ ist
+$L_1\circ L_2\defeq\{uw\mid u\in L_1,\ w\in L_2\}$. Die Kleene'sche
+Hülle einer Sprache $L$ ist dann
+$L^*\defeq\{\underbrace{x_1...x_k}_{\mathclap{\text{Konkatenation von $k$ Wörtern}}}\mid x_i\in L,\ k\in\N_0\}$.
+
+Eine $k$-fache Aneinanderhängung von Wörtern ist
+$w_k=\underbrace{w...w}_\text{$k$-mal}$.
+:::
+
+::: bsp
+-   $w=010$, $u=001$, $wu=\underbrace{010}_w \underbrace{001}_u$,
+    $uwu=\underbrace{001}_u \underbrace{010}_w \underbrace{001}_u$
+-   $w^3=010\ 010\ 010$
+:::
+
+::: bem
+Die Konkatenation auf $\Sigma^*$ hat die Eigenschaften:
+
+-   assoziativ: $a(bc)=(ab)c$
+-   nicht kommutativ: $ab\ne ba$
+-   neutrales Element $\varepsilon$: $\varepsilon a=a\varepsilon=a$
+-   ein inverses Element
+:::
+
+::: defi
+Ein Wort $x$ heißt *Teilwort* eines Wortes $y$, falls es Wörter $u$ und
+$v$ gibt, sodass $y=uxv$.
+
+-   Falls $u=\varepsilon$, $x$ *Präfix* von $y$
+-   Falls $v=\varepsilon$, $x$ *Suffix* von $y$
+:::
+
+::: bsp
+-   $01$ ist Teilwort von $0\textbf{01}11$
+-   $10$ ist Präfix von $\textbf{10}10011$
+-   $011$ ist Suffix von $10101110\textbf{011}$
+:::
+
+## Endlicher, deterministischer Automat
+
+::: defi
+Für einen *endlichen, deterministischen Automat*
+$(Q,\Sigma,\delta,q_0,F)$ ist
+
+-   $Q$ eine endliche Menge der *Zustände*
+-   $\Sigma$ das *Alphabet*
+-   $\delta: Q\times\Sigma\to Q$ die Übergangsfunktion
+-   $q_0\in Q$ der *Startzustand*
+-   $F\subset Q$ die Menge der *akzeptierenden Zustände*
+:::
+
+::: bsp
+```{=tex}
+\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
+    \node[state]           (q_3)  [right of=q_2]    {$q_3$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_3)
+          edge [loop above] node {1}    (   )
+    (q_3) edge [bend left]  node {0,1}  (q_2);
+\end{tikzpicture}\end{center}
+```
+$Q=\{q_1,q_2,q_3\}$, $\Sigma=\{0,1\}$, $q_1$ Startzustand, $F=\{q_2\}$.
+
+$\delta$ kann dargestellt werden durch
+
+  /       0       1
+  ------- ------- -------
+  $q_1$   $q_1$   $q_2$
+  $q_2$   $q_3$   $q_2$
+  $q_3$   $q_2$   $q_2$
+
+Die Zustandsfolge ist mit $w=001$
+$$q_1\xrightarrow{0}q_1\xrightarrow{0}q_1\xrightarrow{1}q_2.$$
+:::
+
+::: defi
+-   partielle Übergangsfunktion: nicht alle Übergänge sind definiert
+-   totale Übergangsfunktion: alle Übergänge sind definiert
+:::
+
+::: defi
+Eine Folge $s_0,...,s_n\in Q$ von Zuständen heißt *Berechnung* des
+Automaten $M=(Q,\Sigma,\delta,q_0,F)$ auf dem Wort $w=w_1...w_n$, falls
+
+-   $s_0=q_0$,q
+-   $\forall i=0,...,n-1: s_{i+1}=\delta(s_i,w_{i+1})$
+
+Es ist also eine "gültige" Folge von Zuständen, die man durch Abarbeiten
+von $w$ erreicht.
+:::
+
+::: bsp
+```{=tex}
+\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
+    \node[state]           (q_3)  [right of=q_2]    {$q_3$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_3)
+          edge [loop above] node {1}    (   )
+    (q_3) edge [bend left]  node {0,1}  (q_2);
+\end{tikzpicture}\end{center}
+```
+-   $w=001$ ergibt die Zustandsfolge $q_1q_1q_1q_2$
+:::
+
+::: defi
+Eine Berechnung *akzeptiert* das Wort $w$, falls die Berechnung in einem
+akzeptierten Zustand endet.
+
+Die von einem endlichen Automaten $M$ *akzeptierte* (erkannte) Sprache
+$L(M)$ ist die Menge der Wörter, die von $M$ akzeptiert werden:
+$$L(M)\defeq\{w\in\Sigma^*\mid M\text{ akzeptiert } w\}$$
+:::
+
+::: bem
+Eine Berechnung kann mehrmals in akzeptierenden Zuständen
+eintreten/austreten. Wichtig ist der Endzustand, nachdem der letzte
+Buchstabe des Eingabewortes verarbeitet wurde.
+:::
+
+::: bsp
+```{=tex}
+\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_1)
+          edge [loop above] node {1}    (   );
+\end{tikzpicture}\end{center}
+```
+-   $w=1101\rightarrow q_1q_2q_2q_1q_2\rightarrow w$ wird akzeptiert
+-   $w=010\rightarrow q_1q_1q_2q_1\rightarrow w$ wird **nicht**
+    akzeptiert
+
+Es folgt:
+$$L(M)=\{w\in\Sigma^*\mid w=\varepsilon\text{ oder }w\text{ endet mit }0\}$$
+:::
+
+::: defi
+Sei $\delta:Q\times\Sigma\to Q$ eine Übergangsfunktion. Die *erweiterte
+Übergangsfunktion* $\delta^*$: $Q\times\Sigma^*\to Q$ sei induktiv
+definiert:
+
+-   $\delta^*(q,\varepsilon)=q$ für alle $q\in Q$
+-   Für $w\in\Sigma^*$, $a\in\Sigma$ ist:
+    $$\delta^*(q,wa)=\delta(\underbrace{\delta^*(q,w)}_{\mathclap{\text{Zustand nach Lesen von $w$}}}, \overbrace{a}^{\mathclap{\text{Lesen von Buchstabe $a$}}}).$$
+:::
+
+## Reguläre Sprachen und Abschlusseigenschaften
+
+::: defi
+Eine Sprache $L\subset\Sigma^*$ heißt *reguläre Sprache*, wenn es einen
+endlichen Automaten $M$ gibt, der diese Sprache akzeptiert.
+
+Die Menge aller regulären Sprachen ist *REG*.
+:::
+
+::: satz
+Sei $L$ eine reguläre Sprache über $\Sigma$. Dann ist auch
+$\bar{L}\defeq\Sigma^*\setminus L$ eine reguläre Sprache.
+
+::: proof
+-   $L$ regulär $\implies$ es gibt Automaten
+    $M=(Q,\Sigma,\delta,q_0,F)$, der $L$ akzeptiert
+-   Definiere "Komplementautomat"
+    $\bar{M}=(Q,\Sigma,\delta,q_0,\bar{F})$ mit
+    $\bar{F}\defeq Q\setminus F$.
+-   Dann gilt:
+    `\begin{align*} w\in\bar{L}&\iff M\text{ akzeptiert }w\text{ nicht}\\ &\iff \bar{M}\text{ akzeptiert }w. \end{align*}\qed`{=tex}
+:::
+:::
+
+::: satz
+Die Menge der regulären Sprachen ist abgeschlossen bezüglich der
+Vereinigung: $$L_1,L_2\in\text{REG}\implies L_1\cup L_2\in\text{REG}.$$
+
+::: proof
+Sei $M_1=(Q_1,\Sigma_1,\delta_1,s_1,F_1)$ ein Automat, der L_1 erkennt,
+$M_2=(Q_2,\Sigma_2,\delta_2,s_2,F_2)$ ein Automat, der L_2 erkennt.
+
+Wir definieren den Produktautomaten $M\defeq M_1\times M_2$:
+$M=(Q,\Sigma,\Delta,s,F)$ mit
+
+-   $Q=Q_1\times Q_2$
+-   $\Sigma=\Sigma_1\cup\Sigma_2$,
+-   $\underbrace{s}_{\mathclap{\text{neuer Startzustand}}}=(s_1,s_2)$,
+    $F=\{(f_1,f_2)\mid f_1\in F_1\text{ oder } f_2\in F_2\}$,
+-   $\underbrace{\Delta}_{\mathclap{\text{neue Übergangsfunktion}}}: Q\times\Sigma\to Q$,
+    $$\Delta((\underbrace{r_1}_{\in Q_1},\underbrace{r_2}_{\in Q_2}),\underbrace{a}_{\in\Sigma})=(\delta_1(r_1,a),\delta(r_2,a)).$$
+
+Übertragung der Definition auf erweiterte Übergangsfunktionen: Beweis
+durch Induktion (ausgelassen).
+
+Nach Definition von $F$ akzeptiert $M$ ein Wort $w$, wenn $M_1$ oder
+$M_2$ das entsprechende Wort akzeptieren. Der Satz folgt. `\qed`{=tex}
+:::
+:::
+
+::: bsp
+```{=tex}
+$M_1$: \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_1)
+          edge [loop above] node {1}    (   );
+\end{tikzpicture}\end{center}
+$M_2$: TODO \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state]           (q_2)  [right of=q_1]    {$q_2$};
+    \node[state,accepting] (q_2)  [right of=q_2]    {$q_2$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_1)
+          edge [loop above] node {1}    (   )
+    (q_3) edge [bend left]  node {0}    (q_1)
+          edge [loop above] node {1}    (   );
+\end{tikzpicture}\end{center}
+$M_1\times M_2$: TODO \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_1)
+          edge [loop above] node {1}    (   );
+\end{tikzpicture}\end{center}
+```
+:::
+
+::: satz
+Seien $L_1,L_2$ zwei reguläre Sprachen. Dann sind auch $L_1\cap L_2$ und
+$L_1\setminus L_2$ reguläre Sprachen.
+
+::: proof
+-   $L_1\cap L_2$: Beweis funktioniert analog wie für $L_1\cup L_2$, nur
+    mit
+    $$F\defeq\{(q_1,q_2)\mid q_1\in F_1\text{\textbf{ und }}q_2\in F_2\}.$$
+-   $L_1\setminus L_2=L_q\cap\bar{L_2}$
+
+`\qed`{=tex}
+:::
+:::
+
+## Nicht-deterministische Automaten
+
+::: bsp
+TODO (ggf. auch Sipser).
+
+```{=tex}
+\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
+  \tikzstyle{every state}=[]
+
+    \node[state,initial]   (q_1)                    {$q_1$};
+    \node[state,accepting] (q_2)  [right of=q_1]    {$q_2$};
+    \node[state]           (q_3)  [right of=q_2]    {$q_3$};
+
+    \path[->]
+    (q_1) edge [loop above] node {0}    (   )
+          edge [bend left]  node {1}    (q_2)
+    (q_2) edge [bend left]  node {0}    (q_1)
+          edge [loop above] node {1}    (   );
+\end{tikzpicture}\end{center}
+```
+:::
+
+::: defi
+Ein *nicht-deterministischer Automat* besteht aus einem $5$-Tupel
+$(Q,\Sigma,\delta,q_0,F)$.
+
+-   $Q$, $\Sigma$, $q_0$, $F$ wie beim deterministischen Automat,
+-   $\delta: Q\times\Sigma\cup\{\varepsilon\}\to\overbrace{\pot(Q)}^{(*)}$
+    Übergangsfunktion
+
+$(*)$: Die Funktion definiert die **Menge** der möglichen Zustände, in
+die man von einem Zustand durch Lesen eines Buchstabens gelangen kann.
+:::
+
+::: defi
+Sei $M=(Q,\Sigma,\delta,q_0,F)$ ein nicht-deterministischer endlicher
+Automat, $w=w_1...w_n\in\Sigma^*$. Eine Folge von Zuständen
+$s_0,s_1,...,s_m\in Q$ heißt *Berechnng von $M$ auf $w$*, falls man $w$
+schreiben kann als $w=u_1u_2...u_m$ mit
+$u_i\in\Sigma\cup\{\underbrace{\varepsilon}_{\mathclap{\text{Übergänge $\varepsilon$, hier $u_i=\varepsilon$}}}\}$,
+sodass
+
+-   $s_0=q_0$,
+-   für alle $0\le i\le m-1:s_{i+1}\in\delta(s_1,u_{i+1}).$
+
+Die Berechnung heißt *akzeptierend*, falls $s_m\in F$.
+
+Der nicht-deterministische Automat $M$ *akzeptiert Wort $w$*, falls es
+eine akzeptierende Berechnung von $M$ auf $w$ gibt.
+:::
+
+::: bem
+$\varepsilon$-Transitionen: TODO.
+:::
+
+::: bsp
+Betrachte die regulären Sprachen
+
+-   $A\defeq\{x\in\{0,1\}^*\mid\text{Anzahl }0\text{ gerade}\}$
+-   $B\defeq\{x\in\{0,1\}^*\mid\text{Anzahl }0\text{ ungerade}\}$
+
+Zugehörige Automaten: TODO
+
+Nun betrachte *Konkatenation $AB$*. Um die Sprache zu erkennen, müsste
+der Automat bei einer Eingabe zunächst einen ersten Teil $A$ des Wortes
+betrachten und schauen, ob die Anzahl der $0$ gerade ist. **Irgendwann**
+müsste er beschließen, dass nun der zweite Teil $B$ des Wortes anfängt
+und er müsste schauen, ob dort die Anzahl der $0$ ungerade ist.
+
+$$\text{"Irgendwann"}\implies\text{nicht-deterministisch.}$$
+
+TODO: Graph.
+:::
+
+## Mächtigkeit
+
+::: bem
+Die Mächtigkeit eines Automaten wird hierbei beschrieben durch die
+Anzahl an Sprachen, die dieser erkennen kann.
+:::
+
+::: defi
+Zwei Automaten $M_1$, $M_2$ heißen *äquivalent*, wenn sie die gleiche
+Sprache erkennen: $$L(M_1)=L(M_2)$$
+:::
+
+::: satz
+Zu jedem nicht-deterministischen endlichen Automaten gibt es einen
+äquivalenten deterministischen endlichen Automaten.
+
+::: proof
+Lang aber trivial. Basically konstruiert man einfach eine
+deterministische Übergangsfunktion auf den nicht-deterministischen
+Verzweigungen.
+:::
+:::
+
+::: satz
+Es folgt:
+
+Eine Sprache $L$ ist regulär $\iff$ es gibt einen
+nicht-deterministischen Automaten, der $L$ akzeptiert.
+:::
+
+::: satz
+Die Klasse der regulären Sprachen ist abgeschlossen unter Konkatenation:
+$$L_1,L_2\in\mathrm{REG}\implies L_1L_2\in\mathrm{REG}$$
+:::
+
+::: satz
+Die Klasse REG ist abgeschlossen unter Bildung der Kleene'schen Hülle,
+d.h.: $$L\in\mathrm{REG}\implies L^*\in\mathrm{REG}$$
+:::
+
+## Reguläre Ausdrücke
+
+::: defi
+Sei $\Sigma$ ein Alphabet. Dann:
+
+-   $\underbrace{\emptyset}_{\mathclap{\text{leere Sprache}}}$ und
+    $\overbrace{\varepsilon}^{\mathclap{\text{leeres Wort}}}$ sind
+    reguläre Ausdrücke.
+-   Alle Buchstaben aus $\Sigma$ sind reguläre Ausdrücke.
+-   Falls $R_1$, $R_2$ reguläre Ausdrücke sind, dann sind auch die
+    folgenden Ausdrücke regulär:
+    -   $R_1\cup R_2$,
+    -   $R_1\circ R_2$,
+    -   $R_1^*$.
+:::
+
+::: defi
+Sei $R$ ein regulärer Ausdruck. Dann ist die *von $R$ induzierte Sprache
+$L(R)$* wie folgt definiert:
+
+-   $R=\emptyset\implies L(R)=\emptyset$
+-   $R=\epsilon\implies L(R)=\{\varepsilon\}$
+-   $R=\sigma\text{ für ein }\sigma\in\Sigma\implies L(R)=\{\sigma\}$
+-   $R=R_1\cup R_2\implies L(R)=L(R_1)\cup L(R_2)$
+-   $R=R_1\circ R_2\implies L(R)=L(R_1)\circ L(R_2)$
+-   $R=R_1^*\implies L(R)=(L(R_1))^*$
+:::
+
+::: satz
+Eine Sprache ist genau dann regulär, wenn sie durch einen regulären
+Ausdruck beschrieben wird.
+
+::: proof
+Strukturelle Induktion. Tja.
+:::
+:::
diff --git a/notes/theo2/main.pdf b/notes/theo2/main.pdf
new file mode 100644
index 0000000..398474f
--- /dev/null
+++ b/notes/theo2/main.pdf
diff --git a/notes/algo/makefile b/notes/theo2/makefile
index 58570c7..58570c7 100644
--- a/notes/algo/makefile
+++ b/notes/theo2/makefile
diff --git a/notes/theo2/title.tex b/notes/theo2/title.tex
new file mode 100644
index 0000000..3adc197
--- /dev/null
+++ b/notes/theo2/title.tex
@@ -0,0 +1,21 @@
+\begin{titlepage}
+	\begin{center}
+		\vspace*{1cm}
+
+		{\huge\textbf{Theoretische Informatik 2\bigskip\\Berechenbarkeit und Komplexität}}
+
+		\vspace{0.5cm}
+		{\Large Inoffizielles Skript}\\
+		\textbf{Marvin Borner}
+
+		\vfill
+		{\Large \textbf{WARNUNG WIP: Fehler zu erwarten!}\\\textbf{Stand: \today, \currenttime}}\\
+		{\large Bitte meldet euch bei mir, falls ihr Fehler findet.}
+		% \includegraphics[width=0.4\textwidth]{zeller_logo}\\
+		\vfill
+
+		Vorlesung gehalten von\\
+		\textbf{Ulrike von Luxburg}\\
+		Sommersemester 2023
+	\end{center}
+\end{titlepage}
diff --git a/sync.sh b/sync.sh
index 389216d..e2ccf67 100755
--- a/sync.sh
+++ b/sync.sh
@@ -6,11 +6,14 @@ rm -rf notes/
 
 # mathe
 for i in $(seq 3); do
-	mkdir -p "notes/mathe$i/" && find "$path/SM$i/mathe$i/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/mathe$i/" \;
+	mkdir -p "notes/mathe$i/" && find "$path/SM$i/mathe$i/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "exam.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/mathe$i/" \;
 done
 
-# algo
-mkdir -p "notes/algo/" && find "$path/SM3/algo/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/algo/" \;
+# theo1
+mkdir -p "notes/theo1/" && find "$path/SM3/algo/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "exam.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/theo1/" \;
+
+# theo2
+mkdir -p "notes/theo2/" && find "$path/SM4/theo2/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "exam.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/theo2/" \;
 
 git add .
 git status