% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}
\usepackage{listings}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 17
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die siebzehnte Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Hinweis: Autoren sind f\"{u}r den Inhalt ihrer Artikel oder Werke selbst verantwortlich. Die in MATHEMATIQ ver\"{o}ffentlichten Beitr\"{a}ge widerspiegeln ausschlie\ss{}lich die Meinung ihrer Autoren und nicht jene des Vereins Mensa. Die Zusendung von Beitr\"{a}gen gilt auch als Einverst\"{a}ndnis zu deren Ver\"{o}ffentlichung in MATHEMATIQ.}
\\
\\ \textbf{Diese Ausgabe} leitet in ein neues Thema (Algorithmik) ein.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Der Euklidische Algorithmus}
\end{center}
\normalsize Ein Algorithmus ist im Allgemeinen eine Rechenvorschrift, die einen Rechner anweist, welche Schritte er auszuf\"{u}hren hat, um (irgendwann) zum gesuchten Ergebnis zu bekommen. Ein Beispiel f\"{u}r einen solchen Algorithmus ist der Euklidische Algorithmus zur Berechnung des gr\"{o}\ss{}ten gemeinsamen Teilers zweier nat\"{u}rlicher Zahlen.
\\
\\ Bekanntlich gilt f\"{u}r zwei nat\"{u}rliche Zahlen $a$ und $b$:
\\
\\ $a$ = $x$ ggT($a$, $b$),
\\ $b$ = $y$ ggT($a$, $b$),
\\
\\ beide Zahlen sind also Vielfaches dieses gemeinsamen Teilers, aber die Faktoren $x$ und $y$, die ebenfalls nat\"{u}rliche Zahlen sind, d\"{u}rfen selbst nicht Vielfache dieses gemeinsamen Teilers sein (sonst w\"{a}re es nicht der gr\"{o}\ss{}te gemeinsame Teiler).
\\
\\ Jede nat\"{u}rliche Zahl l\"{a}sst sich auch auf folgende Art darstellen:
\\
\\ $a$ = $q_1$ $r_0$ + $r_1$.
\\
\\ Solange $r_0$ eine nat\"{u}rliche Zahl kleiner als $a$ ist, kann man also $a$ durch $r_0$ dividieren. Man erh\"{a}lt dann einen ganzzahligen Quotienten $q_1$ und einen Rest $r_1$. Der Trick ist nun, wiederum $r_0$ auf diese Weise darzustellen - also als Produkt eines Quotienten $q_2$ mit dem ehemaligen Rest $r_1$ plus einem neuen Rest $r_2$. Wenn man das in die obige Gleichung einsetzt, sieht man, dass die urspr\"{u}ngliche Zahl $a$ tats\"{a}chlich, bis auf ein Vielfaches von $r_2$ als Rest, ein Vielfaches von $r_1$ ist:
\\
\\ $a$ = $q_1$ ($q_2$ $r_1$ + $r_2$) + $r_1$
\\ = $q_1$ $q_2$ $r_1$ + $q_1$ $r_2$ + $r_1$
\\ = $r_1$ ($q_1$ $q_2$ + 1) + $q_1$ $r_2$
\\
\\ Der Trick ist nun, das Ganze so lange durchzuiterieren, bis wir zu $r_n$ = 0 kommen. Denn dann wissen wir: Es gibt keinen Rest mehr; $a$ ist durch $r_{n-1}$ ohne Rest teilbar. Wir wissen aber auch, dass $r_0$ ein Vielfaches von $r_{n-1}$ ist. Somit ist $r_{n-1}$ ein gemeinsamer Teiler von $a$ und $r_0$ - und zwar der gr\"{o}\ss{}te gemeinsame Teiler. (Warum? \"{U}berlegt es euch mal!)
\\
\\ Um den gr\"{o}\ss{}ten gemeinsamen Teiler von $a$ und $b$ zu ermitteln, setzen wir also $b$ := $r_0$ und f\"{u}hren den hier skizzierten Algorithmus aus.
\\
\\ Ein Computer versteht einen in nat\"{u}rlicher Sprache angegebenen Algorithmus nicht. Deswegen werden Algorithmen normalerweise in Computersprachen \"{u}bersetzt. Nun gibt es in der Programmierung mehrere Paradigmen. Das dominante Paradigma die imperative Programmierung. Dabei weist man den Rechner Schritt f\"{u}r Schritt an, was er zu tun hat. In diesem Fall k\"{o}nnte man zum Beispiel in der Programmiersprache C das Problem wie folgt l\"{o}sen:
\\
\begin{lstlisting}
int ggt(int a, int b)
{
  while (b)
  {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}
\end{lstlisting}
\vspace{5 mm}
In der Praxis eines Programmierers wird zwar meistens so oder \"{a}hnlich gearbeitet - als eleganter gilt es jedoch, wenn man, wo immer m\"{o}glich, einen funktionalen Stil pflegt. Die Idee dahinter ist, eine Funktion nur durch andere Funktionen auszudr\"{u}cken - anders gesagt: im Rumpf der Funktion befindet sich, in C-Syntax, im Prinzip nur eine return-Anweisung. Beim Euklidischen Algorithmus l\"{a}\ss{}t sich das recht leicht bewerkstelligen, weil der Algorithmus rekursiv ausgedr\"{u}ckt werden kann (also als Funktion, die sich mit ver\"{a}nderten Parametern selbst aufruft), etwa wie folgt:
\\
\begin{lstlisting}
int ggt(int a, int b)
{
  return b ? ggt(b, a % b) : a;
}
\end{lstlisting}
\vspace{5 mm}
Es ist schon eine Kunst, einen m\"{o}glichst eleganten und effizienten Algorithmus zu finden, der ein gegebenes Problem l\"{o}st. Da es sich dabei um eines meiner Spezialgebiete im Studium handelte, werde ich wahrscheinlich noch \"{o}fter hier in MATHEMATIQ \"{u}ber dieses Thema schreiben.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
