FH Graubünden PH Graubünden

Der Schulweg

Algorithmisches Denken in der Primarschule

Zusammenfassung

Graphen und Wege sind nützliche Konzepte der Informatik, die uns alle mehrmals am Tag beschäftigen. Die Auseinandersetzung mit Fragen wie den folgenden geschieht bei vielen allerdings unbewusst und die angewandten Algorithmen sind uns oft nicht bewusst. Das Thema bietet interessante Fragen wie beispielsweise:

Mehrere interessante Algorithmen können in diesem Gebiet erforscht werden. Dazu verwenden wir das Beispiel einer fiktiven Stadt «Biberhausen», in welcher sich zwei Biber aufhalten. Die Biber sind neu in der Stadt und kennen sich darin noch nicht aus. Aus ihrer lokalen Sicht ist es schwierig, das unbekannte Wegsysteme systematisch zu erkunden. Die Leserin/der Lesers hat eine globale Sicht auf die Stadt und kann so bei der Planung einer Reise und der Einhaltung von Restriktionen helfen. Die Leserinnen und Leser erkunden das Konzept der Graphen und Wege und machen interessante Erkenntnisse, die sich auch auf ihren eigenen Alltag übertragen lassen.

Beispielsequenz

In dieser Unterrichtseinheit befassen wir uns mit Navigationsaufgaben durch die fiktive Stadt «Biberhausen». Zwei junge Biber sind frisch in die Stadt gezogen und brauchen nun bei der Planung ihres neuen Schulwegs deine Hilfe. Die Stadt hat viele Plätze, die die Möglichkeit bieten, um einen Ausflug zu machen auf dem Weg von der Schule nach Hause...

Biberhausen

Die Biber-Brüder Bruno und Beni sind neu nach Biberhausen gezogen, wo es nun viele interessante Plätze zu entdecken gibt: Schule, Zirkus, Pool, Bonbonladen, Getränkeautomat, Feuerwehr und sogar ein Spielplatz mit grosser Rutsche. Auf dem Weg zurück von der Schule sehen sie verschiedene Plätze der Stadt. Es gibt etliche verschiedene Möglichkeiten, wie sie von der Schule nach Hause gehen können... .biberhausen.png.

Aufgabe 1

Finden Sie einen Weg, um Bruno und Beni von der Schule wieder zurück nach Hause zu führen. Beschreiben Sie ihnen den Weg in Worten, indem Sie folgenden Satz vervollständigen.

Wenn du aus der Schule trittst ...

Aufgabe 2

Biber mögen es nicht, lange Texte zu lesen. Das ist mühsam. Deshalb fragt Bruno nach einer kürzeren Beschreibung. Finden Sie eine Möglichkeit, den Heimweg mit möglichst wenigen Worten zu beschreiben. Wie viele Worte braucht es mindestens?

Graphen und Wege

Die Informatik bietet eine nützliche Darstellungsform, die es uns, erlaubt Situationen wie diese einfach abzubilden. Die Darstellungsform nennt man einen Graphen. Dieser stellt die Beziehung zwischen Objekten abstrakt dar mittels Linien (sogenannten Kanten) und Kreisen (sogenannten Knoten).

Die beiden Konzepte werden in unserem Beispiel wie folgt verwendet:

Biberhausen könnte also auch wie folgt dargestellt werden: .g1.png. Ein weiteres Konzept der Informatik erlaubt es, eine Reise als Abfolge von Knoten im Graphen darzustellen. Dies nennt man einen Weg. .g2.png. Der markierte Weg von der Schule nach Hause kann als Sequenz der besuchten Knoten angegeben werden, wie beispielsweise hier:

Schule – Pool – Feuerwehr – Haus

Wegbeschreibungen

