Eine gekürzte Fassung dieses Artikels erscheint im Tagungsband der Tagung "Informatiktage '99 der Gesellschaft für Informatik. 12. - 13. November 1999 in Bad Schussenried". Konradin Verlag.

Gestaltung von Lernprogrammen zu Algorithmen für aktives Lernen mit virtuellen Brettspielen

Nils Faltin

Faltin@informatik.uni-oldenburg.de

Computer Graphics & Software-Ergonomie
C. v. Ossietzky Universität Oldenburg
D-26111 Oldenburg

Betreuer der Arbeit: Prof. Dr. Peter Gorny

Art der Arbeit: Dissertation

Fachbereich GI: 2

Zusammenfassung

In diesem Artikel wird eine Methode für die Gestaltung von Lernprogrammen zum Themengebiet Algorithmen beschrieben. Der Lerner soll die Fähigkeit erwerben, den Algorithmus weiterzuentwickeln. Im Lernprogramm werden erklärende Teile mit einer neuen Form von Aufgabe, dem virtuellen Brettspiel, kombiniert. Es eröffnet einen experimentellen Zugang zum Algorithmus über grafische Interaktion mit Funktionen und Datenobjekten.

Einführung

Lernmedien für das eigenständige Lernen stehen als Mittler zwischen dem Lerner und dem Lerngegenstand. Sie sollten von ihren Autoren so gestaltet werden, daß sie dem Lerner einen möglichst ungehinderten, eigenständigen und angemessenen Zugang zum Lerngegenstand ermöglichen. Das Lernmedium "Multimediale interaktive Lernprogramme" hat hierbei für das Lerngebiet Algorithmen ein besonders großes Potential. Unter den mir bekannten Lernprogrammen, die (auch) Algorithmen behandeln, schöpfen selbst die besten dieses Potential noch nicht aus. Zu nennen wären hier z. B. "Animated Algoritms" ([GlDyLe93], [Gloo97]), "Viacobi" ([Jans98a], [Jans98b]) und "ORWelt" ([Blum98a], [Blum98b]).

Diese Lernprogramme nutzen im erklärenden Teil Texte, Bilder und Algorithmen-Animationen. Aufgaben sind, falls vorhanden, meist auf Multiple-Choice-Fragen beschränkt. Mir scheint bei den Aufgaben das größte Potential für neue Formen des Zugangs zum Lerngegenstand zu liegen. Es stellt sich daher die Frage, wie Aufgaben für das Medium Lernprogramm zum Themengebiet Algorithmen gestaltet werden können.

Didaktische Ziele

Im folgenden werde ich die von mir entwickelte didaktische Methode "Strukturiertes Aktives Lernen von Algorithmen (SALA)" vorstellen. Sie ist darauf ausgelegt, ein tiefes Verständnis für die Funktionen eines Algorithmus zu vermitteln. Der Lerner soll sowohl die Datenstruktur als auch die Schritte der Funktionen verstehen. Für die Datenstruktur soll er lernen, welche Typen von Objekten es gibt, wie sie miteinander verzeigert sind und welche (mathematischen) Bedingungen zwischen den Objekten gelten. Es soll ihm klar werden aus welchen Schritten eine Funktion besteht, warum die Schritte erlaubt sind und zum Ziel führen.

Das Verständnis des Algorithmus umfaßt damit auf jeden Fall die Fähigkeit, den Algorithmus von Hand auszuführen. Das didaktische Ziel von SALA geht aber darüber hinaus. Der Lerner soll fähig sein, den Algorithmus um neue Funktionen zu erweitern. Daher wird er schon beim Erlernen der Funktionen in die Rolle eines Algorithmus-Entwicklers gestellt und soll kreativ und problemlösend tätig werden.

Wurde dieses tiefe Verständnis erworben, so ist es sicher auch eine große Hilfe, um den Algorithmus zu programmieren oder mathematisch zu analysieren. Man könnte natürlich auch versuchen, einen Algorithmus einfach Zeile für Zeile aus einer Pseudocode-Beschreibung in ein Programm zu übertragen, ohne ihn verstanden zu haben. Damit würde aber eine wichtige Kontrolle auf Korrektheit entfallen und es ist fraglich, ob man die Möglichkeiten der Programmiersprache ausschöpfen könnte. In den meisten Fällen wird auch die mathematische Analyse nur gelingen, wenn man das Zusammenspiel von Schritten einer Funktion und den Objekten der Datenstruktur verstanden hat.

Vom Lehrbuch zum Lernprogramm

