Software Engineering an der Schule: Rekursive Datenstrukturen in neuem Gewand Dr. rer. nat. habil. Markus Steinert Peutinger-Gymnasium Augsburg Seminarlehrer

Software Engineering an der Schule: Rekursive Datenstrukturen in neuem

Gewand

Dr. rer. nat. habil. Markus SteinertPeutinger-Gymnasium AugsburgSeminarlehrer

Dr. Markus Steinert Karlsruhe, 2011 2

Rekursion im Alltag / in der Kunst


Selbstähnliche Strukturen

Eugen Jost

So versteht Rekursion jeder


Rekursion in der Informatik

1,1,0,

21

1

0

icYbYaiYiY

Y

ii

i

Samuelson‘ sches Wirtschaftswachstum:

let rec binomial n k = match k with| 0 -> 1| k when (n=k) -> 1| _ -> binomial (n-1) (k-1) + binomial (n-1) k;;

Binomialkoeffizienten:

A(0, n) = n + 1A(m+1, 0) = A(m, 1)A(m+1, n+1) = A(m, A(m+1, n))

Ackermannfunktion:

So verstehen Rekursion anscheinend nur wenige


Zentrale Frage

Was macht Rekursion in formaler Schreibweise so schwierig, obwohl Visualisierungen auf den ersten (evtl. auch zweiten) Blick klar sind?

• Die Visualisierungen können als Instanziierungen konkreter Aufrufe der zugrunde liegenden rekursiven Vorschriften interpretiert werden

• Die funktionalen Repräsentationen sind die Vorschriften, mit denen derartige Strukturen erzeugt werden können


Klassische didaktische Strategien zur Einführung der Rekursion

Rekursive Funktionen über (natürlichen) Zahlen:• Fakultätsfunktion• Fibonacci – funktion• Binomialkoeffizienten

Didaktisch – motivatorische Probleme:• Für die Implementierung dieser Funktionen ist Rekursion nicht unbedingt

notwendig;• Sie können iterativ oft besser gelöst werden;• Sie entstammen mathematischen Begrifflichkeiten:

• Schüler: Wir machen Mathematik• Brauchen wir überhaupt Informatik ?

• Schwache Schüler haben kein (korrektes) mentales Modell der Rekursion


Fehlerhafte Vorstellungen rekursiver Abläufe

Sanders, et al. (2003 / 2006): Mental Models of recursion • Kategorisierung der Fehlvorstellungen• Empirische Untersuchungen (brauchbar / unbrauchbar)


Fehlerhafte Vorstellungen rekursiver Abläufe

1. Die häufigsten Fehlvorstellungen (Sanders et al.)• Schleifenartige Konzepte (Looping): Die rekursive Vorschrift wird

schleifenartig immer wieder durchlaufen, d.h. - es findet keine Instanziierung eines neuen Prozesses - keine Generierung eines Aufrufbaums statt

• Einschränkung auf Endrekursion (tail recursion); (Active):- Rekursionen, bei denen nach Erreichen des Terminierungsfalls ein rückwärtiges

Abarbeiten des Aufrufterms notwendig ist, werden nicht verstanden - Wird auf kognitiver Ebene überhaupt ein Aufrufbaum realisiert?

• Einschränkung auf einmaliges Durchführen der Alternative (Step):- Die Alternative wird einmal ausgewertet und das „Ergebnis“ zurückgegeben

• Weitere Fehlvorstellungen: Magic, ….


Folgerungen aus den empirischen Arbeiten

Wie hängen die Fehlvorstellungen mit den zu lernenden Konzepten zusammen?

• Die Lernenden können den Übergang vom rekursiven Algorithmus zum Aufrufbaum kognitiv nicht nachvollziehen bzw. bewältigen

• Die Lernenden hängen zu sehr an Ablaufmustern, wie sie aus dem „imperativen“ Programmierparadigma vertraut sind (Funktional vor Imperativ?)