Um in einer Stadt von einem Ort zu einem anderen zu gelangen, benutzt man einen Weg. Dieser besteht aus einer Folge von Orten, die man unterwegs besucht. Die Orte werden angegeben in derselben Reihenfolge, wie man sie unterwegs sieht und müssen jeweils durch eine Strasse verbunden sein. Den Weg kann man als Folge von Sätzen, Worten oder auch Bildern darstellen.

Aufgabe 3

Finden Sie einen Weg von der Schule nach Hause, der es den Biber-Brüdern erlaubt, unterwegs ...

  1. die Giraffen im Zirkus füttern.
  2. ein Bonbon kaufen.
  3. die Rutsche benutzen.

Mögliche und unmögliche Wege

Fies! Bruno will seinem kleinen Bruder einen Streich spielen. Bruno versucht Beni dazu zu bringen, sich die Schuhe dreckig zu machen, indem er die Strasse verlässt. Er zeichnet fünf Wegbeschreibungen, wovon einige dazu führen, dass Beni die Strasse verlässt - dies ist nicht erlaubt.

Beispiel: Von der Schule darf man direkt zum Pool laufen, denn diese sind über eine Strasse miteinander verbunden. Von der Schule darf man hingegen nicht direkt zum Getränkeautomaten gehen, denn die beiden Orte sind nicht durch eine Strasse verbunden. .biberhausen.png. Im folgenden Bild sind zwei Wege gezeichnet. Der linke Weg ist unzulässig, denn zwischen der Schule und dem Getränkeautomat gibt es keine direkte Strasse. Der Weg rechts hingegen ist zulässig, denn alle zwei Orte entlang des Wegs sind jeweils durch eine Strasse miteinander verbunden. .insGruene.png.

Aufgabe 4

Welche dieser fünf Wege bringen Beni von der Schule nach Hause, ohne dabei das Strassennetz zu verlassen? .insGrueneFragen.png.

Aufgabe 5

Gestern haben Bruno und Beni nach der Schule noch lange auf der Rutsche gespielt. Als sie nach Hause kamen, war es schon dunkel und Mama Biber war sehr besorgt. Deshalb hat sie den Biber-Jungs gesagt, sie sollen heute ohne Umweg nach Hause kommen. Sie zählen, an wie vielen Orten der Schulweg sie vorbeiführt. Jeder Weg, der mit Schule und Zuhause mehr als vier Orte zählt, ist zu lang. Achtung: Jeder Ort, der doppelt besucht wird, wird auch doppelt gezählt.

  1. Welche der folgenden Wege zählen gemäss Mama Bibers Definition als Umwege? .umwege.png.
  2. Finden Sie alle Wege von der Schule nach Hause, die keine Umwege sind.

Aufgabe 6

Gibt es einen Heimweg, der weniger als vier Orte besucht? Falls ja, nennen Sie den Weg. Falls nein, begründen Sie, weshalb es keinen solchen Weg gibt und erklären Sie wie Sie vorgegangen sind.

Aufgabe 7

Gibt es einen Weg von der Schule nach Hause, der keine Strasse zweimal besucht und die Biber-Brüder an ...

  1. sechs Orten vorbeiführt?
  2. sieben Orten vorbeiführt?
  3. acht Orten vorbeiführt?
  4. neun Orten vorbeiführt?
  5. zehn Orten vorbeiführt?

Finden Sie alle Wege einer bestimmten Länge.

Achtung: Wenn Orte in einem Weg zweimal besucht werden, so zählen sie auch doppelt.

Aufgabe 8

Ändern sich Ihre Lösungen, wenn man es erlaubt, dass Strassen doppelt besucht werden dürfen, allerdings keine Orte doppelt besucht werden dürfen?

Aufgabe 9

Angenommen, es dürfen sowohl alle Strassen wie auch alle Orte mehrmals besucht werden. Gibt es unter diesen Umständen einen längsten Schulweg? Falls ja, wie viele Orte werden auf diesem Weg besucht? Falls nein, wieso gibt es keinen längsten Schulweg?

Aufgabe 10

