Projektdokumentation Gruppe 5 „MSA–Divide and Conquer“

Lehrveranstaltung Skriptsprachen / Objektorientierte Programmierung

Aus dem Modulhandbuch zu K7461 vom 1. September 2007:

„Aufbauend auf den Kursen ‚Programmiersprachen I und II‘ vermittelt diese Lehrveranstaltung eine Skriptsprache, die aktuell in Internetanwendungen genutzt wird. […] Die Studierenden werden in die Lage versetzt, komplexe Internet-Anwendungen zu verstehen und selbständig Applikationen mittleren Schwierigkeitsgrades zu implementieren.“

Teil der Aufgabenstellung ist es, eine Web-Anwendung zur Demonstration des Ablaufs eines wohlbekannten Algorithmus zu entwicklen und zu programmieren. Die Veranschaulichung des Ablaufs soll dabei bildhaft/animiert realisiert werden.

Die Aufgabe soll in einer Projektgruppe von etwa vier Studenten bearbeitet werden. Es sind die Aufgabenbereiche Projektleitung, Design und Logik sowie Funktionalität personell zu besetzen. Der Prokjektleiter soll dem Dozenten wöchentlich Bericht über den Status erstatten.

Abgabe ist am Donnerstag, 21. Januar 2010. Abzugeben ist ein komplettes und lauffähiges Projekt mit gut dokumentierten Programmen einschließlich Dokumentation der einzelnen Arbeitsanteile der Projektbeteiligten.

Über dieses Dokument

Dieses Dokument ist Teil des wöchtentlichen Berichts der Gruppe 5 (Algorithmus: Maximum–Sub-Array–Problem, Divide-and-Conquer–Lösung), bestehend aus Antonia Boemanns, Bianca Förster, Arne Johannessen und Holger Schropp. Es wächst zusammen mit dem Projekt und hält Ergebnisse, aber teils auch Hintergründe fest, die Teil der Durchführung oder der Leitung des Projekts sind.

Autor
Arne Johannessen
Letzte Änderung
$Date$

Terminplanung

Projektstatus
Implementierung ist nahzu abgeschlossen, Text und Layout sind immer noch offen
Nächster Meilenstein
15. Januar 2010
(verpasst)

Meilensteine

27. November 2009
Visualisierungskonzept fertig
4. Dezember 2009
Software-Design und Arbeitsaufteilung fertig, Beginn Implementierung
23. Dezember 2009
totale Korrektheit der Numerik, erste Ansätze einzelner Animationen zu erkennen
15. Januar 2010
Implementierung abgeschlossen, Beginn der Qualitätssicherungs-Phase
(verpasst)
19. Januar 2010, 24:00 Uhr
Freeze für Version 1.0
21. Januar 2010, 09:50 Uhr
Abgabe, Projektabschluss

Projekttreffen

Regelmäßiger Termin für die Projekttreffen ist freitags um 13:00 Uhr 12:45 Uhr 12:30 Uhr in der Cafete im Keller Bibliothek im Obergeschoss des A-Baus. Der Termin kann kurzfristig geändert werden. Folgende Projekttreffen haben stattgefunden:

  1. 5. November 2009
  2. 9. November 2009
  3. 20. November 2009
  4. 27. November 2009
  5. 4. Dezember 2009
  6. 11./12. Dezember 2009
  7. 18. Dezember 2009
  8. 8. Januar 2010
  9. 15. Januar 2010

Versionsgeschichte

20. Januar 2010, Version 1.0
erste Endfassung
21. Januar 2010, Version 1.0.1
Probleme 7, 10 und 11 behandelt
testweise eine Query-String–Abfrage für Arrays nach Nutzervorgabe eingebaut (z. B. [2, -3, 4, -1])
@accesskey eingefügt
Timing optimiert
kleinere Änderungen und Bugfixes
28. Januar 2010, Version 1.0.2
Lizenz geändert auf BSD 3-clause (einvernehmlich mit allen Teilnehmern)

Aufgabenverteilung

Administrativ

Projektleitung
Arne Johannessen
stellvertretende Projektleitung
Holger Schropp
Design und Logik
Bianca Förster und Antonia Boemanns
Funktionalität
Holger Schropp

