FH Graubünden PH Graubünden

Algorithmisches Denken

Einleitung

Unter algorithmischem Denken werden Prozesse verstanden, die zum Ziel haben, Probleme strukturiert zu lösen. Im Mittelpunkt steht meist die Entwicklung eines Algorithmus, also einer Folge von Anweisungen, deren strikte Befolgung ein Problem (bzw. eine Instanz des Problems) löst. Während die Ausführung eines Algorithmus weder Kreativität noch Intellekt erfordert, stehen diese bei der Entwicklung eines Algorithmus im Vordergrund.

Wir stellen hier 27 Vorschläge für Unterrichtseinheiten vor, die verschiedene Aspekte des algorithmischen Denkens abdecken und in verschiedenen Fächern angewendet werden können. Im Zentrum steht dabei, einen Unterricht zu gestalten, der nachhaltige Problemlösekompetenzen vermittelt. Die Schülerinnen und Schüler sollen dazu befähigt werden, in Strukturen zu denken, Muster zu erkennen, zu analysieren und flexibel anzuwenden.

Algorithmen

Für den Begriff «Algorithmus» existieren viele äquivalente formale Definitionen. Diese sind erforderlich, um beispielsweise die Unlösbarkeit oder Komplexität eines Problems nachzuweisen. Soll jedoch die Lösbarkeit eines Problems gezeigt werden, so genügt die Angabe eines konkreten Algorithmus. Da im Projekt algorithmisches Denken das Entwickeln von Problemlösestrategien im Zentrum steht, reicht eine informelle Beschreibung des Begriffs somit aus.

Ein Algorithmus ist eine genau festgelegte Folge von Anweisungen, welche zur Lösung eines Problems (bzw. einer Instanz des Problems) führt. Diese Anweisungen müssen so formuliert sein, dass sie aus kleinen, einfachen, eindeutigen und präzisen Schritten bestehen.

Mit «einfach» meinen wir heutzutage in der Regel, dass wir die Schritte, und damit den gesamten Algorithmus, von einem Computer ausführen lassen können. Um es mit den Worten eines berühmten Informatikers zu sagen:

«Science is what we understand well enough to explain to a computer. Art is everything else we do.» – Donald Knuth

Um einen Algorithmus zu entwickeln, ist es notwendig, dass die zu lösende Problemstellung so formuliert ist, dass ein Lösungsalgorithmus überhaupt erstellt werden kann. Hierzu muss die Formulierung des Problems eindeutig sein und darf keinen Interpretationsspielraum zulassen; zum Beispiel lässt die Problemstellung «Finde die kürzeste Verbindung von Bern nach Basel» noch viele wesentliche Parameter wie das Fortbewegungsmittel oder die Ankunftszeit unspezifiziert.

Soll ein «echtes» Problem aus der Praxis so formuliert werden, dass es von einem Computer durch Ausführung eines Algorithmus gelöst werden kann, so muss das Problem auf wesentliche Parameter heruntergebrochen und so dargestellt werden, dass keine intellektuellen Fähigkeiten zur weiteren Verarbeitung notwendig sind. Eine für Menschen lesbare Karte des Schweizer Schienennetzes ist für uns vielleicht ausreichend, um einen Trip zu planen, enthält für den Computer aber erstens überflüssige und zweites unvollständige Informationen. Für ihn ist es irrelevant, ob sich auf der Strecke ein Tunnel befindet oder eine Kurve liegt, um eine geeignete Verbindung von A nach B zu berechnen. Beim algorithmischen Denken geht es auch zu einem wesentlichen Teil darum, die Fähigkeit zur sinnvollen Formulierung von Problemstellungen zu erlangen.