Ob Gummibiber, Schoklade, Cola oder Kaugummi – Bruno liebt sie alle! Deshalb hat er in den letzten Tagen auf dem Rückweg von der Schule heimlich einen Abstecher beim Bonbonladen und dem Getränkeautomaten gemacht. Auf die Frage, wie er nach Hause gekommen sei, sagt Bruno er sei von der Schule direkt nach Hause gekommen, via Zirkus und Feuerwehr. Wie viel länger ist Brunos Umweg als der kürzere Weg ohne Bonbonladen und Getränkeautomaten?

Aufgabe 11

Blöd gelaufen! Bruno trifft soeben von seinem süssen Ausflug wieder beim Zirkus ein – ausgerüstet mit Lollipop und Limonade. Doch heute übersieht er einen grossen Stein, der mitten auf dem Weg liegt. Bruno stolpert. Dabei schüttet er die ganze Limonade aus und auch der Lolli fliegt in hohem Bogen auf den Misthaufen hinter dem Zirkus. Au weia!

Bruno überlegt, ob er nochmals zurück gehen soll, um einen neuen Lolli und eine neue Limonade zu kaufen. Wie viel länger wird Brunos Schulweg, wenn er jetzt noch eine zweite Schleife zum Bonbonladen und dem Getränkeautomaten macht?

Aufgabe 12

Bruno fragt sich, wie lang sein Schulweg wohl insgesamt wird, wenn er die Schleife via Bonbonladen und Getränkeautomat 0, 1, 2, 3 oder gar 4 Mal am gleichen Tag machen würde.

  1. Erstellen Sie eine Tabelle, in der Sie die Anzahl der Extrarunden und die daraus resultierende Länge des Schulwegs eintragen.
  2. Gelingt es Ihnen, eine allgemeine Aussage aus den beobachteten Werten abzuleiten? Berechnen Sie damit wie lang der Schulweg wäre, wenn Beni 99-mal die Extra-Runde via Getränkeautomat und Bonbonladen machen würde.

Aufgabe 13

Süsses und Klebriges sind nicht Benis Ding. Doch auch er macht manchmal heimliche Umwege. Können Sie herausfinden, welchen Teil seines Heimwegs er verheimlicht? .umweg1.png.

Aufgabe 14

Heute hat Beni seinen heimlichen Umweg gleich zweimal nacheinander gemacht. Welchen der folgenden Wege hat Beni genommen? .umweg2.png.

Lösungen zu den Aufgaben

Aufgabe 1

Wir beschreiben einen von vielen Wegen durch die Stadt. Dabei verwenden wir Prosa und versuchen den Weg so detailliert wie möglich zu beschreiben. Achtung: Aufgrund eines Perspektivenwechsels können wir Begriffe wie «rechts» und «links» nur aus der Perspektive der Biber verwenden. Deren Perspektive stimmt nicht zwingend mit der globalen Sicht des Lesers/der Leserin überein. Eine mögliche Lösung ist folgende:

Wenn du aus der Schultür trittst, gehe der Strasse nach links entlang. Diese Strasse führt dich zum Schwimmbad. An der Kreuzung beim Schwimmbad wählst du die mittlere Strasse Richtung Feuerwehr aus. Wenn Du die Feuerwehr erreichst, musst du links abbiegen und kommst nach Hause.

Aufgabe 2

Anstatt lange Texte zu schreiben, nennen wir nur noch diejenigen Plätze, die Bruno und Beni unterwegs sehen. Dies erlaubt es uns, eine Wegbeschreibung zu verfassen, die nur so viele Wörter umfasst, wie der Weg lang ist. Das heisst: Je länger der Weg, umso länger die Beschreibung. Ein Beispiel einer solchen gekürzten Wegbeschreibung ist die folgende.

Schule – Schwimmbad – Rutsche – Feuerwehr – Bibers Haus

Aufgabe 3

