diff options
| -rw-r--r-- | math/math.tex | 2 | ||||
| -rw-r--r-- | other/other.tex | 3 | ||||
| -rw-r--r-- | string/string.tex | 15 | ||||
| -rw-r--r-- | tcr.pdf | bin | 641935 -> 643539 bytes |
4 files changed, 17 insertions, 3 deletions
diff --git a/math/math.tex b/math/math.tex index 6d3d3f2..fe288dc 100644 --- a/math/math.tex +++ b/math/math.tex @@ -254,7 +254,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/gauss.cpp} \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} -Multipliziert Polynome $A$ und $B$. + Multipliziert Polynome $A$ und $B$. \begin{itemize} \item $\deg(A \cdot B) = \deg(A) + \deg(B)$ \item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe diff --git a/other/other.tex b/other/other.tex index db3fd55..1a56919 100644 --- a/other/other.tex +++ b/other/other.tex @@ -149,11 +149,12 @@ \item \textbf{Satz von \textsc{Pick}:} Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand. - Es gilt: + Es gilt:\vspace*{-\baselineskip} \[ A = I + \frac{R}{2} - 1 \] +\columnbreak \item \textbf{Lemma von \textsc{Burnside}:} Sei $G$ eine endliche Gruppe, die auf der Menge $X$ operiert. Für jedes $g \in G$ sei $X^g$ die Menge der Fixpunkte bei Operation durch $g$, also $X^g = \{x \in X \mid g \bullet x = x\}$. diff --git a/string/string.tex b/string/string.tex index f426c61..0daaef2 100644 --- a/string/string.tex +++ b/string/string.tex @@ -107,7 +107,7 @@ \sourcecode{string/lyndon.cpp} \sourcecode{string/duval.cpp} \begin{itemize} - \item \textbf{De-Bruijn-Sequenze $\boldsymbol{B(\Sigma, n)}$:}~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird. + \item \textbf{De-Bruijn-Sequenze $\boldsymbol{B(\Sigma, n)}$:}~~~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird. \item es gibt $\frac{(k!)^{k^{n-1}}}{k^{n}}$ verschiedene $B(\Sigma, n)$ \item $B(\Sigma, n)$ hat Länge $\abs{\Sigma}^n$ \end{itemize} @@ -116,3 +116,16 @@ \end{methods} \sourcecode{string/deBruijn.cpp} \end{algorithm} + +\begin{algorithm}{Pattern Matching mit Wildcards} + Gegeben zwei strings $A$ und $B$,$B$ enthält $k$ \emph{wildcards} enthält. Sei: + \begin{align*} + a_i&=\cos(\alpha_i) + i\sin(\alpha_i) &\text{ mit } \alpha_i&=\frac{2\pi A[i]}{\Sigma}\\ + b_i&=\cos(\beta_i) + i\sin(\beta_i) &\text{ mit } \beta_i&=\begin{cases*} + \frac{2\pi B[\abs{B}-i-1]}{\Sigma} & falls $B[\abs{B}-i-1]\in\Sigma$ \\ + 0 & sonst + \end{cases*} + \end{align*} + $B$ matcht $A$ an stelle $i$ wenn $(b\cdot a)[|B|-1+i]=|B|-k$. + Benutze FFT um $(b\cdot a)$ zu berechnen. +\end{algorithm} Binary files differ |