path: root/math/math.tex

\section{Mathe}

\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
\lstinputlisting{math/gcd-lcm.cpp}
\lstinputlisting{math/extendedEuclid.cpp}

\paragraph{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.\newline
\textbf{Falls $d = 1$:}
\begin{itemize}[nosep]
	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
	$\alpha x + \beta n = 1$.
	\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$.
	\item $x^{-1} :\equiv \alpha \mod n$
	\end{itemize}
\textbf{Falls $d \neq 1$:} Es existiert kein $x^{-1}$.
\lstinputlisting{math/multInv.cpp}

\subsection{Mod-Exponent über $\mathbb{F}_p$}
\lstinputlisting{math/modExp.cpp}

\subsection{LGS über $\mathbb{F}_p$}
\lstinputlisting{math/lgsFp.cpp}

\subsection{LGS über $\mathbb{R}$}
\lstinputlisting{math/gauss.cpp}

\subsection{Chinesischer Restsatz}
\begin{itemize}
	\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
	\item Direkte Formel für zwei Kongruenzen $x \equiv a \mod n$, $x \equiv b \mod m$:
		\[
			x \equiv a - y * n * \frac{a - b}{d} \mod \frac{mn}{d}
			\qquad \text{mit} \qquad
			d := ggT(n, m) = yn + zm
		\]
		Formel kann auch für nicht teilerfremde Moduli verwendet werden.
		Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
		wenn $a_i \equiv a_j \mod \gcd(m_i, m_j)$. In diesem Fall sind keine Faktoren
		auf der linken Seite erlaubt.
\end{itemize}
\lstinputlisting{math/chineseRemainder.cpp}

\subsection{Primzahlsieb von \textsc{Eratosthenes}}
\lstinputlisting{math/primeSieve.cpp}

\subsection{Primzahltest \& Faktorisierung}
\lstinputlisting{math/primes.cpp}

\subsection{Binomialkoeffizienten}
Vorberechnen, wenn häufig benötigt.
\lstinputlisting{math/binomial.cpp}

\subsection{\textsc{Euler}sche $\varphi$-Funktion}
\begin{itemize}[nosep]
	\item Zählt die relativ primen Zahlen $\leq n$.

	\item Multiplikativ:
	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$

	\item $p$ prim, $k \in \mathbb{N}$:
	$~\varphi(p^k) = p^k - p^{k - 1}$

	\item $n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}$:
	$~\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$
	Evtl. ist es sinnvoll obgien Code zum Faktorisieren zu benutzen und dann diese Formel anzuwenden.

	\item \textbf{\textsc{Euler}'s Theorem:}
	Seien $a$ und $m$ teilerfremd. Dann:
	$a^{\varphi(m)} \equiv 1 \mod m$\newline
	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
	$a^{m} \equiv a \mod m$
\end{itemize}
\lstinputlisting{math/phi.cpp}

\subsection{Primitivwurzeln}
\begin{itemize}[nosep]
	\item Primitivwurzel modulo $n$ existiert genau dann wenn:
	\begin{itemize}[nosep]
		\item $n$ ist $1$, $2$ oder $4$, oder
		\item $n$ ist Potenz einer ungeraden Primzahl, oder
		\item $n$ ist das Doppelte einer Potenz einer ungeraden Primzahl.
	\end{itemize}

	\item Sei $g$ Primitivwurzel modulo $n$.
	Dann gilt:\newline
	Das kleinste $k$, sodass $g^k \equiv 1 \mod n$, ist $k = \varphi(n)$.
\end{itemize}
\lstinputlisting{math/primitiveRoot.cpp}

\subsection{Diskreter Logarithmus}
\lstinputlisting{math/discreteLogarithm.cpp}

\subsection{Polynome \& FFT}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}[nosep]
	\item $\deg(A * B) = \deg(A) + \deg(B)$
	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
	$\deg(A * B) + 1$ haben.
	Größe muss eine Zweierpotenz sein.
	\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
\end{itemize}
\lstinputlisting{math/fft.cpp}

\subsection{3D-Kugeln}
\lstinputlisting{math/spheres.cpp}

\subsection{Longest Increasing Subsequence}
\lstinputlisting{math/longestIncreasingSubsequence.cpp}

\subsection{Kombinatorik}

\subsubsection{Berühmte Zahlen}
\begin{tabular}{|l|l|}
	\hline
	\textsc{Fibonacci}	&
	$f(0) = 0 \quad
	f(1) = 1 \quad
	f(n+2) = f(n+1) + f(n)$ \\

	\textsc{Catalan}	&
	$C_0 = 1 \qquad
	C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
	\frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\

	\textsc{Euler} I &
	$\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad
	\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\

	\textsc{Euler} II &
	$\eulerII{n}{0} = 1 \quad
	\eulerII{n}{n} = 0 \quad
	\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\

	\textsc{Stirling} I &
	$\stirlingI{0}{0} = 1 \qquad
	\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
	\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\

	\textsc{Stirling} II &
	$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
	\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ \\

	\textsc{Bell} &
	$f(1,1) = 1 \quad
	f(n,k) = 0 \text{ für } k > n \quad
	f(n,k) = f(n-k,k) + f(n,k-1)$ \\
	\hline
\end{tabular}

\begin{bem}[\textsc{Zeckendorfs} Theorem]
	Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
	verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei
	aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.

	\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
	hineinpasst.
\end{bem}

\begin{bem}[\textsc{Catalan}-Zahlen]
	\begin{itemize}[nosep]
		\item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows.
		\item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen
		bezüglich eines Moduls genutzt werden.
		\item Die \textsc{Catalan}-Zahlen geben an: $C_n =$
		\begin{itemize}[nosep]
			\item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
			\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
			\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
			\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken in
			Dreiecke zu zerlegen.
			\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
			einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
		\end{itemize}
	\end{itemize}
\end{bem}

\begin{bem}[\textsc{Euler}-Zahlen 1. Ordnung]
	Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.

	Begründung: Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
	Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
	\end{bem}

\begin{bem}[\textsc{Euler}-Zahlen 2. Ordnung]
	Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
\end{bem}

\begin{bem}[\textsc{Stirling}-Zahlen 1. Ordnung]
	Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.

	Begründung: Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie
	bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus
	einsortiert werden.
\end{bem}

\begin{bem}[\textsc{Stirling}-Zahlen 2. Ordnung]
	Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.

	Begründung: Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition
	einzuordnen. Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge
	(alleine) steht.
\end{bem}

\begin{bem}[Bell-Zahlen]
	Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit
	maximalem Elment $\leq k$.
\end{bem}

\subsubsection{Verschiedenes}
\begin{tabular}{|l|l|}
	\hline
	Türme von Hanoi, minimale Schirttzahl:					& $T_n = 2^n - 1$ \\
	\#Regionen zwischen $n$ Gearden									& $n\left(n + 1\right) / 2 + 1$ \\
	\#Abgeschlossene Regionen zwischen $n$ Geraden	& $\left(n^2 - 3n + 2\right) / 2$ \\
	\#Markierte, gewurzelte Bäume										& $n^{n-1}$ \\
	\#Markierte, nicht gewurzelte Bäume							& $n^{n-2}$ \\
	\hline
\end{tabular}

\subsection{Satz von \textsc{Sprague-Grundy}}
Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
\[
	g\left(X\right) := \min\left\{
		\mathbb{Z}_0^+ \setminus
		\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
	\right\} 
\]
$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.

\subsection{Big Integers}
\lstinputlisting{math/bigint.cpp}