Aus: Schubert / Schwill, 2004, S.115-132

 

4.3 Unterrichtsbeispiele

 

Einführung in Problemlösetechniken

Das prädikative programmiersprachliche Denkschema eignet sich besonders gut zur Einführung in das Problemlösen mit Methoden und Mitteln der Informatik, da das Aufstellen von Regeln für den Problemlöseprozess hier explizit erlernt wird. Außerdem werden allgemeingültige Problemlösetechniken wie Komplexitätsredu­zierung durch Problemzerlegung, Strukturierung der Teilaufgaben, Suche nach Analogien oder Verknüpfung von Anfangs- und Zielzustand durch Vorwärts- und Rückwärtsverkettung erkannt und angewendet. Die Schüler definieren Relationen zwischen den Objekten des Problemraums. Sie schreiben auf, was sie über das Problem wissen und nicht, wie man die Lösung erhält. Der Arbeitsstil des experi­mentierend forschenden Arbeitens eignet sich gut für das prädikative Problemlö­sen.

 

Spracherweiterung

Indem die Anfänger die Objekte und deren Eigenschaften aus der Aufgabenstel­lung herauslesen und in ihrer Muttersprache aufschreiben, bilden sie neue Schlüs­selwörter der Programmiersprache. Eine Sprache für prädikatives Problemlösen ist Prolog. Sie besitzt deklarative und prozedurale Bestandteile. Dieser Programmie­rung liegt die Prädikatenlogik l. Stufe zugrunde. Die Resolution wird als Beweis­verfahren bei der Lösungsbestätigung angewendet, d. h. das Prolog-System geht wie ein Theorembeweiser vor. Die Wissensbasis entspricht dem Programm (Fak­ten, Regeln). Fragen wirken wie Eingabewerte, mit denen das Programm gestartet wird. Die Antworten stellen die Ausgabewerte dar. Die fundamentale Kontroll­struktur ist die Rekursion. Damit werden Zyklen ausgedrückt.

 

Virtuelle Maschine

Das Prolog-System besitzt einen vorgefertigten Lösungssuchalgorithmus - die virtuelle Maschine — als Verarbeitungsmechanismus, der die Fakten und Regeln auswertet und zur Lösung verknüpft. Der Algorithmus der Programmausführung setzt sich also aus der selbstgestalteten Wissensbasis und dem vorgegebenen Such­algorithmus zusammen. Die virtuelle Maschine entlastet die Schüler bei der Lö­sungskonstruktion. Sie müssen die Tiefensuche mit Rückkehrverfahren, Backtracking genannt, nicht selbst entwickeln, sondern wenden sie an. Allerdings kann die Lösungbeschreibung nur gelingen, wenn diese virtuelle Maschine verstanden wurde. Backtracking kann z.B. nur gelingen, wenn Variablenbindungen wieder aufgelöst werden können.

Besondere Lemschwierigkeiten bereitet die Anwendung des Schnittoperators, mit dem man erfolglose Pfade von der Tiefensuche ausnehmen kann. Der Suchraum und damit der Suchaufwand wird reduziert, indem Zweige des Suchbaums abgeschnitten (besser gesperrt) werden. So erhält man effizientere Lösungen. Man muss dafür Wissen über den Problembereich besitzen, um entscheiden zu können, dass die weitere Suche in der Wissensbasis von bestimmten Zuständen aus prinzipiell keine Lösung mehr liefern kann.

Die typischen Anfängerfehler lassen sich in Modellierungs- und Dialogprobleme einteilen:

 

Modellierungsprobleme:

-                      Abgrenzung des Weltausschnittes (Modell "abgeschlossene Welt"),

-                      Bestimmung der Objekte,

-                      Zuordnung der Eigenschaften,

-                      Aufstellen von Regeln (Regeln als virtuelle Aussagen).

Dialogprobleme:

-                      Notwendigkeit von Anfragen,

-                      keine Beurteilung der Aussagen durch das System,

-                      mangelnde Transparenz der Lösungssuche,

-                      Flüchtigkeit von logischen Variablen (beziehen sich auf Objekte, nicht auf Speicherzellen).

 

 

Die fachdidaktische Gestaltung konzentriert sich auf:

 

Wissen strukturieren:

-                      Objekte, Eigenschaften, Beziehungen,

-                      Modell abgeschlossene Welt,

-                      Formalisierung zu Fakten und Regeln,

-                      Varianten für Datenstrukturen.

 

Erkunden der Prolog-Maschine:

-                      Faktenbasen erweitern,

-                      Ableitungsbaum als Darstellungsmittel,

-                      Ableitungsregeln,

-                      Regelverkettung,

-                      Beobachtung der Variablenbindung,

-                      Backtracking steuern.

 

Programmierheuristik:

-                      Reihenfolge der Fakten und Regeln,

-                      Gefahr von Endlosschleifen,

-                      Strukturierung von Regelwerken.

 

Heuristik zur Beschränkung von Suchräumen.

 

Wir empfehlen nicht, die informatische Bildung ausschließlich auf das prädikative programmiersprachliche Denkschema aufzubauen. Es sprechen aber gute Gründe für eine Einführung in dieses alternative Konzept der Informatik:

 