Algorithmen existieren überall um uns herum, nicht erst, seitdem die Informatik eine eigene wissenschaftliche Disziplin ist. Wir finden sie an offensichtlichen Stellen wie bei Lichtsignalanlagen, Waschmaschinen, Autos, Smartphones und zahlreichen weiteren technischen Einrichtungen. Menschen haben schon früh in ihrer Geschichte Algorithmen entwickelt, beispielsweise für das Zählen (Entwicklung unterschiedlicher Zahlsysteme), für die Darstellung von Daten oder bei der Entwicklung der Zeitmessung. So erstaunt es nicht, dass das Verstehen von Algorithmen, das Nachkonstruieren bestehender und Entwickeln neuer Algorithmen zentrale Aspekte des Mathematikunterrichts in der Volksschule sind. Ebenso existieren Algorithmen in der Natur (Bienentanz, Genetik, Evolution etc.), ganz ohne einen Computer in der Nähe. Solche Algorithmen haben häufig auch neuzeitliche Problemlösestrategien inspiriert.

In den Medien hat der Begriff oftmals eine negative Konnotation, da automatisierte Prozesse vielfach auf eine zweifelhafte Art und Weise verwendet werden. Obwohl eine kritische Haltung zur Omnipräsenz von Algorithmen in der Auswertung von personalisierten Daten sicherlich gerechtfertigt ist, sind Algorithmen grundsätzlich aber weder etwas Schlechtes noch eine neumodische Erscheinung.

Der Begriff «Algorithmus» geht auf keine Informatikerin und keinen Informatiker zurück, sondern auf den persischen Mathematiker Muhammad ibn Mūsā al-Khwārizmī, der im achten und neunten Jahrhundert lebte. Die Definition und das frühe Auftreten illustrieren, dass dieser Begriff unabhängig von dem des Computers ist. Ein Kochrezept oder eine Wegbeschreibung sind ebenfalls nichts anderes als Algorithmen, wenn sie präzise genug sind. Im Wesentlichen geht es darum, dass ein Algorithmus ohne Intellekt oder die Fähigkeit, improvisieren zu können, ausgeführt werden kann. Ob es am Ende ein Mensch oder ein Computer ist, der die Schritte strikt abarbeitet, ist unwesentlich.

Einige wichtige Punkte seien noch erwähnt:

Algorithmen sind also endliche Methoden, die möglicherweise unendlich viele Probleminstanzen lösen.

Algorithmisches Denken

Was versteht man nun unter algorithmischem Denken? Eine erste Antwort wäre, dass darin alles beinhaltet ist, was erforderlich ist, um ein Problem so zu formalisieren, dass es überhaupt automatisiert gelöst werden kann. Ausserdem zählen Kompetenzen dazu, die nötig sind, entsprechende Algorithmen zu entwerfen und zu bewerten. Dies führt idealerweise zu einem iterativen Prozess, in welchem der Algorithmus und womöglich auch die Formalisierung des Problems wiederholt evaluiert und verbessert werden.

Im Englischen wird oftmals der Begriff «computational thinking» gebraucht, der zuerst von MIT-Professor Seymour Papert, einem Schüler von Jean Piaget und Erfinder der Programmiersprache Logo, verwendet wurde. Wir benutzen ihn hier synonym mit algorithmischem Denken. Beim Gebrauch des Begriffs ist es wichtig, dass Papert von vorneherein gesagt hat, dass es ihm nicht darum geht, dass Menschen lernen, wie Computer zu werden:

«My central focus is not on the machine but on the mind.» – Seymour Papert

Popularisiert wurde der Begriff «computational thinking» insbesondere von Jeannette Wing, Professorin an der Columbia University, die – genau wie Papert vor ihr – den Menschen in den Vordergrund stellt und nicht den Computer:

«Computational thinking is a way humans solve problems; it is not trying to get humans to think like computers. Computers are dull and boring; humans are clever and imaginative. We humans make computers exciting.» – Jeannette Wing

Dies ist ebenfalls der Kern des algorithmischen Denkens, das in den hier vorgestellten Unterrichtseinheiten gefördert werden soll. Es geht darum, kreative Ideen zu haben, diese dann aber so zu formulieren, dass keine weitere Kreativität zu ihrer Ausführung nötig ist: der langweilige Teil kann an den Computer delegiert werden – nicht der spannende!

