diff options
Diffstat (limited to 'math/math.tex')
| -rw-r--r-- | math/math.tex | 159 |
1 files changed, 96 insertions, 63 deletions
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} |