Seminar:
"Interaktive Visualisierung von Algorithmen"
WS 98/99
Ausarbeitung zum Thema:
Anzeigen für Algorithmen-Animationen

Michael Gründler



Inhalt

Einleitung

In dieser Ausarbeitung werden zwei Kapitel aus dem Buch: "'Software Visualization - Programming as a Multimedia Experience"' behandelt. Kapitel 3 des Buches mit dem Titel "'A Taxonomy of Algorithm Animation Displays"' verfaßte Marc H. Brown und Kapitel 7 mit dem Titel: "'Fundamental Techniques for Algorithm Animation Displays"' verfaßten Marc H. Brown und John Hershberger. Diese Ausarbeitung wurde im Rahmen eines Seminars als Vortrag gehalten.
Die Visualisierung von Algorithmen ist eine bildhafte Darstellung von Abstraktionen von Software. Die Animation von Algorithmen ist eine dynamische Visualisierung über ein passives Medium, wie z.B. Video, Film oder ein interaktives System. Animationen von Algorithmen zeigen mittels graphischer oder auditiver Methoden wie Algorithmen funktionieren. Die Visualisierung von Algorithmen ist mehr als nur die Anzeige des Programm-Codes und der zu verarbeitenden Daten, und geht über die Programmvisualisierung hinaus. Als wichtigen Teil der Software Visualisierung werde ich im folgenden die Anzeige der Algorithmen-Animationen im Detail betrachten.


Charakterisierung von Anzeigen

Anzeigen für Algorithmen-Animationen lassen sich in drei Dimensionen charakterisieren:

   
Abbildung 1: In der Inhalts-Achse reicht die Darstellung von der direkten Repräsentation des Programmcodes bzw. der Daten bis hin zur Darstellung mittels generierter Abbilder der Informationen. In der Persistenz-Achse reicht die Darstellung von dem augenblicklichen Stand der Daten bis zu einer Darstellung in der auch alle vorangegangenen Änderungen sichtbar gemacht werden. Die Skala der Transformations-Achse reicht von einer diskreten bis zur kontinuierlichen Darstellung der Änderungen.

Die Inhalts-Achse

Die direkte Anzeige besteht aus zu einer oder mehreren Datenstrukturen eines Programms oder zu einem Programm isomorphen Bildern. Die Datenstrukturen können jederzeit aus der Anzeige, und die Anzeige jederzeit aus den Datenstrukturen konstruiert werden. Für diesen Prozeß werden keine zusätzlichen Informationen benötigt. Die Programmcode- Ansicht in Abbildung 2 ist eine direkte Anzeige des statischen Programmcodes des Algorithmus. In dem obersten Fenster der Programmcode- Ansicht ist anhand einer hervorgehobenen Zeile ein dynamischer Programmzähler zu erkennen. Ein dynamischer Stack ist durch überlappende Fenster dargestellt.


  
Abbildung 2: Der Algorithmus First-fit binpacking zur Lösung des Binpacking Problems. Das Binpackingproblem besteht darin, eine Anzahl von Gewichten in eine Reihe von Behältern einzuordnen. Die Behälter verfügen über eine begrenzte Kapazität, die nicht überschritten werden darf. Der First-fit Algorithmus durchläuft die Reihe der Behälter von links nach rechts bis in einem Behälter genügend Platz für das gewählte Gewicht vorhanden ist. Eine optimale Aufteilung der Gewichte kann durch diesen Algorithmus nicht garantiert werden.

Synthetische Anzeigen zeigen die Ursache für die Änderungen der Daten an oder sind Abstraktionen der Daten. Sie sind keine Abbildungen der Programmvariablen.
Die Waste view(Verschnittsicht) in Abbildung 2 zeigt ein Beispiel für eine synthetische Anzeige. Nachdem jedes Gewicht in einen Behälter abgelegt wurde, zeigt der obere Graph wieviel Platz in jedem Behälter übrig ist, und dieser somit nicht optimal genutzt wurde. Das Konzept des ungenutzten Platzes ist nicht Bestandteil des Programmes.

  
Abbildung 3: zeigt den Algorithmus Insertion sort. Das linke Fenster zeigt die Stick view. Ein Array ist dargestellt als eine Reihe von Säulen deren Höhe mit ihrem Wert korrespondiert. Die unter den Säulen plazierten Rechtecke bezeichnen die zur Zeit gerade aktiven Säulen. Die im rechten Fenster abgebildete Compare-Exchange view repräsentiert Vergleiche zwischen zwei Elementen als graue Kreise und Vertauschungen als schwarze. Für jedes Element das einsortiert werden soll, wird eine neue Zeile begonnen.