1.  Dem Schüler wird ein erheblicher Teil des Programmieraufwandes abgenom­men. Er beschreibt sein zu lösendes Problem mit Fakten und Regeln, ohne sich um die Lösungssuche selbst zu kümmern. Diese wird ihm in vorgefertigter Software zur Verfügung gestellt (Tiefensuche mit Rückkehrverfahren). Das hat für den Schüler den Vorteil, dass er mit einfachen Anfragen an sein Programm, kompli­zierte Lösungsmechanismen auslösen kann, die er schrittweise zu erkunden und anzuwenden lernt.

2. Die Algorithmenstruktur Zyklus und die Datenstruktur Liste beruhen im prädi­kativen programmiersprachlichen Denkschema auf der rekursiven Arbeitsweise und sind nur damit möglich. Rekursion steht damit nicht am Ende einer langen Einführung, sondern gehört bereits zur Gestaltung erster, einfacher Programme. So wird Rekursion zu einer rasch vertrauten Entwurfsmethode bei den eigenen Prob­lemlösungen. Es hat sich gezeigt, dass rekursive Denk- und Arbeitsweisen, die zu den fundamentalen Ideen der Informatik gehören, fast spielerisch erlernt werden. Damit gelingt ein erstaunlich einfacher Zugang zu anspruchsvollen Konzepten der Informatik.

3.  Der Schüler wird vom sonst üblichen Ballast der Syntaxbesonderheiten einer Programmiersprache entlastet. Er braucht kaum Schlüsselworte zu erlernen; er bildet sie selbst. Die wenigen Schreibregeln von Prolog sind gut überschaubar. Dagegen liegt der Schwerpunkt auf den Anforderungen an das Modellieren der Problembeschreibung.   Logisches Denken wird   gefördert.   Die   eigene   Ver­antwortung für die Korrektheit der Wissensbasis, das Prolog-Programm, ist leichter einzusehen als in anderen programmiersprachlichen Denkschemata.

 

Die folgende Unterrichtsskizze soll mehr Lehrer ermutigen, diesen Weg zur Ein­führung in das Problemlösen mit Mitteln und Methoden der Informatik zu wählen, und ihnen zugleich helfen, mit vertretbarem Einarbeitungsaufwand zu Unterrichts­erfolgen zu gelangen. Ergebnis der informatischen Bildung könnte dann für immer mehr Schüler die Erkenntnis sein, dass zu jeder Problemklasse das richtige pro­grammiersprachliche Denkschemata auszuwählen ist. Eine anspruchvolle Erweite­rung des Algorithmenbegriffs kann die Anwendung von Regeln darstellen, die eine Wissensbasis modifizieren, indem sie zur Ausfuhrungszeit eines Programms vor­bereitete Regeln hinzufügen oder löschen.

 

Lernbereiche

I. Einführung in die gewählte Programmierumgebung:

1.                                          Starten des Systems - Kennenlernen der Benutzungsoberfläche, Laden und Nutzen des l. Beispiels - Anfragen an die Faktenbasis, Analyse des l. Beispiels - Lösungssuche als fertige Software,

2.                                          Erweiterung des l. Beispiels um Regeln - Programm als Sequenz, Laden, Editieren, Nutzen und Speichern des veränderten Programms, Kennenler­nen der Ableitung durch Mustergleichheit,

3.                                          neue Faktenbasis des 2. Beispiels entwerfen, Wiederholung des Editierens und Speicherns, Anfragen mit Variablen (Name, Wert, Typ) - Variablen­bindung als Selektion.

 

II. Daten- und Algorithmenstrukturen mit rekursiver Arbeitsweise:

 

4.                                          Erweiterung des 2. Beispiels um eine rekursive Regel, Zyklus durch Rekursion, Rekursionsaufruf und Rekursionsabbruch, praktische Realisie­rung der rekursiven Arbeitsweise,

5.                                          Entwerfen einer rekursiven Lösung für das 3. Beispiel, Wiederholung Rekursionsaufruf und Rekursionsabbruch, Spur der Ableitung verfolgen -Suchprozess mit Rückkehr,

6.                                          Prozedurmodell entwickeln - Aufruf, Erfolg, Misserfolg, Rückkehr, Ein­führen der Datenstruktur Liste - Kopf und Restliste, Anwendung der Da­tenstruktur Liste im 4. Beispiel

7.                                          Analyse des 5. Beispiels - rekursive Datenstruktur, Beobachten des rekur­siven Abbaus der Liste bis zur leeren Liste, Wiederholung des Suchpro­zesses mit Rückkehr am 5. Beispiel.

 

III. Komplexe Übungen:

 

8.                                          Ziel: Färben einer Landkarte - Analyse des Programms, Kennenlernen der Beschreibung eines Suchraumes durch Aufzählung, Programm als Wis­sensbasis aus Fakten und Regeln, Wiederholung des Prozedurmodells (zu Färbungsproblem s. auch Kapitel 6.4),

9.                                          Ziel: Vorfahren-Relation in einen Familienstammbaum einfügen, Wieder­holung der rekursiven Arbeitsweise, Programmierheuristik zur Reihenfol­ge der Fakten und Regeln,

10.                                      Ziel: Mahnung zu einer Bibliotheksdatei entwerfen, Wiederholung des Variablen- und Datenkonzepts, Zusammenfassung zum Problemlösen mit einer logischen Programmiersprache.

 

