Visualisierung von Algorithmen


Es ist sehr aufwändig, eine gute Visualisierung für einen Algorithmus zu programmieren; daher nutzen wir die interaktive Geometriesoftware
Cinderella als Basis für unsere Programme.
In der jetzigen Phase unserer Forschung beschränken wir uns auf Graphalgorithmen, da diese sich durch ihre Anschaulichkeit besonders für den Schulunterricht eignen.
Außerdem arbeiten wir mit anderen Projekten innerhalb des Forschungszentrums zusammen, die Bedarf an 2D-Visualisierung haben; durch die leistungsfähige Basis und unsere Expertise können wir schnell angepasste Visualisierungswerkzeuge entwickeln.
Zentrale Fragen
  • Was ist eine gute Visualisierung eines Graphalgorithmus'?
  • Wie kann ein Benutzer Algorithmen und Spezifikationen für ihre Visualisierung möglichst einfach eingeben?
  • Ist es möglich, eine gute Visualisierung automatisch aus einem Algorithmus abzuleiten? Wenn nein, wie weit kann der Benutzer bei der Visualisierungsspezifikation entlastet werden?
  • Können die separaten Probleme des Algorithmus selber und seiner Visualisierung vom Benutzer unabhängig voneinander behandelt werden?
Zwei Beispiele

Dijkstra

Dijkstras kürzeste-Wege-Algorithmus. Es werden mehrere verschiedene Informationen dargestellt:

  • Kantengewichte
  • Startknoten
  • Aktueller Knoten
  • Bisherige kürzeste Wege
  • Aktuell geprüfte Kanten
  • Bisherige Kosten der kürzesten Wege
  • Aktuelle Gesamtkosten über die geprüfte Kante
  • Spezielle Darstellung, wenn die aktuellen Gesamtkosten zu einem Knoten niedriger sind als die bisherigen
Inwieweit können die Positionen und Sichtbarkeiten dieser Informationen automatisch bestimmt werden? Welche Eingaben muss ein Benutzer mindestens noch tätigen?

Depth-First-Search

Tiefensuche. Eine etwas unkonventionelle Darstellung, nach jedem Backtracking wird eine neue Farbe gewählt. Nicht dargestellt, aber wünschenswert, wäre eine Visualisierung des vom Algorithmus benutzten Stacks.