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{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.
	\item 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{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
\lstinputlisting{math/millerRabin.cpp}

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

\subsection{Maximales Teilfeld}
\lstinputlisting{math/maxTeilfeld.cpp}
Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu:
\begin{enumerate}
	\item Finde maximales Teilfeld, das nicht übers Ende geht.
	\item Berechne minimales Teilfeld, das nicht über den Rand geht (analog).
	\item Nimm Maximum aus gefundenem Maximalen und Allem ohne dem Minimalen.
\end{enumerate}

\subsection{Polynome \& FFT}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}
	\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{Kombinatorik}

\subsubsection{Berühmte Zahlen}
\begin{tabularx}{\textwidth}{|l|X|l|}
	\hline
	\textsc{Fibonacci}-Zahlen	&
	$f(0) = 0 \qquad
	f(1) = 1 \qquad
	f(n+2) = f(n+1) + f(n)$ &
	Bem. \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy} \\

	\textsc{Catalan}-Zahlen	&
	$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}$ &
	Bem. \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung} \\

	\textsc{Euler}-Zahlen (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} $ &
	Bem. \ref{bem:euler1} \\

	\textsc{Euler}-Zahlen (II) &
	$\eulerII{n}{0} = 1 \qquad
	\eulerII{n}{n} = 0 \qquad
	\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ &
	Bem. \ref{bem:euler2} \\

	\textsc{Stirling}-Zahlen (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}$ &
	Bem. \ref{bem:stirling1} \\

	\textsc{Stirling}-Zahlen (II) &
	$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
	\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ &
	Bem. \ref{bem:stirling2} \\

	Integer-Partitions &
	$f(1,1) = 1 \qquad f(n,k) = 0 \text{ für } k > n \qquad f(n,k)  =
	f(n-k,k) + f(n,k-1)$ &
	Bem. \ref{bem:integerPartitions} \\
	\hline
\end{tabularx}

\begin{bem}\label{bem:fibonacciMat}
	$
	\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n
	\cdot
	\begin{pmatrix} 0 \\ 1 \end{pmatrix}
	=
	\begin{pmatrix}f_n \\ f_{n+1} \end{pmatrix}
	$
\end{bem}

\begin{bem}[\textsc{Zeckendorfs} Theorem]\label{bem:fibonacciGreedy}
	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}\label{bem:catalanOverflow}
	\begin{itemize}
		\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.
	\end{itemize}
\end{bem}

\begin{bem}\label{bem:catalanAnwendung}
	Die \textsc{Catalan}-Zahlen geben an: $C_n =$
	\begin{itemize}
		\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{bem}

\begin{bem}[\textsc{Euler}-Zahlen 1. Ordnung]\label{bem:euler1}
	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]\label{bem:euler2}
	Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
\end{bem}

\begin{bem}[\textsc{Stirling}-Zahlen 1. Ordnung]\label{bem:stirling1}
	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]\label{bem:stirling2}
	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}\label{bem:integerPartitions}
	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)$.
\lstinputlisting{math/nimm.cpp}

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

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