% 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 26
\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 sechsundzwanzigste 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} besch\"{a}ftigt sich mit Methoden der K\"{u}nstlichen Intelligenz zur L\"{o}sung von Denksportaufgaben durch den Computer.
\\
\\ 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{Denksportaufgaben mit Computern l\"{o}sen}
\end{center}
\normalsize Heute ist mir im Internet ein R\"{a}tsel untergekommen, das sehr leicht mit einem Computer gel\"{o}st werden kann und als gute Illustration zur Demonstration eines allgemeinen Prinzips der K\"{u}nstlichen Intelligenz dient.
\\
\\ Eine sechsk\"{o}pfige Familie (Mutter, Vater, je zwei T\"{o}chter und zwei S\"{o}hne) sowie ein Str\"{a}fling und ein Polizist stehen auf einer Seite des Flusses und wollen diesen mit Hilfe eines Bootes \"{u}berqueren. Das Boot kann von einer Seite des Flusses zur anderen fahren, aber nur jeweils zwei Personen gleichzeitig transportieren. Eine davon muss in der Lage sein, das Boot zu steuern; dazu sind nur die Mutter, der Vater und der Polizist imstande. Ferner darf niemals die Mutter mit einem Sohn zusammen ohne den Vater auf einer Seite des Flusses stehen, ebenso wenig der Vater zusammen mit einer Tochter ohne die Mutter. Au\ss{}erdem darf niemals der Str\"{a}fling mit einem anderen Familienmitglied zusammen auf einer Seite des Flusses stehen, ohne dass auch der Polizist dabei w\"{a}re.
\\
\\ Solche R\"{a}tsel k\"{o}nnen mit Computern leicht gel\"{o}st werden. Man muss sich zun\"{a}chst Gedanken \"{u}ber die Repr\"{a}sentation der Daten machen. Wir haben acht Personen, jede Person ist entweder auf der einen oder auf der anderen Seite des Flusses. Also haben wir acht Bin\"{a}rvariablen, damit insgesamt $2^8$, also 256 verschiedene Zust\"{a}nde. Der Urzustand ist dezimal gleich der Zahl 0, der Endzustand gleich 255. Ferner wissen wir, dass in jedem ungeraden Schritt eine oder zwei Nullen zu Einsen umgewandelt werden und in jedem geraden Schritt eine oder zwei Einsen zu Nullen. Dabei sind aber nicht alle Zustands\"{u}berg\"{a}nge erlaubt. Verboten sind etwa Zust\"{a}nde, in denen der Vater und eine Tochter den Wert 0 haben, die Mutter aber den Wert 1.
\\
\\ Man kann nun, ausgehend vom Urzustand, alle Folgezust\"{a}nde errechnen und von jedem einzelnen dieser Folgezust\"{a}nde wiederum die Folgezust\"{a}nde zweiter Ordnung und so weiter. Im Prinzip erh\"{a}lt man dadurch einen Graphen: Von jedem Zustand verweist ein Pfeil auf jeden m\"{o}glichen Folgezustand. Effektiv kann man diesen Graphen in Form einer Adjazenzmatrix darstellen, also in Form eines zweidimensionalen Arrays, dessen erster Index der Nummer des Ausgangszustands entspricht und dessen zweiter Index die Nummer des Folgezustands angibt. Dieser Array belegt $256^2$, also 65536 Bit. Den k\"{u}rzesten Pfad vom Urzustand zum Endzustand zu finden, bewerkstelligt man dann wahlweise mit einer Breiten- oder einer Tiefensuche. Eine Breitensuche sieht sich immer zuerst alle Folgezust\"{a}nde an, dann die Folgezust\"{a}nde all dieser Folgezust\"{a}nde und so weiter, wohingegen eine Tiefensuche zuerst mit einem Folgezustand beginnt, dann den ersten Folgezustand dieses Folgezustands \"{u}berpr\"{u}ft und so weiter; erst wenn man auf diese Weise, wenn man schon sehr in die ``Tiefe'' vorgedrungen ist, in eine Sackgasse ger\"{a}t, macht man beim zweiten Folgezustand des Urzustands weiter. Klar ist jedenfalls, dass man keinen Zustand mehr als einmal betrachten muss; gelangt man in eine Schleife, wei\ss{} man also, dass man diesen Pfad nicht weiter beschreiten muss.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
