From ca12778acdf6f2da84aec311c5ab63cde5d847cd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 1 Mar 2021 21:20:36 +0100 Subject: add slides --- vorlesungen/common/packages.tex | 3 + vorlesungen/slides/4/Makefile.inc | 3 + vorlesungen/slides/4/chapter.tex | 3 + vorlesungen/slides/4/euklidbeispiel.tex | 44 ++++++++++ vorlesungen/slides/4/euklidmatrix.tex | 86 +++++++++++++++++- vorlesungen/slides/4/fp.tex | 150 ++++++++++++++++++++++++++++++++ vorlesungen/slides/4/ggt.tex | 2 +- vorlesungen/slides/test.tex | 6 +- 8 files changed, 292 insertions(+), 5 deletions(-) create mode 100644 vorlesungen/slides/4/euklidbeispiel.tex create mode 100644 vorlesungen/slides/4/fp.tex diff --git a/vorlesungen/common/packages.tex b/vorlesungen/common/packages.tex index 94a7c6f..d71438b 100644 --- a/vorlesungen/common/packages.tex +++ b/vorlesungen/common/packages.tex @@ -11,10 +11,13 @@ \usepackage{ifthen} \usepackage{lmodern} \usepackage{amsmath} +\usepackage{amssymb} \usepackage{mathtools} \usepackage{adjustbox} \usepackage{multimedia} \usepackage{verbatim} +\usepackage{wasysym} +\usepackage{stmaryrd} \usepackage{tikz} \usetikzlibrary{shapes.geometric} \usetikzlibrary{decorations.pathreplacing} 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} diff --git a/vorlesungen/slides/test.tex b/vorlesungen/slides/test.tex index 2faf3b3..e7108ec 100644 --- a/vorlesungen/slides/test.tex +++ b/vorlesungen/slides/test.tex @@ -30,9 +30,9 @@ % XXX \folie{3/adj1291.tex} \folie{4/ggt.tex} -% XXX \folie{4/euklidmatrix.tex} - -% XXX \folie{4/fp.tex} +\folie{4/euklidmatrix.tex} +\folie{4/euklidbeispiel.tex} +\folie{4/fp.tex} % XXX \folie{4/division.tex} % XXX \folie{4/gauss.tex} % XXX \folie{4/dh.tex} -- cgit v1.2.1