Blockseminar 1. - 2. März 1999

"Interaktive Visualisierung von Algorithmen"

Thema 5: Die Lernsoftware `Animated Algorithms'

Michael Köhrmann



Inhaltsverzeichnis


Einleitung

`Animated Algorithms' ist eine Lernsoftware aus dem Jahre 1993, die am Massachusetts Institute of Technology unter der Leitung von P. A. Gloor entwickelt wurde. Es handelt sich um eine Software, die das Erlernen und Verstehen von Algorithmen und algorithmischen Methoden aus dem Bereich der Informatik unterstützen soll. Es werden verschiedene Medien eingesetzt, um dem Benutzer eine ansprechende Oberfläche zu bieten, mit der komplexe Methoden auf eine spielerische Art und Weise veranschaulicht werden können. Der wissenschaftliche Aspekt soll dabei jedoch nicht in den Hintergrund treten.

Das Programm wurde auf einem Macintosh-Rechner getestet und ist auch nur auf diesen Systemen lauffähig.

Inhaltsverzeichnis


Beschreibung des Programms

`Animated Algorithms' ist eine interaktive Lernumgebung, die aus den folgenden Komponenten besteht: Sie wurde speziell für Studenten und Studienanfänger aus dem Fachbereich Informatik, sowie für Schüler konzipiert, die den Umgang mit Algorithmen und Datenstrukturen erlernen und verstehen sollen. Im Vordergrund steht dabei nicht nur die Visualisierung, sondern der Kontext, in dem Algorithmen und elementare Datenstrukturen wissenschaftlich betrachtet werden können. Konkret heißt dies, daß alle vorgestellten Algorithmen textuell beschrieben und mit Animationen veranschaulicht werden. Asymptotische Notationen werden erklärt, verschiedene Algorithmen werden miteinander verglichen und analysiert.

Inhaltsverzeichnis


Aufbau der Software

Beim Start des Programms wird der Benutzer mit einer kleinen Animation begrüßt, woraufhin das erste Hauptfenster des Inhaltsverzeichnisses erscheint. Es gibt insgesamt acht Hauptfenster dieser Art, von welchen der Benutzer zu allen Themenbereichen gelangen kann, die in dem Programm bearbeitet werden: Ferner kann der Benutzer direkt in eine Hypertextversion des Buchs `Introduction to Algorithms' verzweigen und sich dort über eine Vielzahl von Algorithmen informieren. Hierbei wird die Recherche durch direkte Links von der Animationsumgebung auf die entsprechenden Kapitel im Buch und durch Volltextsuche erleichtert.

Inhaltsverzeichnis


Arbeiten mit den Animationen

Beim Anwählen dieser Option erhält der Benutzer eine Erklärung, wie die Oberfläche der Animationssoftware zu bedienen ist. Dabei wird kurz die Bedeutung jedes einzelnen Knopfes erläutert, der einem während der Arbeit mit `Animated Algorithms' begegnet.

Mit einem Druck auf den Animations-Knopf in einem der Hauptfenster (rechts neben den Knöpfen für die einzelnen Themengebiete) wird eine Videosequenz abgespielt, in der dem Benutzer eine kurze Einleitung über das jeweilige Thema per Videofilm gegeben wird.  Dabei sind zwei Arten von Videosequenzen zu unterscheiden: zum einen das Video eines sogenannten `talking head', die Videoaufnahme eines der Programmentwickler (siehe unteres Bild), der eine einfache und knapp gehaltene Einleitung in das jeweilige Thema gibt. Zum anderen wird eine gefilmte Vorführung präsentiert, bei der dem Benutzer die durchzuführenden Arbeitsschritte gezeigt und von einem Sprecher kommentiert werden.

Die gefilmte Vorführung eines Algorithmus wird durch drücken des Knopfes mit der Kennzeichnung `A' gestartet. Der Knopf ohne diese Kennzeichnung startet den `talking head'.