Module zur Implementerung in Software

„Schaltstelle“ (quasi Rahmen, Leinwand und Kleber, um alles zusammen zu halten)
Arne Johannessen
arne/schaltstelle.js
Benutzerschnittstelle (Anbindung des HTML-DOMs an JS)
Arne Johannessen
arne/ui.js
Zahlenleiste zeichnen
Bianca Förster
bianca/zeichnen.zahlenleiste.js
MSA-Algorithmus (Numerik und ereignisbasierter Wiedereinstieg)
Holger Schropp
holger/algorithmus.js
„split“–Animation (Visualisierung der Einschränkung der Zahlenleiste auf den momentan betrachteten Sub-Array)
Holger Schropp
holger/animation.split.js
Hochfahr-Animation [1+2] (bereits bekanntes, linkes/rechtes Ergebnis „fährt hoch“; einschl. trivialer Fall)
Bianca Förster
bianca/animation.hochfahren.js
Randmaximum-Animation „Blöcke fliegen runter“ [A], Teil von [3+4]
Arne Johannessen
arne/animation.rmax.js
Randmaximum-Animation „positive und negative Blöcke annihilieren sich gegenseitig“ [B], Teil von [3+4]
Arne Johannessen
arne/animation.explosion.js
Randmaxima-Animation [5] und [6] (Visualisierung der Addition beider Randmaximorum; Ergebnis „fährt hoch“)
Antonia Boemanns
toni/animation.addition.js, toni/animation.rmax-summe.js
„merge“–Animation [7] (Visualisierung der Auswahl des höchsten aus je drei Maximis)
Antonia Boemanns
toni/animation.merge.js

Weitere Arbeitspakete

Basis für HTML/CSS
Arne Johannessen
Text
offen (kommissarisch durch den Projektleiter, falls keine andere Lösung gefunden wird)
Grafikdesign
Bianca Förster
Default-Zahlen für MSA
Arne Johannessen

Design und Implementierung

Allgemeine Hinweise

Soweit möglich und sinnvoll, werden Aufgabenaufteilung und Implementierung ähnlich Contract-first Design im Sinne des diesbezüglichen Montagsvortrags von Volker Birk durchgeführt. Im Wesentlichen sind die Konsequenzen folgende:

Die Dokumentation der einzelnen Module auf Projektebene wird überwiegend in den Modulen selbst in Textform vorgenommen. Die Module enthalten alle einen oder wenige JavaScript-„Klassen“ (genauer: Objekte zur Verwendung als Prototyp zusammen mit dem new-Operator). Neben einer kurzen Dokumentation zur „Klasse“ selbst in einem Dokumentationskommentar werden die Schnittstellen aller dieser „Klassen“ jeweils auf Methoden-Ebene dokumentiert. Das Ergebnis ähnelt dem Javadoc-Dokumentationsstil, eine automatische Weiterverarbeitung ist jedoch nicht vorgesehen.

Parallel zur Entwicklung ist eine Anzahl von Struktur- und Sequenzdiagrammen entstanden, deren graphische Qualität jedoch nicht wiedergabefähig ist. Diese (oder auch nur eine Auswahl davon) zur Ergänzung der Dokumentation sauber neu zu zeichnen, hat die Zeit leider nicht erlaubt.

Weitere Eigenschaften von Contract-first Design

Andere Eigenschaften des Contract-first Design nach Volker Birk werden bei uns nicht systematisch integriert. Eine Anwendung von automatisierten Softwaretestverfahren erfolgt lediglich im Einzelfall der Numerik des MSA-Algorithmus; der weitergehende Einsatz wird einerseits durch die fehlende Erfahrung der Mehrzahl der Entwickler, andererseits aber auch durch die Unit-Tests auf DOM-Operationen durch asynchrone gekapselte Objekte inhärente Komplexität erschwert.

Im Übrigen wurde festgestellt, dass der Ausbau der bereits bestehenden JavaScript-Kenntnisse bei der Mehrheit der Mitwirkenden von Vorteil wäre. Dies erfolgt nach Bedarf „on the job“.

Begriffsabgrenzung Contract-first Design