Viele Anzeigen sind eine Mischung aus direkter und synthetischer Anzeige. Abbildung 3 zeigt eine Compare-Exchange view eines Sortieralgorithmus. Zusatzinformationen, die das Ergebnis eines Vergleiches oder einer Vertauschung zeigen, sind durch unterschiedliche Farben der Elemente dargestellt. Der aktuelle Inhalt des Arrays läßt sich aus dem Gesamtbild rekonstruieren, diese Eigenschaft ist aber nicht umkehrbar. Das Bild kann nicht mit dem Wissen über den aktuellen Inhalt des Arrays rekonstruiert werden. Um die fundamentalen Operationen des Algorithmus darzustellen, wird der Ablauf des Algorithmus gezeigt. Jede Iteration des Algorithmus wird in einer separaten Zeile angezeigt.

  
Abbildung 4: zeigt den Algorithmus Quicksort. Das linke Fenster zeigt eine Dots view. Jedes Element ist durch einen Punkt dargestellt. Die horizontale Koordinate korrespondiert mit der Position im Array, die vertikale Koordinate mit dem Wert des Elements. Die Partition- Tree view auf der rechten Seite, zeigt jedes Element des Array als Knoten in einem Baum. Die horizontale Position der Elemente korrespondiert mit deren Position im Array. Elemente, die bereits richtig einsortiert wurden sind durch runde Knoten dargestellt. Elemente, die noch einsortiert werden müssen sind in rechteckigen Knoten zusammengefaßt. Die Tiefe der Rechtecke im Baum gibt das Intervall an, in dem die Elemente einsortiert werden.

Die Partition-Tree viewin Abbildung 4 beinhaltet sowohl den direkten als auch den synthetischen Aspekt. Sie ist eine direkte Anzeige des bearbeiteten Arrays, da jeder Knoten mit einem Element des Arrays korrespondiert. Ein inorder Durchlauf des Baumes zeigt die Elemente des Arrays in geordneter Reihenfolge an. Die Anzeige ist synthetisch, denn die Baumansicht zeigt mehr als nur die Daten; sie zeigt den Weg wie der Algorithmus die Daten verarbeitet hat.

Die Persistenz-Achse

Die Tatsache, ob eine Anzeige aktuelle Informationen oder alle vergangenen Informationen zeigt, ist das zweites Kriterium, um Anzeigen zu klassifizieren.In Abbildung 2 zeigen - bis auf die Bins view alle Anzeigen auch vergangene Informationen. Die Weight view zeigt alle - über die Variable wt eingelesenen und in die Behälter abgelegten - Gewichte. Ein darunter gezeichnetes Dreieck gibt an, wann ein neuer Behälter angefangen wurde. Auch die Waste view zeigt vergangene Informationen, lediglich die rechte Ecke zeigt den Verschnitt des Platzes des gerade gewählten Behälters an. Die Code view zeigt den Programmtext. Die Compare-Exchange viewaus Abbildung 4 zeigt alle Vergleiche und Vertauschungen des Algorithmus. Diese Anzeige zeigt deutlich, daß Insertion sort ein Algorithmus mit quadratischem Aufwand ist. Sei die Anzahl der zu sortierenden Elemente gleich n, dann existieren in der Anzeige n Zeilen und n Spalten und damit n 2 Punkte. Im Durchschnitt wird jede Zeile zur Hälfte gefüllt, d.h. markierte Punkte. Im schlechtesten Fall liegen die Elemente in geordneter abnehmender Reihenfolge vor, und die Hälfte der n2 möglichen Punkte werden markiert.

Die Übergangs-Achse