Mit einem nach SALA entwickelten Lernprogramm soll es möglich sein, selbständig zu lernen. Damit ist gemeint, daß keine zusätzlichen Texte oder helfende Personen nötig sind, um den Algorithmus zu erlernen. Natürlich kann und soll ein solches Lernprogramm auch begleitend zu herkömmlichen Lehrformen, wie Vorlesung und Übung einsetzbar sein. Es liegt daher nahe, herkömmliche Lehrbücher zu Algorithmen (z. B. [OtWi96], [CLR90]) zu betrachten und zu überlegen, wie dortige Präsentationsformen und Lernmethoden in das Medium Lernprogramm übertragen werden können.

Texte und Formeln sollten als Hypertext dargestellt werden. Bilder aus dem Buch können im Lernprogramm wieder als Bilder gezeigt werden. Sollen aber die Bilder im Buch einen dynamischen Vorgang veranschaulichen, wie z. B. Veränderungen der Werte oder der Verzeigerung der Datenstruktur, so wird man im Lernprogramm Animationen zeigen. Autoren von Lernsoftware, die einen Einblick in das Gebiet der Algorithmen-Animation gewinnen wollen finden hierzu im Buch "Software Visualization" [SDBP98] eine Fülle von Hinweisen und Berichte über einschlägige Projekte.

Der erklärende Teil eines Lehrbuches läßt sich damit gut darstellen. Aber wie steht es mit den Aufgaben? Aufgaben fordern den Lerner heraus, sich aktiv mit dem Stoff zu beschäftigen. Sie decken Wissenslücken auf, festigen das gelernte Wissen und geben einen Rahmen, um abstraktes Wissen auf konkrete Aufgaben oder Situationen anzuwenden. In der didaktischen Literatur wird immer wieder darauf hingewiesen, daß Lerner aktiv am Stoff arbeiten sollen, um ihn besser zu verstehen und zu behalten.

Aufgaben aus Lehrbüchern soll der Lerner typischerweise mit Papier und Stift bearbeiten. Vereinzelt gibt es auch Programmieraufgaben, die dann aber meist zeitaufwendig sind und Lerner ohne Programmiererfahrung überfordern. Beim eigenständigen Lernen gibt es niemanden, der weiterhelfen kann, wenn es bei der Programmierung ein Problem gibt.

Dem Autor von Lernprogrammen bietet das Medium Computer viele neue Ausdrucksmöglichkeiten: Farbgrafik, Animation, Ton und insbesondere Interaktivität mit dynamischer Hilfestellung und Fehlermeldungen. Es sind mir nur wenige Lernprogramme zu Algorithmen bekannt, die überhaupt interaktive Aufgaben beinhalten. Die Interaktion beschränkt sich dabei auf die Auswahl von Lösungsalternativen bei Multiple-Choice-Tests und auf die Vorhersage des nächsten Schrittes eines Algorithmus (z. B. durch anklicken eines Objekts mit der Maus). SALA versucht mit den unten beschriebenen Aufgaben des Typs virtuelles Brettspiel einen forschenden und kreativen Zugang zu den Funktionen und Datenstrukturen zu öffnen.

Strukturierung des Lernprogramms in Sektionen

Im folgenden werden Hinweise gegeben, wie der Stoff eines Lernprogramms in Sektionen aufgeteilt werden kann. Eine Sektion soll es dem Lerner ermöglichen, sich auf einen Teil des Stoffes zu konzentrieren. Da einem Anfänger der Überblick über den Stoff fehlt, kann er schwerlich eine sinnvolle Reihenfolge für die Bearbeitung der Sektionen bestimmen. Daher sollte der Autor des Lernprogramms einen Vorschlag für eine Reihenfolge ausarbeiten. Dazu werden unten einige Kriterien genannt. Der Lerner soll aber nicht stark gelenkt werden, wie dies in den 60er Jahren bei den Lernprogrammen der "programmierten Instruktion" der Fall war. Vielmehr soll er vom Standardpfad abweichen dürfen. Zur freien Navigation dienen einerseits das Inhaltsverzeichnis, andererseits Hyperlinks zwischen Sektionen, die inhaltliche Zusammenhänge aufzeigen. Somit eignet sich das Lernprogramm neben dem ersten Erlernen eines Algorithmus auch zum "Nachschlagen" einzelner Teilthemen und zum (erneuten) Durcharbeiten auf neuen Wegen.

