% 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 25
\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 f\"{u}nfundzwanzigste 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 Constraint Propagation als Methode der K\"{u}nstlichen Intelligenz zur L\"{o}sung von Logikaufgaben 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{Logiktrainer mit Computern l\"{o}sen}
\end{center}
\normalsize Anl\"{a}sslich einer diesbez\"{u}glichen Anfrage beim Mensa-Caf\'{e} m\"{o}chte ich dar\"{u}ber schreiben, wie man Aufgaben aus dem PM Logiktrainer mit Hilfe eines Computers l\"{o}sen kann.
\\
\\ Zun\"{a}chst einmal: Ja, man kann Computer programmieren, dass sie diese Aufgaben l\"{o}sen k\"{o}nnen! Es ist richtig, dass Intelligenz nichts spezifisch Menschliches ist. An der TU Wien lernt man, dass intelligentes Verhalten wahrscheinlich nur eine Frage der Berechnung ist und man daher den Computer (der im Deutschen ja auch als ``Rechner'' bezeichnet wird) ohne weiteres so programmieren kann, dass er intelligentes Verhalten an den Tag legt, welches man bislang vielleicht nur Menschen zugetraut h\"{a}tte.
\\
\\ Die einzige Schwierigkeit beim L\"{o}sen von Logiktrainer-Aufgaben durch einen Computer besteht darin, die Hinweise in eine f\"{u}r den Computer verst\"{a}ndliche Sprache zu \"{u}bersetzen. Die Verarbeitung nat\"{u}rlicher Sprache ist noch nicht so weit fortgeschritten. Aber: Einmal \"{u}bersetzt, kann der Computer die Logiktrainer-Aufgaben problemlos l\"{o}sen!
Sehen wir uns eine typische Logiktrainer-Aufgabe an: Drei M\"{a}dchen, drei Fr\"{u}chte, drei S\"{u}\ss{}igkeiten. Bei diesen Aufgaben gilt immer, dass genau eine Frucht von genau einem M\"{a}dchen gegessen wird, genau eine S\"{u}\ss{}igkeit von genau einem M\"{a}dchen bevorzugt wird und auch genau eine Frucht mit genau einer S\"{u}\ss{}igkeit assoziiert ist. Im PM-Logiktrainer wird, um die L\"{o}sung zu erleichtern, in der Regel eine Tabelle wie die folgende vorgegeben:

\begin{figure}[h!]
\includegraphics[width=96mm,height=28mm]{math25_01.jpg}
\end{figure}

\noindent Angenommen, der erste Hinweis lautet, dass Anna gern Zitronen isst. Das bedeutet, dass wir in diese Tabelle in der Zelle, die Anna und die Zitronen verbindet, ein Plus setzen. Da aber nur Anna die Zitrone isst und nicht auch die anderen M\"{a}dchen und Anna auch nur die Zitrone isst und nicht auch die anderen Fr\"{u}chte, bedeutet ein Plus in der Zelle ``Anna - Zitrone'', dass wir in demselben K\"{a}stchen in den Zellen, die in der gleichen Spalte und in der gleichen Zeile liegen, ein Minus setzen k\"{o}nnen.
\\
\\ Die Regel, dass ein Plus automatisch lauter Minus in der gleichen Zeile und der gleichen Spalte impliziert, kennt auch ein entsprechend programmierter Computer. Intern wird der Computer mit einer Datenstruktur arbeiten, die dieser Tabelle sehr \"{a}hnlich ist. Er wird wissen: Wenn ich irgendwo ein Plus setze, dann kann ich anderswo ein Minus setzen. Diese Methode nennt sich ``Constraint Propagation''. Gemeint ist: Eine ``Constraint'', also eine Einschr\"{a}nkung der M\"{o}glichkeiten, wo ich ein Plus oder ein Minus setzen darf, hat auch Auswirkungen auf andere Felder; ich ``propagiere'' also diese ``Constraint'' weiter. ``Constraint Propagation'' ist die wichtigste Methode, mit der ein Computerprogramm Logikaufgaben l\"{o}sen kann.

\begin{figure}[h!]
\includegraphics[width=96mm,height=28mm]{math25_02.jpg}
\end{figure}

\noindent Wenn ein weiterer Hinweis nun lautet, dass Anna keine Bonbons mag, dann bedeutet das zwar in erster Linie, dass ich im Feld ``Anna - Bonbon'' ein Minus setzen muss; es hat aber auch die Auswirkung, dass ich im Feld ``Bonbon - Zitrone'' ein Minus setzen muss, weil Anna ja mit der Zitrone positiv verkn\"{u}pft ist. Das hei\ss{}t, alles, was f\"{u}r Anna gilt, gilt auch f\"{u}r die Zitrone, und umgekehrt. Auch das ist ``Constraint Propagation''. Der Computer muss lediglich so programmiert werden, dass er jedesmal, wenn ein Minus gesetzt wird, \"{u}berpr\"{u}ft, ob in der gleichen Zeile oder in der gleichen Spalte ein Plus steht; wenn das der Fall ist, dann muss er diese Constraint ``propagieren''.
\\
\\ Die Aufgaben im PM Logiktrainer k\"{o}nnen ohne Ausnahme durch ``Constraint Propagation'' gel\"{o}st werden. Im Prinzip geht der Computer genauso vor, wie es auch ein ge\"{u}bter menschlicher R\"{a}tsell\"{o}ser tun w\"{u}rde.
\\
\\ Davon abgesehen, besteht f\"{u}r den Computer noch eine weitere M\"{o}glichkeit, Logikaufgaben zu l\"{o}sen: n\"{a}mlich indem er systematisch alle M\"{o}glichkeiten durchprobiert und \"{u}berpr\"{u}ft, ob sie die ``Constraints'' erf\"{u}llen. Diese Methode nennt man ``Backtracking''. Sie ist langsam, f\"{u}hrt aber in jedem Fall zum Ziel, selbst wenn ``Constraint Propagation'' nicht reicht (was zum Beispiel bei Sudoku-R\"{a}tseln vorkommen kann).
\\
\\ Ich hoffe, dass der Artikel interessant war und man daraus lernen konnte.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
