Die Reihenfolge von Zahlen in einem bestimmten Zahlenbereich aufzeigen.
Mathematik: Zahlenverständnis
Erklären, wie der parallele Algorithmus eines Sortiernetzwerks funktioniert.
Informatisches Denken: Algorithmisches Denken
Objekte von der kleinsten bis zur größten Größe ordnen.
Mathematik: Zahlenverständnis
Schlüsselfragen
Was sind Beispiele für Aufgaben, die schneller abgeschlossen werden, wenn mehr Personen dabei mitwirken? Was sind Beispiele für Aufgaben, die nicht schneller abgeschlossen werden, wenn mehr Personen dabei mitwirken?
Mögliche Antworten wären beispielsweise:
Hier kommen eventuell Aufgaben wie das Aufräumen des Klassenzimmers, das Einsammeln von Müll oder das Ordnen von Büchern in der Bibliothek als solche auf, die von mehreren Helfern profitieren. Zu den Dingen, die nicht schneller gehen, gehört beispielsweise das Abgeben einer Mitteilung beim Sekretariat (wenn zehn Personen die Mitteilung abliefern, kommt sie nicht zehnmal schneller an), oder Geschirr spülen, wenn es nur eine Spüle gibt (zwei Personen sind schneller als eine, aber durch mehr Personen wird der Vorgang wahrscheinlich nicht beschleunigt).
Lektionseinstieg
Unterrichtsbeispiel ansehen
Die folgenden Videos zeigen weitere Beispiele zu Sortiernetzwerken:
Zeichnen Sie anhand der Sortiernetzwerkvorlage auf einer geteerten Fläche im Freien mit Kreide ein Sortiernetzwerk für 6 Personen (alternativ dazu können Sie auch Abdeck- oder Kreppband auf Teppich- oder Holzboden, Klebeband auf einer Abdeckplane oder Markierungsstreifenfarbe auf Gras verwenden). Hinweis: Für das Sortiernetzwerk werden nicht unbedingt verschiedene Farben oder Linienstärken benötigt. Falls jedoch geeignetes Kreide- oder Klebebandmaterial verfügbar ist, kann dies den Schüler dabei helfen, sich an die einzuschlagende Richtung zu erinnern. Es sollte groß genug sein, sodass zwei Schüler bequem in den Quadraten stehen können. Je großflächiger das Netzwerk, desto wirkungsvoller ist die Übung. Auf engem Raum kann die Übung auch auf einer Tischfläche mit Spielfiguren anstelle von herumlaufenden Schülern abgehalten werden, was jedoch nicht ganz so interessant ist.
Zeigen Sie den Schülern das auf den Boden gezeichnete Sortiernetzwerk und erklären Sie: „Dieser Kreidecomputer kann einige Dinge sehr schnell erledigen. Lasst uns herausfinden, was er macht.“
Mathematische Zusammenhänge
Unterstützt Schüler dabei, das Ordnen beliebiger Zahlenbereiche, vom Ordnen einstelliger Zahlen bis hin zu Brüchen und Dezimalzahlen oder Zahlen in Millionenhöhe, besser zu verstehen.
Lektionsaktivitäten
Teilen Sie die Schüler in Sechsergruppen auf. Es wird sich jeweils nur ein Team im Netzwerk aufhalten.
Das Team, das an der Reihe ist, sollte sich in den Kreisen am „Eingabe“-Ende des Sortiernetzwerks aufstellen.
Geben Sie jedem der sechs Schüler eine Karte in die Hand (verwenden Sie zunächst die Karten mit den Zahlen von 1 bis 6; die Karten sollten den Schülern ungeordnet ausgehändigt werden). Diese Karten sind die Eingaben in diesen coolen Kreidecomputer (es handelt sich um einen speziellen Computer, der mehrere Operationen gleichzeitig ausführen kann).
Lassen Sie die ersten beiden Schüler den Linien von ihren Kreisen aus folgen, bis sie sich in einem Quadrat treffen (die anderen sollten aufmerksam zusehen).
Nachdem die beiden das Quadrat betreten haben, sollten sie „Hallo“ zueinander sagen (damit soll sichergestellt werden, dass beide anhalten und sich mit diesem Schritt auseinandersetzen) und dann ihre Karten vergleichen, um festzustellen, wer die niedrigere und wer die höhere Zahl hat.
Der Schüler mit der niedrigeren Zahl soll der nach links führenden Linie folgen und zum nächsten Quadrat gehen, während die Person mit der höheren Zahl der nach rechts führenden Linie folgt, um zum nächsten Quadrat zu gelangen.
Lassen Sie nun das nächste Schülerpaar denselben Ablauf durchführen – sich in einem Quadrat treffen und mit der kleineren Zahl nach links und mit der größeren Zahl nach rechts gehen.
Jetzt können Sie das verbleibende Schülerpaar den Ablauf durchführen lassen (erinnern Sie sie daran, „Hallo“ zu sagen, wenn sie sich treffen).
Sobald die Schüler verstehen, worauf Sie hinauswollen, lassen Sie sie diesen Ablauf so oft wiederholen, bis sie am Ende des Netzwerks ankommen. Bleibt jemand zurück, müssen die Schüler zum Anfang zurückkehren. Sie müssen acht geben, wenn sie sich in einem Quadrat treffen, und sichergehen, dass beide Personen, die sich getroffen haben, das Ergebnis kennen.
Wenn alle die Kreise am anderen Ende des Netzwerks erreicht haben, bitten Sie sie, sich in Richtung Startkreise umzudrehen und dann von links nach rechts vorzulesen, was auf ihrer Karte steht. Die Zahlen sollten nun in der richtigen Reihenfolge sein, von der kleinsten zur größten. Ist dies nicht der Fall, müssen sie es möglicherweise erneut versuchen und sorgfältiger vorgehen.
Wenn jede Gruppe das Sortiernetzwerk durchlaufen hat, schlagen Sie ein Sortiernetzwerk-Rennen vor, um herauszufinden, welche Gruppe die Aufgabe am schnellsten durchführen kann (entweder mit zwei Sortiernetzwerken und zwei Rennteams gleichzeitig oder einem Netzwerk, bei dem jeweils die Zeit mit einer Stoppuhr genommen wird).
Unterrichtsbeobachtungen
Sofern es nicht funktioniert hat, ist möglicherweise ein Schülerpaar zum falschen Quadrat gelaufen oder eine Person ist allen anderen voraus gerannt. Lassen Sie die Gruppe die Aufgabe wiederholen und überprüfen Sie jeden Vergleich. Falls es ein zweites Mal nicht funktioniert, bitten Sie ein paar Schüler, als „Prüfer“ zu fungieren und zu bestätigen, dass an jedem Quadrat die richtige Entscheidung getroffen wurde, welche Person nach links und welche nach rechts laufen muss. Wenn die Schüler dazu anzuregt werden, beim Zusammentreffen in einem Quadrat „Hallo“ zu sagen, kann vermieden werden, dass jemand weiterläuft, bevor eine Entscheidung über die Werte getroffen wurde.
Sofern ein Schüler vor allen anderen zum Ende rennt, weil er bereits weiß, wo die Zahl hinkommt, sobald die Zahlen sortiert sind (das passiert ziemlich oft!) werden einige Schüler im Netzwerk stecken bleiben, weil sie niemanden haben, mit dem sie ihre Zahl vergleichen können. Dies ist eine gute Gelegenheit, die Schüler daran zu erinnern, dass Computer die eingegebenen Anweisungen genau befolgen müssen, um sicherzustellen, dass sie das richtige Ergebnis erzielen. Und es bestärkt auch die Notwendigkeit von Teamarbeit!
Das Gelernte anwenden
Diese parallele Anweisungsmethode kann nicht direkt auf der Art von Computersystemen ausgeführt werden, die Schüler vermutlich lernen werden, da einfachere Systeme nur jeweils ein Wertepaar vergleichen können, während dieses System bis zu drei Wertepaare gleichzeitig vergleicht. Und obgleich dieser Algorithmus nicht zur Ausführung auf konventionellen Systemen geschrieben wurde, kann dennoch eine Rechenregel festgestellt werden, und zwar ein paralleler Algorithmus, der auf spezialisierter Hardware und Software ausgeführt werden kann. Die Schwierigkeit beim Erstellen von parallelen Algorithmen besteht darin, möglichst viele Dinge gleichzeitig stattfinden zu lassen, damit Aufgaben schneller erledigt werden können. Es ist jedoch nicht immer einfach, Problemstellungen so zu zerlegen, dass einzelne Arbeitsgänge gleichzeitig ablaufen können, da einzelne Vergleiche oftmals vom Ergebnis eines anderen Vergleichs abhängen. Darüber hinaus ist das von uns oben verwendete Strukturdiagramm das kürzeste System, das zum Ordnen von sechs Werten angelegt werden kann.
Woher wissen wir, dass dieses Sortiernetzwerk zuverlässig ist und immer funktioniert?
Als Ergebnis wollen wir erreichen, dass die Zahlen in der richtigen Reihenfolge herauskommen, und zwar die kleinste Zahl im ganz linken Feld und die zweitkleinsten Zahl daneben, bis hin zur größten Zahl im ganz rechten Feld. Wenn wir sicherstellen wollen, dass dies für alle nur möglichen Eingaben funktioniert, müssten wir es für jede nur mögliche Ausgangsreihenfolge der Werte testen. Da es jedoch bei sechs Elementen 720 (6 x 5 x 4 x 3 x 2 x 1) verschiedene Ausgangsreihenfolgen gibt, wären eine Unmenge verschiedener Fälle zu prüfen. Um mehr als 6 Elemente zu ordnen gibt es viel zu viele verschiedene Reihenfolgen, um sie alle auszuprobieren. Daher müssen wir einen mathematischen Nachweis dafür erbringen, warum es funktioniert. Hier sind einige Elemente eines solchen Nachweises:
Lassen wir die Zahlen vorerst außer Acht und sehen uns das Sortiernetzwerk im Hinblick auf die Befolgung der Pfade an. Wenn die kleinste Zahl im Knotenpunkt 1 wäre – welchen Pfad würde sie nehmen und wird sie am Ende am ganz linken Knotenpunkt ankommen?
Wiederholen Sie dies nun, indem Sie fragen, welchen Pfad die kleinste Zahl nehmen würde, wenn sie im Knotenpunkt 2 wäre, und ob sie am Ende trotzdem am ganz linken Knotenpunkt ankommen würde?
Wiederholen Sie dies, bis alle 6 Knotenpunkte getestet wurden. Wenn die kleinste Zahl unabhängig von ihrem Ausgangspunkt stets am ganz linken Knotenpunkt ankommt, ist damit bereits zum Teil nachgewiesen, dass die Struktur stets funktioniert.
Dies kann auch mit der größten Zahl wiederholt werden – egal, wo sie startet, sie wird stets am ganz rechten Knotenpunkt ankommen.
Diesen Test mit den anderen vier Werten (z. B. dem zweitgrößten) durchzuführen, ist nicht ganz so einfach. Informatiker können jedoch nachweisen, dass auch diese Werte stets an der richtigen Position ankommen.
Lektionsbetrachtung
Gab es eine Situation, in der die Karten nicht richtig geordnet waren? Wie kam es dazu? Wie wurde dies berichtigt?
Könnt Ihr die Pfade der niedrigsten Zahl aufzeigen, egal in welcher Position sie platziert wird? Was ist mit der größten Zahl?
Informatische Denkzusammenhänge erkennen
Aus allen Lektionen ergeben sich Verbindungen zu informatischem Denken. Nachstehend sind ein paar allgemeine Verbindungen aufgeführt, die diesen Inhalt betreffen.
Teaching computational thinking through CSUnplugged activities supports students to learn how to describe a problem, identify what are the important details they need to solve this problem, break it down into small logical steps so that they can then create a process which solves the problem, and then evaluate this process. These skills are transferable to any other curriculum area, but are particularly relevant to developing digital systems and solving problems using the capabilities of computers.
Diese informatischen Denkkonzepte sind alle miteinander verbunden und stützen sich gegenseitig. Insoweit möchten wir jedoch anmerken, dass nicht alle Aspekte des informatischen Denkens in jeder Unterrichtseinheit oder Lektion vorkommen. Wir haben jeweils die für Sie wichtigen Verbindungen hervorgehoben, um Ihre Schüler in Aktion zu beobachten. Unser Artikel zu informatischem Denken enthält weitere Hintergrundinformationen dazu, wie wir informatisches Denken definieren.
Algorithmisches Denken
In dieser Lektion haben wir einen Algorithmus verwendet, um die Zahlen mithilfe eines Parallelprozessors in eine Reihenfolge zu ordnen (normalerweise wäre dieser Prozessor in eine Hardware eingebaut, aber unser Kreidenetzwerk ist ja auch einer! Es wird nur von Menschen anstatt von Strom angetrieben).
Worauf Sie beispielsweise achten können:
Verstehen die Schüler, wie die einzelnen Knotenpunkte funktionieren (zwei Werte annehmen und diese zu tauschen, wenn sie in der falschen Reihenfolge sind)? Können sie anderen Schülern erklären, wie das Netzwerk richtig angewendet wird?
Erkennen die Schüler, dass wir unabhängig davon, welche Zahlen oder Daten wir in das Netzwerk eingeben, stets eine Lösung erhalten, wenn wir den Algorithmus genau befolgen?
Abstraktion
Das bei diesen Aktivitäten verwendete Sortiernetzwerk ist an sich eine abstrakte Darstellung davon, wie Sortiernetzwerke in Hardware und Software ausgeführt werden. Es stellt die Kernfunktionalitäten eines Sortiernetzwerks dar, während alle wesentlichen Funktionsdetails der Hardware und der Schaltkreise verborgen bleiben.
Worauf Sie beispielsweise achten können:
Sind die Schüler in der Lage, zwischen den Linien und Knotenpunkten dieser grafischen Darstellung und der Art und Weise, wie Computer durch Vergleichsvorgänge Daten verarbeiten, eine Verbindung herzustellen? Verstehen die Schüler, dass anhand dieser Darstellung vorgeführt werden kann, wie ein echter Parallelcomputer arbeiten würde?
Dekomposition
Der gesamte Prozess des Sortierens in dieser Aktivität ist in eine äußerst einfache Operation zerlegt: zwei Werte vergleichen. Die Operation an sich ist sehr simpel, wenn sie jedoch viele, viele Male ausgeführt wird, kann damit eine Lösung zu einer viel größeren Aufgabenstellung aufbaut werden.
Worauf Sie beispielsweise achten können:
Verstehen die Schüler, wie ein Sortiernetzwerk erstellt wird, um nur zwei Werte zu sortieren? (Es wäre nur ein einziger Komparatorknotenpunkt.)
Generalisierung und Muster
In dieser Lektion haben die Schüler nur mit einer Art von Daten, nämlich Zahlen, gearbeitet, so dass Generalisierung wenig zum Tragen kam. Dies wird in der nächsten Lektion eingehender behandelt.
Auswertung
Bei diesem Sortiernetzwerk können bis zu drei Vergleiche gleichzeitig vorgenommen werden und die Länge des Netzwerks bestimmt, wie lange es dauern würde, all diese Vergleiche durchzuführen. Obgleich beim Durchlaufen des Netzwerks 12 Vergleiche vorgenommen werden müssen, kann das Netzwerk in der Zeit durchlaufen werden, die ein einzelner Knotenpunkt dazu benötigt, 5 Vergleich vorzunehmen.
Worauf Sie beispielsweise achten können:
Können die Schüler den längsten Pfad bestimmen, den eine beliebige Zahl durchlaufen müsste, um ans Ende zu gelangen? (Die zwei mittleren Zahlen müssen fünf Vergleiche vornehmen.) Können die Schüler erklären, dass der Sortiervorgang in 5 x 2 Sekunden und nicht 12 x 2 Sekunden abgeschlossen wäre, wenn jeder Vergleich circa zwei Sekunden dauern würde?
Logik
Der kleinste Wert nimmt bei jedem Vergleichsvorgang stets den linken Pfad und jeder Pfad, der von einem Startpunkt aus nach links abzweigt, führt zu diesem Knotenpunkt. Daher kommt der kleinste Wert am Ende stets an der ganz linken Position an.
Worauf Sie beispielsweise achten können:
Können die Schüler erklären, wo der kleinste Wert ankommen wird, unabhängig davon, was die anderen Werten sind? Verstehen die Schüler die Funktion der einzelnen Knotenpunkte? Vermeiden sie es, einfach zum letzten Knotenpunkt zu gehen, ohne die Vergleiche durchzuführen?
Diese Definition ist leider nicht in Deutsch verfügbar!