FH Graubünden PH Graubünden

Suchen und Ordnen

Algorithmisches Denken in der Primarschule

Zusammenfassung

Diese Unterrichtseinheit befasst sich im Kern mit der Frage wie wir eine vorgegebene Ordnung von Daten nutzen können, um auf der Suche nach Information schnell und strukturiert zu einer Lösung zu gelangen. Das Ziel ist es, sich mit dem Konzept der Ordnung auseinander zu setzen. Die Teilnehmerinnen und Teilnehmer werden sich der engen Verbindung zwischen Suchen und Ordnen bewusst und stellen sich die Frage «Wie gehen wir vor, wenn wir nach einer Information suchen und welche Möglichkeiten bietet uns eine Ordnung, diesen Prozess zu verbessern?»

Die Studierenden werden wiederholt mit der Aufgabe konfrontiert, eine bestimmte Zahl in einem Stapel von Karten zu finden oder eine bestimmte Zahl an der richtigen Stelle einzufügen. Das Ziel ist, beim Suchen so wenige Karten wie nur möglich aufzudecken. Die Studierenden lernen, dass es einen Unterschied macht, ob die Karten sortiert oder nicht sortiert vorliegen und ob die Folge von Elementen kontinuierlich ist oder nicht.

Je öfter gesucht werden muss, desto wichtiger ist es Ordnung zu halten, denn nur so kann effizient gesucht werden. Um jedoch über eine längere Zeit die Ordnung aufrecht erhalten zu können, ist es wichtig, dass auch neue Elemente in eine bereits vorhandene Ordnung eingefügt werden können, ohne diese dabei zu zerstören.

Beispielsequenz

Im Folgenden bearbeiten wir Aufgaben, die eine Menge von Karten voraussetzen. Benötigt werden 30 identische Karten, die mit den Zahlen 1 bis 30 beschriftet sind. Zunächst beschäftigen wir uns mit der Frage wie in einer Menge von Elementen effizient gesucht werden kann. Ab Aufgabe 3 stellen wir uns die Frage, wie eine vorherrschende Ordnung beibehalten werden kann trotz neu einzufügender Elemente.

.karte1.png.
Abbildung 1. Für die folgenden Aufgaben liegen jeweils 30 Karten verdeckt auf dem Tisch.

Aufgabe 1

Mischen Sie die 30 Karten gut durch und legen Sie sie verdeckt in einer Reihe auf den Tisch. Die Aufgabe besteht nun darin, die Karte mit der Nummer 13 zu finden. Wie viele Karten decken Sie auf, bevor Sie die gesuchte Zahl 13 finden? Führen Sie dasselbe Experiment 5-mal durch und mischen Sie die Karten dabei immer wieder neu. Bestimmen Sie, wie viele Versuche Sie durchschnittlich benötigen, um die Zahl 13 zu finden.

Aufgabe 2

Nun beobachten wir, welchen Effekt es hat, wenn die Karten geordnet sind. Zum Ausführen dieser Aufgabe benötigen Sie eine Hilfsperson. Mischen Sie die 30 Karten und legen Sie davon zufällig 15 Karten zur Seite, ohne diese anzuschauen. Die beiseite gelegen Karten benötigen Sie in diesem Durchgang nicht mehr. Die Hilfsperson zieht nun aus den verbliebenen 15 Karten zufällig eine Karte, merkt sie sich und steckt sie wieder zurück. Anschliessend sortiert die Hilfsperson die Karten und legt sie verdeckt in einer Reihe auf den Tisch. Nun sind Sie wieder an der Reihe: Probieren Sie mit möglichst wenigen Versuchen, die zuvor von der Hilfsperson gezogene Karte zu finden. Führen Sie das Experiment 5-mal durch (mischen Sie nach jedem Durchgang die Karten und wählen Sie zufällig 15 neue Karten aus). Berechnen Sie am Ende, wie viele Versuche sie durchschnittlich benötigt haben, um die gesuchte Karte zu finden.

Aufgabe 3

Lassen Sie sich von einer Hilfsperson 15 zufällige Karten aus dem Deck auswählen. Die Hilfsperson legt diese anschliessend verdeckt und aufsteigend sortiert vor Sie hin. Ziehen Sie nun eine zufällige Karte aus den restlichen 15 Karten. Der Wert dieser Karte ist noch nicht in der ausgelegten Kartenreihe vor Ihnen enthalten. Ihre Aufgabe ist es nun, diese Karte an der richtigen Stelle in die Kartenreihe einzufügen. Decken Sie zum Finden der richtigen Stelle so wenige Karten wie möglich auf. Wie gehen Sie vor?

Aufgabe 4

Wir spielen dasselbe Spiel wie in Aufgabe 2 nochmals, dieses Mal jedoch mit dem vollständigen Kartenset, ohne vorgängig Karten zu entfernen. Sortieren Sie zunächst die Karten aufsteigend nach Wert (die Karte mit dem Wert 1 liegt anschliessend ganz links, die Karte mit dem Wert 30 ganz rechts). Wir suchen nach der Karte mit dem Wert 13. Wie viele Karten müssen Sie umdrehen, bis Sie die Karte gefunden haben? Vergleichen Sie mit dem Resultat aus Aufgabe 2 – wieso unterscheiden sich die Resultate?

Lösungen zu den Aufgaben

Aufgabe 1