Folgerung:• Beim Erlernen rekursiver Abläufe sollte die Datenstruktur, die dabei

traversiert wird, in den Vordergrund rücken• Problem mit bisherigen Zugängen über Fibonacci-Funktion etc.: Die

Traversierung ist zu trivial• Alternative: Mit „weniger trivialen“ rekursiven Datenstrukturen beginnen!


Didaktik rekursiver Strukturen in der Literatur

Velazquez – Iturbide (2000):• Gradual Steps:

- Recursion in Grammars, - Recursion in Functional Programming,- Recursion in Imperative Programming;

• Argumentation: - Rekursiver Regeln in Grammatiken weisen einen minimalen syntaktischen

Overhead auf und die Verbindung zur rekursiven Struktur ist denkbar einfach:- S a | aS; zur Erzeugung der Sprache {an; n ≥ 1}- Funktionale Sprachen im nächsten Schritt haben ebenfalls geringe syntaktische

Anforderungen• Problem: Für den Informatikunterricht weniger geeignet, da Grammatiken

meist nur am Rande (bzw. sehr spät, z.B. im bayerischen Lehrplan erst in Jahrgangsstufe 12) und Funktionales Programmieren nicht thematisiert wird


Wo stehen wir?

• Offenbar werden graphische Repräsentationen rekursiver Strukturen intuitiv verstanden!

• Rekursive Algorithmen werden ohne Bezug auf die zugrunde liegende rekursive Struktur häufig nicht verstanden

Folgerung: Wir sollten bei der Vermittlung von Rekursion von einem Modell der zugrunde liegenden rekursiven Strukturen ausgehen


Didaktische Rahmenbedingungen für das Unterrichten rekursiver Strukturen

Lehrplan für den Informatikunterricht an bayerischen Gymnasien:• Rekursion als zentrale Thematik in der 11. Jahrgangsstufe• Vorwissen der Schüler

• Fundierte Kenntnisse im objektorientierten Modellieren: Objektdiagramme, Klassendiagramme, Sequenzdiagramme, Zustandssemantik

• Einschlägige Fertigkeiten beim Implementieren von objektorientierten Modellen (Aggregation, Assoziation, Vererbung, abstrakte Klassen, …)

• Einschlägige Fertigkeiten beim Implementieren imperativ konzipierter Abläufe

• Für das weitere wichtig: „Objects first!!“• Vom Objektdiagramm zum Klassendiagramm


Didaktische Rahmenbedingungen für das Unterrichten rekursiver Strukturen im Detail

Jahrgangsstufe 6 / 7:• Objekt- und Klassendiagramme hierarchischer Objektstrukturen

Jahrgangstufe 10: • Nichtrekursive objektorientierte Programmierung (Felder, Referenzen, ….)

Vererbung; abstrakte Klassen

Jahrgangsstufe 11:1. Konstruktion listen- / baumartiger Objektstrukturen2. Das Kompositum als Schlüssel zur Rekursion3. Rekursive Funktionen im Kompositum

Realisierung im aktuellen Informatikunterricht: • Jahrgangsstufe 11, Informatik, an bayerischen Gymnasien• Inzwischen im zweiten Durchlauf• Erste Abiturprüfungen: Mai 2011


Vom Objektdiagramm zum Klassendiagramm: Informatikunterricht in der Unterstufe (6. Jahrgangsstufe)

Beispiel: Textstrukturen

d1 : DOKUMENT

a1 : ABSATZ a2 : ABSATZ a3 : ABSATZ

z1 : ZEICHEN z14 : ZEICHEN z15 : ZEICHEN z55 : ZEICHEN……... ……

DOKUMENT ABSATZ ZEICHENenthält > enthält >


Objektorientierte Analyse von Ordnerstrukturen in Jahrgangsstufe 6 / 7

Vm Objekt- zum Klassendiagramm: Hierarchische Objektstrukturen

ORDNERDATEI

enth

ält