In dem nächsten Bild sieht man das Kontrollfenster, welches dem Benutzer während der Animationen zur Verfügung steht. Die Knöpfe haben dabei die folgenden Funktionen:

Bei einigen Algorithmen sind an die Palette noch weitere klar definierte Funktionen angehängt, wie im unteren Bild bei der Palette des 'Insertion Sort'-Algorithmus zu sehen ist.

Inhaltsverzeichnis


Asymptotische Notationen

Hier wird dem Benutzer die Bedeutung und der Umgang mit der asymptotischen Notation erklärt. Beispiel einer solchen Hypertextkarte:

Die fettgedruckten Wörter sind Links auf weitere Hypertextkarten:

Man gelangt so zu den vier verschiedenen Notationsarten. Diese werden jeweils durch Hypertext und interaktive Animationen beschrieben. Im nächsten Bild wird zum Beispiel die formale Definition der O-Notation erklärt, eine von vier Definitionen.

Auf der nächsten Karte kann der Benutzer durch Auswahl einer der drei Möglichkeiten das zuvor Gelernte anwenden. Wird eine Möglichkeit ausgewählt, so ertönt eine Stimme, die dem Benutzer erklärt, aus welchem Grund die eingegebene Möglichkeit richtig beziehungsweise falsch ist. Daraufhin wird eine entsprechende Kurve in das Koordinatensystem eingetragen.

Inhaltsverzeichnis


Rekursion

Der Benutzer lernt anhand vieler Hypertextkarten und interaktiver Aufgaben das Prinzip der Rekursion. Dabei werden die Texte durch animierte Aufgaben unterstützt, die teilweise aus dem täglichen Leben, oder aus der Informatik stammen. Das nächste Beispiel zeigt eine Rekursion, die Fotographie eines Hundes. Dieser hält ein früheres Eigenportrait von sich selbst im Maul. Nun soll der Benutzer per Mausklick auf die jeweiligen Felder links neben der Fotografie angeben, welche Eigenschaften einer Rekursion erfüllt sind. Jede Entscheidung des Benutzers wird von Stimme kommentiert. Treffen alle fünf Eigenschaften zu, so handelt es sich bei dem Beispiel um eine Rekursion.

Das untere Bild zeigt ein Beispiel aus dem Bereich der Informatik, bei dem der Benutzer den Aufbau einer rekursiven Funktion `nachprogrammieren' muß, indem er die einzelnen Zeilen richtig zusammensetzt. Bei einer falsch zusammengesetzten Funktion erklärteine Sprecherin, welchen Fehler der Benutzer gemacht hat.

Inhaltsverzeichnis


Sortieralgorithmen

Aus dem zweiten Hauptfenster des Inhaltsverzeichnisses kann sich der Benutzer die Beschreibungen und Animationen zu den einzelnen Sortieralgorithmen anzeigen lassen.

Zu jedem der oben aufgeführten Algorithmen sind Animationen vorhanden, die sich in ihren Darstellungen ähneln. Dies erleichtert dem Benutzer einen Vergleich zu der Arbeitsweise der verschiedenen Algorithmen.

Im folgenden Bild sieht man eine vom Algorithmus `Insertion Sort' sortierte Menge von Kugeln unterschiedlicher Größe. In der unteren Bildhälfte wird in einem separaten Fenster der Pseudocode dieses Algorithmus angezeigt. Während der Abarbeitung ist die in der Animation aktive Programmzeile markiert. Der Benutzer erkennt auf diese Weise leicht, unter welchen Voraussetzungen in die einzelnen Programmteile gesprungen wird und was während der Abarbeitung des Algorithmus mit den zu  sortierenden Elementen passiert.

In der linken unteren Ecke erkennt man die Kontrollpalette, mit der der Benutzer auf den Ablauf der Animation Einfluß nehmen kann, indem er (bei einigen Algorithmen möglich) die Menge der zu sortierenden Elemente selbst auswählt und den Algorithmus starten beziehungsweise vorzeitig unterbrechen kann. Einige Algorithmen sind während der Laufzeit mit Tönen unterlegt.

Als nächstes wird der Benutzer in die Analyse von Sortieralgorithmen eingewiesen. Dies erfolgt einerseits durch Hypertextdokumente, andererseits durch eine Animation, in der vier der bereits vorgestellten Algorithmen miteinander verglichen werden.

An diesem Diagramm erkennt der Benutzer, daß der `Counting Sort'-Algorithmus am schnellsten arbeitet. Die Vorbedingung für diesen ist allerdings, daß Maximum und Minimum der Menge der zu sortierenden Elemente vorher bekannt sein müssen. Ist dies nicht der Fall, wurde also eine beliebige Menge von Elementen verwendet, so ist die Anwendung des `Counting Sort'-Algorithmus nicht möglich. Dieser Sachverhalt geht leider nicht aus dem Diagramm hervor.

Inhaltsverzeichnis


Weitere Themenbereiche

Dieses Kapitel beschäftigt sich mit einigen wichtigen Datenstrukturen, die in der Informatik häufig Anwendung finden:

Die Darstellungen und Animationen ähneln denen der Sortieralgorithmen, so daß sich der Benutzer auf die Arbeitsweise der verschiedenen Algorithmen und Datenstrukturen konzentrieren kann.

Bei einigen Animationen ist es möglich, eigens geschriebene Skripte in den Ablauf der Animationen einzubinden. Nach einiger Suche ist eine Dokumentation mit einigen Beispielen und Listen der verfügbaren Befehle zu finden.

Inhaltsverzeichnis



 

Hypertextversion des Lehrbuchs `Introduction to Algorithms'

Dem Benutzer wird die Möglichkeit gegeben, während der Arbeit mit der Lernsoftware, Informationen zu allen in der Software bearbeiteten Themen aus dem tausendseitigen Standardwerk zu erhalten. Unterstützung findet der Benutzer in den ausgereiften Hypertext-Konzepten, den Navigationsmöglichkeiten durch das Buch (siehe unteres Navigationsfenster), der Volltextsuche und der Möglichkeit, eigene Pfade durch das Buch definieren zu können.


 
 

Inhaltsverzeichnis


Bewertung der Software

`Animated Algorithms' ist eine gelungene und professionelle Lernsoftware, die sicherlich dem Stand der Softwareentwicklung von 1993 entsprach, wenn sie dieser nicht sogar in vielen Dingen voraus war. Die positiven Punkte sind zum einen das gut durchdachte Konzept, mit dem das Produkt geplant und implementiert wurde, zum anderen die einfach zu verstehende und homogene Oberfläche, die den Studenten nicht vom eigentlichen Ziel, dem Verständnis für die unterschiedlichen Algorithmen, abbringen soll. Trotz all der Homogenität und Klarheit bleibt das Interesse des Benutzers durch viel Interaktivität mit dem Programm stets erhalten.

Die große Anzahl von Algorithmen und Datenstrukturen, die `Animated Algorithms' visualisiert, macht das Programm regelrecht zu einem Nachschlagewerk, einerseits, um sich die Arbeitsweise der Algorithmen wieder ins Gedächtnis zu rufen, andererseits, um die formalen Aspekte zu verstehen. Dazu bietet das mitgelieferte Buch `Introduction to Algorithms' in Hypertextversion ein umfassendes Referenzwerk, in dem nahezu alle elementaren Algorithmen und Datenstrukturen aufgeführt sind.

Äußerst positiv sind die verwendeten Hypertext-Konzepte zu beurteilen. Die Navigationsmöglichkeiten durch das Lehrbuch bieten den Benutzern auch noch im heutigen Zeitalter des Internets eine komfortable Hypertextumgebung. Die Verbindung zwischen Buch und Animationsumgebung ist nicht so gelungen, wie man es sich vorgestellt hätte, denn es bedarf einiger Zeit und Mühe, einen Link direkt von der Animation zum entsprechenden Thema im Buch zu sinden. Leider können keine Textdokumente ausgedruckt werden. Durch die schlechte Darstellung der Texte auf dem Bildschirm wird ein längeres Lesen erschwert.

