Einfach verkettete Liste, Rekursion und Entdeckungen bei Powerpoint

Gestern habe ich in Informatik die erste rekursive Methode eingeführt: die Länge einer Liste bestimmen. Hm, ja. Dann muss ich wohl zuerst erklären, was eine Liste ist. Das wird jetzt etwas technisch. wer durchhält, wird mit Videos belohnt.

1. Die Liste

Eine beliebig lange Liste von Objekten, zum Beispiel Wörtern, oder Schülern, oder Gegenständen im Computerspiel, kann man mit einer einfach verketteten Liste darstellen. Einfach verkettet heißt, dass sich einfach jedes Element seinen unmittelbaren Nachfolger merkt. Das sieht dann so aus:

liste1

Die Liste ist hier dargestellt als waagrechte Schnur mit Knoten daran, und an jedem Knoten baumelt – wie bei einem Adventskalender – ein Säckchen mit dem von dem Knoten verwalteten Element – Wort, Schüler, Patient, Gegenstand, was man halt alles auflistet. Und jeder Knoten merkt sich seinen Nachfolger; er hat quasi einen Zeiger hat, der auf den Nachfolger verweist. Eine Ausnahme ist nur der Zeiger des letzten Knotens; der verweist ins Leere, informatisch null genannt.

Das mit den Knoten und dem Baumeln geschieht deshalb, weil es einem Wort, Schüler, Patient, Gegenstand ja egal sein sollte, wer sein Nachfolger ist; mit diesen Verwaltungsaufgaben ist der dazu gehörende Knoten beschäftigt. Diese Verwaltungsaufgaben werden später immer mehr, wenn es darum geht, die Liste zum Beispiel alphabetisch zu sortieren, oder Elemente daraus zu löschen oder welche hinzuzufügen. Das machen dann die Knoten unter sich aus, welche Elemente unter ihnen baumeln, ist weitgehend egal..

Mit einer kleinen Geschichte gesagt:

Im Reich der Schätze und Dschinn

Harun ar-Raschid, Kalif von Baghdad, der herrlichsten Stadt des Landes und aller anderen Länder unter der Sonne, hatte viele Frauen, viele Paläste, viele Schätze. Eifersüchtig hütete er seinen Besitz und war stets voller Misstrauen, deshalb verfügte er, dass jedes Stück durch einen Dschinn, einen Geist, bewacht werden sollte.

Jeder Dschinn erhielt eine Kiste für das Gut, das er bewachen konnte. So konnte es dem Dschinn egal sein, was er bewachte, Hauptsache, es passte in die Kiste.

Nun hatte Harun so viel Besitztümer, dass er sie nicht zählen konnte, so viele, dass er ihre Namen nicht wusste, so viele, dass er sie nicht zu finden wusste, wenn es ihm nach einem besonderen Kleinod verlangte.

Deshalb verfügte er, dass sich in Zukunft Verwalter um die Fülle seines Besitzes kümmern sollten. Den ersten unter ihnen, Jaffar, ernannte er zum Herren über die Schätze, also Juwelen und Perlen und Ringe und anderes Geschmeide.
Jaffar erhielt eine magische Lampe, in der ein Dschinn wohnte, der einen Schatz bewachte. Und dieser Dschinn hatte ebenfalls eine Lampe, und in dieser hauste ein weiterer Dschinn mit seinem Schatz, und auch der hatte wieder eine Lampe mit einem Dschinn darin.
Nur der letzte Dschinn, der bewachte zwar auch noch einen Schatz, er hatte auch eine Lampe, aber diese Lampe war leer und kein weiterer Dschinn wohnte darin

Das sieht dann zum Beispiel so aus:

liste

Diese Liste verwaltet zwei Elemente (Perlen und Gold). Jeder Dschinn kennt genau einen Nachfolger, bis auf den letzten in der Liste. Jeder Dschinn ist ein Knoten der Liste.

