Projektvorschlag für Wissenschaftssommer

2008: Die schwersten Spiele ihrer Klasse

Johannes Waldmann und Wolfgang Wittig, HTWK Leipzig 14. September 2007

Teil I

Allgemeines

1 Inhalt

• praktische Aufgabenstellungen (Ressourcen-Zuordnung, Wegplanung usw.)

• werden mathematisch exakt modelliert

• die Modelle sind oft Spiele (Puzzles)

• ausgehend von Modellen kann man algorithmische Lösungen finden

• und die Schwere der Aufgabe/Effizienz der Lösung einordnen

• in der Informatik: Komplexitätstheorie,

• mathematische Grundlagen: diskrete Mathematik, Kombinatorik, Graphentheorie

2 Zielgruppe

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

3 Methode

• konkrete Exponate zum Ausprobieren (Spiele, Puzzles)

• Zuordnung der Spiele zu Motivation (Anwendung) und Theore (Komplexitätsklasse) durch Poster, Handzettel, Standbetreuer • Interaktive Webseite zum Betrachten von Aufgaben (die z. T. den Ex-

ponaten entsprechen), Eingeben von Lösungen, mit sofortiger Bewertung und Speicherung für Sammelauswertung (Highscores) nach gewisser Zeit.

4 Partner, verwandte Projekte

• E-Testing-Werkzeug autotool http://www.imn.htwk-leipzig.de/^{∼}waldmann/
autotool/

mit noch anzupassender, speziell zugeschnittener Benutzeroberfläche

• Leipziger Schülergesellschaft für Mathematik http://www.lsgm.de/

langjährige Erfahrung in der mathematischen Schülerbildung

5 erwünschte Nebenwirkungen

• (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)

• Bei Bearbeitung der Online-Aufgaben: deutlicher Verweis (Links usw.) auf HTWK (Studienwerbung) und LSGM (erhöht Attraktivität)

• Aufgaben-Webseite kann zu diesen Zwecken auch unabhängig weiter genutzt werden

• Preise gestiftet von Sponsoren, z. B. lokale IT-Unternehmen (”wer diese Aufgabe lösen kann, wird sofort eingestellt”u.ä.)

Teil II

Mögliche Exponate/Aufgabentypen (gegenständlich)

6 Komplexität von (Such)problemen

Idee: je ein Beispiel aus Komplexitätsklassen

• P: Sortieren

Sortieren (von verdeckten Spielkarten) mit möglichst wenig Fragen • NP: Graphenfärben, Vertex Cover

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

• NP: SAT

• NP: Binpacking

• PSPACE: Verschiebe-Puzzles (Lunar Lockout usw.)

• RE: Postsches Korrespondenzproblem

jeweils Diskussion der Größe des Suchraumes möglich

Teil III

Mögliche Exponate/Aufgabentypen (Online)

Können getestet werden unter https://autotool.imn.htwk-leipzig.de/

cgi-bin/Super.cgi Schule: HTWK, Matrikel: 319, Passwort: loqzotepos, Semester: Sommer07, Vorlesung: WEL-Demonstration.

6.1 Sortiernetze

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

Beispiel (Sortier-Direct-12):

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---

6.2 Graphenfärben

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

Test: Col-Quiz-4

6.3 Lunar Lockout

Beispiel (Robots-Quiz-4)

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 )
                      }
              ]

6.4 Postsches Korrespondenzproblem

Test: PCProblem-Quiz-4

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" )

7 Codierungstheorie

Beispiel (Hamming-Direct-6)

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.

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

8 Algebraische Ausdrücke (Operatoren)

8.1 Mengen

Algebraic_Set-Direct-2
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}}}

8.2 Relationen

Algebraic_Relation-Direct-5
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.

8.3 Graphen

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

8.4 boolesche Funktionen

(Darstellung in gegebener Basis)

9 Weiter denkbare Aufgaben (Experimentell)

das hat Bezüge zur Forschung (Waldmann).

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

• Wortersetzung: Schleifen finden, Bsp: Regelmenge \{100 → 00110\}, zu finden ist Schleife \underline{100}00 → 001\underline{100}0 → 001001\underline{100} → 00100\underline{100}110 → 00 10000 110110 Bsp: finde Schleife für {cb → bba, ab → bca}.

• Wortersetzung: Termination durch Interpretation finde lineare additive Gewichte (löse lineares Ungleichungssystem), finde Matrix-Interpretation (Schieberegler für Matrix-Einträge)

• Wortersetzung: matchbounds und inverse Matchbounds