Ein Lernprogramm sollte in folgende Sektionen aufgeteilt werden:

  1. Das zu lösende Problem und seine praktische Bedeutung
  2. Vergleich verschiedener Algorithmen die das Problem lösen
  3. Datenstruktur. Zeigerstruktur und mathematische Bedingungen zwischen den Datenobjekten
  4. Funktionen (4.1 bis 4.x). Eine Sektion für jede Funktion des Algorithmus
  5. Implementierung. Diese Sektion behandelt die Abbildung von abstrakten Zeigerstrukturen auf Datentypen einer Programmiersprache und Implementierungstricks. In typischen Lehrbüchern wird dieser Punkt zuerst behandelt. Ich meine aber, daß dem Lerner erst die Funktionsweise des Algorithmus klar sein sollte, da er dann auch motiviert ist, sich in Implementierungsdetails einzuarbeiten. Auch kann hier echter Programmcode gezeigt werden.

Strukturierung des Algorithmus in Funktionen

Der Autor soll für das Lernprogramm die funktionale Struktur des Algorithmus herausarbeiten. Dazu werden wiederholt elementare Schritte des Algorithmus und Funktionsaufrufe zu einer Funktion zusammengefasst. Diese Funktion kann dann wieder in anderen Funktionen verwendet werden. Ein triviales Beispiel ist eine Swap-Funktion, die zwei Werte in einem Array vertauscht. Der Algorithmus wird selbst als eine (oberste) Funktion modelliert. Funktionale Abstraktion wird bei der systematischen Programmierung mit dem Ziel des "information hiding" und der Wiederverwendung eingesetzt. Sie erleichtert aber auch das Erlernen eines Algorithmus, da es einfacher wird übergeordnete Funktionen zu erklären und zu verstehen, wenn andere Funktionen als Bausteine zur Verfügung stehen. Es empfiehlt sich, eine Funktion erst zu erklären, wenn die in ihr verwendeten Funktion schon beschrieben wurden. Ansonsten müßten die verwendeten Funktionen an dieser Stelle ausführlicher beschrieben werden. Die funktionale Strukturierung ist eine Voraussetzung dafür, daß die unten beschriebenen "virtuellen Brettspiele" erstellt werden können.

Vergleichbar mit der funktionalen Strukturierung ist die von Stern et al vorgeschlagene hierarchische Strukturierung, die sie für ihr Lernprogramm zu Heapsort wählten [StSoNa99]. In einem typischen Lehrbuch wird ein Algorithmus nicht oder nur in sehr wenige Funktionen aufgeteilt. Dies mag daran liegen, daß die Darstellung als eine Folge von z. B. 30 Pseudocodezeilen optisch übersichtlicher und einfacher wirkt als eine Darstellung in z. B. 7 Funktionen. Aus didaktischen Gesichtspunkten erscheint mir eine stark funktionale Strukturierung aber sinnvoller.

Strukturierung am Beispiel Heapsort

Im folgenden zeige ich am Beispiel des Heapsort-Algorithmus ([Floy64], [Wilj64]) den Entwurf eines Lernprogramms. Heapsort ist hierfür gut geeignet, da der Algorithmus vielen bekannt ist und die richtige Komplexität hat. Ich werde den Algorithmus hier nur skizzieren. Eine detaillierte Beschreibung ist in den meisten Lehrbüchern zu finden.

Das Lernprogramm zu Heapsort gliedert sich in die folgenden Sektionen:

  1. Das Sortierproblem
  2. Vergleich von Heapsort mit anderen Sortieralgorithmen
  3. Der vollständige Binärbaum, der als Datenstruktur verwendet wird.
  4. Die Heapeigenschaft
  5. (5.1 bis 5.7): Eine Sektion für jede der sieben Funktionen
  6. Speicherung des Heaps und der Ergebnisliste

Abb. 1 - Heapbaum mit markierten Knoten

Abbildung 2 - Heapsort Funktionen

Heapsort verwendet eine spezielle Datenstruktur, den Heap, nach dem der Algorithmus benannt ist. Der Heap ist ein vollständiger Binärbaum, bei dem alle Ebenen bis auf die letzte vollständig gefüllt sind. Die unterste Ebene ist von links nach rechts gefüllt, aber nicht notwendigerweise vollständig. In einem Heap muß der Schlüssel an jedem Knoten größer oder gleich den Schlüsseln der Kindknoten sein. Das ist die sog. Heapeigenschaft. Abb. 1 zeigt einen Heapbaum bei dem die Schlüsselwerte durch die Größe des inneren Quadrats dargestellt sind. Der Schlüssel, der die Heapeigenschaft verletzt, ist markiert. Die folgenden Sektionen behandeln die Funktionen des Heapsort-Algorithmus. Zuletzt wird behandelt, wie der Heap und die Ergebnisliste effizient in einem einzigen Array gespeichert werden können.