Ich fürchte, dieser Schnelldurchgang muss vorerst reichen. Ich könnte das ausführlicher erklären, und bei Schülern geschieht das ja auch langsamer und mit ständiger Umsetzung in Java. Aber das ist ja ein Blog und kein Fernkurs Informatik.

2. Eine Methode, um die Länge zu bestimmen

Also: Die Liste soll eine Methode haben, herauszufinden, wie lange sie ist. Da gibt es grundsätzlich zwei Möglichkeiten. Die eine kennen die Schüler schon und manche können sie bereits progammieren. Das ist die, auf die man – nach ersten Programmiererfahrungen – am ehesten kommt. Diese Methode heißt iterativ und sieht so aus, dass die Liste – Jaffar – einfach die ganze Reihe abgeht und mitzählt, und das solange, bis die Liste leer ist. Kennzeichen dafür ist eine while-Schleife und die Tatsache, dass ein Objekt – Jaffar – die ganze Rechenarbeit übernimmt. Man kann es sich so vorstellen, dass man mit dem Zeigefinger die Elemente der Liste durchgeht und bei jedem Knoten den Zähler um eins erhöht. Ist man beim letzten Knoten angekommen, hat man die Anzahl ausgerechnet.

(Wenn man das mit einer Reihe von Schülern vorne im Klassenzimmer macht, wird das Prinzip klar.)

Die andere Möglichkeit ist die rekursive Programmierung. Die ist elegant, und wenn man sie einmal begriffen hat, auch einfach. Aber auf dem Papier lässt sie sicher schwer erklären. Auch hier wieder nur ganz kurz: es gibt keine while-Schleife. Dafür wird die Aufgabe auf mehrere Schultern verteilt. Jeder Dschinn lässt seinen Nachfolger einen Teil der Arbeit machen. Wenn man den ersten Dschinn fragt, wie lang die Liste ist, sagt der: „Warte mal, ich frage meinen Nachfolger, wie lange die Liste ab ihm ist“. Und wenn der dann antwortet, zählt der erste Dschinn eins dazu, und das ist dann die Länge der Liste.

Wie kriegt der zweite Dschinn heraus, wieviele hinter ihm stehen? Genau so wie der erste: er fragt wiederum seinen Nachfolger, wartet auf die Antwort, und zählt 1 dazu – das ist dann seine Antwort. Und das macht jeder Dschinn so, bis auf den letzten, der muss niemanden fragen, der sagt einfach: 1. (Auf die Frage des Vorhergehenden.)

Um das zu illustrieren, sollten sich neun Schüler in einer Reihe aufstellen. Jeder bekam den gleichen Zettel in die Hand:

Das wird ein Experiment. Bitte lesen Sie die Anweisungen genau.
Wenn Ihnen jemand eine Frage stellt, verhalten Sie sich folgendermaßen:
Fall a) Wenn Sie nicht der letzte in der Reihe sind, also ihr Nachfolger nicht null ist:
1.Stellen Sie bitte die wörtlich gleiche Frage an ihren Nachfolger.
2.Warten Sie mit gespanntem Gesichtsausdruck auf seine Antwort. (Schauen Sie ihn dabei an.) Das kann eine Weile dauern.
3.Sobald die Antwort kommt, addieren Sie im Kopf 1 dazu. Teilen Sie diese Antwort laut dem mit, der Ihnen die ursprüngliche Frage gestellt hat.
Fall b) Wenn Sie der letzte sind, also ihr Nachfolger null ist: Antworten Sie laut: Eins.

Dazu muss man sagen, dass die Schüler zu diesem Zeitpunkt mit den angesprochen Konzepten bereits vertraut sein sollten. „Nachfolger“, „null“, das sind bekannte Fachausdrücke.