Es existieren viele unterschiedliche Lösungswege. Wir führen hier jeweils eine mögliche Lösung auf.

  1. Schule – Zirkus – Feuerwehr – Haus
  2. Schule – Zirkus – Bonbonladen – Zirkus – Feuerwehr – Haus
  3. Schule – Zirkus – Feuerwehr – Rutsche – Feuerwehr – Haus

Aufgabe 4

Zwei Wege sind unzulässig: Der vierte Weg verlangt, dass Beni vom Schwimmbad zum Getränkeautomat läuft, was nicht durch eine direkte Strasse möglich ist. Der fünfte Weg enthält zwei Fehler: Einerseits ist es nicht möglich, vom Schwimmbad direkt zum Zirkus zu gehen, andererseits ist das Haus der Biber auch nicht auf direktem Weg zugänglich vom Spielplatz. Die anderen drei Wege sind alle zulässig: .insGrueneSolutions.png.

Aufgabe 5

  1. Nur der erste Weg zählt weniger als vier Orte und ist somit kein Umweg.
  2. Es gibt nur zwei mögliche Wege, die vier oder weniger Orte besuchen und demzufolge keine Umwege sind:

    Schule – Schwimmbad – Feuerwehr – Haus

    und

    Schule – Zirkus – Feuerwehr – Haus

Aufgabe 6

Nein, es gibt keinen Weg von der Schule nach Hause der weniger als vier Orte besucht. Dies lässt sich experimentell bestimmen. Wir listen alle Wege der Länge 3 auf, die in der Schule beginnen:

  1. Schule – Zirkus – Feuerwehr
  2. Schule – Zirkus – Bonbonladen
  3. Schule – Zirkus – Getränkeautomat
  4. Schule – Zirkus – Schule
  5. Schule – Pool – Rutsche
  6. Schule – Pool – Feuerwehr
  7. Schule – Pool – Schule

Allgemein beobachten wir, dass alle Wege zunächst mit der Strasse von der Schule zum Zirkus oder mit einer Strasse von der Schule zum Pool beginnen. Da allerdings weder der Zirkus noch der Pool direkt mit dem Heim der Biber verbunden ist, benötigt jeder Heimweg mindestens vier Zwischestopps.

Aufgabe 7

  1. Nein, es gibt keinen Weg der Länge 6, welcher keine Strasse doppelt besucht.
  2. Ja, es gibt mehrere solche Wege:

    Schule – Zirkus – Bonbonladen – Getränkeautomat – Zirkus – Feuerwehr – Haus
    Schule – Zirkus – Getränkeautomat – Bonbonladen – Zirkus – Feuerwehr – Haus
    Schule – Zirkus – Feuerwehr – Pool – Rutsche – Feuerwehr – Haus
    Schule – Zirkus – Feuerwehr – Rutsche – Pool – Feuerwehr – Haus

  3. Nein, es gibt keinen Weg der Länge 8, welcher keine Strasse doppelt besucht.
  4. Nein, es gibt keinen Weg der Länge 9, welcher keine Strasse doppelt besucht.
  5. Ja, es gibt mehrere solche Wege:

    Schule – Zirkus – Bonbonladen – Getränkeautomat – Zirkus – Feuerwehr – Pool – Rutsche – Feuerwehr – Haus
    Schule – Zirkus – Getränkeautomat – Bonbonladen – Zirkus – Feuerwehr – Pool – Rutsche – Feuerwehr – Haus
    Schule – Zirkus – Bonbonladen – Getränkeautomat – Zirkus – Feuerwehr – Rutsche – Pool – Feuerwehr – Haus
    Schule – Zirkus – Getränkeautomat – Bonbonladen – Zirkus – Feuerwehr – Rutsche – Pool – Feuerwehr – Haus

Aufgabe 8

Ja, diese Einschränkung führt zu komplett anderen Resultaten. Keine unserer Lösungen aus Aufgabe 7 wäre weiterhin gültig, wenn man es verbietet, dass gewisse Orte doppelt besucht werden. Grundsätzlich gilt dann, dass beispielsweise die Schleife zwischen dem Zirkus, dem Getränkeautomaten und dem Bonbonladen nicht mehr benutzt werden können, da es keine Möglichkeit gibt, ohne Zirkus wieder aus der Schleife heraus zu kommen.

Aufgabe 9

Nein, es gibt keinen längsten Schulweg, weil man Schleifen bilden kann. Die Biber könnten also endlos zwischen dem Zirkus, dem Getränkeautomaten und dem Bonbonladen im Kreis laufen und so an immer mehr Orten vorbeikommen. Wenn wir zum Beispiel einen vermeintlich längsten Schulweg gefunden haben, der die Schleife zwischen dem Zirkus, dem Getränkeautomaten und dem Bonbonladen 4-mal enthält, so können wir sofort sehen, dass es in Wahrheit nicht der längste Weg sein kann, da wir auch einen Weg finden können, in welchem die Schleife 5-mal begangen wird. Der neue Weg kann aber auch nicht der längste Weg sein, da es einen noch längeren Weg gibt, in welchem die Schleife 6-mal begangen wird usw.

Aufgabe 10

3 Stationen länger (der Zirkus kommt zweimal vor).

Aufgabe 11

Insgesamt wird der Weg dann 6 Stationen länger sein, als bei einer Route ganz ohne Abstecher und 3 Stationen länger im Vergleich zur Lösung von Aufgabe 12.

Aufgabe 12

  1. Wir erhalten folgende Tabelle.

    Anzahl Extrarunden 0 1 2 3 4
    Länge des Schulwegs 4 7 10 13 16

  2. Die allgemeine Lösung, in welcher die Länge des Schulwegs für i Extra-Runden berechnet wird, lautet: \[ \text{distanz}(i) = i · 3 + 4 \] Wenn wir berechnen möchten, wie lang der Schulweg mit 99 Extra-Runden ist, so setzen wir den Wert i = 99 ein und berechnen, was die Formel ergibt: \[ \text{distanz}(99) = 99 · 3 + 4 = 297 + 4 = 301 \]

Aufgabe 13

Beni macht gelegentlich eine Extra-Runde via Rutsche, Schwimmbad und Feuerwehr.

Aufgabe 14

Beni hat den mittleren Weg genommen. Aus Aufgabe 13 wissen wir, dass Benis Umweg darin besteht, von der Feuerwehr zur Rutsche zum Pool zu gehen. Unter all den Wegen, die zur Auswahl stehen, macht nur der mittlere Weg diesen Teil zweimal.

Didaktischer Kommentar

Graphen sind nützliche Werkzeuge, um Zusammenhänge zwischen Objekten auf abstrakte Art darzustellen. Der Anwendungsbereich dieser Konzepte geht weit über die hier erforschte Navigation zwischen verschiedenen Orten hinaus. So können Graphen beispielsweise auch in der Ahnenforschung, der Zahlentheorie, der Landkartenfärbung, in Suchmaschinen wie auch beim Auffinden von Schwachstellen in Rohrsystemen eingesetzt werden.

In dieser Unterrichtseinheit wurde eine Bandbreite verschiedener Aspekte bearbeitet. Themen wie beispielsweise kürzeste Wege, gleich lange Wege, Schleifen so wie auch das blosse Verfolgen und Ablaufen von vorgegebenen Wegen geübt. Dies erlaubt es uns, verschiedene Bezugspunkte des algorithmischen Denkens gezielt zu fördern.

Diese Unterrichtseinheit enthält die folgenden Aspekte des algorithmischen Denkens.

Abbildungsverzeichnis

Sämtliche Bilder wurden von Vaidotas Kincius angefertig und wurden uns exklusiv zur Verfügung gestellt für diese Unterrichtseinheit.

Zurück PDF Übungen als PDF