# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1391278972 -3600
# Node ID a9b64faf4b8f197f1a6f762762dee9ccd7bbba0a
# Parent  6669987ffd3251e1d6c324120b41a29bcedef998
fourteenth sheet and notes

diff -r 6669987ffd32 -r a9b64faf4b8f ds13-14.pdf
Binary file ds13-14.pdf has changed
diff -r 6669987ffd32 -r a9b64faf4b8f notes/complete_notes.pdf
Binary file notes/complete_notes.pdf has changed
diff -r 6669987ffd32 -r a9b64faf4b8f notes/tex/algebra.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/algebra.tex	Sat Feb 01 19:22:52 2014 +0100
@@ -0,0 +1,304 @@
+\defineUnit{algebradefinitionen}{%
+\begin{frame}
+    \frametitle{Modulo}
+
+    \begin{definition}[Modulo-Kongruenz]
+        Zwei Zahlen $a, b \in \Z$ heißen \structure{kongruent Modulo $n \in \N$}, falls
+        \begin{align}
+            \exists k \in Z.\; a = k \cdot n + b
+        \end{align}
+        Wir schreiben dann $a \equiv b \pmod n$ oder $a \equiv_n b$.\\
+        Durch $\equiv_n$ wird eine \alert{Äquivalenzrelation} definiert.
+    \end{definition}
+
+    \begin{definition}[Modulo-Operator]
+        Der \structure{Modulo-Operator} ordnet jeder Zahl $a \in \Z$ seine Äquivalenzklasse (\structure{Restklasse}) Modulo $n \in \N$ zu. Es gilt
+        \begin{align}
+            a \mod n = r \text{\qquad gdw. \qquad} \exists q \in \Z.\; a = q \cdot n + r \text{\quad mit \quad } 0 \leq r < n
+        \end{align}
+        Modulo gibt den \alert{Rest} bei einer \alert{Ganzzahldivision} zurück.
+    \end{definition}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{-1.5em}
+        \begin{align}
+            5 \mod 3 &= 2 & 6 \mod 3 &= 0 & -5 \mod 3 &= 1
+        \end{align}
+        \vspace{-1.5em}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Algebren}
+
+    \begin{definition}[Algebra]
+        Eine \structure{Algebra $\langle M, \left( \circ_i \right)_{i \in I}\rangle$} besteht aus einer Menge von Operanden und einer oder mehrerer innerer Verknüpfungen.\\
+        Eine \structure{innere Verknüpfung} auf $M$ ist eine Abbildung
+        \begin{align}
+            \circ : M \times M \to M
+        \end{align}
+        Eine Verknüpfung heißt
+        \begin{description}[kommutativ\qquad]
+            \item[assoziativ] wenn $\left( a \circ b \right) \circ c = a \circ \left( b \circ c \right)$
+            \item[kommutativ] wenn $a \circ b = b \circ a$
+        \end{description}
+        für alle $a, b, c \in M$.
+    \end{definition}
+
+    \vfill
+
+    \begin{example}[]
+        Einige Beispiele für Algebren sind (mit üblichen Verknüpfungen)
+        \begin{itemize}
+            \item $\langle \Z, +, \cdot \rangle$ die ganzen Zahlen
+            \item $\langle \Z_{11}, +\rangle$ die Restklassen Modulo 11
+            \item $\langle \R^3, +, \cdot\rangle$ der 3-Dimensionale $\R$-Vektorraum
+        \end{itemize}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Gruppen}
+
+    \begin{definition}[Gruppe]
+        Eine Algebra $\alg{G, \circ, e}$ heißt \structure{Gruppe}, wenn für alle $a, b, c \in G$ gilt
+        \begin{description}[Neutrales Element\qquad]
+            \item[Assoziativität] $(a \circ b) \circ c = a \circ (b \circ c)$
+            \item[Neutrales Element] Für $e$ gilt $a \circ e = e \circ a = a$
+            \item[Inverse Elemente] Es gibt $a^{-1}$ mit $a \circ a^{-1} = a^{-1} \circ a = e$
+        \end{description}
+        Wir schreiben auch kurz $G$.\\
+        Wir nennen $G$ \structure{abelsch (oder kommutativ)}, wenn $\circ$ kommutativ ist.
+    \end{definition}
+
+    \begin{example}[]
+        Die Menge $[4]$ zusammen mit der Multiplikation modulo $5$ beschreibt die Gruppe $\alg{[4], \cdot_5, 1} = \Z^*_5$.
+        \vspace{.5em}
+        \begin{columns}[T]
+            \begin{column}{.4\textwidth}
+                \centering
+                \tabulinesep=3pt
+                \begin{tabu} to .8\textwidth {X|[1pt]XXXX}
+                    $\cdot_5$ & 1 & 2 & 3 & 4\\\tabucline[1pt]{-}
+                    1 & 1 & 2 & 3 & 4\\
+                    2 & 2 & 4 & 1 & 3\\
+                    3 & 3 & 1 & 4 & 2\\
+                    4 & 4 & 3 & 2 & 1\\
+                \end{tabu}
+            \end{column}
+            \begin{column}{.6\textwidth}
+                \begin{itemize}
+                    \item Erfüllt \enquote{Sudokuprinzip}
+                    \item Multiplikation ist assoziativ
+                    \item $1$ ist neutrales Element
+                    \item Inverse existieren
+                    \item Kommutativ da symmetrisch
+                \end{itemize}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Untergruppen}
+
+    \begin{definition}[Untergruppe]
+        Sei $G$ eine Gruppe und $H \subseteq G$ eine Teilmenge.\\
+        $H$ heißt \structure{Untergruppe} von $G$, wenn für $a, b \in H$ gilt
+        \begin{description}[Abgeschlossenheit\qquad]
+            \item[Abgeschlossenheit] $a \circ b \in H$
+            \item[Inverse] $a^{-1} \in H$
+        \end{description}
+        Wir schreiben $H < G$.
+    \end{definition}
+
+    \begin{itemize}
+        \item Um zu zeigen dass $H < G$ gilt, reicht es zu zeigen dass
+            \begin{align}
+                a, b \in H \rightarrow ab^{-1} \in H
+            \end{align}
+        \item Jede Gruppe enthält $\left\{ e \right\}$ und sich selbst als Untergruppe
+    \end{itemize}
+
+    \begin{example}[]
+        Betrachte $G = \alg{\Z_{10}, +, 0}$ die Restklassen Modulo 10.\\
+        Dann ist $H = \alg{\left\{ 0, 2, 4, 6, 8 \right\}, +, 0}$ eine Untergruppe von $G$, da die Summe zweier gerader Zahlen gerade ist und für $a \in H$ gilt, dass $a^{-1} = 10 - a \in H$.
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Ordnung und Erzeugnis}
+
+    Sei $\alg{G, \circ, e}$ eine Gruppe.
+    \begin{definition}[Ordnung]
+        Die \structure{Ordnung} eines Elements $a \in G$ ist die kleinste Potenz $k$, sodass $a^k = e$.
+        \begin{align}
+            \ord(a) \defeq \min \left\{ k \in \N \setminus \left\{ 0 \right\} \mid a^k = e \right\}
+        \end{align}
+        Existiert kein solches $k$, so ist $\ord(a) \defeq \infty$.
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Erzeugnis]
+        Das \structure{Erzeugnis $\alg{a}$} von $a$ in $G$ ist die Menge aller Elemente, die durch Potenzierung von $a$ und $a^{-1}$ erhalten werden können.
+        \begin{align}
+            \alg{a} \defeq \left\{ a^k \mid k \in \alert{\Z} \right\}
+        \end{align}
+        Es gilt $\alg{a} < G$.
+    \end{definition}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Zyklische Gruppen}
+
+    \begin{definition}[Zyklische Gruppe]
+        Man nennt eine Gruppe $G$ \structure{zyklisch}, wenn ein Element $a \in G$ existiert, sodass $a$ die gesamte Gruppe erzeugt.
+        \begin{align}
+            \alg{a} = G
+        \end{align}
+        Man nennt $a$ einen \structure{Generator (oder Erzeuger)}.
+    \end{definition}
+
+    \begin{itemize}
+        \item Alle Untergruppen einer zyklischen Gruppe sind \alert{zyklisch}
+        \item Zyklische Gruppen sind isomorph zu einer $\Z_i$ oder $\Z$
+    \end{itemize}
+
+    \vfill
+
+    \begin{example}[]
+        Die ganzen Zahlen $\Z$ und alle Gruppen der Form $\alg{\Z_i, +, 0}$ sind zyklisch mit dem Generator $1$.\\
+        Betrachte $\alg{\Z_7, +, 0}$. Es ist
+        \begin{itemize}
+            \item $\Z_7 = \left\{ 0, 1, 2, 3, 4, 5, 6 \right\}$
+            \item $\alg{2} = \left\{ 2, 4, 6, 1, 3, 5, 0 \right\} = \alg{1} = \Z_7$
+        \end{itemize}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Homomorphismen}
+
+    Seien $\alg{G, \circ, e}$ und $\alg{G^\prime, \bullet, e^\prime}$ Gruppen.
+    \begin{definition}[Homomorphismus]
+        Eine Abbildung $\varphi : G \to G^\prime$ heißt \structure{Homomorphismus}, wenn gilt
+        \begin{align}
+            \varphi(a \circ b) = \varphi(a) \bullet \varphi(b)
+        \end{align}
+        Ist $\varphi$ bijektiv, so nennt man sie einen \structure{Isomorphismus}.
+    \end{definition}
+
+    \begin{itemize}
+        \item Homomorphismen sind \alert{strukturerhaltend}
+        \item Sie betten eine Gruppe in eine andere ein
+    \end{itemize}
+
+    \vfill
+
+    \begin{theorem}[]
+        Ist $\varphi : G \to G^\prime$ ein Homomorphismus, so gilt
+        \begin{itemize}
+                \item $\varphi(e) = e^\prime$
+                \item Für alle $a \in G$ gilt $\varphi(a)^{-1} = \varphi(a^{-1})$
+                \item Ist $H < G$, dann auch $\varphi(H) < G^\prime$
+        \end{itemize}
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Nebenklassen}
+
+    Sei $\alg{G, \circ, e}$ eine Gruppe und $H < G$.
+    \begin{definition}[Nebenklasse]
+        Zu einem Element $a \in G$ nennen wir
+        \begin{align}
+            aH &\defeq \left\{ ax \mid x \in H \right\}\\
+            Ha &\defeq \left\{ xa \mid x \in H \right\}
+        \end{align}
+        die \structure{linke/rechte Nebenklasse} von $a$ bezüglich $H$.\\
+        Die Anzahl der Nebenklassen zu $H$ nennt man ihren \structure{Index $\ind(G: H)$}.
+    \end{definition}
+
+    \begin{itemize}
+        \item Die Nebenklassen zu $H$ sind eine \alert{Partition} von $G$
+    \end{itemize}
+
+    \vfill
+
+    \begin{theorem}[Satz von Lagrange]
+        Ist $G$ eine endliche Gruppe, so gilt
+        \begin{align}
+            \ord(G) &= \ord(H) \cdot \ind(G : H)
+        \end{align}
+        Daraus folgt direkt \structure{$\ord(a) \mid \ord(G)$} für alle $a \in G$.
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Eulersche $\varphi$-Funktion}
+
+    \begin{definition}[Eulersche $\varphi$-Funktion]
+        Die Funktion $\varphi : \N \setminus \left\{ 0 \right\} \to \N$ heißt \structure{Eulersche $\varphi$-Funktion}. Sie ist definiert durch die Anzahl der zu $n$ \alert{teilerfremden} Zahlen.
+        \begin{align}
+            \varphi(n) \defeq \abs{\left\{ x \mid x \in [n], \ggt(x, n) = 1 \right\}}
+        \end{align}
+        \vspace{-1.5em}
+    \end{definition}
+
+    Es gilt für
+    \begin{description}[$p$ prim, $k > 0$\qquad]
+        \item[$\ggt(m, n) = 1$] $\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)$
+        \item[$p$ prim] $\varphi(p) = p - 1$
+        \item[$p$ prim, $k > 0$] $\varphi(p^k) = p^{k -1} (p - 1)$
+    \end{description}
+
+    \begin{theorem}[Euler-Fermat]
+        Für $m \in \N$ mit $m \geq 2$ und $k \in \Z$ mit $\ggt(k, m) = 1$ gilt
+        \begin{align}
+            k^{\varphi(m)} &\equiv 1 \pmod m
+            \intertext{ist $p$ prim, so gilt im speziellen}
+            k^{p - 1} &\equiv 1 \pmod p
+        \end{align}
+        \vspace{-2em}
+    \end{theorem}
+\end{frame}
+}
+
+\defineUnit{erweitertereuklid}{%
+\begin{frame}
+    \frametitle{Erweiterter Euklidscher Algorithmus}
+
+    \vspace{-1em}
+    \begin{block}{Erweiterter Euklidscher Algorithmus}
+        Der \structure{erweiterte Euklische Algorithmus} berechnet für zwei Zahlen $a, b \in \N$ ganze Zahlen $x, y \in \Z$, sodass gilt
+        \begin{align}
+            a \cdot x + b \cdot y &= \ggt(x, y)
+            %\intertext{Er verwendet dazu die Beobachtung, dass für $a > b > 0$ gilt}
+            %\ggt(a, b) &= \ggt(b, a-b)
+        \end{align}
+        \vspace{-1.5em}
+    \end{block}
+
+    \begin{example}[]
+        Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.
+        \begin{align}
+            \structure{99} &= 1 \cdot \structure{78} + \structure{21} &&\longrightarrow& \alert{21} &= \structure{99} - 1 \cdot \structure{78} \\
+            \structure{78} &= 3 \cdot \structure{21} + \structure{15} &&\longrightarrow& \alert{15} &= \structure{78} - 3 \cdot \structure{21} \\
+            \structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\
+            \structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\
+            \structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0}
+        \end{align}
+        \vspace{-1.5em}
+        \begin{align}
+            \alert{3} &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \structure{6} \\
+            &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \left( \structure{21} - 1 \cdot \structure{15} \right) = \hphantom{1}(-2) \cdot \structure{21} + \hphantom{1}3 \cdot \structure{15} \\
+            &= (-2) \cdot \structure{21} + \hphantom{1}3 \cdot \left( \structure{78} - 3 \cdot \structure{21} \right) = \hphantom{(-1)}3 \cdot \structure{78} -11 \cdot \structure{21} \\
+            &= \hphantom{(-)}3 \cdot \structure{78} - 11 \cdot \left( \structure{99} - 1 \cdot \structure{78} \right) = (-11) \cdot \alert{99} + 14 \cdot \alert{78}
+        \end{align}
+        \vspace{-2em}
+    \end{example}
+\end{frame}
+}
diff -r 6669987ffd32 -r a9b64faf4b8f notes/tex/complete_notes.tex
--- a/notes/tex/complete_notes.tex	Tue Jan 28 00:42:39 2014 +0100
+++ b/notes/tex/complete_notes.tex	Sat Feb 01 19:22:52 2014 +0100
@@ -75,4 +75,8 @@
 %ue13
 \showUnit{graphfaerbung}
 \showUnit{planaritaet}