Wenn die Schüler sich an diese Regeln halten können, sieht das ganz eindrucksvoll aus. (Sie können es leider nicht immer. Lesekompetenz und so.) Wenn man einen Schüler fragt: „Wie lange ist die Liste noch?“, dann schaut der seinen Nachbarn an und stellt ihm die gleiche Frage. (Und wartet auf Antwort.) Der Nachbar schaut seinen Nachbarn an und stellt ihm die gleiche Frage. (Und wartet auf Antwort.) Und der fragt seinen Nachfolger, und so weiter, bis zum letzten Schüler. Der sagt laut „eins“, vorauf der vorletzte „zwei“ sagt. Und der vor ihm „drei“. Und so weiter bis zum ersten, der „neun“ sagt, wenn die Liste neun Elemente enthält.

Wenn man es sieht, kapiert man’s.

Eigentlich wollte ich das durch folgende Präsentation ergänzen, aber leider hat der Beamer gestreikt. Hier kurz als Video:

Ich schau mal, ob ich nächste Stunde die Schüler dazu kriege, sich auf Video aufnehmen zu lassen, dann wird’s noch klarer.

3. Powerpoint-Basteleien

Erzeugt habe ich den Film mit der Demoversion von E.M. PowerPoint Video Converter. Der macht Videos aus Powerpoint-Dateien. Leider tatsächlich nur aus diesen, nicht aus Impress. (In der Demoversion ist die Auswahl an Videoformaten beschränkt.) Man kann das Programm als Video Capture nutzen, dann nimmt es in der Geschwindigkeit auf, in der man jeweils arbeitet. Das ist praktisch, wenn man in Echtzeit Ton dazu sprechen möchte; auch das ermöglicht das Programm. Will man keinen Ton, geht es noch einfacher, weil automatisiert: Dann gibt man einfach an, wieviel Sekunden zwischen zwei Folien und wieviel zwischen den einzelnen Animationen vergehen sollen, und den Rest macht das Programm allein. Vielleicht machen das neue PP-Version schon selber; ich arbeite mit Impress und habe nur ein recht altes PP herumliegen.

Wo ich gerade bei Powerpoint bin, will ich auf ein richtig cooles Makro dafür hinweisen: The Magic PowerPoint Macro. Leider auch wieder nicht für Impress. Damit kann man das machen, was man eigentlich mit jedem vernünftigen Präsentationsprogramm machen können sollte, und zwar: die Objekte auf der Präsentationsoberfläche per drag & drop verschieben. Während der Präsentation natürlich. Das sieht dann so aus:

(Eher planloses Beispiel, nur zur Demonstration.)

Gibt es Präsentationsprogramm, mit dem ich das ohne Makro machen kann? Während der Vorführung anklicken und bewegen, und vergrößern und drehen und so weiter. Prezi.com ist mir da schon mehrfach empfohlen worden. Ich glaube, ich sollte mich mal ernsthaft damit beschäftigen – allerdings verwende ich eh nicht viele Präsentationen.

8 Gedanken zu “Einfach verkettete Liste, Rekursion und Entdeckungen bei Powerpoint

  1. Sehr schön! So würde ja sogar mir Informatik Spaß machen!

    Meine bisherigen Erfahrungen mit Informatik sind eher unangenehm konfuser und undurchdringlicher Art gewesen…

    Also: Beide Daumen hoch für diese Erklärung!

  2. Großartiges Makro. Habe ich gleich ausprobiert und zwei Folien für den Englischunterricht gebastelt. Danke für diesen Tipp.

  3. Danke schön, LaBe, ich dachte schon, diesmal hätte ich wirklich etwas geschrieben, das niemanden interessiert. Und: gern geschehen, Christian.

  4. Ich staune hier des Öfteren, dass mich Sachen interessieren, die mich normalerweise nicht interessieren (bräuchten). Auch dieser Beitrag hat mir auf interessante Weise neues Wissen beschert. Dankeschön und weiter so!

  5. Ich bastle gerade an vielen weiteren Folien zur verketteten Liste. Kann gar nicht aufhören – ich muss nur noch ein bisschen Arbeit für meine Schüler übrig lassen. Die sollen dann nämlich auch basteln.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *