Welfenlab Competition 2003

Schülerwettbewerb Informatik

Resonanz

Die Welfenlab Competition 2003 ist nun beendet und die Preisträger des Wettbewerbs wurden im Rahmen der Ada Lovelace Memorial Celebration geehrt. Die Gewinner sind:

1.Platz
Oliver Müller , Niedersächsisches Internatsgymnasium Bad Harzburg

2.Platz
Steffen Matthias, Gymnasium Bad Nenndorf

3.Platz
Ulrich v.d. Ohe, Otto-Hahn-Gymnasium Springe
Dariush Forouher, Bernhard-Riemann-Gymnasium Scharnebeck

Anerkennungspreise
Marc Röhrig, Philipp Kleybolte (beide Leibnizschule Hannover), Michael Siebert (Halephagen-Schule Buxtehude), Andre Ryll (Oldenburg)

Wir hoffen, dass alle Teilnehmenden genauso viel Spass hatten wie wir und freuen uns über die positive Resonanz:
Bericht der Leibnizschule Hannover
Bericht der Halepaghen-Schule Buxtehude

Organisatorisches

Wir haben den folgenden Text und das Anschreiben, welches wir an verschiedene Schulen geschickt haben, auch im PDF Format:

  • die Beschreibung,
  • das Anschreiben.

Testdaten

Einige Testdaten sind jetzt online abrufbar. Es gibt folgende Datensätze:

  • 2-Doppelkringel
  • 2.5-Doppelkringel
  • 4-Kringel
  • 5-Kringel
  • komplizierte Schlinge

Worum geht es?

Die Aufgabe dieser Competition kommt aus dem spannenden und noch nicht besonders gut erforschten Gebiet der Knotentheorie. Was ein Knoten ist, weiss so ziemlich jeder, der schon mal beim Öffnen der Schleife am Schuh an einem Ende gezogen hat, das dummerweise durch eine der Schlaufen verlief. Allerdings lassen sich solche Knoten entknoten (da ja beide Enden einfach nur entlang ihrem Verlauf im Knoten zurückgeführt werden müssen). Daher betrachten wir auch nur Fälle, bei denen die beiden Enden miteinander verbunden sind, also geschlossene Knoten:

Abbildung: 1 a) Unknoten b) Trefoil

Den Wissenschaftlern stellt sich dabei die Frage, ob ein gegebener Knoten entknotbar ist, also ob er sich auf den sogenannten Unknoten (Abb. 1a) zurückführen lässt. Der Trefoil aus Abb. 1b lässt sich z.B. nicht entknoten. Auch die Verknotung (Abb. 2a und 2b) eines DNS-Moleküls unter dem Elektronenmikroskop ist nicht der Unknoten.

Abbildung: 2 a) DNS Molekül b) zugehöriger Knoten

Ziel dieser Competition ist es, ein Programm zu schreiben, das Knoten einlesen, konvertieren und vereinfachen kann. Außerdem soll festgestellt werden, ob zwei Knoten miteinander verlinkt sind, oder ob sie sich ohne Aufschneiden voneinander trennen lassen. Doch mehr dazu später ...

Und was gibt es zu gewinnen?

Unabhängig von viel Erfahrung, Ehre und Ruhm gibt es auch etwas Handfestes zu gewinnen:

1. Platz 2. Platz 3. Platz
17'' Flachbildschirm DVD-Brenner USB Stick
NEC LCD1760NX o.ä. Plextor PX-708A o.ä. USB 2.0 256MB

Hintergrund

Da die zu Anfang beschriebenen Knoten beliebig komplex werden können, wollen wir uns im weiteren Verlauf der Competition mit der "Verlinkungsfrage" bei einfachen "Links" beschäftigen. Ein Link besteht aus zwei geschlossenen Knoten, die entweder voneinander getrennt werden können, d.h. separierbar sind (siehe Abb. 3a) oder nicht (dann sind sie verlinkt, siehe Abb. b):

Abbildung 3: a) Separierbar b) Verlinkt

Aufgabenstellung

