Mercurial > 13ws.ds
comparison notes/tex/algebra.tex @ 56:1cbb4a5e6ce7
nicer euklid; ue15 notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 25 Feb 2014 00:26:19 +0100 |
| parents | 4192e96b7b3e |
| children |
comparison
equal
deleted
inserted
replaced
| 55:1cb55fb1c934 | 56:1cbb4a5e6ce7 |
|---|---|
| 266 \end{theorem} | 266 \end{theorem} |
| 267 \end{frame} | 267 \end{frame} |
| 268 } | 268 } |
| 269 | 269 |
| 270 \defineUnit{erweitertereuklid}{% | 270 \defineUnit{erweitertereuklid}{% |
| 271 %\begin{frame} | |
| 272 %\frametitle{Erweiterter Euklidscher Algorithmus} | |
| 273 | |
| 274 %\vspace{-1em} | |
| 275 %\begin{block}{Erweiterter Euklidscher Algorithmus} | |
| 276 %Der \structure{erweiterte Euklische Algorithmus} berechnet für zwei Zahlen $a, b \in \N$ ganze Zahlen $x, y \in \Z$, sodass gilt | |
| 277 %\begin{align} | |
| 278 %a \cdot x + b \cdot y &= \ggt(x, y) | |
| 279 %%\intertext{Er verwendet dazu die Beobachtung, dass für $a > b > 0$ gilt} | |
| 280 %%\ggt(a, b) &= \ggt(b, a-b) | |
| 281 %\end{align} | |
| 282 %\vspace{-1.5em} | |
| 283 %\end{block} | |
| 284 | |
| 285 %\begin{example}[] | |
| 286 %Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$. | |
| 287 %\begin{align} | |
| 288 %\structure{99} &= 1 \cdot \structure{78} + \structure{21} &&\longrightarrow& \alert{21} &= \structure{99} - 1 \cdot \structure{78} \\ | |
| 289 %\structure{78} &= 3 \cdot \structure{21} + \structure{15} &&\longrightarrow& \alert{15} &= \structure{78} - 3 \cdot \structure{21} \\ | |
| 290 %\structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\ | |
| 291 %\structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\ | |
| 292 %\structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0} | |
| 293 %\end{align} | |
| 294 %\vspace{-1.5em} | |
| 295 %\begin{align} | |
| 296 %\alert{3} &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \structure{6} \\ | |
| 297 %&= \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} \\ | |
| 298 %&= (-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} \\ | |
| 299 %&= \hphantom{(-)}3 \cdot \structure{78} - 11 \cdot \left( \structure{99} - 1 \cdot \structure{78} \right) = (-11) \cdot \alert{99} + 14 \cdot \alert{78} | |
| 300 %\end{align} | |
| 301 %\vspace{-2em} | |
| 302 %\end{example} | |
| 303 %\end{frame} | |
| 304 | |
| 271 \begin{frame} | 305 \begin{frame} |
| 272 \frametitle{Erweiterter Euklidscher Algorithmus} | 306 \frametitle{Erweiterter Euklidscher Algorithmus} |
| 273 | 307 |
| 274 \vspace{-1em} | 308 \vspace{-1em} |
| 275 \begin{block}{Erweiterter Euklidscher Algorithmus} | 309 \begin{block}{Erweiterter Euklidscher Algorithmus} |
| 290 \structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\ | 324 \structure{21} &= 1 \cdot \structure{15} + \hphantom{1}\structure{6} &&\longrightarrow& \alert{6} &= \structure{21} - 1 \cdot \structure{15} \\ |
| 291 \structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\ | 325 \structure{15} &= 2 \cdot \hphantom{1}\structure{6} + \hphantom{1}\structure{3} &&\longrightarrow& \alert{3} &= \structure{15} - 2 \cdot \structure{6} \\ |
| 292 \structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0} | 326 \structure{6} &= 2 \cdot \hphantom{1}\structure{3} + \hphantom{1}\structure{0} |
| 293 \end{align} | 327 \end{align} |
| 294 \vspace{-1.5em} | 328 \vspace{-1.5em} |
| 295 \begin{align} | 329 \begin{alignat}{2} |
| 296 \alert{3} &= \hphantom{(-)}1 \cdot \structure{15} - \hphantom{1}2 \cdot \structure{6} \\ | 330 \alert{21} &= 1 \cdot \structure{99} - 1 \cdot \structure{78} \\ |
| 297 &= \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} \\ | 331 \alert{15} &= 1 \cdot \structure{78} - 3 \cdot \structure{21} &&= -\hphantom{1}3 \cdot \structure{99} + \hphantom{1}4 \cdot \structure{78} \\ |
| 298 &= (-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} \\ | 332 \alert{6} &= 1 \cdot \structure{21} - 1 \cdot \structure{15} &&= \hphantom{-1}4 \cdot \structure{99} - \hphantom{1}5 \cdot \structure{78} \\ |
| 299 &= \hphantom{(-)}3 \cdot \structure{78} - 11 \cdot \left( \structure{99} - 1 \cdot \structure{78} \right) = (-11) \cdot \alert{99} + 14 \cdot \alert{78} | 333 \alert{3} &= 1 \cdot \structure{15} - 2 \cdot \hphantom{1}\structure{6} &&= -11 \cdot \structure{99} + 14 \cdot \structure{78} |
| 300 \end{align} | 334 \end{alignat} |
| 301 \vspace{-2em} | 335 \vspace{-2em} |
| 302 \end{example} | 336 \end{example} |
| 303 \end{frame} | 337 \end{frame} |
| 338 | |
| 339 \begin{frame} | |
| 340 \frametitle{Erweiterter Euklidscher Algorithmus} | |
| 341 | |
| 342 \begin{theorem}[] | |
| 343 Die vorhergehende Rechnung kann kompakter in einer Tabelle dargestellt werden. Setze dazu | |
| 344 \begin{align} | |
| 345 q_k &= r_{k-1} \div r_k & s_k &= s_{k-2} - s_{k-1} \cdot q_{k-1} \\ | |
| 346 r_k &= r_{k-2} \mod r_{k-1} & t_k &= t_{k-2} - t_{k-1} \cdot q_{k-1} | |
| 347 \end{align} | |
| 348 Und initialisiere die Tabelle folgendermaßen: | |
| 349 \begin{center} | |
| 350 \tabulinesep=3pt | |
| 351 \begin{tabu} {c|[1pt]cccc} | |
| 352 $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-} | |
| 353 0 & - & 99 & 1 & 0 \\ | |
| 354 1 & & 78 & 0 & 1 \\ | |
| 355 $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ | |
| 356 n & - & 0 & - & - | |
| 357 \end{tabu} | |
| 358 \end{center} | |
| 359 Dann gilt für jedes $k$: $a \cdot s_k + b \cdot t_k = r_k$ und | |
| 360 \begin{align} | |
| 361 a \cdot s_{n-1} + b \cdot t_{n-1} = \ggt(a,b) | |
| 362 \end{align} | |
| 363 \end{theorem} | |
| 364 \end{frame} | |
| 365 | |
| 366 \begin{frame} | |
| 367 \frametitle{Erweiterter Euklidscher Algorithmus} | |
| 368 | |
| 369 \begin{example}[] | |
| 370 Seien $a = 99$, $b = 78$ mit $\ggt(99, 78) = 3$.\\ | |
| 371 | |
| 372 \begin{center} | |
| 373 \tabulinesep=3pt | |
| 374 \begin{tabu} {c|[1pt]cccc} | |
| 375 $k$ & $q_k$ & $r_k$ & $s_k$ & $t_k$\\\tabucline[1pt]{-} | |
| 376 0 & - & \structure{99} & 1 & 0 \\ | |
| 377 1 & 1 & \structure{78} & 0 & 1 \\ | |
| 378 2 & 3 & 21 & 1 & -1 \\ | |
| 379 3 & 1 & 15 & -3 & 4 \\ | |
| 380 4 & 2 & 6 & 4 & -5 \\ | |
| 381 5 & 2 & \alert{3} & \alert{-11} & \alert{14} \\ | |
| 382 6 & - & 0 & - & - | |
| 383 \end{tabu} | |
| 384 \end{center} | |
| 385 | |
| 386 Es ist $\alert{3} = \alert{-11} \cdot \structure{99} + \alert{14} \cdot \structure{78}$. | |
| 387 \end{example} | |
| 388 \end{frame} | |
| 304 } | 389 } |