Negativ zu bewerten ist zum einen, daß die Anzahl von zu sortierenden Elementen bei fast allen Sortieralgorithmen zu gering ist. So ist die Arbeitsweise von `Quick Sort' sicherlich nicht mit nur fünfzehn Elementen visualisierbar, dazu bräuchte es annähernd fünfzig Elemente. Die Auswahl aus einer kleinen Grundmenge kann der Benutzer zwar eigens festlegen, nicht aber die Anzahl der Elemente. Ferner wird beim `Quick Sort' das aktuelle Pivot-Element nur mit der Angabe einer Zahl im oberen Bereich des Animationsfensters angezeigt. Eine Färbung der entsprechenden Kugel in der Animation wäre vorteilhafter gewesen. Die Ablaufgeschwindigkeit der Animationen läßt sich anzeigen, (vermutlich wegen eines Programmierfehlers) aber nicht verändern, wobei gerade dieses Feature bei Visualisierungen von Algorithmen besonders wichtig ist (vgl. Gloor, Kapitel 27 des Buchs `Software Visualization').

Insgesamt wurde sehr an Farbe gespart, so daß es schwer fällt, die Knöpfe, die auf Mausklick reagieren, ausfindig zu machen. Gloor nennt in einem seiner Artikel den Geschwindigkeitsverlust der Animationen als Grund für die wenigen Farben. Dann bleibt jedoch die Mitlieferung von Videosequenzen unverständlich, denn gerade diese beanspruchen wesentlich mehr Ressourcen, als eine zusätzliche Markierungsfarbe für Knöpfe. Der Inhalt, der durch die `talking head`-Videos vermittelt werden soll, ist hauptsächlich auf knappe Einleitungen beschränkt, die ohnehin schriftlich in den Hypertextdokumenten vorhanden sind. Des weiteren beschränkt sich der Ton außerhalb der Videosequenzen, der ebenfalls in dem Artikel von Gloor angepriesen wird, auf systemeigene Töne.

Schade ist, daß sich mit `Animated Algorithms' nur die mitgelieferten Algorithmen veranschaulichen lassen. Zwar hätte man in einigen wenigen Fällen eigens programmierte Skripte in den Ablauf von Algorithmen einbringen können, aber wie bereits erwähnt, ist es relativ schwer, eine Anleitung zu diesem Thema zu finden. Es handelt sich bei dem getesteten Produkt also wirklich nur um Lernsoftware, nicht um eine Oberfläche, mit der beliebige Algorithmen visualisiert werden können.

Inhaltsverzeichnis


Fazit

Die Lernsoftware `Animated Algorithms' ist insgesamt ein weiterzuempfehlendes Produkt für Anfänger, die den Umgang mit Algorithmen und Datenstrukturen erlernen wollen. Eingeschränkt bleibt die Benutzung des Programms jedoch auf Besitzer eines Macintosh.

Fortgeschrittenen sei geraten, sich das Buch `Introduction to Algorithms' von Cormen, Leiserson und Rivest in gedruckter Form anzuschaffen.

Gloor sagt im letzten Absatz seines Artikels: "Auch wenn die meisten anspruchsvollen Hypermedia-Lernumgebungen niemals einen menschlichen Lehrer ersetzen können, so sollen sie ihn zumindest bei der Vermittlung komplexer Sachverhalte unterstützen." Mit `Animated Algorithms' liegt ein solch unterstützendes Lernprogramm vor. Dem Lernenden ist es allerdings nicht immer möglich, bei diesem Lernprozeß seine eigenen Ideen einzubringen.

Inhaltsverzeichnis


Quellenangabe: