Ich zeige, wie das Verständnis von Algorithmen gefördert und überprüft werden kann, ohne dass Studenten durch Eigenheiten konkreter Programmiersprachen abgelenkt werden. Ich verwende stattdessen stark eingeschränkte Modellierungssprachen mit unformer und trivialer Syntax sowie aufgabenspezifischer Semantik. Aufgaben-Erzeugung sowie -Bewertung werden im E-Learning/EAssessment-System autotool technisch realisiert, das seit ca. 2000 an der Universität Leipzig, der HTWK Leipzig, sowie gelegentlich an weiteren Hochschulen eingesetzt wird. Ein klassischer Bestandteil der Lehre von Algorithmen und Datenstrukturen [CLR09] ist das Thema „balancierte Suchbäume“, mit dem Beispiel AVL-Bäume. Der Inhalt sind Sätze über Algorithmen: Balance erzwingt logarithmische Höhe, Rotation erhält die SuchbaumEigenschaft und repariert die Balance lokal; sowie die zugrundeliegenden Beweismethoden (Induktion über die Höhe) sowie Programmierkonzepte (Rekursion, Iteration). Das Verständnis dieser Ideen kann dadurch unterstützt werden, dass Studenten die Algorithmen ausführen (auf dem Papier, an der Tafel) und implementieren (als Programmtext). Ich beschreibe hier eine weitere Möglichkeit von unterstützenden Aufgaben sowie deren Automatisierung innerhalb des Systems autotool[RW02, Wa17]. Studenten sollen eine Folge s von Einfüge- und Lösch-Operationen finden, die aus einem vorgegebenen AVLBaum t1 einen vorgegebenen Baum t2 erzeugt. Für die Folge s sind die Länge sowie einige Elemente vorgegeben und die restlichen zu finden. Die Vorgabe ist ein Folge mit Lücken s?. Die Aufgabenstellung besteht dann aus ¹t1; s?; t2º. Studenten tragen einen Lösungsversuch (eine Folge s) in einem Web-Formular ein. Nach Absenden führt das autotool-System die Operationsfolge s aus und gibt die Folge der dabei erzeugten Bäume aus. Schließlich wird das Endresultat mit der Vorgabe verglichen. Eine Lösung ist jede Folge s, die zu s? passt und t1 in t2 überführt. Korrektheit ist also 1 HTWK Leipzig, Fakultät IMN, Postfach 301166, 04251 Leipzig, https://www.imn.htwk-leipzig.de/~waldmann/
2
Suchbäume S¹Kº mit Schlüsseln einer Menge K realisieren den abstrakten Datentyp Menge mit folgender Schnittstelle. Die Semantik JtK eines Baumes ist die Menge seiner Schlüssel. empty : S¹Kº mit JemptyK = ;, null : S¹Kº ! B mit Jnull¹tºK = ¹; = JtKº contains : K S¹Kº ! B mit Jcontains¹x; tºK = ¹x 2 JtKº insert : K S¹Kº ! S¹Kº mit Jinsert¹x; tºK = fxg [ JtK delete : K S¹Kº ! S¹Kº mit Jdelete¹x; tºK = JtK n fxg
besitzt eine Funktion zur grafischen Darstellung. Wir verwenden dot [Ga17].
Automatische Erzeugung und Bewertung von Aufgaben zu Algorithmen und Datenstrukturen 3 Derzeit existieren diese Implementierungen: nicht balancierte binäre Bäume, AVL-Bäume, Rot-Schwarz-Bäume, B-Bäume.
Ein Beispiel für eine Aufgabenstellung für AVL-Bäume ist:
sollen diese Operationen angewendet werden (wobei Sie Any geeignet ersetzen sollen): [ Any , Any , Any , Delete 86 , Any, Any , Insert 13 , Insert 21 ] so dass dieser Baum entsteht: Eine korrekte Lösung ist [ Insert 53, Insert 80, Delete 97, Delete 86 , Delete 96, Insert 0, Insert 13, Insert 21 ] Für die Erzeugung zufälliger Aufgabeninstanzen werden, wie in der Einleitung beschrieben, t1 und s0 ausgewürfelt und daraus t2 bestimmt. Damit interessante, d.h., nicht trivial lösbare, Instanzen entstehen, werden jeweils mehrere Kandidaten-Instanzen bestimmt und dann diejenige verwendet, die den Hamming- oder Editier-Abstand von t1 zu t2 maximiert. Die Wurzeln von t1 und t2 sollen sich unterscheiden und die Wurzeln der nächsten Teilbäume möglichst auch, usw., damit die Aufgabe nicht durch Betrachtung unabhängiger Teilbäume einfach lösbar ist. Unterschiedliche Wurzeln erreicht man bei nicht balancierten Bäumen durch delete-Operationen, bei anderen auch als Folge von Balance-Reparaturen. 3
abstrakten Datentyp Prioritätswarteschlange unter anderem den folgenden Operationen. Die Semantik JhK eines Heaps h ist die (Multi)menge der Schlüssel. Die insert-Operation liefert einen Verweis p 2 Ref¹Kº, der bei decrease verwendet wird. In der grafischen Darstellung werden für jeden Knoten der Schlüssel sowie der Name des Verweises auf diesen Knoten gezeichnet.
Derzeit wird die Schnittstelle implementiert durch fast vollständig balancierte binäre Heaps. Dabei sind alle Blätter in Tiefe h oder, rechts davon, in Tiefe h 1. Solche Heaps können implizit durch Arrays repräsentiert werden, was in dieser Aufgabe jedoch keine Rolle spielt. Grundsätzlich trefen Bemerkungen zu Suchbäumen aus Abschnitt 2 zu. Es zeigte sich, dass Aufgaben zu Heaps schwieriger waren, erkennbar an einer höheren Anzahl von Fehlversuchen. Das kann daran liegen, dass die decrease-Operation eine direkte Zuordnung zwischen den Schlüsseln in der Eingabe t1 und denen in der Ausgabe t2 erschwert. 4
verwendet direkten Zugrif mittels Hashfunktionen. Gegenüber den vorher beschriebenen Aufgaben zu Bäumen enthalten Aufgaben zu Hashing nicht nur eine Beschreibung der vorgegebenen Start- und Endzustände, hier: Belegung der Hashtabelle, sondern zusätzlich eine Spezifikation des verwendeten Hash-Verfahrens sowie seiner Parameter, insbesondere seiner Hashfunktion(en). Form und Koefizienten von Hashfunktionen können teilweise versteckt werden. Damit wird die Angabe der Hashfunktion zu einem Teil der Aufgabe. Derzeit gibt es Aufgaben zu diesen Hashverfahren:
Hashing mit Verkettung: jede Zelle der Hashtabelle enthält eine Liste von Elementen. ofenes Hashing mit linearem Sondieren: jede Zelle enthält kein oder ein Element, die Sondierungsreihenfolge für x mit hash¹xº = p ist p; p + 1; p + 2; : : : (modulo Tabellengröße).
Automatische Erzeugung und Bewertung von Aufgaben zu Algorithmen und Datenstrukturen 5 doppeltes Hashing: jede Zelle enthält kein oder ein Element, die Sondierungsreihenfolge für x mit hash1¹xº = p und hash2¹xº = q ist p; p + q; p + 2q; : : : .
Die Hashfunktion kann vorgegeben werden als lineare Funktion mit unbekannten Koefifzienten h¹xº = ? + ? x. Bei Hashing mit Verkettung sind die Koefizienten leicht zu rekonstruieren, da man Paare ¹x; h¹xºº direkt aus der Tabelle ablesen kann. Bei ofenem Hashing ist das schwieriger, da nicht klar ist, nach wieviel Sondierungs-Schritten ein Element eingefügt wurde. Das ist gut so, denn dann wird genau das beim Bearbeiten der Aufgabe geübt. Eine Beispiel-Aufgabenstellung für doppeltes Hashing ist
Config { size = 10 , hash1 = \ x -> _ + _ * x , hash2 = \ x -> _ }
and in the sequence of operations
[ Insert _ , Insert _ , Insert _
, Insert 40 , Insert _ , Insert _ , Insert 22 ]
with a numerical expression
such that the sequence of operations transforms
Table (listToFM [ (
Solution { config = Config { size = 10 , hash1 = \ x -> 6 + 3 * x , hash2 = \ x -> 1 } , ops = [ Insert 25 , Insert 11 , Insert 89 , Insert 40 , Insert 97 , Insert 64 , Insert 22 ] } Ein Ausschnitt aus der Antwort des System ist Die Aufgaben zum doppelten Hashing erwiesen sich beim Einsatz im Sommersemester 2017 tatsächlich als schwierig, mit einer hohen Anzahl von Fehlversuchen.
Die Breitensuche wird durch folgenden Aufgabentyp getestet: eine Aufgaben-Instanz besteht aus einem Muster GM für die Adjazenz-Listen-Darstellung eines Graphen, einem Startknoten s und einem Muster TM für einen Baum. Eine Lösung ist eine AdjazenzListen-Darstellung G eines Graphen. Die Lösung ist korrekt, wenn G zu GM paßt und der
Eine Beispiel-Aufgabenstellung ist
Adjacency_List [ ( _ , [ _, 4, 7] ), ( _, [ 5, _]), ( 4, [ _, _]) , ( _, [ _, _, 4, 5]), ( _, [ 4, _, 1, 3]), ( 3, _), ( 6, [ _, 1, _]) ] so that the breadth first search tree of G, starting at 3, matches the pattern
Die Konfiguration des Aufgabengenerators ist
Es werden 100 Graphen G erzeugt und für jeden T = BFS¹Gº bestimmt. In G und T werden zufällig ausgewählte Teilstrukturen versteckt, d.h., durch _ ersetzt, so dass der Anteil der sichtbaren Funktionssymbole möglichst nahe bei 70 Prozent liegt.
Eine ähnliche Aufgabe behandelt Tiefensuch-Wälder.
Das System autotool besteht aus einem zustandslosen Semantik-Service zur Generierung von Aufgabeninstanzen und zur Bewertung von Lösungsversuchen, implementiert als XML-RPC-Service mit haxr, einer Persistenz-Schicht zur Speicherung von Aufgaben, Einschreibungen, Punkten u.ä., implementiert als mysql (mariabdb) mit persistent [Sn17] einer Web-Oberfläche [Si16], implementiert mit yesod [Sn12]. Damit können Studenten Aufgaben bearbeiten und Bewertungen betrachten sowie Dozenten die Aufgaben konfigurieren und testen sowie Aufgaben und Punkte verwalten.
Automatische Erzeugung und Bewertung von Aufgaben zu Algorithmen und Datenstrukturen 7 Die hier beschriebenen Aufgaben sind als Module im Semantik-Service realisiert. Die gemeinsame Modulschnittstelle ist durch diese mehrparametrige Relation (Typklasse) für p (Aufgabentyp), i (Typ der Instanz), b (Typ der Einsendung) beschrieben: describe: p i ! Text beschreibt Aufgabenstellung, initial: p i ! b berechnet einen syntaktisch korrekten, aber semantisch falschen Lösungsvorschlag,
Text bewertet die Einsendung, liefert Resultat richtig/falsch und eval: p i b ! B Begründung generate: p c
Das Würfeln von Aufgabeninstanzen nach einer Konfiguration c wird beschrieben durch wobei Seed aus der Matrikelnummer (oder einem anderen Kennzeichen des Studenten) bestimmt wird und der Initialisierung eine deterministischen Pseudozufallsgenerators dient. Der Student gibt eine textuelle Repräsentation der Lösung (vom Typ b) ein. Das Texteingabefeld wird mit initial¹p; iº initialisiert. Mit Absicht gibt es keine grafische Eingabemöglichkeit, um Studenten an die wissenschaftliche Notation (durch Terme in einer geeigneten Signatur) zu gewöhnen. Bei den allermeisten Aufgaben ist die konkrete Syntax für b die DatenSyntax von Haskell [Sim10], mit den Ausdrucksmitteln für primitive Daten: 123, False, für Tupel: (124,False), für (typreine) Listen: [(123,False),(456,True)], Konstruktoren algebraischer Datentypen, mit Argumenten: Just (123,False), Records mit benannten Komponenten: Config{size=10}. Pretty-Printer und Parser werden automatisch generiert. Gelegentlich wird eine aufgabenspezifische konkrete Syntax verwendet, z.B. für arithmetische Ausdrücke in Hashfunktionen.
Die Eingabe-Parser [LM16] erzeugen nützliche Fehlermeldungen. Die fehlerhafte Stelle wird markiert und mögliche Fortsetzungen werden ausgegeben. Jedes Eingabefeld (für den Studenten: das für den Lösungsversuch, für den Dozenten: das für die Konfiguration der Instanz oder des Instanzengenerators) ist typisiert und wird automatisch mit einem Verweis auf die API-Dokumentation des jeweiligen Typs versehen.
Die hier gezeigten Aufgabe verwenden das Prinzip, dass Teile einer Datenstruktur (Bsp: Koefizienten der Hashfunktion, Elemente der Liste von Operationen) in der Aufgabenstellung versteckt werden und zur Lösung zu ergänzen sind. Ein Typ p dient in diesem Sinne als Vorlagentyp, wenn für ihn diese Eigenschaften deklariert werden: der zugehörige Basistyp: type (Base p) der Mustervergleich match : p
Text die Injektion inject: Base¹pº ! p das pseudozufällige Verstecken von Bestandteilen obfuscate : Base¹pº
7
Der autotool-Semantik-Service wird ebenfalls vom autolat-Plugin [FS10] für OpenOLAT [Fr17] unterstützt und an der Universität Leipzig angewendet. Ich möchte autotool gern in weitere Systeme integrieren. Eine Verwendung der QTI-Schnittstelle [IM15] ist naheliegend, scheint aber derzeit nicht möglich, da im Standard weder das externe Generieren von Aufgaben noch das externe Bewerten von Einsendungen vorgesehen sind, sondern höchsten Zeichenkettenvergleiche, die von QTI-Player selbst ausgeführt werden. Das ist für eine semantische Bewertung mit sinnvoller Rückmeldung völlig unzureichend. Die hier beschriebenen Aufgaben habe ich für die Vorlesung Algorithmen und Datenstrukturen für Informatik-Bachelor-Studenten im 2. Semester, die ich vertretungsweise übernommen habe, überarbeitet bzw. neu entwickelt. Dabei haben ca. 80 Studenten über das Sommersemester 2017 hinweg jede Woche 1 bis 2 autotool-Aufgaben bearbeitet, mit ca. 10 Einsendungen pro Aufgabe. Für einzelne Aufgaben habe ich deutlich mehr Einsendungen registriert. Das kann an der Schwierigkeit der Aufgabe liegen, aber auch daran, dass ich explizit zum Durchprobieren verschiedener, auch “falscher” Einsendungen ermuntert hatte. Ich habe damit die eigentlich vorgesehenen Java-Programmier-Übungen ersetzt. Die autotool-Aufgaben schienen mir dem didaktischen Ziel des Verständnisses der Algorithmen nützlicher. Der Aufwand zum Lösen und Korrigieren von Java-Programmen ist für Student und Dozent deutlich höher, so dass Programmieraufgaben üblicherweise nur dreimal während des Semesters gestellt wurden. Tatsächlich habe ich wohl die Arbeit verschoben: vom (z.T. händischen) Korrigieren der Java-Aufgaben zum Programmieren der autotool-Aufgaben — allerdings in Haskell, das sehr konzise Quelltexte ermöglicht und sehr hohe statische Sicherheit garantiert und somit den Entwicklungsaufwand verringert. Die Studenten haben in dieser Vorlesung keine Programme selbst geschrieben und (außer Pseudocode im Skript und autotool-Quelltexten) kaum welche gesehen — das finde ich nicht so tragisch, zumal es parallel eine Vorlesung zur anwendungsorientierten JavaProgrammierung gibt und vorher eine zu Grundlagen der Programmierung. Durch die autotool-Aufgaben haben sich die Studenten auch ohne Programmieren mit den Algorithmen beschäftigt, indem sie ihre Ausführung durch das autotool beobachtet und durch geeignete Eingaben zielgerichtet gesteuert haben. Für die Übungen habe ich damit Zeit gewonnen für die Diskussion von Aufgaben zu Eigenschaften von Algorithmen. (Die Prüfungszulassung ergibt sich aus beiden Anteilen.) Eine wissenschaftliche fundierte Einschätzung des tatsächlichen Nutzens (und Aufwandes) von autotool-Aufgaben scheint mir hier nicht möglich, da zu viele weitere Parameter variieren: nicht nur Änderung der Übungs-Aufgaben, sondern auch im Vortragsstil, im Skript, in Klausuraufgaben. Berichten von Kollegen sowie eigene Erfahrung mit autotool in anderen Vorlesungen [Wa15, Wa14] bestätigen, dass Studenten das System schnell verstehen und gern benutzen und besonders die sofortigen, ausführlichen und objektiven Antworten begrüßen.
Automatische Erzeugung und Bewertung von Aufgaben zu Algorithmen und Datenstrukturen 9