Eine genaue formale Definition ist (wie beim Algorithmus) nicht einfach zu geben; es gibt unter Expertinnen und Experten beispielsweise keine Einigkeit darüber, welche Aspekte genau zum algorithmischen Denken gehören. Für die hier präsentierten Unterrichtseinheiten verzichten wir deswegen auf sperrige Definitionen und fokussieren auf einige wesentliche Aspekte, die beim Vorgang des algorithmischen Denkens wichtig sind und in Teilen bereits besprochen wurden. Im einführenden Abschnitt wurde bereits hervorgehoben, dass die Schülerinnen und Schüler lernen sollen, Muster zu erkennen und diese in neuen Herausforderungen anzuwenden. Während das Erkennen von Mustern die Fähigkeit des Abstrahierens verlangt, braucht es zur Anwendung erkannter Muster die Fähigkeit des Generalisierens. Daher stehen diese beiden Aspekte am Anfang der folgenden Auflistung.

Abstraktion

Abstraktion steht für die selektive Konstruktion eines Begriffsinhalts aus Kontexten. Die Lernenden erkennen in konkreten Aufgabenstellungen Muster sowie Beziehungen zwischen diesen Mustern und entwickeln dadurch ein Verständnis für Strukturen. Der Prozess lässt sich an folgendem Beispiel illustrieren: Lisa soll möglichst viele verschiedene Tanzpaare aus ihrer 20-köpfigen Klasse bilden. Für jedes Paar wählt sie jeweils zwei Schülerinnen oder Schüler aus der Klasse aus. Sie erinnert sich, dass sie schon früher Paare von Personen bilden musste, als es um die Berechnung der Anzahl von Handschlägen ging, wenn sich sechs Freundinnen und Freunden begrüssen. Sie erkennt ein gemeinsames Muster, nämlich das Auswählen von zwei Elementen aus einer Menge von n Elementen. Im Verlaufe ihrer Schulzeit wird Lisa mit weiteren Aufgaben konfrontiert, in welchen sie dieses Muster wiedererkennt. So entdeckt sie bei der Berechnung von Wahrscheinlichkeiten beim Würfeln mit zwei Würfeln, dass ebenfalls Paare gebildet werden. Wie bei den Handschlägen unter sechs Freundinnen und Freunden müssen zwei Elemente aus sechs zur Verfügung stehenden Elementen (Augenzahlen auf Würfeln) ausgewählt werden. Trotz dieser Gemeinsamkeit des Musters erkennt sie jedoch auch einen Unterschied. Während sie beim Würfeln auch zweimal dasselbe Element wählen kann, ist dies weder bei den Tanzpaaren noch beim Händeschütteln möglich. Würfelt Lisa mit mehr als zwei Würfeln, so muss sie drei oder mehr Elemente aus den sechs Zahlen auswählen. Sie entwickelt allmählich ein Verständnis für die Struktur, k Elemente aus einer Menge von n Elementen auswählen, und für somit den Binomialkoeffizienten \(\binom{n}{k}\).