Es soll ein Programm entwickelt werden. In der dazugehörigen Dokumentation sollen Algorithmen und Programmaufbau verständlich dargestellt werden. Folgende Teilaufgaben sollen gelöst werden:

  1. Einlesen eines geschlossenen Kantenzuges aus einer Datei. Dabei stehen in jeder Zeile die drei Koordinaten (x,y,z). Z.B. :

        12.222  -1.01   13.4
        34      23.3   -17.93
      ...

    Jeder dieser Punkte gibt eine Ecke des Kantenzuges an. Die Kanten sind die geradlinigen Verbindungen der Ecken. Vom letzten Punkt des Kantenzuges führt wieder eine Kante zum ersten, um den Kantenzug zu schließen.
    Die erste Ecke wird nicht nochmal am Ende der Datei angegeben. Es können beliebig viele Freizeichen oder Tabs zwischen zwei Zahlen vorkommen. Wichtig ist nur, dass pro Zeile nur drei Zahlen stehen. Der eingelesene Kantenzug soll nun verrastert werden, das heißt, er soll in ganzzahlige Koordinaten (die sogenannten Voxel) konvertiert werden.


    Abbildung 4: Verrasterte Kante von (0,0,0) nach (12,5,0)

    Hierbei ist darauf zu achten, dass entlang des Kantenzuges zwei benachbarte Voxel immer über eine gemeinsame Seitenfläche benachbart sind. Die Voxel um (0,0,0) und (1,1,1) sind demnach nicht benachbart, sondern können z.B. so verbunden werden:


    (0, 0, 0)
    (1, 0, 0)
    (1, 1, 0)
    (1, 1, 1)

    Um z.B. die Verbindungsstrecke zwischen (-24, 11, 15) und (33,45,-23) zu verrastern, ist es sinnvoll, das Problem zunächst in der xy-Ebene zu lösen, und im zweiten Schritt die z-Komponente zu bearbeiten. Dabei müssen dann evtl. neue Voxel eingefügt werden. Die Voxel-Daten sollen in eine Text-Datei gespeichert werden (drei Integer pro Zeile für die drei Koordinaten eines jeden Voxel). Außerdem sollen solche Dateien auch eingelesen werden können. Das Programm soll erkennen, wenn zwei Kanten zu nah beieinander liegen, damit nach dem Vervoxeln keine Berührungen verschiedener Kanten stattfinden und immer klar bleibt, in welcher Reihenfolge die Voxel durchlaufen werden.

  2. Es soll ein gegebener Knoten eingelesen werden. Der Knoten wird als ein Link (s.o.) betrachtet, indem wir die z-Achse als Teil eines zweiten (Un-)knotens auffassen, der entlang der z-Achse läuft, dann einmal ganz außen um den ersten Knoten herum und von der negativen z-Achse wieder entlang der z-Richtung durch den ersten Knoten hindurch. Dieser zweite Knoten wird nicht in der Datei mit angegeben oder extra eingelesen, sondern er existiert nur implizit innerhalb des Programms bzw. innerhalb der nötigen Algorithmen. Auf diese Weise vereinfacht sich das Datenformat und die Darstellung erheblich.


    Abbildung 5: a) Link b) z-Achse als Stange c) Schlaufenentfernung

    Es soll nun entweder im Voxel-Modell oder im Kantenzug versucht werden, einen Link zu vereinfachen, indem z.B. überflüssige Schlaufen abgeschnitten werden. Dabei müssen verlinkte Knoten nach dem Entfernen einer Schlaufe immernoch verlinkt bleiben. In Abb. 4c z.B. kann alles rechts außerhalb des Bildes abgeschnitten werden. Die offenen Enden werden dann verbunden.

  3. Das Programm soll nun versuchen festzustellen, ob der vereinfachte Link wirklich verlinkt ist, oder ob sich die beiden Knoten separieren lassen. Sollte dies nicht für alle Links möglich sein, muss angegeben werden für welche Klasse bzw. Sonderfälle von Links das Programm die Verlinktheit feststellen kann, bzw. für welche Fälle eine Feststellung der Verlinktheit fehlschlägt.


    Abbildung 6: a) separierbar b) nicht separierbar

Teilnahmebedingungen

  • Anmeldeschluss ist der 20.12.03.

  • Gruppenmeldungen sind nicht möglich.

  • Als Programmiersprache sind Pascal, C, C++ und Java zugelassen. Die Sprache muss bei der Anmeldung mit angegeben werden. Es dürfen nur die Standard-Bibliotheken und keine Codegeneratoren verwendet werden.

  • Es muss eine 5 bis 10-seitige Ausarbeitung angefertigt werden, in der die benutzten Algorithmen erklärt werden, und in der das Programm ausführlich dokumentiert wird.

  • Das erstellte Programm und die Ausarbeitung sowie ein Ausdruck eines Testdurchlaufs bzw. die Ergebnisse mit von uns gestellten Daten sind spätestens bis zum 16.02.04 bei uns einzureichen.

  • Es dürfen nur Schüler der Sekundarstufe I oder II allgemeinbildender Schulen aus Niedersachsen an dem Wettbewerb teilnehmen. Familienangehörige von Mitarbeitern des Fachgebietes Graphische Datenverarbeitung an der Universität Hannover sind leider ausgeschlossen.

  • Der Rechtsweg ist ausgeschlossen.

Bewertungskriterien

  • Lauffähigkeit und Korrektheit des Programms

  • Gut verständliche Dokumentation der Algorithmen ggf. mit Ergebnissen von Beispieldaten

  • Besondere eigenständige Ideen

  • In Zweifelsfällen: Strukturierter Programmierstil

So, das war's erstmal. Hoffentlich hast Du ein wenig Lust bekommen, bei diesem Gewinnspiel mitzumachen. Es geht bei dieser Competition nicht darum, alles perfekt zu machen. Wir freuen uns auch über Teillösungen. Wenn wir merken, dass Du Dich mit der Problematik beschäftigt hast, hier und da ein paar interessante eigene Ideen hattest und Deine Gedanken und Algorithmen dokumentierst, hast Du gute Chancen unter den drei Besten zu sein. Bei Rückfragen kannst Du Dich gerne bei uns melden.

E-Mail: competition(at)gdv.uni-hannover.de

Viel Erfolg,


i.A. Dipl. - Math. Martin Reuter
Lehrstuhl Graphische Datenverarbeitung

Prof. Dr. F. - E. Wolter