aboutsummaryrefslogtreecommitdiffstats
path: root/vorlesungen/slides/4
diff options
context:
space:
mode:
Diffstat (limited to 'vorlesungen/slides/4')
-rw-r--r--vorlesungen/slides/4/Makefile.inc3
-rw-r--r--vorlesungen/slides/4/chapter.tex3
-rw-r--r--vorlesungen/slides/4/euklidbeispiel.tex44
-rw-r--r--vorlesungen/slides/4/euklidmatrix.tex86
-rw-r--r--vorlesungen/slides/4/fp.tex150
-rw-r--r--vorlesungen/slides/4/ggt.tex2
6 files changed, 286 insertions, 2 deletions
diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc
index dabdb7c..24e4a80 100644
--- a/vorlesungen/slides/4/Makefile.inc
+++ b/vorlesungen/slides/4/Makefile.inc
@@ -6,5 +6,8 @@
#
chapter4 = \
../slides/4/ggt.tex \
+ ../slides/4/euklidmatrix.tex \
+ ../slides/4/euklidbeispiel.tex \
+ ../slides/4/fp.tex \
../slides/4/chapter.tex
diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex
index 1e04e9f..4fec776 100644
--- a/vorlesungen/slides/4/chapter.tex
+++ b/vorlesungen/slides/4/chapter.tex
@@ -4,3 +4,6 @@
% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi
%
\folie{4/ggt.tex}
+\folie{4/euklidmatrix.tex}
+\folie{4/euklidbeispiel.tex}
+\folie{4/fp.tex}
diff --git a/vorlesungen/slides/4/euklidbeispiel.tex b/vorlesungen/slides/4/euklidbeispiel.tex
new file mode 100644
index 0000000..cbc3137
--- /dev/null
+++ b/vorlesungen/slides/4/euklidbeispiel.tex
@@ -0,0 +1,44 @@
+%
+% euklidmatrix.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule
+%
+\bgroup
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\begin{frame}[t]
+\frametitle{Beispiel}
+\setlength{\abovedisplayskip}{0pt}
+\setlength{\belowdisplayskip}{0pt}
+\vspace{-0pt}
+\begin{block}{Finde $\operatorname{ggT}(25,15)$}
+\vspace{-12pt}
+\begin{align*}
+a_0&=25 & b_0 &= 15 &25&=15 \cdot {\color{red} 1} + 10 &q_0 &= {\color{red}1} & r_0 &= 10\\
+a_1&=15 & b_1 &= 10 &15&=10 \cdot {\color{darkgreen}1} + \phantom{0}5 &q_1 &= {\color{darkgreen}1} & r_1 &= \phantom{0}5 \\
+a_2&=10 & b_2 &= \phantom{0}5 &10&=\phantom{0}5 \cdot {\color{blue} 2} + \phantom{0}0 &q_2 &= {\color{blue}2} & r_2 &= \phantom{0}0
+\end{align*}
+\end{block}
+\vspace{-5pt}
+\begin{block}{Matrix-Operationen}
+\begin{align*}
+Q
+&=
+Q({\color{blue}2}) Q({\color{darkgreen}1}) Q({\color{red}1})
+=
+\begin{pmatrix}0&1\\1&-{\color{blue}2}\end{pmatrix}
+\begin{pmatrix}0&1\\1&-{\color{darkgreen}1}\end{pmatrix}
+\begin{pmatrix}0&1\\1&-{\color{red}1}\end{pmatrix}
+=\begin{pmatrix}
+-1&2\\3&-5
+\end{pmatrix}
+\end{align*}
+\end{block}
+\vspace{-5pt}
+\begin{block}{Relationen ablesen}
+\begin{align*}
+\operatorname{ggT}({\usebeamercolor[fg]{title}25},{\usebeamercolor[fg]{title}15}) &= 5 = -1\cdot {\usebeamercolor[fg]{title}25} + 2\cdot {\usebeamercolor[fg]{title}15} \\
+ 0 &= \phantom{5=-}3\cdot {\usebeamercolor[fg]{title}25} -5\cdot {\usebeamercolor[fg]{title}15}
+\end{align*}
+\end{block}
+
+\end{frame}
diff --git a/vorlesungen/slides/4/euklidmatrix.tex b/vorlesungen/slides/4/euklidmatrix.tex
index 2090c0a..6ffa4c2 100644
--- a/vorlesungen/slides/4/euklidmatrix.tex
+++ b/vorlesungen/slides/4/euklidmatrix.tex
@@ -4,6 +4,90 @@
% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule
%
\begin{frame}[t]
-\frametitle{Matrixform}
+\frametitle{Matrixform des euklidischen Algorithmus}
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.52\textwidth}
+\begin{block}{Einzelschritt}
+\vspace{-10pt}
+\[
+a_k = b_kq_k + r_k
+\;\Rightarrow\;
+\left\{
+\begin{aligned}
+a_{k+1} &= b_k = \phantom{a_k-q_k}\llap{$-\mathstrut$}b_k \\
+b_{k+1} &= \phantom{b_k}\llap{$r_k$} = a_k - q_kb_k
+\end{aligned}
+\right.
+\]
+\end{block}
+\end{column}
+\begin{column}{0.44\textwidth}
+\begin{block}{Matrixschreibweise}
+\vspace{-10pt}
+\begin{align*}
+\begin{pmatrix}
+a_{k+1}\\
+b_{k+1}
+\end{pmatrix}
+&=
+\begin{pmatrix}
+b_k\\r_k
+\end{pmatrix}
+=
+\underbrace{\begin{pmatrix}0&1\\1&-q_k\end{pmatrix}}_{\displaystyle =Q(q_k)}
+\begin{pmatrix}
+a_k\\b_k
+\end{pmatrix}
+\end{align*}
+\end{block}
+\end{column}
+\end{columns}
+\vspace{-10pt}
+\begin{block}{Ende des Algorithmus}
+\vspace{-10pt}
+\begin{align*}
+\begin{pmatrix}
+a_{n+1}\\
+b_{n+1}\\
+\end{pmatrix}
+&=
+\begin{pmatrix}
+r_{n-1}\\
+r_{n}
+\end{pmatrix}
+=
+\begin{pmatrix}
+\operatorname{ggT}(a,b) \\
+0
+\end{pmatrix}
+=
+\underbrace{Q(q_n)
+\dots
+Q(q_1)
+Q(q_0)}_{\displaystyle =Q}
+\begin{pmatrix} a_0\\ b_0\end{pmatrix}
+=
+Q\begin{pmatrix}a\\b\end{pmatrix}
+\end{align*}
+\end{block}
+\begin{block}{Konsequenzen}
+\[
+Q=\begin{pmatrix}
+q_{11}&q_{12}\\
+a_{21}&q_{22}
+\end{pmatrix}
+\quad\Rightarrow\quad
+\left\{
+\quad
+\begin{aligned}
+\operatorname{ggT}(a,b) &= q_{11}a + q_{12}b \\
+ 0 &= q_{21}a + q_{22}b
+\end{aligned}
+\right.
+\]
+\end{block}
\end{frame}
diff --git a/vorlesungen/slides/4/fp.tex b/vorlesungen/slides/4/fp.tex
new file mode 100644
index 0000000..a893238
--- /dev/null
+++ b/vorlesungen/slides/4/fp.tex
@@ -0,0 +1,150 @@
+%
+% fp.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\def\feld#1#2#3{
+ \node at ({#1},{5-#2}) {$#3$};
+}
+\def\geld#1#2#3{
+ \node at ({#1},{6-#2}) {$#3$};
+}
+\def\rot#1#2{
+ \fill[color=red!20] ({#1-0.5},{5-#2-0.5}) rectangle ({#1+0.5},{5-#2+0.5});
+}
+\begin{frame}[t]
+\frametitle{Galois-Körper}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Restklassenring$\mathstrut$}
+$\mathbb{Z}/n\mathbb{Z}
+=\{ \llbracket r\rrbracket\;|\; 0\le r < n \} \mathstrut$
+ist ein Ring
+\end{block}
+\begin{block}{Nullteiler}
+Falls $n=n_1n_2$, dann sind $\llbracket n_1\rrbracket$ und
+$\llbracket n_2\rrbracket$ Nullteiler in $\mathbb{Z}/n\mathbb{Z}$:
+\[
+\llbracket n_1\rrbracket
+\llbracket n_2\rrbracket
+=
+\llbracket n_1n_2 \rrbracket
+=
+\llbracket n\rrbracket
+=
+\llbracket 0 \rrbracket
+\]
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Galois-Körper $\mathbb{F}_p\mathstrut$}
+$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}\mathstrut$
+\end{block}
+\begin{block}{$n$ prim}
+Für $n=p$ prim ist $\mathbb{Z}/n\mathbb{Z}$ nullteilerfrei
+\medskip
+
+$\Rightarrow \quad \mathbb{F}_p$ ist ein Körper
+\end{block}
+\end{column}
+\end{columns}
+\vspace{-20pt}
+\begin{center}
+\begin{tikzpicture}[>=latex,thick,scale=0.45]
+\begin{scope}[xshift=-7cm]
+\rot{2}{3}
+\rot{4}{3}
+\rot{3}{2}
+\rot{3}{4}
+\fill[color=gray!40] (-0.5,5.5) rectangle (5.5,6.5);
+\fill[color=gray!40] (-1.5,-0.5) rectangle (-0.5,5.5);
+\foreach \x in {-0.5,5.5}{
+ \draw (\x,-0.5) -- (\x,6.5);
+}
+\foreach \x in {0.5,...,4.5}{
+ \draw[line width=0.3pt] (\x,-0.5) -- (\x,6.5);
+}
+\foreach \y in {0.5,...,5.5}{
+ \draw[line width=0.3pt] (-1.5,\y) -- (5.5,\y);
+}
+\foreach \y in {-0.5,5.5}{
+ \draw (-1.5,\y) -- (5.5,\y);
+}
+\draw (-1.5,-0.5) -- (-1.5,5.5);
+\draw (-0.5,6.5) -- (5.5,6.5);
+\foreach \x in {0,...,5}{
+ \node at (\x,6) {$\x$};
+ \node at (-1,{5-\x}) {$\x$};
+}
+\foreach \x in {0,...,5}{
+ \feld{\x}{0}{0}
+ \feld{0}{\x}{0}
+}
+\foreach \x in {2,...,5}{
+ \feld{\x}{1}{\x}
+ \feld{1}{\x}{\x}
+}
+\feld{1}{1}{1}
+\feld{2}{2}{4}
+\feld{2}{3}{0} \feld{3}{2}{0}
+\feld{2}{4}{2} \feld{4}{2}{2}
+\feld{2}{5}{4} \feld{5}{2}{4}
+\feld{3}{3}{3}
+\feld{4}{3}{0} \feld{3}{4}{0}
+\feld{5}{3}{3} \feld{3}{5}{3}
+\feld{4}{4}{4}
+\feld{4}{5}{2} \feld{5}{4}{2}
+\feld{5}{5}{1}
+\end{scope}
+\begin{scope}[xshift=7cm]
+\fill[color=gray!40] (-0.5,6.5) rectangle (6.5,7.5);
+\fill[color=gray!40] (-1.5,-0.5) rectangle (-0.5,6.5);
+\foreach \x in {-0.5,6.5}{
+ \draw (\x,-0.5) -- (\x,7.5);
+}
+\foreach \x in {0.5,...,5.5}{
+ \draw[line width=0.3pt] (\x,-0.5) -- (\x,7.5);
+}
+\foreach \y in {0.5,...,6.5}{
+ \draw[line width=0.3pt] (-1.5,\y) -- (6.5,\y);
+}
+\foreach \y in {-0.5,6.5}{
+ \draw (-1.5,\y) -- (6.5,\y);
+}
+\draw (-1.5,-0.5) -- (-1.5,6.5);
+\draw (-0.5,7.5) -- (6.5,7.5);
+\foreach \x in {0,...,6}{
+ \node at (\x,7) {$\x$};
+ \node at (-1,{6-\x}) {$\x$};
+}
+\foreach \x in {0,...,6}{
+ \geld{\x}{0}{0}
+ \geld{0}{\x}{0}
+}
+\foreach \x in {2,...,6}{
+ \geld{\x}{1}{\x}
+ \geld{1}{\x}{\x}
+}
+\geld{1}{1}{1}
+\geld{2}{2}{4}
+\geld{2}{3}{6} \geld{3}{2}{6}
+\geld{2}{4}{1} \geld{4}{2}{1}
+\geld{2}{5}{3} \geld{5}{2}{3}
+\geld{2}{6}{5} \geld{6}{2}{5}
+\geld{3}{3}{2}
+\geld{4}{3}{5} \geld{3}{4}{5}
+\geld{5}{3}{1} \geld{3}{5}{1}
+\geld{6}{3}{4} \geld{3}{6}{4}
+\geld{4}{4}{2}
+\geld{5}{4}{6} \geld{4}{5}{6}
+\geld{6}{4}{3} \geld{4}{6}{3}
+\geld{5}{5}{4}
+\geld{6}{5}{2} \geld{5}{6}{2}
+\geld{6}{6}{1}
+\end{scope}
+\end{tikzpicture}
+\end{center}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/4/ggt.tex b/vorlesungen/slides/4/ggt.tex
index 77b2a1d..e3c55e6 100644
--- a/vorlesungen/slides/4/ggt.tex
+++ b/vorlesungen/slides/4/ggt.tex
@@ -22,7 +22,7 @@ a_0&=b_0q_0 + r_0 & a_1 &=b_0 & b_1&=r_0 \\
a_1&=b_1q_1 + r_1 & a_2 &=b_1 & b_2&=r_1 \\
a_2&=b_2q_2 + r_2 & a_3 &=b_2 & b_3&=r_2 \\
&\;\vdots & & & & \\
-a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&)=\operatorname{ggT}(a,b)
+a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&=\operatorname{ggT}(a,b)
\end{align*}
\end{block}
\end{column}