Im Rahmen der präsentierten Unterrichtseinheiten bedeutet Abstraktion in erster Linie, eine Problemstellung auf ihre wesentlichen Aspekte zu reduzieren, um ihnen innewohnende Muster und Beziehungen zu erkennen. Um erneut die eingangs erwähnte Problemstellung des Berechnens einer schnellsten Zugverbindung zu verwenden, wäre dies beispielsweise eine für Menschen lesbare Karte des Schweizer Schienennetzes von allen Details zu befreien, die für die Berechnung kürzester Wege nicht gebraucht werden. Es ist hierfür zum Beispiel unerheblich, wie der genaue Verlauf der Schienen zwischen zwei Orten A und B ist. Auch die zurückgelegten Höhenmeter interessieren nicht. Was hingegen wichtig ist, ist die durchschnittliche Fahrzeit zwischen A und B. Mit derartigen Überlegungen entsteht ein abstraktes Modell, das aber über alle Informationen verfügt, die notwendig sind, um die Aufgabe zu lösen, und alle hierfür nicht benötigten Informationen weglässt. \paragraph{Generalisierung (oder Verallgemeinerung)} Generalisieren steht für die konstruktive Erweiterung eines Begriffsinhalts durch neue Erfahrungen. Dieser Prozess führt zur Entwicklung eines vertieften Verständnisses der Strukturen und der Entfaltung von Fähigkeiten zur Anwendung des Begriffsinhalts in neuen Herausforderungen. In Lernprozessen ist es manchmal schwierig zu erkennen, wo das Abstrahieren in Generalisieren übergeht. Wenn im Beispiel zur Abstraktion (siehe oben) Lisa durch neue Aufgaben ein zunehmend besseres Verständnis der Struktur, k Elemente aus einer Menge von n Elementen auswählen, entwickelt, so muss sie bei jeder einzelnen Aufgabe durch Abstraktion innewohnende Muster, Gemeinsamkeiten und Unterschiede erkennen. Mit dem Verknüpfen der Muster untereinander, dem Entwickeln von Lösungswegen in neuen Aufgaben oder gar dem Entwerfen von Lösungsstrategien für eine ganze Klasse von Problemen erfolgt der Übergang zum Generalisieren. So lernt Lisa auch neue konkrete Herausforderungen zu bewältigen unabhängig von der Anzahl k der auszuwählenden Elemente und der Mächtigkeit n der Menge aller zur Verfügung stehenden Elemente. Gleichzeitig vertieft Lisa zunehmend ihr Verständnis dieser Struktur. Dabei kann sie auch unterscheiden, ob Elemente wiederholt gewählt werden können oder nicht. Im Laufe weiterer Lernprozesse wird sie ihr Konzept des Begriffs erweitern und neu organisieren, wenn es um die Bedeutsamkeit der Reihenfolge einer Auswahl geht (unstrukturierte Gruppe oder Rangliste, Würfeln mit unterscheidbaren oder nicht unterscheidbaren Würfeln).

Das Beispiel zeigt, dass zwar alles einzelne und unterschiedliche Probleminstanzen sind, sie gehören jedoch derselben Problemklasse an und haben verwandte Attribute. Auf der Basis eines vertieften Verständnisses der Struktur lassen sich allgemeine Lösungsstrategien für alle Probleminstanzen der zugrundeliegenden Problemklasse entwerfen.

Algorithmendesign

Dieser zentrale Aspekt algorithmischen Denkens stellt den Algorithmus selber ins Zentrum beziehungsweise dessen Entwurf. Hierbei soll die Lösung einer konkreten Probleminstanz nicht einfach selber erstellt werden, sondern es soll eine Problemlösemethode entwickelt werden, die möglichst eindeutig ist und keinen Interpretationsspielraum zulässt. Dies kann mit Hilfe einer Programmiersprache geschehen. Fluss- oder Zustandsdiagramme, eine genaue Beschreibung in natürlicher Sprache und viele weitere Darstellungsformen sind allerdings genauso geeignet.

Die Fokussierung auf den Algorithmus ist der wesentliche Punkt des algorithmischen Denkens; alle anderen Aspekte werden auch in anderen Zusammenhängen des wissenschaftlichen Arbeitens gefunden.

Präzise Kommunikation

Computer verstehen weder Kontext, noch Gestik oder Mimik, wenn wir mit ihnen kommunizieren. Ein ganz wesentlicher Punkt beim Entwurf eines Algorithmus ist also, eine Methode so zu kommunizieren, dass es keinen Intellekt benötigt, um sie auszuführen. Wir haben bereits Donald Knuth zitiert, doch könnten wir auch noch einen Schritt weiter gehen und einen berühmten Physiker anstatt eines Informatikers bemühen:

«If you can't explain it simply, you don't understand it well enough.»– Albert Einstein

Evaluation

Am wichtigsten ist bei der Evaluation eines Algorithmus zunächst einmal, ob er überhaupt korrekt arbeitet. Dies bedeutet, dass er für alle möglichen Probleminstanzen ein korrektes Resultat berechnet. Da dies potenziell unendlich viele sind, müssen wir hier allgemeine Betrachtungen anstellen, denn es kann nicht über jede Instanz einzeln argumentiert werden.