Funktionen des Heapsort

Der Heapsort-Algorithmus wurde von mir in die folgenden sieben Funktionen aufgeteilt. Abb. 2 zeigt die funktionale Struktur des Heapsort. Die einzelnen Funktionen werden erklärt, bevor sie in anderen Funktionen benutzt werden.

  1. heapify-locally stellt die Heapeigenschaft für einen Knoten und seine beiden Kinder her.
  2. heapify stellt die Heapeigenschaft für einen Teilbaum her. Der Pfeil mit Stern bedeutet, daß heapify heapify-locally mehrfach aufruft.
  3. build-heap baut den Heap erstmals auf indem es mehrmals heapify aufruft.
  4. move-max entfernt den größten Schlüssel aus dem Heap, fügt ihn in die Ergebnisliste ein und stellt die Heapeigenschaft wieder her.
  5. sort verwendet move-max, um die Schlüssel zu sortieren
  6. heapsort initialisiert den heap mit build-heap und sortiert die Schlüssel mit der Funktion sort

Eine Algorithmus-Funktion erlernen

Eine Algorithmus-Funktion wird in einer Sektion des Lernprogramms in drei Phasen behandelt:

  1. Problemstellung. Was ist der Zweck der neuen Funktion? Welche Funktionen wurden bisher gelernt und sind verfügbar um die neue Funktion zu realisieren? Ein typisches Lehrbuch würde den Pseudocode der Funktion angeben und erklären. Dies soll im Lernprogramm nicht geschehen, sondern der Lerner soll versuchen die Lösung (den Pseudocode) selbst herauszufinden.
  2. Probierphase. Daher ist der nächste Schritt eine Aufgabe mit Probierphase. Ein Satz Beispieldaten wird präsentiert und der Lerner kann experimentieren um eine korrekte Abfolge zu finden in der die verfügbaren Funktionen auf die Datenobjekte angewendet werden. Der Lerner soll selbst eine Idee entwickeln, wie der Code der Funktion aussieht und die Schritte ausprobieren. Für diese Aufgabe wird ein virtuelles Brettspiel verwendet. Ist die Funktion sehr einfach, kann diese Phase vom Autor ausgelassen werden.
  3. Standardverfahren. In der letzten Phase wird die Standardlösung mit Pseudocode erklärt. Anschließend übt der Lerner die Schritte des Standardverfahrens. Hierzu wird ihm wieder ein virtuelles Brettspiel angeboten. Allerdings gibt das Lernprogramm nun eine stärkere Rückmeldung indem es nur die Schritte der Standardlösung erlaubt. Bei einfachen Funktionen kann das virtuelle Brettspiel entfallen.

Das virtuelle Brettspiel

In einem virtuellen Brettspiel werden die Datenstrukturen grafisch dargestellt. Der Lerner startet Funktionen, indem er mit Funktionsnamen beschriftete Schaltflächen und Datenobjekte mit der Maus anklickt. Er muß dabei in der Probierphase nicht die Schritte des Standardverfahrens einhalten, sondern kann experimentieren und Fehler machen. Das Lernprogramm simuliert die Wirkung der Funktionsaufrufe und gibt visuelle und textuelle Rückmeldungen über Fortschritt und Fehler. Der Name kommt von einer Analogie mit echten Brettspielen wie Schach oder Mühle. Auch dort hat ein Spieler ein Ziel vor Augen und bewegt Spielsteine zwischen diskreten Positionen, wobei er die Spielregeln einhalten muß.

Abb. 3 - Virtuelles Brettspiel für build-heap

In Abb. 3 ist die Ausgangslage der Probierphase für das virtuelle Brettspiel zur build-heap-Funktion zu sehen. Klickt der Lerner auf heapify und dann auf den Knoten A oder B, so wird der Teilbaum heapgeordnet, da dort die Vorbedingung erfüllt ist. Der Knoten wird dann ausgefüllt dargestellt. Bei den anderen Knoten wird eine Fehlermeldung "Falsch! Die Kindbäume müssen heapgeordnet sein!" ausgegeben. Sind alle Knoten heapgeordnet, so muß der Lerner dies erkennen und Done anklicken. Das Brettspiel ist dann erfolgreich beendet. Die Schaltflächen heapify-locally und swap werden zwar für die Lösung nicht benötigt, sind aber aufgeführt, um dem Lerner zu ermöglichen damit zu experimentieren.

Ein virtuelles Brettspiel ist keine Algorithmen-Animation sondern eine interaktive grafische Simulation von Teilen des Algorithmus.

Realisierte Lernprogramme

