% 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 18
\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 achtzehnte 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} setzt das Thema (Algorithmik) fort.
\\
\\ 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 Sieb des Eratosthenes}
\end{center}
\normalsize Man kennt noch keine allgemeing\"{u}ltige einfache Formel zur Ermittlung von Primzahlen. Wohl gibt es aber einen sehr einfachen Algorithmus dazu. Dieser Algorithmus dient dazu, s\"{a}mtliche Primzahlen zwischen 2 und einer gegebenen Zahl $n$ zu finden, wobei $n$ im Prinzip beliebig gro\ss{}, aber nicht unendlich sein darf. Der Algorithmus ist unter der Bezeichnung ``Sieb des Eratosthenes'' bekannt und ist ein gutes Beispiel f\"{u}r einen immer noch recht einfachen Algorithmus, der uns aber einige neue Konzepte der Algorithmik n\"{a}herbringen wird.
\\
\\ Die Idee des Algorithmus: Wir schreiben zuerst alle Zahlen von 2 bis $n$ auf, gehen dann die Zahlen der Reihe nach, von der kleinsten bis zur gr\"{o}\ss{}ten, durch und streichen alle Vielfachen, denn diese k\"{o}nnen ja keine Primzahlen sein. Logischerweise sind alle Zahlen, die am Ende \"{u}brig bleiben, Primzahlen.
\\
\\ Wie setzt man das am Computer um? Wir ben\"{o}tigen in diesem Fall eine Datenstruktur, die sich Feld oder englisch Array nennt. Dabei handelt es sich quasi um eine Ansammlung von K\"{a}stchen, in die wir Werte stecken k\"{o}nnen. Jedes K\"{a}stchen hat eine Nummer. Diese Nummer ist in diesem Fall die Zahl, und im K\"{a}stchen wollen wir speichern, ob diese Zahl Primzahl ist oder nicht.
\\
\\ Man k\"{o}nnte nun meinen, dass es pro Zahl drei Zust\"{a}nde g\"{a}be: Entweder ist noch unbekannt, ob die Zahl Primzahl ist, oder sie ist Primzahl, oder sie ist keine Primzahl. Das w\"{u}rde bedeuten, dass wir pro Zahl 2 Bit speichern m\"{u}ssten, denn die Zahl drei ist als Dualzahl zweistellig. In Wirklichkeit brauchen wir aber nur 1 Bit, denn es gen\"{u}gen zwei Zust\"{a}nde: ``undefiniert oder Primzahl'' bzw. ``keine Primzahl''. Das ist deswegen m\"{o}glich, weil wir in einer Variablen speichern, wie weit wir schon mit dem Algorithmus sind - welche Zahlen wir schon gew\"{a}hlt haben, um die Vielfachen dieser Zahlen zu markieren. Wir k\"{o}nnen daher jederzeit feststellen, ob die Primzahlen-Eigenschaft einer Zahl undefiniert oder positiv ist: denn jene Zahlen, die wir schon untersucht haben und die als ``undefiniert oder Primzahl'' markiert sind, sind Primzahlen, und die \"{u}brigen Zahlen, die als ``undefiniert oder Primzahl'' markiert sind, sind noch undefiniert. Wir brauchen also f\"{u}r $n$ Zahlen nur $n$ - 1 Bit. Das ist eine sehr schlanke Datenstruktur.
\\
\\ Der Code s\"{a}he in etwa wie folgt aus:
\\
\begin{lstlisting}
char *eratosthenes(int n)
{
  char *array = new char[n];
  int i, j;
  for (i = 0; i < n; i++) array[i] = 0;
  for (i = 0; i < n; i++)
    for (j = i + i; j < n; j += i) array[j] = 1;
  return array;
}
\end{lstlisting}
\vspace{5 mm}
Nota bene: Diese Implementierung arbeitet mit Arrays vom Datentyp ``char'', in dieser Implementierung nimmt also jedes Feldelement 8 Bit ein, obwohl eigentlich 1 Bit reichen w\"{u}rde. Dadurch wird zwar theoretisch viel Speicherplatz verschwendet, in der Praxis ist das Ganze aber auf diese Weise sowohl einfacher zu implementieren als auch schneller, weil man bei modernen Rechnern nicht so einfach einzelne Bits adressieren kann - man m\"{u}sste dazu so genannte Masken berechnen, was den Algorithmus etwas langsamer machen w\"{u}rde. Eine m\"{o}gliche Implementierung mit Verwendung solcher Masken w\"{a}re jedenfalls:
\\
\begin{lstlisting}
char rol(char x)
{
  x <<= 1;
  if (!x) x = 1;
  return x;
}

