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ätsreduzierung 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 experimentierend forschenden
Arbeitens eignet sich gut für das prädikative Problemlösen.
Spracherweiterung
Indem die Anfänger die Objekte und deren
Eigenschaften aus der Aufgabenstellung herauslesen und in ihrer Muttersprache
aufschreiben, bilden sie neue Schlüsselwörter der Programmiersprache. Eine
Sprache für prädikatives Problemlösen ist Prolog. Sie besitzt deklarative und
prozedurale Bestandteile. Dieser Programmierung liegt die Prädikatenlogik l.
Stufe zugrunde. Die Resolution wird als Beweisverfahren bei der
Lösungsbestätigung angewendet, d. h. das Prolog-System geht wie ein
Theorembeweiser vor. Die Wissensbasis entspricht dem Programm (Fakten,
Regeln). Fragen wirken wie Eingabewerte, mit denen das Programm gestartet wird.
Die Antworten stellen die Ausgabewerte dar. Die fundamentale Kontrollstruktur
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 Suchalgorithmus 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 abgenommen. 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, komplizierte
Lösungsmechanismen auslösen kann, die er schrittweise zu erkunden und
anzuwenden lernt.
2. Die Algorithmenstruktur Zyklus und die
Datenstruktur Liste beruhen im prädikativen 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 Problemlö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 Verantwortung 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 Einführung in das Problemlösen mit Mitteln und
Methoden der Informatik zu wählen, und ihnen zugleich helfen, mit vertretbarem
Einarbeitungsaufwand zu Unterrichtserfolgen zu gelangen. Ergebnis der informatischen
Bildung könnte dann für immer mehr Schüler die Erkenntnis sein, dass zu jeder
Problemklasse das richtige programmiersprachliche Denkschemata auszuwählen
ist. Eine anspruchvolle Erweiterung des Algorithmenbegriffs kann die Anwendung
von Regeln darstellen, die eine Wissensbasis modifizieren, indem sie zur
Ausfuhrungszeit eines Programms vorbereitete 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, Kennenlernen
der Ableitung durch Mustergleichheit,
3.
neue Faktenbasis des 2. Beispiels entwerfen, Wiederholung des
Editierens und Speicherns, Anfragen mit Variablen (Name, Wert, Typ) - Variablenbindung
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 Realisierung 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,
Einführen der Datenstruktur Liste - Kopf und Restliste, Anwendung der Datenstruktur
Liste im 4. Beispiel
7. Analyse des 5. Beispiels - rekursive Datenstruktur, Beobachten des rekursiven Abbaus der Liste bis zur leeren Liste, Wiederholung des Suchprozesses 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 Wissensbasis aus Fakten und Regeln, Wiederholung des
Prozedurmodells (zu Färbungsproblem s. auch Kapitel 6.4),
9.
Ziel: Vorfahren-Relation in einen
Familienstammbaum einfügen, Wiederholung der rekursiven Arbeitsweise,
Programmierheuristik zur Reihenfolge 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 entwickeln,
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 Programm kennen
lernen und anwenden, das der Lehrer für sie vorbereitet hat. Die
Prolog-Arbeitsumgebung wird gestartet. Die Schüler finden eine Benutzungsoberflä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 Programm, 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 besteht, 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 Interpreter der
Prolog-Programme zur Verfügung. Es handelt sich um einen Algorithmus für
Tiefensuche, der umkehren kann, wenn er in eine Sackgasse geraten ist. Die
Umkehr wird mit einem Rückkehrverfahren, Backtracking, realisiert. Erfolglose
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 automatische
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 Erfahrungsbereich der Schüler ein. Regeln der Form
"wenn Bedingungen erfüllt, dann Handlungen ausführen" werden mit den
Schülern gemeinsam gebildet für die Freundinnenauswahl. 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 Programmierumgebung starten, das Programm
laden und die Regeln hinzufügen. Das Speichern eines Programms wird neu
eingeführt. Nach dem Aktivieren des Programms 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 Identitä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 entwickelt, 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 Drachenviereck). Ziel der
Modellierung ist eine Abbildung der Objekte mit ihren Relationen in einem
Informationssystem. Der Weltausschnitt wird durch den Bereich der konvexen
Vierecke begrenzt (Abb. 4.7). Im Beispiel "Vierecksarten" führt die
Beschreibung 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 auftreten. 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 ausgehend begründet. Dieses
problemorientierte Lernen ist charakteristisch für die informatische Bildung.
Wiederholung des Editierens und Speicherns: Die Schüler erstellen
dieses Programm (Faktenbasis) mit der Programmierumgebung selbständig. Mit
verschiedenen Anfragen erkunden sie die Programmausführung
(Schlussfolgerungsprozess) und die Variablenbindung. Sie nutzen die
Möglichkeit, alle Lösungen eines Problems 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 bekannten 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 Konsequenzen 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 Variablenbindungen nur vorübergehend erfolgt. Gerade die
Auflösung bestehender Bindungen und die Neubindung ermöglichen die alternativen
Lösungswege bei der Ausführung 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 Eigenschaft existiert. Eine solche Existenzanfrage
wird vom System nicht mit nur "ja" oder "nein"
beantwortet. Im Erfolgfall wird das erste konkrete Objekt, Atom genannt,
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 sondern alle. Durch die Unifikation besteht die
Möglichkeit, eine Anfrage durch Bindung der freien, noch keinem konkreten Objekt
zugeordneten Variablen in Übereinstimmung 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.
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 Abbruchbedingung 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 Regelverarbeitung 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 Modellierung gefunden werden.
Praktische Realisierung der rekursiven
Arbeitsweise: Die Schüler gehen zur praktischen Arbeit über. Sie laden,
modifizieren und speichern das 2. Programm selbständig. Das ist für sie eine
gute Wiederholung im Umgang mit der Programmierumgebung. 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 finden, 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" entsteht ein neues Ziel, wenn der unifizierte
Regelkopf durch den Regelkörper "ist_ein(parallelogramm,Art)."
ersetzt wird.
Die rekursive Arbeitsweise soll an dem einfachen
Beispiel "Computeraufbau" (vgl. Anhang B3) geübt werden. Der grobe
Computeraufbau liefert dafür die Beziehungen 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 erforderlich, um die Analogie zum 2. Programm zu erkennen. Wieder soll
eine Regel mehrfach aktiv werden, um Teile, die wiederum Teile enthalten,
richtig zu verbinden. 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 Erprobung 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 Unterrichtsstunden 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ösungen 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 Prozedurmodell
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 Objekt
"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 Algorithmenstrukturen bekannt sind, soll bei den
Schülern Verständnis für die Bedeutung der Datenstrukturen in der Informatik
geweckt werden. In der Prolog-Programmierumgebung steht mit der Datenstruktur
Liste ein anspruchsvolles Informatikkonzept 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
Demonstration 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 eingesetzt. 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öglichkeiten
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ückkehr (Redo) bedeutet, dass diese Prozedur durch tiefes
Backtracking von einer gescheiterten Prozedur aus erneut verwendet wird. Der
gesetzte Entscheidungspunkt 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 Klauseln innerhalb der gleichen Prozedur.
Komplexe Übungen: Im
Vergleich zum Ausgangsniveau wurde so viel neuer Stoff erarbeitet, dass Übung,
Anwendung und Kontrolle der Einzelheiten im Zusammenhang 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ärbungsproblem). Noch anspruchsvoller wird die Frage nach allen
möglichen Lösungen. 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 Ausgabewerte) 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 Programmiersprache
darzustellen ist. Dazu werden die Nachbarschaftsbeziehungen aufgezählt. Diese
Methode der Beschreibung des Suchraumes durch Aufzählung ist nur vertretbar,
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 keinem
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 gewü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 rekursiven Programmelemente bereits von den
Schülern gefunden werden.
Programmierheuristik zur Reihenfolge der Fakten
und Regeln: Die Schüler ergänzen 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 Lernerfolgskontrolle, die aus einem
praktischen und einem theoretischen Teil bestehen könnte. Der praktische Teil
ergibt sich aus der Vervollständigung des lückenhaften Programms. 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 berührt, das natürlich in
dieser kurzen Einführungsphase nicht zufriedenstellend bearbeitet werden kann.
Die Bibliotheksverwaltung, zum Beispiel der Schülerbibliothek, wird von den
Schülern als echtes Problem verstanden. Also greift der Lehrer exemplarisch
eine Teilaufgabe heraus, die mit den Möglichkeiten der Anfänger lösbar ist.
Wiederholung des Variablen- und Datenkonzepts: Die Zusammenstellung
geeigneter Fakten wie "buch", "leser" und
"ausleihe" bereitet den Schülern keine Schwierigkeiten. 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 Vorname 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 Modellierung
stark beeinflusst. Diese unmittelbare Verbindung zwischen Modell und System
wird in anderen programmiersprachlichen Denkschemata von der Beschreibungssprache
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.