Für alle Probleme, auf die wir stossen werden, gibt es mehr als eine Lösung, oftmals gibt es sogar ebenfalls unendlich viele – aber nicht alle Lösungen sind gleich gut. Wobei wir hier natürlich die Frage stellen müssen, was wir im entsprechenden Kontext mit «gut» überhaupt meinen, das heisst, es wird eine Metrik benötigt, um die Qualität der Lösungen zu messen und zu beurteilen.

Häufig interessieren wir uns in erster Linie dafür, wie schnell die Lösung zu einer gegebenen Probleminstanz berechnet wird. Wir können aber auch fragen, wie viel Speicherplatz zur Lösungsberechnung verwendet wird oder wie übersichtlich sich der Algorithmus formulieren lässt.

Informationsdarstellung

Damit wir Informationen aufbewahren und teilen können, müssen wir sie zuerst in geeigneter Form darstellen. Zur Entwicklung von Lösungswegen können beispielsweise Skizzen, Tabellen, semantische Netze oder andere strukturierte Darstellungen hilfreich sein. Während wir häufig zu Stift und Papier greifen, kann ein Computer ausschliesslich mit digitalisierten Informationen umgehen. Das algorithmische Denken befasst sich mit den Vor- und Nachteilen der unterschiedlichen Darstellungsformen von Daten. Eine Darstellungsform kann zum Beispiel sehr speichereffizient sein, wohingegen eine andere den Vorteil hat, dass sie für den Menschen sehr leicht interpretierbar ist. Je nach Situation wählen wir die am besten passende Informationsdarstellung.

Ausserdem müssen wir bei der Informationsdarstellung darauf achten, dass wir die Probleminstanzen des gegebenen Problems so darstellen, dass sie mit einem Algorithmus bearbeitet werden können, wie eingangs bereits erwähnt. Dies bedeutet, dass die Informationen – beispielsweise das Schweizer Schienennetz – so dargestellt werden sollten, dass die Verarbeitung möglichst einfach geschehen kann. Es gibt eine grosse Anzahl von Möglichkeiten, ein Verkehrsnetz für den Computer darzustellen; welche «die Beste» ist, hängt auch hier davon ab, was unser Algorithmus in dem Schienennetz berechnen soll.

Iterative Verbesserung

Auf die Lösung einer Problemstellung folgt in der Regel eine Evaluation. Meist erreicht man eine Lösung in der gewünschten Qualität nicht auf den ersten Versuch. Dann entsteht – aufbauend auf den Erfahrungen der vorgehenden Versuche – ein sich wiederholender zyklischer Prozess, in dem die Verbesserung und die Evaluation mehrfach aufeinander folgen, bis die Evaluation befriedigende Ergebnisse produziert. Jeder Durchlauf in diesem Prozess wird eine Iteration genannt.

Im Unterricht kann dies geschehen, indem den Schülerinnen und Schülern neue Einsichten oder Blickwinkel vorgestellt werden oder durch konkrete Hinweise beispielsweise darauf, wo der Algorithmus «zu viel Arbeit ausführt». Dies führt zu einer Verbesserung und einer anschliessenden neuen Evaluation, womöglich gefolgt von weiteren Inputs der Lehrperson oder Mitschülerinnen und -schülern bei einer Gruppenarbeit.

Problemzerlegung

Ein gegebenes Problem in Teilprobleme zu zerlegen, ist eine sehr erfolgreiche Strategie bei der Erstellung von Algorithmen. In der Informatik gibt es verschiedenste Formalisierungen dieser Idee (zum Beispiel die dynamische Programmierung oder Divide-and-Conquer-Algorithmen). Wenn wir beispielsweise die Probleminstanz «Finde die schnellste Zugverbindung von Genf nach Basel über Bern, so dass man vor 17:00 ankommt» lösen möchten, könnte es eine gute Idee sein, zunächst nach den schnellsten Zugverbindungen von Genf nach Bern und Bern nach Zürich zu suchen. Wie gut sich Probleme durch eine Zerlegung in Teilprobleme lösen lassen, hängt auch hier wieder von der konkreten Problemstellung ab.