Ziel: Einführung in die gewählte Programmierumgebung

 

Zielorientierung mit dem Eingabe, Verarbeitung und Ausgabe: Der Lehrer führt in den neuen Lernbereich ein, indem er den Schülern erklärt, dass Problemlösen in der Informatik mit Programmen realisiert wird, die Eingaben zur Verarbeitung nutzen und daraus Ausgaben erzeugen. Um eigene kleine Programme zu entwi­ckeln, benötigt man eine spezielle Software zur Entwicklung der Programme, die Programmierumgebung genannt wird. Eine solche Programmierumgebung können die Schüler in den neuen Lernbereichen kennen lernen, um mit ihrer Hilfe die eigenen Ideen in Programme zu fassen.

 

Starten des Systems - Kennenlernen der Benutzungsoberfläche: Die Schüler sollen Eingabe, Verarbeitung und Ausgabe experimentell erkunden, indem sie ein Pro­gramm kennen lernen und anwenden, das der Lehrer für sie vorbereitet hat. Die Prolog-Arbeitsumgebung wird gestartet. Die Schüler finden eine Benutzungsober­fläche vor, die an ihre Erfahrungen bei der Anwendung von Informatiksystemen anknüpft. Sie laden das Programm "Freundinnenauswahl" (vgl. Anhang B1). Der Bildschirm ist in drei Bereiche aufgeteilt. Ganz oben sehen sie das Ausgabefenster, in der Mitte das Eingabefenster und unten das Fenster mit dem aktuellen Pro­gramm, das die Verarbeitung ermöglicht.

 

Laden und Nutzen des 1. Beispiels - Anfragen an die Faktenbasis: Während z.B. bei der Textverarbeitung das Öffnen einer Datei völlig ausreichte, um diese Datei zu nutzen, lernen die Schüler jetzt eine Besonderheit der Prolog-Arbeitsumgebung kennen. Das Programm muss "konsultiert", d. h. für die Verarbeitung aktiviert werden. Nun können Anfragen an die Faktenbasis gestellt werden. Die Schüler lernen, das System zu verlassen.

 

Analyse des 1. Beispiels - Lösungssuche als fertige Software: Die Analyse führt die Schüler zu der Erkenntnis, dass ein einfaches Prolog-Programm aus Fakten be­steht, die das zu lösende Problem näher beschreiben, aber keinen Lösungsweg festlegen. Interessant ist deshalb die Frage, wie der Rechner zu einem ausführbaren Algorithmus kommt. Die Lösungssuche steht als fertige Software mit dem Inter­preter der Prolog-Programme zur Verfügung. Es handelt sich um einen Algorith­mus für Tiefensuche, der umkehren kann, wenn er in eine Sackgasse geraten ist. Die Umkehr wird mit einem Rückkehrverfahren, Backtracking, realisiert. Erfolglo­se Variablenwertbindungen werden gelöscht. Mit einer Anfrage (Eingabe) kann eine Anzahl verschiedener Lösungen (Ausgabe) erzeugt werden. Fakten, die bei der Problembeschreibung vom Menschen vergessen wurden, kann die automati­sche Lösungssuche nicht finden. Der Beweisverlauf kann also die Mängel der Wissensbasis nicht korrigieren.

 

Ziel: Erweiterung des 1. Beispiels um Regeln - Programm als Sequenz

 

Der Lehrer führt den Begriff Regel an Beispielen aus dem täglichen Erfahrungsbe­reich der Schüler ein. Regeln der Form "wenn Bedingungen erfüllt, dann Handlun­gen ausführen" werden mit den Schülern gemeinsam gebildet für die Freundinnen­auswahl. Die Umkehrung der Regel in der Prolog-Schreibweise wird besprochen.

 

Laden, Editieren, Nutzen und Speichern des veränderten Programms: Die Schüler wiederholen ihre Kenntnisse aus der vorhergehenden Stunde, indem sie die Pro­grammierumgebung starten, das Programm laden und die Regeln hinzufügen. Das Speichern eines Programms wird neu eingeführt. Nach dem Aktivieren des Pro­gramms stellen die Schüler erstmals Anfragen, die Regeln zur Ausführung bringen.

 

Kennen lernen der Ableitung durch Mustergleichheit: Die Schüler erkunden den Unterschied zwischen Anfragen, die vom System mit "ja" oder "nein" beantwortet wird, und Existenzanfragen mit einer Variablen, bei der sie verschiedene Lösungen durch die Bindung von konkreten Objekten an diese Variable erhalten. Der Lehrer erklärt am Beispiel, wie es zur Ableitung von Lösungen durch Mustergleichheit (Identität) kommt:

 

Anfrage: ?-freundin(Wer).

Versuch mit der 1. Regel: maedchen(Wer),klug(Wer).

Versuch mit dem 11. Fakt: maedchen(anne),klug(anne).

Erfolgsmeldung: Wer = anne

 