Was bedeutet diese Vorgehensweise aus lernzieltheoretischer Sicht?

Werkzeug: Lernzielgraph

2: Objektorientiertes Modellieren

Textuell || Graphisch 12

3 Objekt

Graphisch 12

3 Klasse

2 Graphisch 1

3 Nichtrekursive Aggregation auf Klassenebene

Graphisch 1

3 Baumartige Objektstrukturen

2 Graphisch 1

3Klassendiagramm

baumartiger Objektstrukturen

2

Graphisch 1

3 Aggregation auf Objektebene

2


Kurzes Zwischenresumè

1. Was wollten wir:• Weg von einer Vorgehensweise, die zu falschen mentalen Modellen über

Rekursion führt• Probleme: Rekursive Aufrufe wurden nicht als Folge von Instanzen des

jeweiligen Algorithmus verstanden2. Was haben wir:

• Wir modellieren zunächst baumartige Strukturen (Verzeichnisbäume etc.)• Für diese rekursive Datenstruktur wird anschließend der „zugehörige

Bauplan“, d.h. das Klassendiagramm konstruiert• Das Klassendiagramm entspricht in diesem Bild der rekursiven

Funktionsvorschrift 3. Wie geht es weiter:

• In der 10. Jahrgangsstufe lernen die Schüler das Implementieren (nichtrekursiver Klassenstrukturen

• In der 11. Jahrgangsstufe erfolgt der Übergang zu rekursiven Strukturen


1. Schritt: Listenartige Objektstrukturen (11. Jgstf.)

Stativ1: STATIV

Korb1: KNOTENApfel: ELEMENT

nächster

erster

Korb2: KNOTENTraube: ELEMENT

nächster

Korb3: KNOTENBanane: ELEMENT

nächster

STATIV

KNOTENELEMENT

näch

ster

erster0, ..1

Entspricht dem aus der Unterstufe bekannten Modell!


1. Schritt: Konstruktion listenartiger Objektstrukturen (11. Jgstf.)

class Knoten { private Element inhalt; private Knoten naechster; public Knoten(Element in) { inhalt = in; naechster = null; }

……..}

Element inhalt1 = new Element(”Apfel”); // Erzeugen der ElementeElement inhalt2 = new Element(”Traube”);Element inhalt3 = new Element(”Banane”);Knoten korb1 = new Knoten(inhalt1, null); // Erzeugen der KnotenKnoten korb2 = new Knoten(inhalt2, null);Knoten korb3 = new Knoten(inhalt3, null);korb1.naechsterSetzen(korb2); // Aufbau der Listekorb2.naechsterSetzen(korb3);

Listenkonstruktion: Zunächst explizit, ohne rekursive AblaufmusterTraversierung: Zunächst Iterativ (Stativ enthält die Anzahl der Listenelemente)


Traversieren listenartiger Objektstrukturen (11. Jgstf.)

Beispiel: Gesamtgewicht der Früchte in obiger Kette soll ermittelt werden!

Stativ0 Knoten0 Knoten1 Knoten2

gewichtGeben()

5 kg

gesamtGewGeben()

0 kg + 5 kg

gewichtGeben()

6 kg5 kg + 6 kg

4 kg11 kg + 4 kg

gewichtGeben()

15 kg


2. Schritt: Das Kompositum als Schlüssel zur Rekursion

Problem: Abbruch bei Traversierung Stativ1: STATIV

Korb1: KNOTENApfel: ELEMENT

nächster

erster

Korb2: KNOTENTraube: ELEMENT

nächster

Korb3: KNOTENBanane: ELEMENT

nächster

Kugel: ABSCHLUSS

STATIV

LISTENELEMENT

KNOTENABSCHLUSS

ELEMENT

näch

ster


3. Schritt: Rekursive Aufrufe (Sequenzdiagramm)

Beispiel: Gesamtgewicht der Früchte in obiger Kette soll ermittelt werden!

Stativ0 Knoten0 Knoten1 Knoten2

gewichtGeben()gesamtGewGeben()

gewichtGeben()

4 kg + 6 kg

4 kg

gewichtGeben()

15 kg

Abschluss0

10 kg + 5 kg

0 kg

gewichtGeben()


abstract class Listenelement {

// Methoden des einzelnen Listenelementes public abstract Listenelement naechsterGeben(); public abstract Element gewInhaltGeben(); // rekursive Methoden der verketteten Liste public abstract int gewichtGeben(); public abstract Element inhaltLetzterGeben(Element aktuellerInhalt); public abstract Knoten hintenEinfuegen(Element knoteninhalt); }

Rekursive Funktionen im Kompositum: Summieren über bestimmte Eigenschaften

class Knoten extends Listenelement { private Listenelement naechster; private Element inhalt;

public int gewichtGeben(){ return inhalt.gewInhaltGeben() + naechster.gewichtGeben(); } ……}

Rekursiver Aufruf

class Abschluss extends Listenelement { public int gewichtGeben(){ return 0; } ……}

Terminierungsfall



// Methoden des einzelnen Listenelementes public abstract Listenelement naechsterGeben(); public abstract Element inhaltGeben(); // rekursive Methoden der verketteten Liste public abstract int anzahlKnotenGeben(); public abstract Element inhaltLetzterGeben(Element aktuellerInhalt); public abstract Knoten hintenEinfuegen(Element knoteninhalt); }


…. public Element inhaltLetzterGeben(Element aktuellerInhalt){ return naechster.inhaltLetzterGeben(inhalt); } ….}

class Abschluss extends Listenelement { …. public Element inhaltLetzterGeben(Element aktuellerInhalt){ return aktuellerInhalt; }

….}

Rekursiver Aufruf

Terminierungsfall

Rekursive Funktionen im Kompositum: Letztes Element ausgeben


Vorteile der Strategie „Kompositum“

Lernzieltheoretisch lässt sich die Objektebene von der Klassenebene völlig trennen

• Es können zunächst die Objektstrukturen und anschließend die „Konstruktionsvorschriften“, d.h. Klassendiagramme für diese Strukturen vermittelt werden

• Der Weg vom Objekt- zum Klassenmodell lässt sich auch hier beschreiten

Rekursive Methodenaufrufe lassen sich direkt auf dem Objektdiagramm ausführen und ergeben dabei in einfacher Weise den rekursiven Algorithmus

• Terminierungsfall und rekursiver Aufruf verteilen sich auf die beiden Klassen ABSCHLUSS und KNOTEN

• Die Ausführung eines rekursiven Methodenaufrufs lässt sich am Objektdiagramm / Sequenzdiagramm direkt illustrieren

• Fehlvorstellungen (Sanders et al.) werden nach Möglichkeit vermieden


Lernzielgraph objektorientierter Modellierung von rekursiven Datenstrukturen

2/3: Funktionales Modellieren

2 – 1 – 3: Rekursiver Datentyp

2-1-3: Mehrstellige Funktion2 – 1 –3: Typoperatoren

2/3: Objektorientiertes Modellieren

2 – 1 – 3: Objekt

Abschlussobjekt

Beziehungen auf Klassenebene

2 – 1 – 3: Methode

2 – 1 – 3: Aggregation auf Objektebene

2 – 1 – 3: Nichtrekursive Aggregation

2 – 1 – 3: Klasse

> 2 : Kompositum ableiten

> 2: Linear rekursiv geschachtelte Objektstrukturen erstellen

2 – 1 – 3: Vererbung

2 – 1 – 3: Elementare Sorten

2 – 1 – 3: Alternative

> 2: Linear rekursiv geschachtelte Datenstrukturen darstellen

2 – 1 –3: Konstruktor

> 2: Rekursive Datendefinition ableiten

Abschlussklasse

Knotenklasse

Knotenobjekt

2 – 1 – 3: Methode

2 – 1 – 3: Attribut

AbschlussKnoten

2 – 1 – 3: Kreuzprodukt

2 –1 – 3: Funktionskomposition2 – 1 –3: Funktionskomposition mit Konstruktoren (T + G)

2 – 1 –3: Funktionskomposition für Typterme (T)

2 – 1 – 3: Abstrakte Klasse

Zusätzliche Modellierungs-konzepte im Vergleich zur Unterstufe:

• Spezifische Klassen (Abschluss, Knoten)

• Verallgemeinerung der Beziehungen

• Vererbung• Abstrakte Klassen

(Programmierung:• Kontrollstrukturen• Umsetzung der Klassen-

diagramme in Quellcode))