Die Teilprobleme erleichtern das Finden einer Lösung, da sie den Schülerinnen und Schülern erlauben, sich auf eine Teilmenge der Probleminstanzen zu konzentrieren und für diese Teilmenge nach Lösungen zu suchen. Diese Strategie bietet sich besonders bei komplexeren Problemen an, bei welchen es unmöglich ist, alle Details des gesamten Problems gleichzeitig anzugehen.

Aufbau und Ziel

Wie oben bereits beschrieben ist das algorithmische Denken nicht auf die Informatik beschränkt. Ganz im Gegenteil: Gerade in den anderen MINT-Fächern, aber auch weit darüber hinaus, finden wir viele der oben beschriebenen Aspekte bereits im Unterricht. In diesen Fällen geht es zu einem grossen Teil darum, sie sowohl den Lehrpersonen als auch den Schülerinnen und Schülern sichtbar bzw. bewusst zu machen.

In der Mathematik stehen Abstraktion, Generalisierung, präzise Kommunikation und Informationsdarstellung im Vordergrund; der Fokus auf die Entwicklung eines Algorithmus zur Lösung beliebiger Probleminstanzen des gegebenen Problems ist hier die Besonderheit der vorgeschlagenen Unterrichtseinheiten.

Das Ziel ist es, die fächerübergreifende Vermittlung nachhaltiger Problemlösekompetenzen zu unterstützen. Es sei noch einmal betont, dass es hierbei nicht darum geht «wie ein Computer zu denken» oder die Schülerinnen und Schüler gar «zu Computern zu machen». Das Gegenteil ist der Fall: Die Kreativität soll gefördert werden; es besteht eine klare Trennung zwischen der intellektuell stimulierenden Arbeit in der Klasse und mechanischer Arbeit, die an den Computer delegiert wird.

Die folgenden Unterrichtseinheiten decken jeweils eine Auswahl der oben beschriebenen Aspekte des algorithmischen Denkens ab, welche jeweils am Anfang aufgelistet sind. Die einzelnen Bausteine richten sich an die Lehrpersonen. Es werden Informationen gegeben, in welchen Fachbereichen beziehungsweise Modulen sie zum Einsatz kommen können und wie viel Zeit für eine Umsetzung im Unterricht eingeplant werden sollte. Es folgen exemplarische Unterrichtseinheiten mit Beispielaufgaben (und deren Lösungen) und didaktischen Kommentaren, die es der Lehrperson ermöglichen, einen ansprechenden Unterricht zu gestalten, der nachhaltige Problemlösekompetenzen vermittelt. In einigen Bausteinen müssen die Aufgaben der Klassenstufe entsprechend ausgewählt und/oder angepasst werden, wobei sich manche Aufgaben für den Unterricht auf Sekundarstufe I eignen. Eine stufengerechte Umsetzung wird in den betreffenden Bausteinen durch didaktische Hilfestellungen und Hinweise vereinfacht und die notwendige Zeitdauer entsprechend variabel angegeben (Mindest- bis Maximalzeit).

Für einzelne Bausteine wird Begleitmaterial online zur Verfügung gestellt. In erster Linie handelt es sich dabei um die Programmcodes, so dass diese nicht abgetippt werden müssen.

Quellenangaben und Weiterführende Literatur

  1. Donald E. Knuth: Vorwort zu M. Petkovsek, H. S. Wilf und Doron Zeilberger: A=B. A. K. Peters/CRC Press, 1996.
  2. Seymour Papert: Mindstorms: Children, computers, and powerful ideas. Basic Books, Inc., 1980.
  3. Seymour Papert: An exploration in the space of mathematics educations. International Journal of Computers for Mathematical Learning. 1, 1996.
  4. Jeanette M. Wing: Computational thinking. Communications of the ACM. 49(3):33, 2006.

Zurück PDF