Die Suche nach identischen (mustergleichen) Fakten wird von den Schülern als Schlusspunkt der erfolgreichen Lösungssuche erkannt. Die Ableitung durch Identi­tät stellt also stets den letzten Beweisschritt dar, wenn überhaupt eine Lösung gefunden wird. Sie ist zugleich die einfachste Form der Unifikation. Unifikation ist die Basisoperation einer virtuellen Prolog-Maschine, wobei zwei Prolog-Ausdrucke in Übereinstimmung gebracht werden. Eine Mustergleichheit wird hergestellt. Die Ableitungsfolge kann grafisch als Ableitungsbaum dargestellt werden. Die Schüler verstehen den einfachsten Programmaufbau als Sequenz. Die Summe der Fakten und Regeln zu einem Problem kann auch als Wissensbasis (Prolog-Programm) bezeichnet werden. Die Schüler erfahren, dass ein Prolog-Programm immer sequentiell vom Interpreter verarbeitet wird. Damit verstehen sie, dass die Fakten am Programmanfang stehen müssen, um unnötige Suchwege zu verhindern. Schrittweise wird so eine Programmierheuristik im Unterricht ent­wickelt, die es den Schülern ermöglicht, eigene Lösungen zu erstellen.

 

Ziel: neue Faktenbasis des 2. Beispiels entwerfen

 

Der Lehrer weist daraufhin, dass jedes Programm einen kleinen, abgeschlossenen Weltausschnitt modelliert (Modell "abgeschlossene Welt"). Der Mensch trägt die Verantwortung für die Grenzen dieses Modells. Fehlende und fehlerhafte Fakten führen mit Sicherheit zu falschen Lösungen. Objektorientierte Denkweisen lassen die Knoten des Netzes als Objekte erkennen (z.B. Rhombus) und die Kanten als Relationen zwischen den Objekten (z.B. Rhombus ist ein spezielles Drachenvier­eck). Ziel der Modellierung ist eine Abbildung der Objekte mit ihren Relationen in einem Informationssystem. Der Weltausschnitt wird durch den Bereich der konve­xen Vierecke begrenzt (Abb. 4.7). Im Beispiel "Vierecksarten" führt die Beschrei­bung aller Kanten zu einer Sammlung von Fakten, über denen einfache Anfragen möglich sind (vgl. Anhang B2).

 

Die Anfrage: "?-ist_ein(trapez,konvexes_Viereck)." liefert die Antwort "nein", obwohl die Relation in der realen Welt gültig ist, falls der l. Fakt vergessen wurde. Der Prolog-Interpreter bringt mit "nein" zum Ausdruck: "Diese Relation wurde nicht in das Modell aufgenommen." Ohne Verständnis für die Lösungsversuche der virtuellen Prolog-Maschine werden mit Sicherheit Modellierungsfehler auftre­ten. Aber auch eine korrekte Faktenbasis liefert im vorliegenden Beispiel keine Relation, die sich über Zwischenstufen ergibt. Die Schüler erkennen, dass Fakten hier nicht ausreichen. Die Erweiterung des Gelernten wird vom Problem ausge­hend begründet. Dieses problemorientierte Lernen ist charakteristisch für die informatische Bildung.

 

Wiederholung des Editierens und Speicherns: Die Schüler erstellen dieses Pro­gramm (Faktenbasis) mit der Programmierumgebung selbständig. Mit verschiede­nen Anfragen erkunden sie die Programmausführung (Schlussfolgerungsprozess) und die Variablenbindung. Sie nutzen die Möglichkeit, alle Lösungen eines Prob­lems vom Prologsystem zu erhalten.

 

Anfragen mit Variablen (Name, Wert, Typ) - Variablenbindung als Selektion: Der Begriff der Variablen in der Informatik knüpft an die aus der Mathematik bekann­ten Kennzeichen Name und Wert an und wird um die neue Eigenschaft des Typs ergänzt. Vorerst bleibt es beim Datentyp Zeichenketten. Später im Lernbereich 6 kann exemplarisch auf die Arithmetik mit den Datentypen für Ziffern verwiesen werden. Die Prolog-Arbeitsumgebung erspart den Schülern die aufwendigen

 

Syntaxbesonderheiten anderer Programmiersprachen. Typdeklarationen sind nicht in das Programm zu schreiben, müssen aber logisch durchdacht und in den Konse­quenzen verstanden werden.

Nach dem sequentiellen Programmablauf lernen die Schüler nun die Selektion mit der Algorithmenstruktur Alternative kennen, die durch Fakten und Regeln ermöglicht wird, die mit dem gleichen Schlüsselwort beginnen. Sie werden zum Begriff Prozedur zusammengefasst. Neu ist für die Schüler, dass die Variablenbin­dungen nur vorübergehend erfolgt. Gerade die Auflösung bestehender Bindungen und die Neubindung ermöglichen die alternativen Lösungswege bei der Ausfüh­rung des Prolog-Programms. Die Leistungsfähigkeit der Prolog-Maschine geht über die Unifikation durch Identität hinaus. Enthält z.B. die Anfrage eine Variable, dann entsteht ein universeller Fakt. In diesem Fall interessiert nicht ein bestimmtes Objekt, sondern die Tatsache, ob überhaupt ein Objekt mit der gewünschten Eigen­schaft existiert. Eine solche Existenzanfrage wird vom System nicht mit nur "ja" oder "nein" beantwortet. Im Erfolgfall wird das erste konkrete Objekt, Atom ge­nannt, angezeigt, mit dem die Existenzanfrage erfüllt werden konnte.

