Algorithmisches Problemlösen

Vorbemerkung

Der Lehrplan für das Wahl(pflicht)fach setzt folgende Rahmenbedingungen: In allen Bereichen der Informatik spielen Algorithmen eine zentrale Rolle. Jede automatisierte Verarbeitung von Daten mithilfe des Computers erfolgt auf der Grundlage präziser Verarbeitungsvorschriften bzw. Algorithmen. Ziel des Informatikunterrichts ist es, ein Grundverständnis für diese Zusammenhänge zu entwickeln. Eine Auseinandersetzung mit Algorithmen darf nicht als „Trockenkurs“ gestaltet werden. Der Unterricht lebt davon, interessante und altersgemäße Probleme bis hin zu einer lauffähigen Lösung zu bearbeiten. ...

Dieser Vorschlag nutzt einen eher spielerischen Zugung zum algorithmischen Problemlösen mit Hilfe der Programmiersprache und -umgebung Scratch und orientiert sich an den Ausführungen auf den Webseiten inf-schule.

Scratch wird von einem Forschungsteam der Lifelong Kindergarten Group am MIT Media Lab mit den Ziel entwickelt, Kindern und Jugendlichen einen einfachen und motivierenden Zugang zu Konzepten der Programmierung zu verschaffen. Scratch erlaubt es, interaktiv und ohne Erlernen programmiersprachlicher Details vielfältige algorithmische Problemlösungen zu entwickeln.

Im Anschluss an das spielerische Erlernen von Konzepten mit Scratch wird der allen Problemlösungen zu Grunde liegende Algorithmusbegriff erarbeitet.

Die einfache Bedienbarkeit von Scratch ermöglicht einen experimentellen und spielerischen Zugang. Mit wenigen Hinweisen können Schülerinnen und Schüler schnell erste Programme entwickeln, mit deren Hilfe vorgegebene (oder selbst erstellte) Figuren animiert werden können, auf der sogenannten Bühne bestimmte Aktionen durchzuführen. Scratch unterstützt das Erstellen von Programmen, indem es vorgefertigte Programmierkacheln zur Verfügung stellt, die wie bei einem Puzzle nur richtig aneinandergefügt werden müssen.

Nach einem ersten Austesten der Programmierumgebung wird die Vorgehensweise reflektiert und mit neuen Begriffen beschrieben.

Figuren - das sind die Bausteine einer Scratch-Welt - werden als Objekte mit spezifischen Eigenschaften dargestellt.

Mit Hilfe von Anweisungen und Programmen lassen sich die Aktionen der Figuren festlegen. Ausgelöst werden diese Aktionen durch Ereignisse.

Zunächst wird ein Problem gelöst, bei dem Aktionen nur unter einer bestimmten Bedingung durchgeführt werden. Beispiel: Eine Figur soll sich nur dann weiterbewegen, wenn sie sich nicht am Rand der Bühne befindet. Dadurch, dass Scratch passende Programmierkacheln zur Lösung des Problems vorsieht, können Schülerinnen und Schülern selbstständig (experimentierend) beim Problemlösen vorgehen.

In einer nachfolgenden Besprechung wird die Kontrollstruktur Fallunterscheidung eingeführt. Der Aufbau einer (einseitigen / zweiseitigen) Fallunterscheidung ist direkt aus den von Scratch zur Verfügung gestellten Programmierkacheln ersichtlich. Dieser Aufbau wird programmiersprachenneutral mit Hilfe entsprechender Struktogramme beschrieben. Die Ausführung von Fallunterscheidungen wird (einmalig) mit einem Flussdiagramm verdeutlicht. Flussdiagramme dienen hier also nur dazu, die Semantik der Fallunterscheidungsanweisung zu beschreiben.

Zunächst wird ein konkretes Problem gelöst, bei dem Aktionen wiederholt durchgeführt werden müssen. Beispiel: Eine Figur bewegt sich solange weiter, bis sie den Rand der Bühne erreicht. Auch hier sollen die Schülerinnen und Schüler selbstständig die passende Programmierkachel zur Lösung des Problems aufsuchen und erkunden.

In einer nachfolgenden Besprechung wird die Kontrollstruktur Wiederholung dann intensiv durchdrungen.

Zunächst wird der Aufbau einer Wiederholung mit fester Anzahl sowie einer Wiederholung mit Abbruchbedingung geklärt und jeweils mit einem Struktogramm beschrieben.

Der von Scratch zur Verfügung gestellte Anweisungstyp wiederhole bis ... wird intensiv besprochen. Mit Hilfe eines Flussdiagramms wird die Abarbeitung dieses Schleifentyps transparent gemacht werden. Dies ist insofern von Bedeutung, da es in anderen Programmierumgebungen ähnliche Anweisungskonstrukte gibt, die jedoch einer etwas anderen Abarbeitungslogik folgen.

Die Verwendung der Kontrollstruktur Wiederholung wird angemessen geübt. Dabei wird auf auch das Phänomen der Endlosschleife angesprochen.

Die Ablaufmodellierung mit Kontrollstrukturen wird vertiefend geübt. Es werden Probleme aus verschiedenen Kontexten bearbeitet, zu deren Lösung die verschiedenen Kontrollstrukturen in überschaubarer Weise verschachtelt werden müssen.