Das dritte und letzte Kriterium beschreibt den Übergang von einer Anzeige in die nächste. Die inkrementelle Transformation zeigt einen fließenden Übergang in die nächste Anzeige. In Abbildung 2 zeigt das Fenster "'packing w/probes"' als einziges eine inkrementelle Transformation. Die gepunktete Box zeigt einen Versuch, ein Gewicht in einen Behälter einzufügen. Alle anderen Fenster zeigen diskrete Transformationen. Bei einer diskreten Transformation wird das neue Bild ohne Übergänge mit sämtlichen neuen Informationen dargestellt. Es wird nicht gezeigt, wie z. B. ein Element versetzt wird sondern nur, daß es versetzt worden ist. Diskrete Transformationen werden als inkrementelle Transformationen wahrgenommen, wenn der Unterschied zwischen zwei Bildern klein genug ist in Beziehung zur Komplexität der Daten. Bei großen Datensätzen haben sich diskrete Transformationen als sinnvoll erwiesen. Inkrementelle Transformationen haben ihre größte Effektivität wenn der Benutzer einen Algorithmus mit kleinen Datensätzen arbeiten läßt. Inkrementelle Transformationen stören durch signifikante Verlangsamung und zuviel Details oftmals die Anzeige des Algorithmus bei großen Datenmengen. Bei inkrementellen Transformationen sind einige Aspekte zu betrachten. Zum Beispiel kann das Umsetzen eines Zeigers in einem Baum ein aufwendiges Umsetzen eines Unterbaumes über eine große Distanz nach sich ziehen. Es ist nicht geklärt, wie lange diese Umsetzung dauert. Es könnte genauso lange dauern wie eine Umsetzung über eine kurze Distanz, andererseits könnte eine Bewegung immer eine konstante Zeit dauern, so daß sehr schnell eine große Distanz überwunden werden kann.

Weitere Aspekte

Eine weitere Fragestellung bei Anzeigen für Algorithmen-Animationen bezieht sich auf die Wiederverwendbarkeit. Es stellt sich die Frage, ob eine Anzeige die für eine bestimmte Situation angefertigt wurde, auch für unterschiedlichen Situationen genutzt werden kann.
Generelle Anzeigen haben den Vorteil, daß sie einmal für einen Algorithmus implementiert, leicht für andere Algorithmen verwandt werden können. Ein triviales Beispiel ist die Code-Anzeige in Abbildung 2. Diese Anzeige kann für jeden Algorithmus verwendet werden. Vorraussetzung dafür ist, daß der Benutzer die Bedeutung von den überlappenden Fenstern und der hervorgehobenen Zeile verstanden hat. In Abbildung 4 ist die Dots view für alle Algorithmen verwendbar, die Partition-Tree view ist nur für Quicksort von Bedeutung. Für den Benutzer haben generelle Anzeigen zwei Vorteile: Ein Nachteil genereller Anzeigen ist es, daß die besonderen Merkmale eines Algorithmen meist nicht illustriert werden können.
  
Abbildung 5: zeigt eine generelle Anzeige für vier unterschiedliche Sortieralgorithmen. Durch die Besonderheit der "'Step Size"' im linken unteren Bild wird die Unterscheidung der mit dieser generellen Anzeige dargestellten Sortieralgorithmen besonders schwierig.


Fundamentale Techniken

Die Gestaltung einer aussagekräftigen Softwarevisualisierung ist eine psychologische Herausforderung. Dem Designer stellen sich mehrere Fragen: Bei der Softwarevisualisierung wird der Animateur mit Problemen konfrontiert mit denen "'klassische"' Grafik- Designer nicht konfrontiert werden. Dazu gehören: Dieses Kapitel behandelt die in der Literatur beschriebenen, fundamentalen Techniken zum Animieren von Algorithmen. Der erste Teil dieses Kapitels beschreibt die Techniken die, von Brown und Sedgewick in der Mitte der 80er Jahre, mit dem "'BALSA algorithm animations system"' an der Brown University entwickelt wurden. Der zweite Teil des Kapitels beschreibt Techniken die im Zeitraum von fünf Jahren mit dem "'Zeus algorithm animation system"' entwickelt wurden. Die in diesem Kapitel beschriebenen Techniken sind nicht formal evaluiert worden.
Obwohl die in diesem Kapitel beschriebenen Techniken im Kontext von "'BALSA"' und "'Zeus"' entwickelt wurden, sind sie dennoch unabhängig von diesen Systemen. Diese Techniken können direkt auf andere Systeme angewendet werden.

Eine oder mehrere Anzeigen

