1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
\section{Mathe}
\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
\lstinputlisting{math/gcd-lcm.cpp}
\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)$.
\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 $x^{-1} :\equiv \alpha \mod n$
\end{itemize}
\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
\end{description}
\lstinputlisting{math/multInv.cpp}
\subsection{Primzahlsieb von Eratosthenes}
\lstinputlisting{math/primeSieve.cpp}
\subsubsection{Faktorisierung}
\lstinputlisting{math/factor.cpp}
\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
\lstinputlisting{math/modExp.cpp}
\subsection{LGS über $\mathbb{F}_p$}
\lstinputlisting{math/lgsFp.cpp}
\subsection{Binomialkoeffizienten}
\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)$.
\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
\end{enumerate}
\subsection{Kombinatorik}
\subsubsection{Berühmte Zahlen}
\begin{tabular}{|l|l|l|}
\hline
\textsc{Fibonacci} & $f(0) = 0 \quad f(1) = 1 \quad f(n+2) = f(n+1) + f(n)$ & siehe Bemerkungen \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy}\\
\textsc{Catalan} & $C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}{2n \choose n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ & siehe Bemerkungen \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung}\\
\hline
\end{tabular}
\begin{bem}\label{bem:fibonacciMat}
$\left(\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right)^n \cdot \left(\begin{array}{c}0 \\ 1\end{array}\right) = \left(\begin{array}{c}f_n \\ f_{n+1}\end{array}\right)$
\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$ 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}
\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}$\\
\hline
\end{tabular}
|