Der universelle Fakt "ist_ein(X,Y)." wird durch Substitution, Variablenbindung, von X durch "trapez" und Y durch "konvexes_Viereck" zur Instanz "ist_ein(trapez,konvexes_Viereck)." Die Variable ist dabei das Mittel, um mehrere Anfragen zusammenzufassen. Der Schüler erhält dann nicht nur eine Lösung son­dern alle. Durch die Unifikation besteht die Möglichkeit, eine Anfrage durch Bin­dung der freien, noch keinem konkreten Objekt zugeordneten Variablen in Über­einstimmung mit einem Fakt zu bringen. Diese Variablenbindung wird Instanziierung genannt. Sie bleibt bis zum Erreichen einer Lösung oder eines Umkehrpunktes durch Backtracking erhalten. Unter Backtracking versteht man die Fortsetzung der Lösungssuche mit alternativen Fakten unter Aufhebung der vorher vollzogenen Variablenbindung.

 

Ziel: Erweiterung des 2. Beispiels um eine rekursive Regel

 

Die Schüler sind unzufrieden damit, dass das 2. Programm nur feststellen kann, dass ein Parallelogramm ein Trapez ist und nicht auch, dass ein Parallelogramm

ein konvexes Viereck ist. Um diesen Mangel zu beheben, entsteht das Ziel eine Regel "gehoert_zu" zu formulieren, die sich selbst wieder aktivieren (aufrufen) kann, um eine ganze Zugehörigkeitskette abzuleiten.

 

Zyklus durch Rekursion, Rekursionsaufruf und Rekursionsabbruch: Dazu führt der Lehrer den neuen Begriff Rekursion anschaulich ein (z.B. Spiegelbild im Spiegel) und erklärt das Kennzeichen der rekursiven Arbeitsweise, eine Regel aktiviert sich selbst wieder. Nachdem der rekursive Aufruf in der rekursiven Regel formuliert wurde, steht die Frage, wie dieser sich ständig wiederholende Prozess, Zyklus, gestoppt werden kann. Deshalb wird vom Lehrer der Begriff der Abbruchbedin­gung eingeführt, die zu jeder Rekursion und zu jedem Zyklus gehört. An diesem Beispiel lässt sich eine typische Modellierungsheuristik erlernen:

 

1.    Der Rekursionsabbruch muss vor dem Rekursionsaufruf erreichbar sein.

2.    Die Teilziele im Körper rekursiver Regeln sind so anzuordnen, dass der Rekursionsaufruf so lange wie möglich aufgeschoben wird.

 

Diese Heuristik folgt nicht aus der Prädikatenlogik l. Stufe, sondern aus der Re­gelverarbeitung mit einer virtuellen Maschine (Abb. 4.8).

Anfänger benötigen die Veranschaulichung der Aktionen in einem Ableitungsbaum (Abb. 4.9), um Wissensbasen auf ihre Vollständigkeit und Korrektheit zu überprü­fen. Aus dem Ableiten der Ziellisten kann die geeignete Heuristik für die Modellie­rung gefunden werden.

 

Praktische Realisierung der rekursiven Arbeitsweise: Die Schüler gehen zur prak­tischen Arbeit über. Sie laden, modifizieren und speichern das 2. Programm selb­ständig. Das ist für sie eine gute Wiederholung im Umgang mit der Programmier­umgebung. Neu ist das Anwenden einer rekursiven Problemlösung. Deshalb sollte ausreichend Zeit zur Verfügung stehen, um verschiedene Anfragen zu stellen und mit der Lösungssuche zu experimentieren.

Um eine Antwort auf die Anfrage "?-gehoert_zu(parallelogramm, Art)" zu fin­den, sucht die Prolog-Maschine sequentiell mit der ersten Klausel, Oberbegriff für alle Fakten und Regeln, beginnend nach einem Fakt oder Regelkopf, der mit der Anfrage zu einer gemeinsamen Instanz unifiziert werden kann. Die l. Regel bietet diese Möglichkeit. Durch Bindung der freien Variablen "X=parallelogramm" ent­steht ein neues Ziel, wenn der unifizierte Regelkopf durch den Regelkörper "ist_ein(parallelogramm,Art)." ersetzt wird.

 

Ziel: Entwerfen einer rekursiven Lösung für das 3. Beispiel

 

Die rekursive Arbeitsweise soll an dem einfachen Beispiel "Computeraufbau" (vgl. Anhang B3) geübt werden. Der grobe Computeraufbau liefert dafür die Beziehun­gen zwischen dem Ganzen und seinen Teilen. Die Formulierung dieser Fakten "teil_von" stellt jetzt für die Schüler schon keine Schwierigkeit mehr dar. Anders verhält es sich mit dem Anwenden der Rekursion.

 

Wiederholung Rekursionsaufruf und -abbruch: Hier ist die Hilfe des Lehrers erfor­derlich, um die Analogie zum 2. Programm zu erkennen. Wieder soll eine Regel mehrfach aktiv werden, um Teile, die wiederum Teile enthalten, richtig zu verbin­den. Der Zyklus wird mit dem Rekursionsaufruf realisiert. Dazu gehört ebenfalls ein passender Rekursionsabbruch. Die Schüler erfahren, dass die einfachste Lö­sungsidee zuerst realisiert wird. So verstehen sie, warum im Prolog-Programm der Rekursionsabbruch immer vor der Regel mit dem Rekursionsaufruf stehen muss. Diese Programmierheuristik fördert die Korrektheit und Effizienz ihrer Lösungen. Nachdem die Lösung gemeinsam entworfen wurde, erfolgt die praktische Erpro­bung individuell von den Schülern.

 

