Abteilung Computer Graphics & Software-Ergonomie

Lernprogramme für Algorithmen mit interaktiven Simulationen und Visualisierungen

Fortgeschrittenenpraktikum im Sommersemester 1999



Inhalt

  • Organisatorisches
  • Ziel
  • Algorithmus und Realisierung
  • Literatur und Quellen

  • Organisatorisches

    Das Fortgeschrittenpraktikum wird von Peter Gorny und Nils Faltin veranstaltet. Wir werden uns voraussichtlich während des Sommersemesters regelmäßig Freitags von 14.15 bis 15.45 im Raum A2 2-215 treffen. Zusätzlich arbeiten die Teilnehmer nach freier Zeiteinteilung. Die Teilnehmerzahl ist auf 12 Personen beschränkt. Bittet melden sie sich möglichst bis 13. Februar 1999 bei Nils Faltin per Email oder persönlich an.


    Ziel

    Ziel des F-Praktikums ist es, ein Lernprogramm zum Themenbereich "Algorithmen für kürzeste Wege in Graphen" zu erstellen. Je nach Teilnehmerzahl werden ein oder meherere Algorithmen behandelt. Der Algorithmus wird in Funktionen zerlegt und entlang dieser Funktionen erklärt. Die wesentliche Grundidee ist, den Benuzter die Schritte des Algorithmus selbst ausführen zu lassen. Dazu werden die Datenstrukturen grafisch dargestellt. Der Benutzer wählt mit der Maus Objekte aus und führt auf ihnen Funktionen aus. Der lernende Menschen soll in seiner problemlösenden Kreativität angesprochen werden. Dazu wird ein Problem beschrieben und dann Gelegenheit gegeben, es durch freies Probieren zu lösen. Anschließend wird das Standardverfahren beschrieben und durch interaktive Übungen gefestigt. In diesen Übungen sind nur die vom Standardverfahren her zulässigen Schritte erlaubt. Bei Fehleingaben werden möglichst erklärende Fehlermeldungen gegeben. Die interaktiven Teile sind in einen Lehrtext mit statischen Bildern und ev. Animationen eingebettet.

    Das F-Praktikum kann auf einem Grobentwurf für eine Lehreinheit zum Algorithmus für kürzeste Wege nach Dijkstra aufbauen. Dieser Grobentwurf soll vor allem in Hinsicht auf Visualisierung und Interaktion erweitert werden. Falls es die Teilnehmerzahl erlaubt, werden im F-Praktikum Lehreinheiten für weitere Algorithmen eigenständig entwickelt. Das Lernprogramm wird objektorientiert entworfen und in Java und HTML implementiert.


    Algorithmus und Realisierung

    Im F-Praktikum wird der Algorithmus "Spannender Baum kürzester Wege in ungerichteten Graphen" das Thema des Lernprogramms sein.

    Die Problemstellung

    Ausgehend von einem Startknoten sollen die kürzesten Wege zu allen anderen Knoten in einem ungerichteten, bewerteten Graphen bestimmt werden. Jeder Kante ist eine Länge (Kosten) zugeordnet. Die kürzesten Wege bilden einen spannenden Baum mit dem Startknoten als Wurzel. Algorithmen die dieses Problem lösen unterscheiden sich nur in der Abbruchbedingung von solchen, die den kürzesten Weg zwischen zwei Knoten suchen.

    Algorithmus und Visualisierung

    Wir betrachten den klassischen Algorithmus von Dijkstra, wie er in Ottmann und Widmayer (1996) beschrieben ist. Die hier vorgestellte Visualisierung lehnt sich an Sedgewick (1992), Fig. 31.11 an.


    Abbildung 1


    Abbildung 2

    (Abbildungen 1 und 2 in eigenem Fenster öffnen)

    Abbildung 1 und 2 zeigen den Zustand der Datenstrukturen, nachdem sich der Algorithmus schon zwei bzw. drei Hauptschritte weit vorgearbeitet hat. Die Länge der Kanten ist nicht in den Abbildungen vermerkt. Der Algorithmus sucht die kürzesten Wege von jedem Knoten zum Startknoten A. Die Knoten (A,B,C), für die inzwischen der kürzeste Weg zum Startknoten bekannt ist, sind als grüne Kreisfläche gezeichnet. Man nennt diese Knoten gewählte Knoten. Die Kanten, von denen schon bekannt ist, daß sie zur endgültigen Lösung gehören, sind grün gezeichnet. Der sogenannte Rand besteht aus Knoten, die direkt an die gewählten Knoten angrenzen. Sie sind als rote Quadrate gezeichnet. Der Algorithmus stellt sicher, daß der kürzeste Weg, der von Randknoten nur über gewählte Knoten führt bekannt ist. Die Kante, über die der Weg führt wird rot unterlegt. Dies muß noch nicht der endgültig kürzeste Weg sein. Für den Knoten des Randes, der die kürzeste Verbindung zum Startknoten hat, ist dieser Weg aber sogar der endgültige. Dieser minimale Randknoten ist als dunkelrotes großes Quadrat gezeichnet. Von den restlichen Knoten ist nichts über kürzeste Wege bekannt. Sie heißen unerreichte Knoten und werden als blaue Kreisflächen gezeichnet. Kanten, die noch nicht betrachtet wurden, werden blau gezeichnet. Werden Kanten verworfen, ändert sich ihre Farbe zu grau.

    Der Algorithmus arbeitet sich in Hauptschritten voran. Ein Hauptschritt besteht aus den folgenden Teilschritten:

    1. Der minimale Randknoten wird zu einem gewählten Knoten
    2. Die Nachbarn des minimalen Randknoten, die im Rand oder in den unerreichten Knoten liegen werden aktualisiert. Für sie wird berechnet, wie lang ein Weg zum Startknoten über den minmimalen Randknoten ist. Ist dieser kürzer als der bisher bekannte Weg, wird dies vermerkt.
    3. Nachbarn, die zu den unerreichten Knoten gehören, werden dem Rand zugeordnet.
    4. Aus dem Rand wird ein neuer minimaler Randknoten bestimmt.

    Die beiden obigen Abbildungen 1 und 2 zeigen den Zustand der Datenstrukturen vor und nach einem solchen Hauptschritt.


    Interaktion mit dem Programm

    Im Lernprogramm wird der Benutzer unter anderem diesen Hauptschritt einüben. Er kann dazu folgende Funktionen durch anklicken von Buttons, Icons und Knoten auslösen. Eine mögliche Realisierung der Icons ist in Abbildung 1 rechts neben dem Graphen zu sehen.

    1. Ordne Knoten den gewählten Knoten zu
    2. Aktualisiere vom Knoten X aus seinen Nachbarn Y
    3. Ordne Knoten dem Rand zu
    4. Berechne minimalen Randknoten
    5. Ordne Knoten den unerreichten Knoten zu
    Die letzgenannte Funktion wird nur bei der Initialisierung der Datenstruktur benötigt.


    Literatur und Quellen

    Nils Faltin: "Designing courseware on algorithms for active learning with virtual board games". Accepted for "ITiCSE '99 - Conference on Innovation and Technology in Computer Science Education, Cracow, Poland, June 27 - July 1, 1999". An Online-Version of the submitted paper (not the final paper) is available.

    Thomas Ottmann und Peter Widmayer: "Algorithmen und Datenstrukturen". 3. Auflage. 1996. Spektrum Akademischer Verlag, Heidelberg u.a..

    Robert Sedgewick: "Algorithms in C++". 1992. Addison-Wesley, New York u.a..

    Im Projekt MuSIK entstandene Lernprogramme

    Animation von Graphalgorithmen mit Java.


    Letzte Änderung 2.2.1999 NF