From e051a4ed9b70bb2363732d1c97f94746a08ed25b Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 14 Feb 2023 17:49:01 +0100
Subject: rearranged math

---
 math/math.tex | 227 +++++++++++++++++++++++++++++-----------------------------
 1 file changed, 114 insertions(+), 113 deletions(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index edaebd1..d648582 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -8,6 +8,25 @@
 	\sourcecode{math/longestIncreasingSubsequence.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Zykel Erkennung}
+	\begin{methods}
+		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
+	\end{methods}
+	\sourcecode{math/cycleDetection.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Permutationen}
+	\begin{methods}
+		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/kthperm.cpp}
+	\begin{methods}
+		\method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/permIndex.cpp}
+\end{algorithm}
+\clearpage
+
 \subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
 %\vspace{-1.25em}
 %\begin{multicols}{2}
@@ -41,15 +60,6 @@
 \textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
 \sourcecode{math/multInv.cpp}
 
-\begin{algorithm}{Lineare Kongruenz}
-	\begin{itemize}
-		\item Löst $ax\equiv b\pmod{m}$.
-		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
-		also $g$ Lösungen modulo $m$.
-	\end{itemize}
-	\sourcecode{math/linearCongruence.cpp}
-\end{algorithm}
-
 \paragraph{Lemma von \textsc{Bézout}}
 Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
 Dann lassen sich wie folgt alle Lösungen berechnen:
@@ -66,73 +76,13 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
 \end{align*}
 
-
-\begin{algorithm}{Zykel Erkennung}
-	\begin{methods}
-		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
-	\end{methods}
-	\sourcecode{math/cycleDetection.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Permutationen}
-	\begin{methods}
-		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
-	\end{methods}
-	\sourcecode{math/kthperm.cpp}
-	\begin{methods}
-		\method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
-	\end{methods}
-	\sourcecode{math/permIndex.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Lineare-Recurenz}
-	\begin{methods}
-		\method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
-		\method{}{aus den ersten $2n$ Werte}{}
-	\end{methods}
-	\sourcecode{math/berlekampMassey.cpp}
-	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
-	
-	\begin{methods}
-		\method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
-	\end{methods}
-	\sourcecode{math/linearRecurence.cpp}
-	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
-	$$\renewcommand\arraystretch{1.5}
-	\setlength\arraycolsep{3pt}
-	\begin{pmatrix} 
-		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
-		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
-		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
-		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
-		0 & \smash{\cdots} & 0 & 1 & 0 \\
-	\end{pmatrix}^k
-	\times~~
-	\begin{pmatrix} 
-		f(n-1) \\
-		f(n-2) \\
-		\smash{\vdots} \\
-		\smash{\vdots} \\
-		f(0) \\
-	\end{pmatrix}
-	~~=~~
-	\begin{pmatrix} 
-		f(n-1+k) \\
-		f(n-2+k) \\
-		\smash{\vdots} \\
-		\smash{\vdots} \\
-		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
-	\end{pmatrix}
-	$$
-\end{algorithm}
-
-
-\begin{algorithm}{Matrix-Exponent}
-	\begin{methods}
-		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
-		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
-	\end{methods}
-	\sourcecode{math/matrixPower.cpp}
+\begin{algorithm}{Lineare Kongruenz}
+	\begin{itemize}
+		\item Löst $ax\equiv b\pmod{m}$.
+		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
+		also $g$ Lösungen modulo $m$.
+	\end{itemize}
+	\sourcecode{math/linearCongruence.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Chinesischer Restsatz}
@@ -140,9 +90,9 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
 		\item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
 		\[
-			x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
-			\qquad \text{mit} \qquad
-			d := \ggT(n, m) = yn + zm
+		x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \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,
@@ -153,10 +103,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/chineseRemainder.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+	\sourcecode{math/millerRabin.cpp}
+	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
+	\sourcecode{math/rho.cpp}
+	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
+	%\sourcecode{math/squfof.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Teiler}
 	\begin{methods}
-		\method{countDivisors}{Zählt Teiler von $n$}{n^\frac{1}{3}}
-		\method{isPrime}{prüft ob Zahl prim ist}{1}
+		\method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
 	\end{methods}
 	\sourcecode{math/divisors.cpp}
 \end{algorithm}
@@ -191,32 +149,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/discreteNthRoot.cpp}
 \end{algorithm}
 
-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
-\begin{methods}
-	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
-	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
-	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
-\end{methods}
-\sourcecode{math/piLehmer.cpp}
-\clearpage
 
-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/lgsFp.cpp}
 
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\sourcecode{math/gauss.cpp}
 
 
-\begin{algorithm}{Primzahltest \& Faktorisierung}
-	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
-	\sourcecode{math/millerRabin.cpp}
-	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
-	\sourcecode{math/rho.cpp}
-	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
-	%\sourcecode{math/squfof.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
 	\begin{itemize}
 		\item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
@@ -247,25 +183,40 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
 	\sourcecode{math/mobius.cpp}
 \end{algorithm}
-\clearpage
 
+\columnbreak
 \subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
 \begin{itemize}
 	\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 \textbf{\textsc{Euler}'s Theorem:}
-		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+	Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
 	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
 	$a^{m} \equiv a \pmod{m}$
 \end{itemize}
 \sourcecode{math/phi.cpp}
 
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
+
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+	\sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
 	\begin{itemize}
@@ -285,13 +236,63 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
 	\sourcecode{math/transforms/fftMul.cpp}
 \end{algorithm}
+\clearpage
 
-\begin{algorithm}{Numerisch Extremstelle bestimmen}
-	\sourcecode{math/goldenSectionSearch.cpp}
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\begin{methods}
+	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
+	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
+	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
+\end{methods}
+\sourcecode{math/piLehmer.cpp}
+
+\begin{algorithm}{Lineare-Recurenz}
+	\begin{methods}
+		\method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
+		\method{}{aus den ersten $2n$ Werte}{}
+	\end{methods}
+	\sourcecode{math/berlekampMassey.cpp}
+	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
+	
+	\begin{methods}
+		\method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/linearRecurence.cpp}
+	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
+	$$\renewcommand\arraystretch{1.5}
+	\setlength\arraycolsep{3pt}
+	\begin{pmatrix} 
+		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
+		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
+		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
+		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
+		0 & \smash{\cdots} & 0 & 1 & 0 \\
+	\end{pmatrix}^k
+	\times~~
+	\begin{pmatrix} 
+		f(n-1) \\
+		f(n-2) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(0) \\
+	\end{pmatrix}
+	~~=~~
+	\begin{pmatrix} 
+		f(n-1+k) \\
+		f(n-2+k) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+	\end{pmatrix}
+	$$
 \end{algorithm}
 
-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
-	\sourcecode{math/simpson.cpp}
+\begin{algorithm}{Matrix-Exponent}
+	\begin{methods}
+		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/matrixPower.cpp}
 \end{algorithm}
 
 \begin{algorithm}{\textsc{Legendre}-Symbol}
@@ -375,7 +376,7 @@ so gilt
 		\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 Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.
 		\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
 		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
 	\end{itemize}
-- 
cgit v1.2.3