Eine monolitische Anzeige konzentriert alle Informationen über einen Algorithmus in einem einzigen dynamischen Bild. Monolitische Anzeigen werden bei einfachen Algorithmen wie z.B. Quicksort verwendet. Wann immer der Benutzer eine monolitische Anzeige eines komplizierten Algorithmus, oder mehrere Aspekte eines einfachen Algorithmus betrachtet, müssen so viel Informationen verschlüsselt werden, daß der Benutzer Schwierigkeiten bekommt, interessante Details aus der Anzeige zu erfahren. Es ist generell effektiver, einen Algorithmus mit mehreren verschiedenen Anzeigen zu illustrieren.
In dem größten Teil des Buches:"'Software Visualization "' werden Animationen mit mehreren Anzeigen benutzt, wobei jede Anzeige nur wenige Aspekte eines Algorithmus zeigt. Jede Anzeige ist auch isoliert leicht zu verstehen, dennoch ist die Komposition mehrerer verschiedener Anzeigen informativer als die Summe ihrer individuellen Beiträge.
Ein weiterer Vorteil von mehreren Anzeigen ist, daß jede Anzeige für sich gewöhnlich einfacher zu entwerfen und deshalb auch einfacher zu implementieren sind.

Zustandsanzeigen

Zustandsveränderungen an der Datenstruktur des Algorithmus können durch Änderungen der graphischen Repräsentation auf dem Bildschirm sichtbar gemacht werden. In einer Animation des Quicksort-Algorithmus ist ein Knoten solange rund dargestellt, wie die zugehörige Menge von Elementen noch nicht fertig sortiert ist. Erst wenn alles sortiert ist, wird der Knoten eckig dargestellt. Zustandsanzeigen zeigen das dynamische Verhalten von Algorithmen. In dem Quicksort-Beispiel werden unsortierte Elemente eines Subfiles durch horizontale Rechtecke repräsentiert. Wird ein Subfile partioniert, wird die Box durch einen Knoten mit zwei kleineren Boxen als Kindknoten ersetzt. Durch die Beobachtung der sich aufteilenden Boxen und das Entwickeln eines Baumes kann der Benutzer ein Verständnis für den Algorithmus erlangen. Durch das Repräsentieren spezifischer Objekte auf die gleiche Art und Weise, werden unterschiedliche Anzeigen miteinander verbunden.

Statische Anzeigen

Eine statische Anzeige, die den Verlauf eines Algorithmus bei der Verarbeitung von Daten zeigt, hilft bei dem Verstehen des Algorithmus ebenso wie ein Beispiel aus dem Lehrbuch. Mit dieser Anzeige kann der Benutzer seine Lerngeschwindigkeit selbst bestimmen, um mit dem dynamischen Verhalten des Algorithmus vertraut zu werden. "'Zeus"' bietet zum Beispiel die Möglichkeit "'Snapshots"' von mehreren Programmläufen zu generieren. Der Benutzer kann sich auf die entscheidenden Ereignisse, die die wichtigen Änderungen herbeiführen, konzentrieren ohne denjenigen Ereignissen zuviel Aufmerksamkeit zu widmen die sich lediglich wiederholen.

Kontinuierliche oder diskrete Übergänge

Die graphische Repräsentation einer Änderung einer Datenstruktur kann entweder inkrementell oder diskret erfolgen. Inkrementelle Änderungen sind bei kleineren Datenstrukturen hilfreicher. Ein Beispiel sei ein Sortieralgorithmus der die Plätze zweier Punkte vertauscht. Diese Vertauschung ist als kontinuierliche Animation besser zu sehen als ein abruptes Löschen und Neuzeichnen der Punkte. Bei großen Datenmengen erscheinen kleine diskrete Änderungen wie kontinuierliche Änderungen.

Darstellung mehrerer Algorithmen

Werden mehrere Algorithmen gleichzeitig animiert, kann der Benutzer die unterschiedlichen Arbeitsweisen direkt miteinander vergleichen.
Im Animationssystem "'Zeus"', werden mehrere Algorithmen in separaten Threads dargestellt. Hat ein Algorithmus einen interessanten Ereignispunkt erreicht, wird auf eine Anzeige eines anderen Algorithmus gewechselt. Es wird solange gewartet bis alle Algorithmen diesen interessanten Ereignispunkt erreicht haben.

Auswahl der Eingabedaten

Die Wahl der Dateneingabe ist stark von dem Zweck einer Animation beeinflußt. Nach Brown und Sedgewick eignen sich kleine Datenmengen gut für die Einführung eines neuen Algorithmus, wohingegen große Datenmengen beim Entwickeln eines intuitiven Verständnisses der Arbeitsweise eines Algorithmus hilfreich sind. Ihre Arbeit mit "'Zeus"' bestätigte diese Schlußfolgerung und leitete neue Untersuchungen über die Wichtigkeit der Wahl der Dateneingabe bei Animationen ein.
Animationen, die die textuelle Beschreibung eines Algorithmus vervollständigen, sollten mit einem Beispiel eines kleinen Problems eingeführt werden. Diese Einführung sollte vorzugsweise mit kleinen textuellen Annotationen durchgeführt werden. Das soll dem Benutzer unterstützen, eine Verbindung zwischen der visuellen Anzeige und seinem Verständnis herzustellen. Hat der Benutzer diese Verbindungen hergestellt, können größere und interessantere Daten eingeführt werden. Dadurch kann die dynamische Leistungsfähigkeit der Animation vollständig ausgenutzt werden.
Die Eingabe von pathologischen Eingabedaten kann zu einem extremen Verhalten des Algorithmus führen. Im worst case für Quicksort (alle Elemente liegen in umgekehrter Reihenfolge vor) steigt die durchschnittliche Laufzeit von auf O(n2).
Aus pädagogischer Sicht kann es sinnvoll sein, Eingabedaten vorzubereiten. Manche Algorithmen arbeiten so perfekt, daß wichtige Schritte in der Praxis der Animation nicht auftreten würden. Zu diesem Zweck werden sogenannte "'Cribbler"' eingesetzt. Mit "'Cribbler"' können auch Effekte betrachtet werden, die durch die Effektivität der Algorithmen bei der Verarbeitung normaler Eingabedaten verborgen bleiben würden.
Als Beispiel dient ein Hashalgorithmus, bei dem es bei den meisten Eingabedaten nicht zu Kollisionen kommt. Erst durch den Einsatz eines "'Cribbler"' konnten die Eingabedaten so modifiziert werden, daß es zu einem Rehashing kommt.

Farb-Techniken

Farbe hat das Potential, große Mengen von Informationen effektiv zu übertragen. Dieses Ziel ist jedoch nicht immer leicht zu erreichen. Theoretiker, allen vorran Jacques Bertin und Edward Tufte gaben exzellente Ratschläge für den Einsatz von Farbe. Brown und Sedgewick versuchten, deren Prinzipien zu folgen, dennoch ist die Psychologie der Farbe zur Verbesserung der Kommunikation nicht Schwerpunkt dieses Kapitels. Farbe wurde in fünf klar voneinander getrennten Arten eingesetzt: Verschlüsseln des Zustands von Datenstrukturen, Hervorheben von Aktivität, Verbinden von Anzeigen, Betonen von Mustern und sichtbar machen von vergangener Aktivität. Die ersten beiden Anwendungen von Farbe sind in den meisten Algorithmenanimationssystemen zu finden.
Tatsache ist, daß diese fundamentalen Techniken des Farbeinsatzes auf erste Arbeiten der Algorithmenanimation zurückzuführen sind. Gezeigt wurden sie in Filmen von Booth mit dem Titel: PQ Trees und Baeckers Sorting Out Sorting.

Zustandskodierung der Datenstrukturen

Farbe erhöht und komplettiert als ein Indikator für den Zustand eines Algorithmus, den Effekt der vorher beschriebenen graphischen Techniken. Somit ergibt sich eine zusätzliche Dimension für Zustandsanzeigen: Informationen werden sowohl über die Farbe als auch über die Form des Objektes übertragen. Dadurch ist eine höhere Präsentationsdichte von Informationen möglich. Für die Darstellung eines Objektes in einer eigenen Farbe werden weniger Pixel benötigt als für die Darstellung in einer eigenen Form. Somit können gleichzeitig mehrere Objekte dargestellt werden. Die Wahrnehmung allgemeiner Muster, wenn z.B. die Darstellung einer einfarbigen Gruppe kleiner Dreiecke zu einer Mischung von Kreisen und Rechtecken wechselt, ist schwerer, als wenn die Darstellung einer Gruppe von schwarzen Punkten zu einer Mischung aus roten und blauen Punkten wechselt.

Aktivität hervorheben

Viele Animationen zeigen zeitweilig eine kleine Region mit einer transparenten kontrastreichen Farbe um die Aufmerksamkeit auf das gezeichnete Gebiet zu lenken. Die zur Hervorhebung benutzte Farbe ist transparent und interferiert nicht mit den auf dem Bildschirm dargestellten Datenelementen.

Verbindung zwischen mehreren Anzeigen

Mehrere Anzeigen zeigen oftmals verschiedene Aspekte der gleichen Datenstruktur oder unterschiedliche Repräsentationen logisch verwandter Objekte. In diesem Fall verwendet eine Anwendung in jeder der Anzeigen die gleichen Farben für korrespondierende Merkmale. Dadurch entsteht ein integriertes harmonischeres Bild.

Anzeigen der historischen Daten

Oftmals wird für die Darstellung der "'Ablaufgeschichte"' eines Algorithmus ein Farbspektrum verwandt. Tufte führt an, daß Menschen die Farbanordnung des Regenbogens als nicht geordnet empfinden. Trotzdem kann eine Ordnung von Farben nach dem Farbton erfolgen, um eine lineare Zeitfolge zu repräsentieren.

Schlußbemerkung

Effektive Visualisierungen zu erstellen ist mehr Kunst als Wissenschaft. Alle hier beschriebenen Techniken sind nicht formal evaluiert oder verifiziert worden. Sie basieren nur auf umfangreiche Erfahrungen und auf Experimente.

Das Softwarevisualisierungsprogramm MacBALSA

Dieses Kapitel ist für die Seminarteilnehmer für eine Demonstration des Softwarevisualisierungsprogramm MacBALSA und als Vorbereitung auf eine Übung mit dem MacBALSA gedacht.

Einleitung MacBALSA

Das Softwarevisualisierungsprogramm MacBALSA stützt sich auf die These, daß Algorithmen am besten über interaktive Simulationen verstanden werden können. Ein Bild ist mehr wert als tausend Worte - ein bewegtes Bild ist noch wertvoller - und die Möglichkeit der Interaktion mit einem Film ist unschätzbar wertvoll.
Marc H. Brown visualisierte Algorithmen aus 5 verschiedenen Anwendungsgebieten mit dem Programm MacBALSA. Dazu gehören:

Die Menues von MacBALSA

MacBALSA bietet 6 Menues an: File, Edit, Run, Chapters, Algs und Views.

Das File-Menu


 
Tabelle 1: Das File-Menu
File-Menu
Menueintrag Funktion
Save Scene speichert die Scene in einer Datei
Restore Scene stellt eine Scene aus einer Datei wieder her
Start Autoring startet die Aufzeichnung einer Scene und sichert sie in einer Datei
Start Reading startet das Abspielen einer Scene aus einer Datei
Quit beendet MacBALSA

Das Edit-Menu

Das Edit-Menu enthält die Standard Macintosh Kommandos zum Editieren von Text. Dazu gehören: cut, copy, paste und undo.

Das Menu-Menu

Ein stop- point in MacBALSA entspricht einem Breakpoint in einem konventionellen Debugger. Mit einem step-point kann man den Algorithmus bis zu einem wichtigen Ereignis ausführen lassen.
 
Tabelle 2: Das Menu-Menu
Menu-Menu
Menueintrag Funktion
Reset stoppt den gerade aktiven Algorithmus
Go führt den Algorithmus bis zu nächsten Stop-Point aus
GoGo führt den Algorithmus aus, pausiert am nächsten Stop-Point
Step führt den Algorithmus bis zu nächsten Step-Point aus
Trace führt den Algorithmus aus, pausiert am nächsten Step-Point
Stops ... zeigt einen Dialog, um die Werte der Kosten, Stops und Steps der Events einzustellen
Speed ... zeigt einen Dialog, um einzustellen wieviel Zeit nach einem Event pausiert werden soll.

Das Chapter-Menu

Die Namen der Menueinträge entsprechen den Namen der Kapitel.

Das Algs-Menu


 
Tabelle 3: Das Algs-Menu
Algs-Menu
Menueintrag Funktion
Parms ... zeigt einen Dialog, in dem man Parameter des ausgewählten Algorithmus einstellen kann. Während ein Algorithmus abläuft heißt der Menueintrag ShowParms, und läßt nur die Beobachtung der Parameter zu.
Windows ... zeigt einen Dialog, um neue Algorithmen-Fenster auszuwählen.

Das Views-Menu


 
Tabelle 4: Das Views-Menu
Views-Menu
Menueintrag Funktion
Parms ... zeigt einen Dialog in dem man Parameter der ausgewählten Anzeige einstellen kann. Das ist nur möglich wenn der Algorithmus einstellbare Parameter anbietet.
Windows ... zeigt einen Dialog, in dem man die Fensteranordnung, die Anzahl der Fenster und deren Funktion wählen kann.

