Didaktik der  Informatik

 Projekttage zum Erwerb eines Scheins zur Vorlesung Algorithmen, Daten und Programme II, SS 98  

PROJEKTGRUPPE 1

Daniel Stebner Kay Dittberner Dirk Bussler      Thomas Neumann  Dokumentation Thomas Fromm   Aufgabe 1 "Abwasserentsorgung"  

Erste Überlegungen zur Lösung

Die Ausgangssituation kann als Baumgraph aufgefasst werden, wobei die einzelnen Häuser als Knoten und die Entfernungen zwischen ihnen als Kanten dargestellt sind. Nun ist dieser Graph, es handelt sich hierbei um einen Spannbaum, von überflüssigen Kanten zu "säubern". Dazu werden alle Zyklen innerhalb des Graphen entfernt. Desweiteren wird der Graph so konstruiert, das immer zuerst die kleinste Kante gezeichnet wird  und dann aufsteigend alle anderen.
Durch diesen Greedy-Algorithmus erhalten wir einen minimalen Graph.
Der Graph wird in unserem Programm in ML als Liste von Elementen geführt.
Dieser minimale Graph enthält nun alle minimalen Kanten bzw. hier Wege von haus zu Haus. Jetzt muss eine Möglichkeit gefunden werden, um
den zentralsten Punkt dieses Graphen zu finden. Der zentrale Punkt in diesem Fall muss eins der Häuser der Kolonie sein, also ein Knoten. Dort wird
die Kläranlage errichtet.
 

Aufteilung der Aufgaben und allgemeine Algorithmenerklärung

Dirk Bussler und Thomas Neumann arbeiten an dem Programm, welches die Ausggangsliste nach dem kleinsten Weg durchsucht und diesen in eine
neue Liste legt. Diese Liste wird zum Test ob ein Ring in ihr enthalten ist zum Programmstück von Daniel Stebner übergeben. Dort wird jeder einzelne
Punkt der Liste auf sich wiederholende Verbindungen also Zyklen. Dabei wird jeder Weg verfolgt. z.B. : Von Knoten 1 führt nur ein Weg nach Knoten 2.
Von Knoten 2 führt auch nur ein Weg nach Knoten 3. Aber von Knoten 3 führt ein Weg nach Knoten 4 und nach Knoten 1. Da Knoten 1 bereits bearbeitet
wurde, existiert eine Schleife bzw. ein Ring.
Die Liste von Dirk und Thomas wird nach diesem Prinzip geprüft. Ist kein Ring vorhanden wird die Liste zurückgegeben und das Programmstück wird nochmal
durchlaufen. So reiht sich ein kleinster Weg nach dem anderen in die neue Liste, die wiederum geprüft wird von Daniel's Routine.
Ist die Ausgangsliste leer, so wird die fertige und geprüfte Liste an Kay übergeben.
Seine Aufgabe ist das Finden des zentralsten Häuschens auf der Kolonie, welches aus seiner idyllischen Umgebung herausgerissen wird und kurzerhand
in eine Kläranlage verwandelt wird. Die Suche nach dem Haus beginnt bei den Blättern. Nicht in Frage kommen die äusseren Blätter des Graphen, sie
sind zuweit vom Zentrum entfernt. Nun wird von den restlichen Knoten alle Wege zu einem Blatt geprüft. Und aus dieser Liste der Strecken
zu einem Blatt wird wiederum der Kürzeste ausgewählt. Diese Strecke bzw. der Ursprungsknoten ist das gesuchte Ziel.
Das ganze Projekt wird von mir, Thomas Fromm kommentiert und dokumentiert.
Ich habe mich dazu entschlossen, um einen kleinen Überblick unserer Aktivitäten zu haben, einen Tagesablaufplan zu schreiben.

Sicher werden sich einige fragen, warum die Wahl zur Berechnung grade auf diese Algorithmen fielen, doch dies ist schnell beantwortet.
Bereits zu Beginn der Diskussionen zur Problembewältigung wurden Wege in diese richtung eingeschlagen, noch bevor uns Unterlagen zur
Greedy-Methode vorlagen. Wie kamen zu dem Schluss, das es wohl die effizienteste Möglichkeit zur Lösung des Problems ist.
Es gibt zwar einige andere Methoden, welche aber nicht so perfekt auf das Problem passten.

Übrigens ist dieses programm nicht nur interessant fuer konstrukteure von Abwassernetzsystemen, nein, die Problematik kann problemlos
auf Netzwerksysteme oder Telefon bzw. Energienetzen übertragen werden. Eine breite Anwendung ist auch bei Routenplanern denkbar.
Dort, wo komplizierte Netzwerke jeglicher Art vorhanden, oder im Aufbau sind kann dieses Programm nützlich sein. Mit einigen wenigen Modifizierungen
kann es eben auch bei einfachen Reisen über Strassen mit dem Auto nützlich sein.

Bevor ich nun zur genaueren Beschreibung das ML-Programms komme möchte ich die Benutzung von ML und diesem Programm erklären.
 

Benutzung des Programms

Um in den Genuss dieses Programms zu kommen, muss Version 0.93 des New Jersey Standart ML vorliegen.
Das Programm selbst heisst "shortway". Zu finden ist es unter :
http://www.didaktik.cs.uni-potsdam.de/lehre/adp2/projekttage/tag1/
Um es zu starten, kopieren Sie es in Ihr Homeverzeichnis und dann starten Sie ML.
Ist ML am laufen kann das Programm durch die Eingabe von use"shortway"; wird es eingeladen und von ML kompiliert.
Nun können Sie einen Beliebigen Baum aufzeichnen und die Knoten durchnumerieren und die Weglänge zwischen Ihnen festlegen.
die Eingabe zur Verarbeitung erfolgt so:
-val graph = [(x,y,z),(a,b,c),...];
Dabei stellt x die Nummer des einen Knotens und y die des nächsten Knotens dar. z ist die Weglänge zwischen x und y.
Simultan gilt es für a,b,c usw. . Bei der Aufstellung des Graphen ist darauf zu Achten das jeder auftretende Weg zwischen zwei Knoten brücksichtigt wird.