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