Spur der Ableitung verfolgen - Suchprozess mit Rückkehr: Der Lehrer demonstriert den Aufruf der Trace-Komponente des Prolog-Systems, um damit die Spur der Ableitung experimentell zu erkunden. Der Suchprozess mit Rückkehr wird im abschließenden Unterrichtsgespräch wiederholt, indem Beispiellösungen begründet werden.

Die Schüler werden erstmals mit den Systemmitteilungen Aufruf (Call), Erfolg (Exil), Misserfolg (Fail) und Rückkehr (Redo) konfrontiert. Vorerst geht es aber nur um das Beobachten ausgewählter Lösungswege. Das dazugehörende Proze-

durmodell (Abb. 4.10) mit den vier Türen wird in den folgenden Unterrichtsstun­den schrittweise entwickelt. Für den weiteren Unterricht stehen jetzt die drei grundlegenden Algorithmenstrukturen Sequenz, Alternative und Zyklus zur Verfü­gung. Die Schüler werden zunehmend besser verstehen, dass alle Informatiklösun­gen aus diesen Bausteinen zusammengesetzt werden können.

 

Ziel: Prozedurmodell entwickeln (Aufruf, Erfolg, Misserfolg, Rückkehr)

 

Die Tiefensuche des Prolog-Interpreters erfordert die Rückkehr von erfolglosen Wegen und die Suche nach alternativen Möglichkeiten. Die Schüler erkennen das an den vier Türen, die es für jede Prozedur (Teillösung) gibt. Der Lehrer führt nochmals die Beobachtung der letzten Stunde vor als Einstieg in die Erklärung des Modells am Beispiel. Am Beispiel der Prozedur "teil_von" wird das Prozedurmo­dell vorgestellt:

 

Anfrage :                      teil_von(computer, Was).

Aufruf der Prozedur :   teil_von(computer, Was).

Erfolg :                         teil_von(computer, Zentraleinheit).

Was = Zentraleinheit

Rückkehr :                   teil_yon(computer, Was).

Erfolg :                         teil_yon(computer,peripherie).

Was = peripherie

Rückkehr :                   teil_von(computer, Was).

Misserfolg :                  teil_von(computer, Was).

 

Der Misserfolg tritt erst dann auf, wenn kein unbenutzter Fakt der Prozedur "teil_von" mit der Anfrage in Übereinstimmung gebracht werden kann. Im 3. Fall sind zwar noch drei unbenutzte Fakten vorhanden, aber dort steht jeweils das Ob­jekt "Zentraleinheit" an der ersten Position. Das kann nicht mit dem Anfrageobjekt "Computer" zur Übereinstimmung der Muster gebracht werden. Von dieser ersten Konfrontation mit dem Prozedurmodell darf noch kein tiefes Verständnis erwartet werden. Die kontinuierliche Anwendung bei allen folgenden Beispielen bringt erst schrittweise diese Einsicht.

 

Einführen der Datenstruktur Liste - Listenkopf und Restliste: Nachdem die Algo­rithmenstrukturen bekannt sind, soll bei den Schülern Verständnis für die Bedeu­tung der Datenstrukturen in der Informatik geweckt werden. In der Prolog-Pro­grammierumgebung steht mit der Datenstruktur Liste ein anspruchsvolles Informa­tikkonzept mit einfachen Beschreibungsmöglichkeiten zur Verfügung. Der Lehrer kann am Beispiel einer Namensliste die neuen Begriffe Listenkopf und Restliste einführen und auf deren Schreibweise in Prolog mit dem Listenoperator eingehen.

 

Anwendung der Datenstruktur Liste im 4. Beispiel: Die Datenstruktur Liste kann sehr einfach zur Beschreibung von Nachbarländern eingesetzt werden. Da das Programm "Nachbarländer" (vgl. Anhang B4) nur aus Fakten besteht können sich die Schüler gut auf die Datenstruktur konzentrieren. Das Editieren, Speichern und Nutzen des Programms bereitet keine Schwierigkeiten.

 

Ziel: Analyse des 5. Beispiels - rekursive Datenstruktur

 

Die Kenntnisse über die Datenstruktur Liste werden vertieft, indem das kleine, aber gehaltvolle Programm "Listenelement" (vgl. Anhang B5) gemeinsam mit den Schülern analysiert wird. Es besteht aus einem Fakt, dem Rekursionsabbruch, und einer einzigen Regel mit dem rekursiven Aufruf. Das Wissen über die Rekursion wird wiederholt. Der Lehrer führt mit der Trace-Komponente die Wirkung des Programms vor und vereinfacht diese Informationsfülle über die Ableitungsspur zu einem Ableitungsbaum.

 

Beobachten des rekursiven Abbaus der Liste bis zur leeren Liste: Nachdem die Schüler den rekursiven Abbau der Liste bis zur leeren Liste durch die Demonstra­tion des Lehrers und das analysierende Unterrichtsgespräch kennen lernten, wird die praktische Nutzung des Programms für beliebige Listen zur Festigung dieses neuen Stoffes eingesetzt.

 