Vergleich: Vorteile und Nachteile

Vorteile:• Der rekursive Aufruf ist stets an den Methodenaufruf eines anderen Objekts (hier:

jeweils an das nächste Objekt) gekoppelt;• Die Fehl-Vorstellung, es werde dieselbe Funktion aufgerufen, ist nahezu

ausgeschlossen;• Das mentale Modell der „Kopien“ wird automatisch vermittelt;• Trennung von Terminierungsfall und rekursivem Aufruf, durch Auslagerung der

Alternative in die Vererbung;Nachteile:

• Großer zeitlicher Aufwand;• Umfangreiches Vorwissen und Fertigkeiten in objektorientierter Modellierung und

Programmierung notwendig;

Übertragung auf Grammatiken / funktionale Programmierung• Definition rekursiver Grammatiken / Datenstrukturen• Definition rekursiver Funktionen auf diesen Datenstrukturen


erster

knoteninhalt

class Liste { private Listenelement erster; public void hintenEinfuegen(Datenelement knoteninhalt){ erster = erster.hintenEinfuegen(knoteninhalt); } ...}


Das Stativ spricht zum Listenelement „erster“:„Erster, füge das Datenelement knoteninhalt hinten ein!“

und wartet auf die Beantwortung der Frage:„Wer ist mein neuer Erster?“