Einen gesonderten Schwerpunkt bilden zusammengesetzte Bedingungen. Die logischen Operatoren nicht, und, oder werden mitsamt ihrer Wertetabellen eingeführt und zum Aufbau komplexerer Bedingungen genutzt.

Über Probleme, zu deren Lösung man sich etwas merken muss oder man zählen können muss, gelangt man zum Variablenkonzept. Scratch macht das Umgehen mit Variablen und Zuweisungen recht transparent, indem es den Wert einer Variablen (auf Wunsch) auf der Bühne anzeigt.

Bei der Besprechung und Erkärung des Variablenkonzepts werden Variablen als Namen für Datenobjekte (wie Zahlen, ...) eingeführt. Zuweisungen werden als spezielle Anweisungen eingeführt, mit deren Hilfe man Variablen neue Datenobjekte zuweisen kann.

Diese Sichtweise erlaubt es, in einer späteren Phase auch Situationen zu erfassen, bei denen Variablen veränderbare Datenobjekte (wie Listen) referenzieren, deren interne Struktur mit Zuweisungen verändert werden können.

In einer Übungs- und Vertiefungsphase wird der sichere Umgang mit Variablen angestrebt. Mit Hilfe von Trace-Tabellen werden die Veränderungen von Variablenwerten bei (sinnvollen) Zuweisungssequenzen transparent gemacht. Typische Zuweisungsmuster (wie sie beim Vertauschen von Werten oder beim Zählen benutzt werden) werden herausgestellt. Auch komplexere Terme innerhalb von Zuweisungen werden beim Problemlösen benutzt. Zudem wird der Umgang mit Variablen und mit Kontrollstrukturen verknüpft.

Bemerkung

Mit Scratch lassen sich auch weitere Fachkonzepte wie das EVA-Prinzip oder das Prozedurkonzept erarbeiten. Es hängt von der Lerngruppe ab, inwieweit die Motivation anhält, Scratch weiterhin als Problemlösewerkzeug zu erkunden.

In der hier skizzierten Unterrichtsreihe soll jetzt ein Übergang zu mehr allgemeinen Fragestellung folgen, bei denen der Algorithmusbegriff im Zentrum der Betrachtungen steht. Für weiterführende Informationen siehe inf-schule.

Der Übergang vom Problemlösen mit Scratch zum etwas allgemeineren algorithmischen Problemlösen knüpft an eine Scratch-Lösung zu einem vorgegebenen Problem an. Die Idee des Übergangs besteht darin, die Scratch-Lösung auf ihren algorithmischen Kern zu reduzieren.

Beispiel: Zunächst wird ein Scratch-Programm zum Spiel Zahlenraten entwickelt, bei dem binäres Raten als Strategie benutzt wird. Der Ratealgorithmus wird jetzt extrahiert und programmiersprachenunabhängig formuliert.

Beispiel: Zunächst werden Scratch-Programme zur Simulation von Zufallsexperimenten entwickelt. Anschließend wird der Simulationsalgorithmus programmiersprachenunabhängig beschrieben.

Ausgehend vom Beispiel-Algorithmus werden die charakteristischen Eigenschaften dieser Verfahrensbeschreibung herausgearbeitet: Ein Algorithmus ist eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie (zumindest im Prinzip) auch von einer Maschine abgearbeitet werden kann. Zudem werden Kriterien wie Eindeutigkeit, Ausführbarkeit, Allgemeinheit und Endlichkeit besprochen, die Algorithmen (in der Regel) erfüllen. Hierbei werden dann auch Verfahrensbeschreibungen aus dem Alltag wie Kochrezepte oder Bauanleitungen eingeordnet, die algorithmische Züge aufweisen.

Anhand von Beispielen wird die Bedeutung von Algorithmen für uns Menschen und unsere Gesellschaft aufgezeigt.

Beispiel: Automatisierung von Vorgängen mit Hilfe von Robotern und deren gesellschaftliche Folgen

Beispiel: Simulation komplexer Vorgängen als Grundlage für Prognosen wie im Fall der globalen Klimaveränderungen

Anhand klassischer Algorithmen wird das Verständis für das Fachkonzept Algorithmus vertieft.

Als Beispiele eignen sich Algorithmen aus der Mathematik wie der Algorithmus zur ägyptischen Multiplikation, der euklidischer Algorithmus zur Bestimmung des ggT, ein Algorithmus zur Primfaktorzerlegung, .... Es können aber auch Mathematik-fernere Algorithmen betrachtet werden wie Suchalgorithmen. Die Auswahl richtet sich auch nach den Implementierungsmöglichkeiten. In der hier skizzierten Unterrichtsreihe werden vorerst nur solche Algorithmen betrachtet, die in Scratch implementiert werden können. Weitere Algorithmen werden behandelt, wenn eine Umsetzung in Python möglich ist.

Wesentlich in dieser Phase ist es, die Bausteine von Algorithmen (Kontrollstrukturen Sequenzbildung, Fallunterscheidung und Wiederholung sowie Elementaranweisungen) herauszustellen und Verfahren zur Darstellung von Algorithmen einzuüben.