Wiederholung des Prozedurmodells: In der praktischen Arbeit mit der Programmierumgebung wird die Trace-Komponente von den Schülern selbständig aktiviert und damit das Prozedurmodell für die Kontrolle des Lösungsweges bewusst einge­setzt. Erste Versuche der Schüler im mündlichen Argumentieren mit den neuen Begriffen Aufruf, Erfolg, Misserfolg und Rückkehr schließen den Lernbereich 5 ab. Die Ableitungsbäume machen deutlich, dass die Prolog-Maschine zuerst einen Ableitungspfad bis zum Ende verfolgt, bevor ein neuer Pfad begonnen wird. Beim Absteigen in die Tiefe werden alle Entscheidungspunkte mit alternativen Möglich­keiten markiert, die noch nicht überprüft wurden. Der Aufruf (Call) kommt durch die sequentielle Auswahl ohne Backtracking zustande. Bei Erfolg (Exil) wird für ein späteres Backtracking ein Entscheidungspunkt gesetzt, falls es alternative Klauseln gibt. Der Misserfolg (Fail) tritt auf, wenn keine von den Klauseln einer Prozedur mit dem Ziel unifiziert werden konnte. Es wird dann ein tiefes Backtracking zu einem anderen Ziel, zum letzten Entscheidungspunkt, eingeleitet. Rück­kehr (Redo) bedeutet, dass diese Prozedur durch tiefes Backtracking von einer gescheiterten Prozedur aus erneut verwendet wird. Der gesetzte Entscheidungs­punkt ermöglicht die Fortsetzung mit der ersten noch nicht benutzten Klausel. Flaches Backtracking führt nicht aus der verwendeten Prozedur heraus. Beim Scheitern einer Klausel der Prozedur kommt es zur Anwendung alternativer Klau­seln innerhalb der gleichen Prozedur.

 

Komplexe Übungen: Im Vergleich zum Ausgangsniveau wurde so viel neuer Stoff erarbeitet, dass Übung, Anwendung und Kontrolle der Einzelheiten im Zusam­menhang erforderlich sind.

 

Ziel: Färben einer Landkarte - Analyse des Programms

 

Das Beispiel "Färben einer Landkarte" (Abb. 4.11) ähnelt einer Knobelaufgabe und hat den Vorteil, dass die Schüler die Lösung nicht sofort kennen (s. Kapitel 6.4, Fär­bungsproblem). Noch anspruchsvoller wird die Frage nach allen möglichen Lösun­gen. Der Vorteil der Informatikanwendung wird hier erstmals so richtig deutlich. Das gelingt in anderen Programmierumgebungen mit Anfängerlösungen selten. Der Schwerpunkt wird jetzt auf die Analyse der Aufgabenstellung (Eingabe- und Ausga­bewerte) und den Grobentwurf (Problembeschreibung) gelegt. Die fertige Lösung stellt der Lehrer danach zum Experimentieren bereit (vgl. Anhang B6).

 

Kennen lernen der Beschreibung eines Suchraumes durch Aufzählung: Diese grundlegende Problemlösemethode ist für die Schüler neu. Sie sollte deshalb in Ruhe genutzt und auf ihre Vor- und Nachteile hin untersucht werden. Die Schüler sollen erkennen, dass die Landkarte in vereinfachter Form in der Programmier­sprache darzustellen ist. Dazu werden die Nachbarschaftsbeziehungen aufgezählt. Diese Methode der Beschreibung des Suchraumes durch Aufzählung ist nur ver­tretbar, wenn die Anzahl der Objekte und der Beziehungen zwischen ihnen klein bleibt. Die Anzahl der Lösungen kann dabei durchaus beachtlich groß sein.

 

Programm als Wissensbasis aus Fakten und Regeln: Neben der Wiederholung des Grundaufbaus einer solchen Wissensbasis, wird die Ausgabeprozedur "write" neu eingeführt. Die Schüler unterscheiden zwischen der Textausgabe in Hochkommas und der Wertausgabe für die Variablen. Hier bieten sich Ansatzmöglichkeiten zur Modifikation des fertigen Programms, indem neue Ausgabemöglichkeiten erprobt werden. In leistungsstarken Gruppen kann auf die Art der Lösungserzeugung durch Generieren einer Farbbelegung und deren Testen auf Verträglichkeit eingegangen werden. An diesem Beispiel lassen sich die zeitweiligen Variablenbindungen mit der Trace-Komponente besonders gut kontrollieren. Die Schüler beobachten auch erstmals, dass sie auf die Ergebnisse warten müssen, weil das System längere Suchzeiten benötigt.

 

Ziel: Vorfahrenrelation in einen Familienstammbaum einfügen

 

Zur Wiederholung und Zusammenfassung aller gelernten Elemente eignet sich besonderes das Beispiel "Familienstammbaum" (vgl. Anhang B7). Es fehlt in kei­nem Anfängerlehrbuch. Der Vorteil besteht darin, dass der Lehrer die Objekte und Beziehungen sofort bei den Schülern als bekannt voraussetzen kann und trotzdem genügend anspruchsvolle Informatikelemente üben kann. Der Lehrer stellt ein Rahmenprogramm zur Verfügung, in das die Schüler nur noch die von ihnen ge­wünschten Namen eintragen müssen. Als Übung werden die Vater-, Mutter- und Geschwisterrelation im Unterrichtsgespräch zusammengetragen.

 