Ohne eine gegebene Struktur bleibt uns nichts anderes übrig, als sämtliche Karten durchzugehen, bis die gesuchte Zahl gefunden wird. Mit viel Glück kann es vorkommen, dass die Karte schon beim ersten Versuch gefunden wird, im schlimmsten Fall kann es allerdings auch vorkommen, dass alle 30 Karten aufgedeckt werden müssen. Im Durchschnitt gemittelt über alle 5 Versuche sollten es ungefähr \(n/2\) (hier also mit \(n=30\) ungefähr 15) Karten sein, die aufgedeckt werden müssen.

Bei 30 Karten mag es vertretbar sein, die Hälfte aller Karte aufdecken zu müssen. Doch stellen Sie sich vor, Sie stehen in einer Bibliothek mit zehntausenden Büchern und Sie möchten genau ein ganz bestimmtes Buch finden. Wenn Sie nun für diese einzelne Suche die Hälfte aller Bücher aus den Bücherregalen anschauen müssten, würde es viel zu lange dauern, bis Sie Ihr Buch finden würden. Aus diesem Grund halten grössere Systeme (Bibliotheken, Telefonbücher, etc) Ordnung, die es ihnen erlaubt, Elemente schneller zu finden.

Aufgabe 2

Eine Strategie, um in einer geordneten aber nicht vollständigen Menge von Elementen ein bestimmtes Element zu finden, ist die binäre Suche. Diese Strategie sieht vor, jeweils Elemente möglichst in der Mitte der noch zu untersuchenden Karten zu wählen und so die Menge jeweils in zwei Hälften zu teilen. Aufgrund der Ordnung wissen wir, dass alle Karten rechts einer Karte einen grösseren Wert haben als die Karte selbst und alle Karten links einen kleineren Wert haben als die Karte selbst. Indem die Karten geschickt gewählt werden (jeweils in der Hälfte des zu untersuchenden Bereichs), können in jedem Schritt die Hälfte aller übrigbleibenden Karten verworfen werden.

Aufgabe 3

Auch in dieser Aufgabe kann die in Aufgabe 2 entdeckte Strategie, die binäre Suche, angewandt werden. Die Kernidee ist: Wenn wir beim Einfügen die vorherrschende Ordnung nicht verletzen wollen, müssen wir zunächst den richtigen Ort für die jeweilige Karte finden. Dazu suchen wir wie zuvor nach der richtigen Stelle. Sobald die korrekte Stelle gefunden ist (also die benachbarte Karte identifiziert ist), kann die Karte an der dieser Stelle eingefügt werden, ohne dabei die Ordnung zu verletzen. Es können nun beliebig viele weitere Karten eingefügt werden und die Ordnung bleibt jeweils erhalten.

Aufgabe 4

Es muss genau eine Karte umgedreht werden. Dieses Vorgehen ist optimal, da die Karten in einer perfekten Ordnung vorliegen (das heisst zwischen der Position einer Karte und deren Wert besteht ein direkter Bezug, hier sind die beiden identisch – die Karte mit dem Wert 13 befindet sich an dreizehnter Stelle in der geordneten Folge). Eine perfekte Ordnung ist nur möglich, wenn zwischen den Karten und den dazugehörigen Zahlenwerten eine eindeutige Relation existiert. Hier beruht das auf der Annahme, dass ein kontinuierlicher Datensatz vorhanden ist.

Didaktischer Kommentar

Algorithmisches Denken heisst, Probleme über eine wohldefinierte Vorgehensweise (das heisst einen Algorithmus) zu lösen. In dieser Aufgabe beschäftigen wir uns mit einfachen Such-Problemen und finden verschiedene Vorgehensweisen, um diese Problemstellung zu lösen: Zunächst geht es darum, in einer Menge von Zahlen möglichst effizient ein bestimmtes Element zu finden. In diesem Kontext erfahren die Lernenden, dass es ein Vorteil ist, wenn die Karten zuvor sortiert werden. Ohne Ordnung müssen wir im schlimmsten Fall sämtliche Karten durchgehen, was besonders bei grossen Datensätzen oder häufiger Suche sehr zeitintensiv wird. In diesem Fall lohnt es sich, die Daten zu ordnen.

Mittels geordneter Daten sind wir fähig, durch binäre Suche wesentlich schneller zum Ziel zu kommen. Wiederholt können wir die Hälfte aller Karten ausschliessen, da deren Wert zu gross oder zu klein ist. So konvergieren wir nach wenigen Schritten zur korrekten Lösung. Zur Illustration: Um in einer Datenmenge von 1 Billion Zahlen (das ist eine beeindruckende Zahl mit 9 Nullen!) eine bestimmte Karte zu finden, müssen wir mangels Ordnung durchschnittlich 500 Milliarden Karten betrachten. Sind die Karten jedoch aufsteigend sortiert, gelingt die Suche in lediglich 30 Schritten.

Der Baustein enthält die folgenden Aspekte des algorithmischen Denkens.

Quellenangaben und weiterführende Literatur

  1. Juraj Hromkovič: Einfach Informatik 7–9 – Daten darstellen, verschlüsseln, komprimieren Klett Verlag.
  2. Juraj Hromkovič: Einfach Informatik 7–9 – Begleitband zu Daten darstellen, verschlüsseln, komprimieren, Klett Verlag.

Zurück PDF Übungen als PDF