Die virtuellen Brettspiele zu Heapsort wurden mit zwei materiellen Prototypen aus Pappe und Filz an Lernern informell erprobt. Die Lerner spielten gerne mit dem Brettspiel und kamen gut voran. Ich erfuhr dadurch auch einiges über den Lernprozeß bei den Lernern. Heapsort wurde noch nicht als Lernprogramm realisiert.

In unserer Arbeitsgruppe wird schon seit längerem Lernsoftware unter besonderer Berücksichtigung didaktischer und software-ergonomischer Anforderungen entwickelt [Gorn98]. Unter meiner Betreuung entstanden in Diplomarbeiten Lernprogramme zu den folgenden Themen [Falt99]:

Sie legen alle einen Schwerpunkt auf aktives Lernen durch grafische, interaktive Aufgaben. Die Lernprogramme sind in HTML und Java realisiert und über normale Webbrowser übers Internet oder lokal lauffähig.

Das Lernprogramm zum Binomial-Heap-Algorithmus wurde eng nach der Methode SALA entwickelt und mit einigen Informatikstudenten evaluiert. Die Probanden kamen gut mit dem Lernprogramm zurecht und äußerten sich positiv über das zugrundeliegende didaktische Konzept.

Ausblick

Es braucht sicher noch weitere Autoren, die moderne didaktische Konzepte aufgreifen und kreativ bei der Gestaltung von Lernprogrammen umsetzen. Ich erwarte für die Zukunft, daß sich solche Lernprogramme (in Konkurrenz z.B. zum Lehrbuch) als das dem Lerngegenstand Algorithmen angemessenere Lernmedium erweisen werden.

Quellen

[Blum98a] Astrid Blumstengel: "Entwicklung hypermedialer Lernsysteme". 1998. Wiss. Verl. Berlin. Hypertext-Version: http://dsor.uni-paderborn.de/organisation/blum_diss/

[Blum98b] Astrid Blumstengel: "ORWelt". Lernsoftware zu Operations Research. Download-Datei für Windows. 1998. Univ. Paderborn. http://dsor.uni-paderborn.de/orwelt/.

[CLR90] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: "Introduction to Algorithms". 1990. MIT Press, Cambridge.

[Falt99] Nils Faltin: "Lernprogramme des Projekts Medienunterstütztes Studium der Informatik". 1999. http://www-cg-hci.informatik.uni-oldenburg.de/~musik/lp_musik.html.

[Floy64] Robert W. Floyd. Algorithm 245 (treesort). Communications of the ACM, 7:701, 1964.

[GlDyLe93] Peter Gloor, Scott Dynes and Irene Lee: "Animated Algorithms". CD-ROM for Macintosh. 1993. MIT Press, Cambridge, MA.

[Gloo97] Peter Gloor: "Elements of Hypermedia Design". 1997. Birkhäuser, Boston, MA.

[Gorn98] Peter Gorny: "Didaktisches Design telematik-gestützter Lernsoftware". In: B. Koerber und I.-R. Peters, Informatische Bildung in Deutschland, Berlin 1998, LOG IN Verlag. pp 127-155. http://www-cg-hci.informatik.uni-oldenburg.de/resources/DidDesign.pdf. English pre-version: http://www-cg-hci.informatik.uni-oldenburg.de/resources/TET.pdf.

[Jans98a] Achim Janser: "ViACoBi - Ein interaktives Lehr-/Lernsystem für Algorithmen der Computergrafik und Bildverarbeitung". CD-ROM für Windows. 1998. FB Informatik II, Univ. Duisburg. Info: http://www.informatik.uni-duisburg.de/Info2/Janser/Janser.html.

[Jans98b] Achim Janser: "Entwurf, Implementierung und Evaluierung des interaktiven Lehr- und Lernsystems VIACOBI für die Visualisierung von Algorithmen der Computergraphik und Bildverarbeitung". 1998. Berlin : Logos-Verl.

[SDBP98] John Stasko, John Domingue, Marc H. Brown and Blaine A. Price (eds.): "Software Visualization". 1998. MIT Press, Cambridge, MA.

[StSoNa99] Linda Stern, Harald Sondergaard and Lee Naish: "A Strategy for Managing Content Complexity in Algorithm Animation". PP 127-130 in: Bill Manaris (Ed.), Proceedings of the 4th Annual SIGCSE/SIGCUE Conference on Innovation and Technology in Computer Science Education - ITiCSE '99. June 1999. ACM Press, New York.

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

[Wilj64] J. W. J. Williams. Algorithm 232 (heapsort). Communications of the ACM, 7:347-348, 1964.