+
+%ue14
+\showUnit{algebradefinitionen}
+\showUnit{erweitertereuklid}
 \end{document}
diff -r 6669987ffd32 -r a9b64faf4b8f notes/tex/frames.tex
--- a/notes/tex/frames.tex	Tue Jan 28 00:42:39 2014 +0100
+++ b/notes/tex/frames.tex	Sat Feb 01 19:22:52 2014 +0100
@@ -13,3 +13,4 @@
 \input{growth.tex}
 \input{combinatorics.tex}
 \input{graphs.tex}
+\input{algebra.tex}
diff -r 6669987ffd32 -r a9b64faf4b8f notes/tex/preamble.tex
--- a/notes/tex/preamble.tex	Tue Jan 28 00:42:39 2014 +0100
+++ b/notes/tex/preamble.tex	Sat Feb 01 19:22:52 2014 +0100
@@ -58,6 +58,10 @@
 \newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)}
 \newcommand{\setnot}[1]{\overline{#1}}
 \newcommand{\setsymdiff}{\,\triangle\,}
+\newcommand{\alg}[1]{\left\langle #1 \right\rangle}
+\DeclareMathOperator{\ind}{ind}
+\DeclareMathOperator{\ord}{ord}
+\DeclareMathOperator{\ggt}{ggT}
 
 \newcommand{\rel}[1]{\,\mathrm{#1}\,}
 \DeclareRobustCommand{\stirlingone}{\genfrac{[}{]}{0pt}{}}
diff -r 6669987ffd32 -r a9b64faf4b8f notes/tex/ue14_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue14_notes.tex	Sat Feb 01 19:22:52 2014 +0100
@@ -0,0 +1,12 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 14: Algebra}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{algebradefinitionen}
+\showUnit{erweitertereuklid}
+\end{document}
diff -r 6669987ffd32 -r a9b64faf4b8f notes/ue14_notes.pdf
Binary file notes/ue14_notes.pdf has changed