# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1393284379 -3600
# Node ID 1cbb4a5e6ce7c2c25ee7f698af9d52924a61a934
# Parent  1cb55fb1c934b34a27bf7329c98bc365fe0163d3
nicer euklid; ue15 notes

diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/complete_notes.pdf
Binary file notes/complete_notes.pdf has changed
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/tex/algebra.tex
--- a/notes/tex/algebra.tex	Sat Feb 15 17:57:11 2014 +0100
+++ b/notes/tex/algebra.tex	Tue Feb 25 00:26:19 2014 +0100
@@ -268,6 +268,40 @@
 }
 
 \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}
+
 \begin{frame}
     \frametitle{Erweiterter Euklidscher Algorithmus}
 
@@ -292,13 +326,64 @@
             \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}
+        \begin{alignat}{2}
+            \alert{21} &= 1 \cdot \structure{99} - 1 \cdot \structure{78} \\
+            \alert{15} &= 1 \cdot \structure{78} - 3 \cdot \structure{21} &&= -\hphantom{1}3 \cdot \structure{99} + \hphantom{1}4 \cdot \structure{78} \\
+            \alert{6} &= 1 \cdot \structure{21} - 1 \cdot \structure{15} &&= \hphantom{-1}4 \cdot \structure{99} - \hphantom{1}5 \cdot \structure{78} \\
+            \alert{3} &= 1 \cdot \structure{15} - 2 \cdot \hphantom{1}\structure{6} &&= -11 \cdot \structure{99} + 14 \cdot \structure{78}
+        \end{alignat}
         \vspace{-2em}
     \end{example}
 \end{frame}
+
+\begin{frame}
+    \frametitle{Erweiterter Euklidscher Algorithmus}
+
+    \begin{theorem}[]
+        Die vorhergehende Rechnung kann kompakter in einer Tabelle dargestellt werden. Setze dazu
+        \begin{align}
+            q_k &= r_{k-1} \div r_k & s_k &= s_{k-2} - s_{k-1} \cdot q_{k-1} \\
+            r_k &= r_{k-2} \mod r_{k-1} & t_k &= t_{k-2} - t_{k-1} \cdot q_{k-1}
+        \end{align}
+        Und initialisiere die Tabelle folgendermaßen:
+        \begin{center}
+            \tabulinesep=3pt
+            \begin{tabu} {c|[1pt]cccc}
+                $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-}
+                0 & - & 99 & 1 & 0 \\
+                1 &   & 78 & 0 & 1 \\
+                $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\
+                n & - & 0 & - & -
+            \end{tabu}
+        \end{center}
+        Dann gilt für jedes $k$: $a \cdot s_k + b \cdot t_k = r_k$ und
+        \begin{align}
+            a \cdot s_{n-1} + b \cdot t_{n-1} = \ggt(a,b)
+        \end{align}
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Erweiterter Euklidscher Algorithmus}
+
+    \begin{example}[]
+        Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.\\
+
+        \begin{center}
+            \tabulinesep=3pt
+            \begin{tabu} {c|[1pt]cccc}
+                $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-}
+                0 & - & \structure{99} & 1 & 0 \\
+                1 & 1 & \structure{78} & 0 & 1 \\
+                2 & 3 & 21 & 1 & -1 \\
+                3 & 1 & 15 & -3 & 4 \\
+                4 & 2 & 6 & 4 & -5 \\
+                5 & 2 & \alert{3} & \alert{-11} & \alert{14} \\
+                6 & - & 0 & - & -
+            \end{tabu}
+        \end{center}
+
+        Es ist $\alert{3} = \alert{-11} \cdot \structure{99} + \alert{14} \cdot \structure{78}$.
+    \end{example}
+\end{frame}
 }
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/tex/complete_notes.tex
--- a/notes/tex/complete_notes.tex	Sat Feb 15 17:57:11 2014 +0100
+++ b/notes/tex/complete_notes.tex	Tue Feb 25 00:26:19 2014 +0100
@@ -79,4 +79,7 @@
 %ue14
 \showUnit{algebradefinitionen}
 \showUnit{erweitertereuklid}
+
+%ue15
+\showUnit{klausurstoff}
 \end{document}
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/tex/frames.tex
--- a/notes/tex/frames.tex	Sat Feb 15 17:57:11 2014 +0100
+++ b/notes/tex/frames.tex	Tue Feb 25 00:26:19 2014 +0100
@@ -14,3 +14,4 @@
 \input{combinatorics.tex}
 \input{graphs.tex}
 \input{algebra.tex}
+\input{outro.tex}
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/tex/outro.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/outro.tex	Tue Feb 25 00:26:19 2014 +0100
@@ -0,0 +1,67 @@
+\defineUnit{klausurstoff}{%
+    \begin{frame}
+        \frametitle{Klausurstoff}
+
+        \begin{columns}
+            \begin{column}{.45\textwidth}
+                \begin{itemize}
+                    \item Basics
+                        \begin{itemize}
+                            \item Mengenoperationen
+                            \item Relationen
+                            \item Funktionen
+                        \end{itemize}
+                    \vspace{1em}
+                    \item Logik
+                        \begin{itemize}
+                            \item Äquivalenzregeln
+                            \item \structure{KNF und DNF}
+                            \item \structure{DPLL}
+                            \item \structure{Resolution}
+                            \item Natürliches Schließen
+                            \item (Wohlfundierte) Induktion
+                        \end{itemize}
+                    \vspace{1em}
+                    \item Landausymbole
+                        \begin{itemize}
+                            \item Quantorenschreibweise
+                            \item Grenzwertschreibweise
+                        \end{itemize}
+                    \vspace{1em}
+                    \item Kombinatorik
+                        \begin{itemize}
+                            \item Binomialkoeffizienten
+                            \item Doppeltes Abzählen
+                            \item Schubfachprinzip
+                            \item Inklusion/Exklusion
+                            \item Stirlingzahlen
+                        \end{itemize}
+                \end{itemize}
+            \end{column}
+            \begin{column}{.55\textwidth}
+                \begin{itemize}
+                    \item Graphentheorie
+                        \begin{itemize}
+                            \item Einfache \& gerichtete Graphen
+                            \item \structure{Prüfercode}
+                            \item \structure{Gradfolgen}
+                            \item \structure{Spannbäume \& Eulertouren}
+                            \item Färung \& Planarität
+                            \item (Matchings)
+                        \end{itemize}
+                    \vspace{1em}
+                    \item Algebra
+                        \begin{itemize}
+                            \item Gruppendefinition
+                            \item Untergruppen
+                            \item Erzeugnisse
+                            \item Modulo-Rechnung
+                            \item \structure{Erweiterter Euklid}
+                            \item Isomorphien
+                            \item (RSA)
+                        \end{itemize}
+                \end{itemize}
+            \end{column}
+        \end{columns}
+    \end{frame}
+}
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/tex/ue15_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue15_notes.tex	Tue Feb 25 00:26:19 2014 +0100
@@ -0,0 +1,11 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Wiederholungsübung}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{klausurstoff}
+\end{document}
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/ue14_notes.pdf
Binary file notes/ue14_notes.pdf has changed
diff -r 1cb55fb1c934 -r 1cbb4a5e6ce7 notes/ue15_notes.pdf
Binary file notes/ue15_notes.pdf has changed