Einfügen eines Knotens am Ende der Liste: Leere Liste

©S.Voss


knoteninhalt

class Abschluss extends Listenelement { public Datenknoten hintenEinfuegen(Datenelement knoteninhalt) { return new Datenknoten(this,knoteninhalt); } ...}

Der Abschluss baut einen neuen Datenknoten, macht sich selbst zum Nachfolger dieses Datenknotens und legt den erhaltenen Inhalt knoteninhalt hinein.

„Wer ist mein neuer Erster?“


©S.Voss


Der Abschluss antwortet seinem Fragesteller:Hier, nimm eine Referenz auf diesen neuen Datenknoten!“

knoteninhalt




©S.Voss


ersterDie Liste speichert nun die Referenz auf das erhaltene

Listenelement in die Variable „erster“.



©S.Voss


erster


knoteninhaltStativ spricht zum Listenelement „erster“:„Erster, füge das Datenelement knoteninhalt hinten ein!“

und wartet auf die Beantwortung der Frage:„Wer ist mein neuer Erster?“

Einfügen eines Knotens am Ende der Liste: Listenlänge > 1

©S.Voss


erster

class Datenknoten extends Listenelement { private Listenelement naechster; private Datenelement inhalt; public Datenknoten hintenEinfuegen(Datenelement knoteninhalt){ naechster = naechster.hintenEinfuegen(knoteninhalt); return this; } ...}

Der Datenknoten spricht zum Listenelement „nächster“:„Nächster, füge das Datenelement knoteninhalt hinten ein!

und wartet auf die Beantwortung der Frage:„Wer ist mein neuer Nächster?“

erstererstererster

nächsterknoteninhaltknoteninhalt



©S.Voss



erstererstererstererster

nächster

nächster

Datenknoten spricht zum Listenelement „nächster“:„Nächster, füge das Datenelement knoteninhalt hinten ein!“



„Wer ist mein neuer Nächster?“