char *eratosthenes(int n)
{
  char *array = new char[n / 8 + 1];
  int i, j, k, x;
  for (i = 0; i < n / 8 + 1; i++) array[i] = 0;
  for (i = 0; i < n; i++)
    for (j = i + i, k = j / 8, x = 1 << (j % 8);
	     j < n; j += i, k += i / 8)
	{
	  array[k] |= x;
	  x = rol(x);
	  if (x == 1) k++;
	}
  return array;
}
\end{lstlisting}
\vspace{5 mm}
Man sieht, dass ein solcher Code schon um Einiges schwieriger zu lesen ist und von Programmierkonzepten Gebrauch macht, die f\"{u}r Anf\"{a}nger nicht so leicht zu durchschauen sind. Da heutige Computer in der Regel \"{u}ber sehr viel Arbeitsspeicher verf\"{u}gen, lohnt sich dieser Aufwand, einzelne Bits zu adressieren, nicht.
\\
\\ Wie komplex ist dieser Algorithmus? Wir sehen auf den ersten Blick: Jede Zahl wird einmal genommen, um daraus Vielfache zu bilden. Die Anzahl der Vielfachen betr\"{a}gt selbst h\"{o}chstens $n$ (eigentlich sogar einen Bruchteil von $n$). Der Algorithmus ist also polynomiell. Als grobe obere Schranke l\"{a}sst sich O($n^2$) angeben.
\\
\\ Tats\"{a}chlich ist der Algorithmus aber sogar noch eine Spur effizienter. Es ist n\"{a}mlich so, dass f\"{u}r die Zahl 2 nur $n$/2 Vielfache untersucht werden m\"{u}ssen, f\"{u}r die Zahl 3 nur $n$/3 Vielfache usw. Insgesamt also $n$ * $\sum_{i=2}^{n}$ Vielfache. Die Summe $\sum_{i=2}^{n}$ hat einen besonderen Namen: Man bezeichnet sie auch als ``Harmonische Zahl'' $H_n$. Es gilt $H_n \approx \log(n)$, die $n$-te Harmonische Zahl ist also asymptotisch ungef\"{a}hr gleich dem Logarithmus von $n$. (Das kann man so salopp sagen, ohne die Basis des Logarithmus zu ber\"{u}cksichtigen, weil ja gilt, dass der Logarithmus zu einer beliebigen Basis $x$ ein Vielfaches - oder ein Bruchteil - des Logarithmus zu einer beliebigen anderen Basis $y$ ist: $\log_x a$ = $\log_y a$/$\log_y x$. Asymptotisch gesehen ist die Basis des Logarithmus also egal.) Eine engere obere Schranke f\"{u}r die Komplexit\"{a}t des Algorithmus ``Sieb des Erathostenes'' betr\"{a}gt also O($n \log(n)$).
\\
\\ Ein bisschen lie\ss{}e sich der Algorithmus noch verbessern: Man muss n\"{a}mlich nicht von 2 bis $n$ iterieren, sondern nur von 2 bis $\sqrt{n}$, denn zu diesem Zeitpunkt sind bereits alle Nicht-Primzahlen markiert. So l\"{a}sst sich die Komplexit\"{a}t also auf
\\
\\ O($\sqrt(n) \log(n)$)
\\
\\ reduzieren. (Da $\log(\sqrt(n)) = 1/2 \log(n)$, ergibt sich 1/2 als Proportionalit\"{a}tsfaktor; bei der Komplexit\"{a}tsanalyse werden diese Faktoren weggelassen, weil sie an der in der ``Big-O-Notation'' angegebenen Komplexit\"{a}t nichts \"{a}ndern.)
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Neuigkeiten und Weblinks}
\end{center}
\normalsize Zun\"{a}chst einmal freut es mich, mitteilen zu d\"{u}rfen, dass unser Mitglied Clemens Raab vor kurzem unter den Auspizien des Bundespr\"{a}sidenten in Mathematik promoviert wurde. Herzliche Gratulation! Seine Homepage ist unter der Adresse
\\
\\ \url{http://www.risc.jku.at/home/craab}
\\
\\ zu finden - dort kann auch seine Dissertation heruntergeladen und begutachtet werden. Sein Spezialgebiet ist die Integralrechnung, auf diesem Gebiet gibt es offensichtlich auch noch Einiges zu erforschen - was man in der Schule darüber lernt, ist noch nicht der Weisheit letzter Schluss.
\\
\\ Ich m\"{o}chte ferner auf eine Website aufmerksam machen, die ich vor kurzem entdeckt habe: Unter der Adresse \url{http://philosophy.lander.edu/logic/index.html} findet sich ein Kurs ``Philosophy 103: Introduction to Logic''. Dieser k\"{o}nnte f\"{u}r alle interessant sein, die \"{u}ber ausreichende Englischkenntnisse verf\"{u}gen und denen mein Artikel in der ersten Ausgabe von MATHEMATIQ \"{u}ber das Thema Logik noch nicht genug war.
\\
\\ Au\ss{}erdem Dank an Michael Ziegler f\"{u}r einen Link zum Thema Physik: Auf
\\
\\ \url{https://www.simonsfoundation.org/quanta/}
\\ \url{20130917-a-jewel-at-the-heart-of-quantum-physics/}
\\
\\ steht: ``Physicists have discovered a jewel-like geometric object that dramatically simplifies calculations of particle interactions and challenges the notion that space and time are fundamental components of reality.'' Was davon zu halten ist, ist eine Frage, mit der ich mich noch besch\"{a}ftigen muss.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
