Sortierungen

Anleitung zur Übung 3

Der Grundstoff

Computer sind schnell, aber es gibt eine Grenze wie schnell sie ein Problem lösen können. Eine Art Rechenvorgänge zu beschleunigen ist, mehrere Computer zu verwenden, die jeweils nur einen Teil des Problems lösen. Oder Computer optimieren ihre Rechnenweise. Diese Optimierung nennt man Algorithmus.

Das Ziel

In dieser Übung lernen wir verschiedene Sortiernetzwerke kennen, die unterschiedliche Sortiervergleiche zur selben Zeit durchführen.

Das Material

Das ist eine Outdoor-Gruppen-Übung, d.h. diese Übung findet am besten im Schulhof oder einem anderen geeigneten Gelände statt, bei dem es möglich ist auf dem Boden mit Kreide zu zeichnen.

• Straßenkreide
• Pro Gruppe sechs Karten. Kopieren Sie die Vorlage und schneiden Sie sie aus.
• Stoppuhr

Und die Downloads:

Anleitung	Kopiervorlage	Handout
1. Übung	1. Übung

Die Ausführung

Zur Vorbereitung malen Sie bitte dieses Netzwerk auf den Boden des Schulhofes. Es dauert etwas und braucht viel Platz – seien sie großzügig!

Anweisungen für die Kinder

Diese Übung zeigt, wie Computer zufällige Zahlen in die richtige Reihenfolge bringen. Dabei benutzen sie ein sogenanntes Sortiernetzwerk.

• Bildet Gruppen zu sechs Kindern. Immer nur ein Team kann das Netzwerk zur selben Zeit nutzen.
• Jedes Gruppenmitglied nimmt eine Nummernkarte.
• Jedes Gruppenmitglied stellt sich auf ein Kästchen auf der linken Seite des Netzwerkes. Deine Zahlen sollten dabei ungeordnet sein.
• Du gehst entlang der Linie vor Dir., und wenn Du einen Kreis erreichst, musst Du warten bis irgendjemand anderes dazu kommt.
• Wenn ein anderes Gruppenmitglied dazu kommt, dann vergleicht Ihr die beiden Zahlen. Das Gruppenmitglied mit der kleineren Zahl geht links weiter. Wenn Du die höhere Zahl hast gehst Du rechts weiter.
• Seid Ihr in der richtigen Reihenfolge, wenn Ihr das Ende des Netzwerkes erreicht?

Wenn ein Team einen Fehler macht, muss man neu starten. Kläre, ob alle verstanden haben, welchen Sinn die Knoten (Kreise) haben, wo die kleinere Zahl links und die größere Zahl rechts geht.

Variationen

• Wenn die Kinder gut mit der Übung zurecht kommen, kann man die Zeit stoppen, welches Team am schnellsten durch das Netzwerk kommt.
• Benutzen Sie die Karten mit den größeren Zahlen. (Siehe Kopiervorlage)
• Machen Sie Karten mit noch größeren Zahlen, die schwieriger sind zu vergleichen oder benutzen Sie Wörter und vergleichen Sie sie alphabetisch.

Erweiterte Übung

1. Was passiert, wenn die kleinere Zahl rechts gehen soll und die größere links? (Die Zahlen kommen in umgekehrter Reihenfolge heraus.) Funktioniert es auch, wenn man das Netzwerk rückwärts benutzt? (Es wird nicht notwendigerweise funktionieren und die Kinder sollten eine Kombination an Startaufstellung finden, die ein falsche Ergebnis
   bringt:)
2. Versuchen Sie kleinere oder größere Netzwerke. Zum Beispiel, dieses hier mit drei Zahlen. Die Kindern sollten von alleine darauf kommen.
3. Unten sind zwei verschiedene Netzwerke, die jeweils vier Eingaben sortieren. Welches ist schneller? (Das zweite ist es. Während das Erste alle Vergleiche nur nacheinander abarbeiten kann, ist das Zweite wesentlich performanter (also schneller), da es mehrere Vergleichsoperationen gleichzeitig ausführt. Das erste Netzwerk ist ein Beispiel für serielle Prozesse, während das zweite eines ist für parallele Prozesse.
   
4. Versuchen Sie größere Netzwerke zu erstellen. Oder Sie lassen weniger Kinder in ein größeres Netzwerk starten.
5. Netzwerke können genauso so gut verwendet werden, um ein Minimum oder ein Maximum zu finden. Zum Bespiel, steht links ein Netzwerk mit acht Eingabemöglichkeiten und die einzige Ausgabe ist das Minimum der Eingaben (die anderen Eingaben enden jeweils auf den x (x = DEAD END).
6. Welche täglichen Prozesse können oder können nicht durch paralelles Arbeiten beschleunigt werden? Zum Beispiel, Essen kochen würde sehr langsam sein, wenn man einen Teil des Gerichts nach dem anderen zu bereiten würde. Welche Arbeiten können durch mehr Menschen schneller erledigt werden, welche nicht?
7. Es gibt auch andere Sortieralgorithmen z.B den Bubblesort (wird selten in der IT eingesetzt, da er zu ineffizient ist, ist aber zur Veranschaulichung ein wunderbares Beispiel. Außerdem lernt man auf diese Weise zum ersten Mal Schleifen kennen). Also: Man beginnt oben und diese Element vergleicht sich mit dem darunter liegenden. Ist es größer, werden die Plätze getauscht, ansonsten bleib es wo es ist. Dann vergleichen sich die zwei Element darunter miteinander. Auch hier wird nur getauscht, wenn das obere Element größer ist als das untere. Ist man unten angelangt, hat man die größte Zahl auf dem letzten Platz und braucht diese nicht mehr zu beachten. Dann geht das Ganze von vorne los, bis alle Zahlen (oder Buchstaben oder Serviervorschläge) in der richtigen Reihenfolge sind.

Wofür das Ganze

Je mehr wir Computer benutzen um so mehr müssen diese noch mehr Informationen verarbeiten und das so schnell wie möglich.

Ein Weg die Geschwindigkeit eines Computer zu erhöhen sind Programme, die weniger Rechenschritte erfordern.

Ein anderer Weg, dieses Problem zu lösen, ist das vernetzen von Computern. Dabei arbeiten dann die Computer jeweils nur an einem Teil des Problems zur gleichen Zeit. Es werden zum Beispiel im sechs-Nummern Sortiernetzwerk insgesamt 12 Vergleiche gebraucht, wo von jeweils drei zeitgleich stattfinden. Das bedeutet, dass insgesamt nur die Zeit für 5 Schritte nötig ist. Damit ist das parallele Netzwerk doppelt so schnell wie ein System, das jeden Vergleich einzeln rechnen muss.

Nicht jede Aufgabe kann durch paralleles Arbeiten schneller werden. Als Analogie, stellen Sie sich eine Person vor die einen 10 Meter langen Graben gräbt. Schneller geht dies natürlich, wenn 10 Personen jeweils einen 1 Meter langen Graben graben. Die gleiche Strategie funktioniert nicht mehr, wenn man ein 10 Meter tiefes Loch gräbt. Denn erst wenn der erste Meter gegraben ist, kann die zweite Person ihre Arbeit ausführen. IT-Experten sind laufend dabei den besten Weg zu finden, Lösungen für Probleme so herunter zu brechen, dass sie parallel von Computern bearbeitet werden können.