Datenknoten spricht zum Listenelement „nächster“:„Nächster, füge das Datenelement knoteninhalt hinten ein!“





©S.Voss



nächster

nächster


nächsternächsternächster

nächsternächster


Der Abschluss baut einen neuen Datenknoten, macht sich selbst zum Nachfolger dieses Datenknotens und legt den erhaltenen Inhalt knoteninhalt hinein.










©S.Voss



nächster

nächster



nächsternächster


Der Abschluss antwortet seinem Fragesteller:Hier, nimm eine Referenz auf diesen neuen Datenknoten!“










©S.Voss



nächster

nächster

nächster



nächster

nächster

nächsternächster

nächsternächster

Der Datenknoten speichert nun die Referenz auf das erhaltene Listenelement in die Variable „nächster“.

und antwortet seinem Fragesteller: Hier, nimm eine Referenz auf mich selbst!“





©S.Voss



nächster

nächster

nächster



nächster

nächster

nächsternächster

nächsternächster

Der Datenknoten speichert nun die Referenz auf das erhaltene Listenelement in die Variable „nächster“.

und antwortet wiederum seinem Fragesteller: Hier, nimm eine Referenz auf mich selbst!“




©S.Voss



nächster

nächster

nächster



nächster

nächster

nächsternächster

nächsternächster

Die Liste speichert nun die Referenz auf das erhaltene Listenelement in die Variable „erster“.



©S.Voss


Einfügen eines Knotens am Ende der Liste: Sequenzdiagramm



// Methoden des einzelnen Listenelementes public abstract Listenelement naechsterGeben(); public abstract Element inhaltGeben(); // rekursive Methoden der verketteten Liste public abstract int anzahlKnotenGeben(); public abstract Element inhaltLetzterGeben(Element aktuellerInhalt); public abstract Knoten hintenEinfuegen(Element knoteninhalt); }


…..... public Knoten hintenEinfuegen(Element knoteninhalt) { naechster = naechster.hintenEinfuegen(knoteninhalt); return this; }} class Abschluss extends Listenelement {

…….

public Knoten hintenEinfuegen(Element knoteninhalt) { return new Knoten (this, knoteninhalt); }}

Rekursiver Aufruf

Terminierungsfall

Einfügen eines Knotens am Ende der Liste: Quellcode


Universelle Einsetzbarkeit: Warteschlange und Stapel






Universelle Einsetzbarkeit: Heterogene Listen


LISTENELEMENT

sortiertEinfügen(datenelement)sortierwertEntnehmen(datenelement)...

SORTIERTELISTE

einfügen(datenelement)wertEntnehmen(datenelement)...

erster

11

1

ABSCHLUSS DATENKNOTEN

DATENELEMENT

istKleiner(datenelement)istGleich(datenelement)datenAusgeben()

<

TELEFONEINTRAGnameabteilungdurchwahl

istKleiner(datenelement)istGleich(datenelement)datenAusgeben()

Universelle Einsetzbarkeit: Sortierte Listen


LISTENELEMENT

LISTEerster

1

1

DATENKNOTEN

DATENELEMENT1

ABSCHLUSS

<

BAUMELEMENT

BINÄRBAUMwurzel

1

2

DATENKNOTEN

DATENELEMENT1

ABSCHLUSS

<

Von der rekursiven Liste zum binären Baum


Von der rekursiven Liste zum binären Baum


Preorder, Inorder, Postorder

Binäre Bäume: Traversierungsstrategien


Geordneter binäre Bäume: Suchen


Geordneter binäre Bäume: Suchen über Schlüssel


Geordneter binäre Bäume: Einfügen


Geordneter binäre Bäume: Einfügen


Vielen Dank Für Ihre

Aufmerksamkeit

Documents

Software Engineering an der Schule: Rekursive Datenstrukturen in neuem Gewand Dr. rer. nat. habil. Markus Steinert Peutinger-Gymnasium Augsburg Seminarlehrer