Wiederholung der rekursiven Arbeitsweise: Mit der neuen Zielstellung, nicht nur die Eltern, sondern auch frühere Vorfahren mit einer Regel zu ermitteln, soll die Analogie zu den bereits gelösten Beispielen hergestellt werden. Wieder werden der Rekursionsabbruch und der Rekursionsaufruf formuliert. Jetzt müssten diese rekur­siven Programmelemente bereits von den Schülern gefunden werden.

 

Programmierheuristik zur Reihenfolge der Fakten und Regeln: Die Schüler ergän­zen den Programmrahmen nach eigenen Vorstellungen und nutzen das vollständige Programm. Im Umgang mit der Programmierumgebung sollte sich eine gewisse Sicherheit eingestellt haben. Dieses Beispiel eignet sich auch für eine Lernerfolgs­kontrolle, die aus einem praktischen und einem theoretischen Teil bestehen könnte. Der praktische Teil ergibt sich aus der Vervollständigung des lückenhaften Pro­gramms. Für den theoretischen Teil bieten sich Fragen nach dem Programmaufbau und zum heuristischen Wissen, z.B. der Reihenfolge der Fakten und Regeln an.

 

Ziel: Mahnung zu einer Bibliotheksdatei entwerfen

 

Die Aufgabenstellung "Bibliotheksmahnung" (vgl. Anhang B8) kann der Auftakt zu einem interessanten, weiterführenden Informatikunterricht in den folgenden Schuljahren sein. Hier wird ein praktisches Anwendungsfeld der Informatik be­rührt, das natürlich in dieser kurzen Einführungsphase nicht zufriedenstellend bearbeitet werden kann. Die Bibliotheksverwaltung, zum Beispiel der Schülerbib­liothek, wird von den Schülern als echtes Problem verstanden. Also greift der Leh­rer exemplarisch eine Teilaufgabe heraus, die mit den Möglichkeiten der Anfänger lösbar ist.

 

Wiederholung des Variablen- und Datenkonzepts: Die Zusammenstellung geeigne­ter Fakten wie "buch", "leser" und "ausleihe" bereitet den Schülern keine Schwie­rigkeiten. Der Lehrer kann in leistungsstarken Gruppen die zusammengesetzten Datenstrukturen einführen, da sie in Prolog erstaunlich leicht zu beschreiben sind. Für jedes Buch bieten sich eine Registriernummer, der Autor mit Name und Vor­name und der Titel an. Gemeinsam wird die Regel für eine Mahnung entworfen. Hier kann der Lehrer die Schüler mit der anonymen Variable als Platzhalter für uninteressante Information bekannt machen. Die Nutzung dieses Programms kann nur der zaghafte Beginn für eine umfassendere Bibliothekslösung sein. Die Schüler werden so zum selbständigen Weiterlernen in der Informatik angeregt. Beim Laden, Ergänzen, Speichern und Nutzen des Teilprogramms sollten keine Schwierigkeiten mehr auftreten.

 

Zusammenfassung zum prädikativen programmiersprachlichen Denkschema: Abschluss dieser Informatikeinführung bildet eine Zusammenfassung des Problemlösens im prädikativen programmiersprachlichen Denkschemata:

 

-                      Das Programm ist eine Wissensbasis mit Fakten und Regeln.

-                      Eingaben werden als Anfragen formuliert.

-                      Ausgaben liefert das System in Form von Antworten.

-                      Zur Lösungssuche wird eine virtuelle Prolog-Maschine verwendet.

-                      Sequenzen entstehen durch die Reihenfolge der Fakten und Regeln

-                      Alternativen entstehen durch verschiedene Fakten und Regeln mit gleichem Namen.

-                      Zyklen entstehen durch Rekursionsaufruf und Rekursionsabbruch.

 

 

Unter dem Begriff "Maschinelles Lernen" können modifizierbare Wissensbasen betrachtet werden, die nach erfolgreicher Modellanwendung neue Fakten erzeugen, mit denen der Anwendungserfolg gemerkt und der künftige Suchprozess gesteuert wird. Die Flüchtigkeit von logischen Variablen liegt in ihrer Verbindung zum Objekt, nicht zur Speicherzelle. Für die informatische Bildung ist die Erkenntnis wertvoll, dass das System die Aussagen nicht bewerten kann, sondern nach festem Kalkül verknüpft. Die Strukturierung von Wissen steht im Vordergrund. Von der eigenen Entwicklung adäquater Sprachelemente für die Prädikate wird die Model­lierung stark beeinflusst. Diese unmittelbare Verbindung zwischen Modell und System wird in anderen programmiersprachlichen Denkschemata von der Be­schreibungssprache vorbestimmt. Prädikative Modellierung wird erschwert durch einen prozeduralen Anteil des Konzeptes, ohne den Ein- und Ausgabeströme und Fenstertechnik nicht bereitgestellt werden könnten. Dieser Einsatz von Prädikaten mit Nebeneffekten (Bratko, 1987), (Clocksin/Mellish, 1987) ist ein notwendiger Kompromiss an die Rechnerarchitektur.