Der Begriff „Contract-first Design“ wird von verschiedenen Personen in unterschiedlichen Zusammenhängen verwendet. Insbesondere entsprechen nicht alle der in den folgenden Quellen beschriebenen relevanten Konzepte Contract-first Design in dem in unserem Falle angewandten Sinn, obschon einzelne Elemente wiederzuerkennen sind:

Zielumgebung

Bereits in den ersten Stunden des Projekts wurde versucht, eine geeignete Definition für die Zielumgebung zu finden, in der die Anwendung lauffähig sein sollte. Interessant für die Zielumgebung sind vor allem Browser-Versionen oder Web-Standards sowie ferner die Pixel-Anzahl („Auflösung“).

Für die Browser-Kompatibilität wurde nach gründlicher Überlegung auf eine Vorabfestlegung der Entwicklungsziele bewusst verzichtet. Angesichts der Tatsache, dass die Anwendung keine Zielgruppe hat, weil sie nicht produktiv eingesetzt werden soll (sondern ausschließlich eine Hausarbeit mit dem Ziel des Erlernens einer Skriptsprache ist, vgl. Modulhandbuch und Aufgabenstellung), und der Tatsache, dass weder die Aufgabenstellung Browser-Versionen oder Web-Standards auch nur erwähnt noch der Dozent der Lehrveranstaltung trotz mehrmaliger Nachfrage des Projektleiters eine konkrete Antwort gab, wäre die Definition einer Zielumgebung Makulatur.

Statt dessen wird hiermit als Zielvorgabe eine Anwendung der relevanten Web-Standards festgelegt, insbesondere HTML 4.01, HTML5 (soweit stabil), CSS Level 2.1, W3C DOM Level 2 und ECMA 262. Abweichungen von den Standards sind nur zulässig, wenn die abweichende Form verbreitet implementiert ist und messbare Vorteile gegenüber der besten konformen Alternative bietet (wie etwa im Falle der innerHTML-Eigenschaft). Angesichts der fehlenden Interoperabilität bestimmter, älterer dieser Standards wird darüber hinaus gefordert, dass die fertige Web-Anwendung in mindestens drei User-Agents korrekt funktioniert (wobei die graphische Ausgabe nicht notwendigerweise identisch sein muss).

Die Pixel-Anzahl wurde erst nach Fertigstellung des Grafik-Mockups (siehe unten) als mögliches Problem erkannt. Die Größen der einzelnen Grafikelemente begründen jedoch die Vermutung, dass handelsübliche Bildschirme mehr als ausreichend zur scroll-freien Darstellung der Anwendung sein werden. Auf eine Festlegung einer konkreten Ziel-Pixelanzahl wurde daher ebenfalls bewusst verzichtet.

Hinweis [Nachtrag per 28. Januar.]

Das Team ist der Ansicht, dass der Aufgabenstellung und den Antworten des Dozenten auf Nachfragen des Projektleiters hinsichtlich einer vorgegebenen Zielumgebung entsprochen wird. Unter anderem ergibt sich dies aus folgender Argumentation:

Der Dozent stellte per E-Mail vom 6. November 2009 klar, dass die Anwendung „in etwa“ auf „zwei wichtige[n] Browser[n]“ laufen solle. Dabei seien „[d]ie exakten Marktanteile […] nicht wichtig.“ Bei wichtigen Browsern besteht einige Auswahl: So dürfte ohne Frage z. B. der „Marktführer“ Firefox hierzu zählen. Aber auch Chrome und Safari dürften mit schätzungsweise 80 Mio. Nutzern weltweit unstrittig wichtige Browser sein, Opera mit weltweit um die 40 Mio. Nutzern wohl ebenso. Unsere Anwendung wurde auf allen vier genannten User Agents efolgreich getestet, womit die Anforderung gar übererfüllt scheint.