Grundlegende Konzepte von MacBALSA

Ein Algorithmus der mit MacBALSA animiert wird, wird aufgeteilt in den Algorithmus, und in mehrere Anzeigen die den Algorithmus in Aktion zeigen. MacBALSA erlaubt dem Benutzer zur Laufzeit Anzeigen auszuwählen, die den Algorithmus zeigen sollen. Der Algorithmus wird von MacBALSA ausgeführt, ohne Kenntnis der vom Benutzer ausgewählten Anzeigen. Die Anzeigen werden ausgeführt, ohne Kenntnis des ausgewählten Algorithmus. Somit gibt es eine saubere Trennung zwischen der Implementation des Algorithmus und der Anzeigen. Erst für die Visualisierung werden Algorithmus und Anzeige miteinander verbunden. Jeder Algorithmus und jede Anzeige kann über Parameter beeinflußt werden.

Rechnerübung und Demo

Das obere Fenster zeigt eine inkrementelle Anzeige des Binpacking Algorithmus. Es wird gezeigt wie der Algorithmus die Gewichte (Weigths) in die Behälter (Bins) einfügt.Das linke untere Fenster zeigt die gleiche Anzeige wie oben als diskrete Animation. Man sieht nur das Gewichte eingefügt werden, aber nicht wie der Zielbehälter gefunden wird. Das rechte Fenster zeigt die Gewichte.
 
Tabelle 5: Die Binpacking-Algorithmen
Binpacking Algorithmen:
Algorithmus Funktion
First-Fit Der Algorithmus überprüft die Behälter von links nach rechts, und fügt das Gewicht in den ersten passenden Behälter ein.
Best-Fit Der Algorithmus überprüft den letzten neuen Behälter zuerst, und prüft dann rückwärts in Richtung des ersten Behälters. Das Gewicht wird in einen möglichst vollen Behälter eingefügt, um so wenig Platz wie möglich ungenutzt zu lassen.
Worst-Fit Der Algorithmus fügt das Gewicht in einen neuen Behälter am Ende der bereits benutzten Behälter ein und sucht den nächsten Behälter der mehr unbenutzten Platz zur Verfügung hat. In diesen Behälter wird das Gewicht eingefügt.

Eine andere Anzeige auswählen

Das rechte Fenster zeigt den Weg den ein Gewicht bis zu seinem Zielbehälter zurücklegt. Für jedes Gewicht wird eine neue Zeile begonnen.

Zwei Sortieralgorithmen animieren

Aufgabe ist es, zwei Sortier-Algorithmen nebeneinander zu animieren. In der Dots-View können die unterschiedlichen Arbeitsweisen der Algorithmen betrachtet werden. Die vertikale Koordinate der Punkte entspricht der Größe der Elemente, die horizontale Koordinate der Positionen im Array. Auffällig ist, das der Heapsort-Algorithmus deutlich schneller sortiert als der Insertion Sort Algorithmus. Aufgabe: Animation von 3 Algorithmen. Die Animation von Bubblesort soll hinzufügt werden, Bubblesort soll 25 Elemente sortieren.

Scene aufzeichnen und wiedergeben

Eine Scene besteht aus einer oder mehreren Animationen. Eine Scene kann aufgezeichnet und in einer Datei abgespeichert werden. Zum Abspielen einer Scene wird eine Datei geladen aus der die Scene ausgelesen wird. Das Abspielen einer Scene kann über eine Steuerleiste am unteren Bildrand beeinflußt werden. Eine Scene abspielen:

Bibliography

1
John T. Stasko, John B. Domingue, Marc H. Brown und Blaine A. Price (Hrsg.): "Software Visualization". 1998. MIT Press, Cambridge, Massachusets.

2
Marc H. Brown: "MacBALSA". Software und Dokumentation.
http://www.research.digital.com/SRC/zeus/balsa/ Heruntergeladen im August 1998.

About this document ...

Seminar:
"Interaktive Visualisierung von Algorithmen" WS 98/99
Ausarbeitung zum Thema:
Anzeigen für Algorithmen-Animationen

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 1 visualisierung.tex.

The translation was initiated by root on 1999-03-19



root
1999-03-19