\documentclass[12pt]{article}

\textheight 25cm \voffset -2cm

\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{url}

\title{
  Projektvorschlag für Wissenschaftssommer 2008: \\
  Die schwersten Spiele ihrer Klasse
}
\author{Johannes Waldmann und Wolfgang Wittig, HTWK Leipzig}

\begin{document}
\maketitle

\part{Allgemeines}

\section{Inhalt}

\begin{itemize}
\item praktische Aufgabenstellungen (Ressourcen-Zuordnung, Wegplanung usw.)
\item werden mathematisch exakt modelliert
\item die Modelle sind oft Spiele (Puzzles)
\item ausgehend von Modellen kann man algorithmische Lösungen finden
\item und die Schwere der Aufgabe/Effizienz der Lösung einordnen
\item in der Informatik: Komplexitätstheorie,
\item mathematische Grundlagen: diskrete Mathematik, Kombinatorik, Graphentheorie
\end{itemize}

\section{Zielgruppe}

Schüler ab 5. Klasse; deren Lehrer;
allgemein wissenschaftlich interessierte Öffentlichkeit.

\section{Methode}

\begin{itemize}
\item
  konkrete Exponate zum Ausprobieren (Spiele, Puzzles)
\item
  Zuordnung der Spiele zu Motivation (Anwendung)
  und Theore (Komplexitätsklasse) durch Poster, Handzettel, Standbetreuer
\item
  Interaktive Webseite zum Betrachten von Aufgaben
  (die z. T. den Exponaten entsprechen),
  Eingeben von Lösungen, mit sofortiger Bewertung
  und Speicherung für Sammelauswertung (Highscores)
  nach gewisser Zeit.
\end{itemize}

\section{Partner, verwandte Projekte}

\begin{itemize}
\item
  E-Testing-Werkzeug autotool \url{http://www.imn.htwk-leipzig.de/~waldmann/autotool/}
  
  mit noch anzupassender, speziell zugeschnittener Benutzeroberfläche
\item
  Leipziger Schülergesellschaft für Mathematik 
  \url{http://www.lsgm.de/}

  langjährige Erfahrung in der mathematischen Schülerbildung
\end{itemize}

\section{erwünschte Nebenwirkungen}

\begin{itemize}
\item
  (Highscore/Preis-)Aufgaben über einen längeren Zeitraum (Woche) online:
  länger anhaltende Beschäftigung (als nur einmal kurz am Exponat);
  z. B. können sich Schüler im Unterricht weiter mit Aufgaben auseinandersetzen
  (dazu evtl. kurze Handreichung für interessierte Lehrer ausarbeiten)
\item
  Bei Bearbeitung der Online-Aufgaben: deutlicher Verweis (Links usw.)
  auf HTWK (Studienwerbung) und LSGM (erhöht Attraktivität)
\item
  Aufgaben-Webseite kann zu diesen Zwecken auch unabhängig weiter genutzt werden
\item
  Preise gestiftet von Sponsoren, z. B. lokale IT-Unternehmen
  (\glqq wer diese Aufgabe lösen kann, wird sofort eingestellt\glqq u.ä.)
\end{itemize}


\part{Mögliche Exponate/Aufgabentypen (gegenständlich)}

\section{Komplexität von (Such)problemen}

Idee: je ein Beispiel aus Komplexitätsklassen
\begin{itemize}
\item P: Sortieren

  Sortieren (von verdeckten Spielkarten) mit möglichst wenig Fragen

\item NP: Graphenfärben, Vertex Cover

  Graph ausdrucken (A3), Knotenfärben, Knotenüberdeckung durch Spielsteine

\item NP: SAT 

  

\item NP: Binpacking

  

\item PSPACE: Verschiebe-Puzzles (Lunar Lockout usw.)
\item RE: Postsches Korrespondenzproblem
\end{itemize}
jeweils Diskussion der Größe des Suchraumes möglich


\part{Mögliche Exponate/Aufgabentypen (Online)}



Können getestet werden unter
\url{https://autotool.imn.htwk-leipzig.de/cgi-bin/Super.cgi}
Schule: HTWK, Matrikel: 319, Passwort: loqzotepos, Semester: Sommer07,
Vorlesung: WEL-Demonstration.


\subsection{Sortiernetze}

Ein Komparator ordnet zwei Eingaben (Ausgaben: max oben, min unten).
Ein Netz besteht aus mehreren (möglichst wenigen) Komparatoren.

Beispiel (Sortier-Direct-12):

\begin{verbatim}
Finden Sie ein Sortiernetz für 6 Eingänge
mit weniger als 15 Komparatoren.

gelesen: mkNetz [ ( 1 , 2 ) , ( 2 , 3 ) , ( 1 , 2 ) , ( 3 , 4 )
                , ( 2 , 3 ) , ( 1 , 2 ) , ( 4 , 5 ) , ( 5 , 6 ) , ( 4 , 5 )
                , ( 3 , 4 ) , ( 2 , 3 ) , ( 1 , 2 )
                ]

partiell korrekt?

Ihr Netz ist: ------------------------------o------------------------------
                                            v                              
              ------------------------o-----o-----o------------------------
                                      v           v                        
              ------------------o-----o-----------o-----o------------------
                                v                       v                  
              ------------o-----o-----o-----------------o-----o------------
                          v           v                       v            
              ------o-----o-----o-----o-----o-----------------o-----o------
                    v           v           v                       v      
              ------o-----------o-----------o-----------------------o------

total korrekt?

Diese Eingabe wird nicht korrekt geordnet:
    [ 5 , 6 , 1 , 2 , 3 , 4 ]
Das Netz berechnet die Ausgabe:
    [ 1 , 2 , 3 , 5 , 4 , 6 ]
Die Rechung des Netzes ist:
    ---------------------------4--o--6---------------------------
                                  v                              
    ---------------------3--o--6--o--4--o--4---------------------
                            v           v                        
    ---------------2--o--6--o--3-----3--o--3--o--5---------------
                      v                       v                  
    ---------1--o--6--o--2--o--5-----------5--o--3--o--3---------
                v           v                       v            
    ---6--o--6--o--1--o--5--o--2--o--2-----------2--o--2--o--2---
          v           v           v                       v      
    ---5--o--5-----5--o--1-----1--o--1-----------------1--o--1---
\end{verbatim}

\subsection{Graphenfärben}

Gegeben ist ein Graph (Bild), gesucht eine konfliktfreie Knotenfärbung
mit vorgegebener Farbzahl.

Test: Col-Quiz-4

\subsection{Lunar Lockout}

Beispiel (Robots-Quiz-4)

\begin{verbatim}
Geben Sie eine Zugfolge an,
die den Roboter (Großbuchstabe)
ins Ziel (entsprechender Kleinbuchstabe) bringt:

    C . A . . . B 
    . . e . . . . 
    D . . . . . . 
    . . . . . . . 
    . . . . . E . 

gelesen: [ ( "A" , O ) , ( "E" , N ) , ( "A" , W ) ]

partiell korrekt?

C . A . . . B 
. . e . . . . 
D . . . . . . 
. . . . . . . 
. . . . . E . 
    nächster Zug: ( "A" , O )

C . . . . A B 
. . e . . . . 
D . . . . . . 
. . . . . . . 
. . . . . E . 
    nächster Zug: ( "E" , N )

C . . . . A B 
. . e . . E . 
D . . . . . . 
    nächster Zug: ( "A" , W )

C A . . . . B 
. . e . . E . 
D . . . . . . 

total korrekt?

C A . . . . B 
. . e . . E . 
D . . . . . . 

Sind alle Roboter an ihren Zielpunkten?
Diese ja:  [ ]
Diese nicht:  [ Robot { name = "E" , position = ( 2 , 1 )
                      , ziel = Just ( -1 , 1 )
                      }
              ]
\end{verbatim}


\subsection{Postsches Korrespondenzproblem}

Test: PCProblem-Quiz-4

\begin{verbatim}
Lösen Sie diese Instanz des Postschen Korrespondenz-Problems:
    PCP [ ( "cb" , "aa" ) , ( "b" , "cb" ) , ( "cabaab" , "cab" )
        , ( "c" , "b" )
        ]

gelesen: [ 3 , 1 , 4 , 2 , 3 ]

Aus Ihrer Folge entstehen die Zeichenketten:
cabaabcbcbcabaab
cabaabcbcab

Die eine muß ein Präfix der anderen sein,
nach Löschen des gemeinsamen Präfixes
    "cabaabcbc"
entstehen jedoch die Reste
    ( "bcabaab" , "ab" )
\end{verbatim}


\section{Codierungstheorie}

Beispiel (Hamming-Direct-6)

\begin{verbatim}
Gesucht ist ein Code (als Liste von Wörtern über L, R)
mit diesen Eigenschaften:
    Config { width = ( Atmost , 6 )     -- Wortlänge
           , size = ( Atleast , 4 )     -- Anzahl der Wörter
           , distance = ( Atleast , 3 ) -- Hamming-Abstand
           , optimize = Size            -- möglichst viele Wörter
           }

gelesen: [ [ L , L , L , L , L , L ] , [ R , R , R , L , L , L ]
         , [ L , L , L , R , R , R ] , [ R , R , R , R , R , R ]
         , [ R , L , R , L , R , L ]
         ]

Haben alle Code-Wörter die gleiche Länge?

Ja: 6

Die Hamming-Weite dieses Codes ist: 2
zwei Wörter mit diesem Abstand sind: ( [ R , R , R , L , L , L ]
                                     , [ R , L , R , L , R , L ]
                                     )

total korrekt?

die Width soll höchstens 6 sein

    Ja.

die Size soll wenigstens 4 sein

    Ja.

die Distance soll wenigstens 3 sein

    Nein.
\end{verbatim}

Diskussion: wie man mit algebraischen Überlegungen günstige Codes konstruiert,
Verweis auf Verwendung in Mobilfunk, Datenspeicherung auf CD usw.

\section{Algebraische Ausdrücke (Operatoren)}

\subsection{Mengen}

\verb|Algebraic_Set-Direct-2|

\begin{verbatim}
Gesucht ist ein Ausdruck (Term) mit dieser Bedeutung:
    {{}, {1, 3, {2}}, {1, {2}}, {3, {2}}, {{2}}}
Der Ausdruck soll höchstens die Größe 10 haben.
Sie dürfen diese Symbole benutzen
    zweistellige : [ + , - , & ]
    einstellige  : [ pow ]
    nullstellige : [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
und diese vordefinierten Konstanten:
    A = {{2}}
    B = {1, 3}

gelesen: pow (1 + pow (2))

partiell korrekt?

Die Baumstruktur Ihrer Einsendung ist:
    pow
    |
    `- +
       |
       +- pow
       |  |
       |  `- 2
       |
       `- 1

Die Größe Ihres Ausdrucks ist 5

total korrekt?

Der Wert Ihres Terms ist
    {{}, {1}, {1, {}}, {1, {}, {2}}, {1, {2}}, {{}}, {{}, {2}}, {{2}}}

stimmen die Werte überein?

Nein, diese Elemente kommen nur in jeweils einer der Mengen vor:
    {{1}, {1, 3, {2}}, {1, {}}, {1, {}, {2}}, {3, {2}}, {{}},
     {{}, {2}}}
\end{verbatim}


\subsection{Relationen}

\verb|Algebraic_Relation-Direct-5|

\begin{verbatim}
Die folgende Aufgabe bezieht sich auf Relationen
über dem Grundbereich mkSet [ 1 , 2 , 3 , 4 ]

Gesucht ist ein Ausdruck (Term) mit dieser Bedeutung:
    {(4 , 1)}
Der Ausdruck soll höchstens die Größe 7 haben.
Sie dürfen diese Symbole benutzen
    zweistellige : [ + , - , & , * ]
    einstellige  : [ inv , tcl , rcl ]
    nullstellige : [ ]
und diese vordefinierten Konstanten:
    R = {(1 , 2) , (3 , 4)}
    S = {(2 , 3)}

gelesen: R * S + S

partiell korrekt?

Die Baumstruktur Ihrer Einsendung ist:
    +
    |
    +- S
    |
    `- *
       |
       +- S
       |
       `- R

Die Größe Ihres Ausdrucks ist 5

total korrekt?

Der Wert Ihres Terms ist die Relation
    {(1 , 3) , (2 , 3)}

stimmen die Relationen überein?

Stimmen die Menge
    Aufgabenstellung = mkSet [ ( 4 , 1 ) ]
und die Menge
    Einsendung = mkSet [ ( 1 , 3 ) , ( 2 , 3 ) ]
überein?

Nein.
\end{verbatim}

\subsection{Graphen} 

(Konstanten: Kreis, Clique; Operatoren: Komplement, Produkt, Kantengraph)

\subsection{boolesche Funktionen}

(Darstellung in gegebener Basis)


\section{Weiter denkbare Aufgaben (Experimentell)}

das hat Bezüge zur Forschung (Waldmann).

Zum interaktiven Ausprobieren muß man aber noch glitzernde Oberflächen bauen.

\begin{itemize}
\item
  Wortersetzung: Schleifen finden, 

  Bsp: Regelmenge $\{100 \to 00110\}$,
  zu finden ist Schleife $\underline{100}00 \to 001\underline{100}0
  \to 001001\underline{100} \to 00100\underline{100}110 \to 00\fbox{$10000$}110110$

  Bsp: finde Schleife für $\{ cb \to bba, ab \to bca \}$.
\item
  Wortersetzung: Termination durch Interpretation

  finde lineare additive Gewichte (löse lineares Ungleichungssystem),

  finde Matrix-Interpretation (Schieberegler für Matrix-Einträge)
\item
  Wortersetzung: matchbounds und inverse Matchbounds
 

\end{itemize}



\end{document}