Ferner ist das Team der Ansicht, dass der didaktische Wert einer Fokussierung auf den Internext Explorer zumindest dubios ist. Auch müsste die Ethik einer entsprechenden Anforderung kritisch hinterfragt werden, nachdem die aktuelle Version des Internet Explorer dem Team während des Projektzeitraumes nicht kostenlos zur Verfügung stand und überdies nur auf einem einzigen Betriebssystem funktioniert, was den Grundgedanken des Webs im Hinblick auf dessen Interoperabilität zuwiederläuft. Diese Bedenken unterstützt der Projektleiter als Public Invited Expert der HTML-Arbeitsgruppe des World Wide Web Consortium nachdrücklich.

Visualisierungskonzept

Das grobe Visualisierungskonzept liegt vollständig vor. Es wurde der Entwurf von Antonia Boemanns und Bianca Förster verwendet. Die Eckpunkte des Entwurfs sind:

Die folgende Zeichnung ist während der Diskussion der Entwürfe entstanden und stellt (für Eingeweihte…) die Zusammenhänge anschaulich dar.

Hier ein (aktualisiertes) Mockup des Grafikdesigns:

Qualitätssicherung

Liste bekannter Probleme („Bugliste“)

Gelöste Probleme sind markiert.

  1. Text (./)
    Umfang: mäßig bis groß
    Schwere: wesentlich
  2. UI / Layout (./, arne/)
    Umfang: mäßig
    Schwere: wesentlich
  3. Das Verstecken der "alten" (nicht-maximalen) Zahlen funktioniert manchmal nicht. (toni/)
    Umfang: klein
    Schwere: wesentlich
    Grund: rmaxs wird nicht versteckt
  4. Das Canvas ist zu klein / die Zahlen im Array sind zu groß. (./, arne/, bianca/)
    Umfang: klein
    Schwere: wesentlich
    Workaround: kleinere Zahlen verwendet
  5. Die Demo lässt sich mehrfach gleichzeitig starten, läuft aber nur beim ersten Start vernünftig. (./, arne/)
    Umfang: gering
    Schwere: gering
  6. Ob der veränderte Algorithmus auf Arrays mit ungerader Länge noch numerisch korrekt arbeitet, ist unsicher; ggf. reparieren. (holger/)
    Umfang: klein (prüfen), groß (reparieren)
    Schwere: gering (Konzept sieht statischen Array vor)
    Grund: arne/test.jsNumerikTest#testTrivialeFaelle_1 schlägt in der Tat fehl, weil der veränderte Algorithmus negative Trivialergebnisse immer unkorrigiert zurückgibt, was nur kein Problem ist g. d. w. Randmaxima berechnet werden. Das ist aber beim Array [-1] nicht der Fall. Weil der veränderte Algorithmus aber für die Animation benötigt wird, ist ein Special-Case die einzige vernünftige Lösung für diese Regression.
  7. Die Positionen diverser Elemente erscheinen noch um einige Pixel daneben. (toni/, holger/, arne/)
    Umfang: mäßig
    Schwere: gering
  8. Die Randmaxima sind noch nicht auf gleicher Höhe. (arne/)
    Umfang: klein
    Schwere: gering
  9. Die Zahlenleiste wird gelegentlich an falscher Position im Canvas gezeichnet; Neuladen hilft. (bianca/)
    Umfang: klein
    Schwere: gering
    Grund: Entweder in Émile.js oder in window.getComputedStyle() gibt es ein Problem, das anscheinend durch unseren Code getriggert wird und das statt des von uns korrekt gesetzten .style.left-Wertes 'auto' zurückliefert, was dann von Émile.js nicht weiterverarbeitet werden kann.
    Workaround: Neu laden
  10. Das z-Ordering passt nicht während der Merge-Animation. (toni/)
    Umfang: klein
    Schwere: trivial
  11. Die Zahlen bei den Randmaxima könnten gestalterisch Verbesserung vertragen. (arne/)
    Umfang: klein
    Schwere: trivial
  12. Die neueren Blockgrafiken haben weiße Punkte in den Ecken, die knallgrüne erste Blockgrafik aber nicht. (bianca/)
    Umfang: klein
    Schwere: trivial
  13. Array-Elemente mit dem Wert 0 werden nicht angezeigt. (bianca/)
    Umfang: klein
    Schwere: gering
    Workaround: Keine Nullen im Array verwenden…

Demo mit anderen Arrays

Eigenen Array eingeben: []


$Id$