From 9e625b89bac7e8daaf583e215f3a0df3dc250bb2 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Mon, 27 Jun 2016 11:17:34 +0200
Subject: Math section rebuild, merged convinience and sonstiges section.

---
 math/math.tex | 159 +++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 96 insertions(+), 63 deletions(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index 59219e5..b0ff8da 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -5,59 +5,66 @@
 \lstinputlisting{math/extendedEuclid.cpp}
 
 \subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
-Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
+Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.
 \begin{description}
 	\item[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 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}
-	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
+	\item[Falls $d \neq 1$:] Es existiert kein $x^{-1}$.
 \end{description}
 \lstinputlisting{math/multInv.cpp}
 
-\subsection{Primzahlsieb von \textsc{Eratosthenes}}
-\lstinputlisting{math/primeSieve.cpp}
-
-\subsection{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
-\lstinputlisting{math/millerRabin.cpp}
-
-\subsection{Faktorisierung}
-\lstinputlisting{math/factor.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{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\{ \mathbb{Z}_0^+ \textbackslash \{g\left(Y\right)~|~Y \text{ von } X \text{ aus direkt erreichbar}\}\} 
-\]
-$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{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 Maximalem und Allem\textbackslash Minimalem
+	\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.
+	\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}
@@ -76,7 +83,8 @@ Multipliziert Polynome $A$ und $B$.
 
 	\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}$ &
+	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) &
@@ -102,82 +110,107 @@ Multipliziert Polynome $A$ und $B$.
 	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)$ &
+	$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}
-$
+	$
+	\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.
+	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.
+	\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}
+	\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$ 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 in einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. (zwischen gegenüberliegenden Ecken)
-\end{itemize}
+	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.
+	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}
+	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.
+	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.
+	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.
+	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.
+	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.
+	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$.
+	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
-	Hanoi Towers (min steps)		& $T_n = 2^n - 1$\\
-	\#regions by $n$ lines			& $n\left(n + 1\right) / 2 + 1$\\
-	\#bounded regions by $n$ lines		& $\left(n^2 - 3n + 2\right) / 2$\\
-	\#labeled rooted trees			& $n^{n-1}$\\
-	\#labeled unrooted trees		& $n^{n-2}$\\
+	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}
 
-- 
cgit v1.2.3

