Den Schülern wird die Idee der binären Suche vorgestellt. Die Idee basiert auf der menschlichen Roboter-Übung.
| Autor | Mikko Muilu |
| Fach | Informatik |
| Länge | 90 Minuten |
| Ansatz | Problem-Basiertes Lernen |
| Kompetenzen | Schüler lernen, was ein Algorithmus bedeutet Die Schülerinnen und Schüler lernen, dass es verschiedene Möglichkeiten gibt, bestimmte Zahlen abzurufen, und dass einige Methoden wesentlich schneller sind als andere. Schüler lernen einfache Algorithmusprinzipien Die Schüler lernen, wie man die programmtechnische if-Anweisung in der Praxis einsetzt |
| Klasse | 4.-6. Klasse |
| Technologien | Stift und Papier |
Beschreibung
Für die Aktivität wird eine gerade Anzahl von Schülern benötigt. Sie werden in Paare aufgeteilt. Die andere Person in einem Paar nennt eine Zahl aus dem vereinbarten Bereich. Die andere Person versucht, die Zahl zu erraten, indem sie Fragen stellt. Die Person, die die Zahl bestimmt hat, kann diese Fragen nur mit “Ja” oder “Nein” beantworten. Wie kommt man am schnellsten auf die gewünschte Zahl?
Einführung
Den Schülern wird das Prinzip der Algorithmen erklärt (Anhang 1) und wie die Algorithmen bestimmten Anweisungen folgen, um immer eine Lösung zu finden, unabhängig von den Daten, die ihnen gegeben werden. Die Schülerinnen und Schüler können an die Übung mit dem menschlichen Roboter erinnert werden, und es wird ihnen geraten, die gegebenen Anweisungen genau zu befolgen.
Aufgabe 1
Die Lehrkraft teilt die Schüler in Paare ein. Der eine ist der Suchende und der andere der Antwortende. Der Antwortende wählt eine Zahl zwischen 1 und 50 aus und schreibt sie auf ein Blatt Papier. Wenn sie fertig sind, stellt der Suchende Fragen und der Antwortende kann nur mit “Ja” oder “Nein” antworten. Zu Beginn kann jemand nach einzelnen Zahlen fragen (“Ist es zwei?”, “Ist es drei?”). Wenn sie nicht auf die Möglichkeit kommen, die Menge durch Fragen wie “Ist sie größer als 10?” einzugrenzen, können sie in die richtige Richtung gelenkt werden. Die Idee der Übung wird im folgenden Video erklärt.
Diskussion: Wie oft musste man raten, um die richtige Zahl zu finden? Welche Art von Taktik hatten die SchülerInnen? Wie würde sich die Anzahl der Schätzungen mit den verschiedenen Taktiken ändern, wenn die Zahl zwischen 1 und 1 000 liegt?
Die Lehrkraft erklärt das Prinzip der binären Suche: Wenn der Suchbereich zwischen 1 und 1 000 liegt, ist es zunächst wichtig zu fragen, ob die Zahl größer als 500 ist (Mitte der Suche). Danach wird die verbleibende Menge mit einer ähnlichen Frage in zwei Hälften geteilt und dies wird fortgesetzt, bis die gewünschte Zahl erreicht werden kann.
Aufgabe 2
Beginnen wir mit dem Bereich von 1 bis 1 000. Die Schüler üben die binäre Suche und können, wenn sie möchten, eine andere Art der Zahlensuche ausprobieren. Die Schüler zählen, wie viele Versuche nötig sind, um die richtige Zahl zu finden. Was passiert, wenn der Bereich von 1 bis 10 000 reicht? Wie wäre es mit 1 bis Million oder 1 bis Milliarde?
Diskussion:
Was haben die Schülerinnen und Schüler über die Anzahl der Vermutungen herausgefunden? Warum wuchs die Anzahl der Schätzungen nicht sehr schnell? Wie viele Vermutungen waren nötig, um eine Zahl zwischen eins und einer Million zu finden?
Sie können den älteren Schülern etwas über die Potenz von zwei erzählen und wie schnell sie wächst. Mit jeder Suche halbiert sich die Zahlenmenge, was es einfacher macht, die gewünschte Zahl zu finden. Mit anderen Worten: Wenn sich die Zahlenmenge verdoppelt, brauchen Sie nur noch eine Frage. Das Bild unten erklärt die Potenz von zwei. Die Zahl zwei wird so oft mit sich selbst multipliziert, wie im Exponenten angegeben ist. Das Bild erklärt auch die Anzahl der Schätzungen, die für eine erfolgreiche binäre Suche erforderlich sind. Wenn der Zahlenbereich 128 beträgt, braucht man bis zu sieben Fragen, um die richtige Zahl zu finden (2 multipliziert mit sich selbst siebenmal gleich 128). Die Zweierpotenz gibt die maximale Anzahl der Fragen an, die benötigt werden, um die gewünschte Zahl zu finden.
Aufgabe 3
Wenn es die Zeit erlaubt, können die Schüler auch in der Praxis ausprobieren, ob die zuvor gemachte Aussage tatsächlich Sinn macht oder nicht.
Anlage 1
Algorithmen sind eine Reihe von Anweisungen, die es ermöglichen, ein gewünschtes Ergebnis zu erzielen. Im Grunde können diese Anweisungen jede Art von Anweisungen sein, zum Beispiel die, die wir in Kochbüchern sehen können. Wenn jedoch von Algorithmen die Rede ist, sind in der Regel mathematische Anweisungen oder Anweisungen gemeint, die für einen Computer verständlich sind. Die binäre Suche, die wir hier praktizieren, ist ein Suchalgorithmus. Viele Such- und Sortieralgorithmen werden in der Informationstechnologie verwendet, aber auch zum Beispiel bei der gezielten Ansprache von Internetnutzern durch Werbung.
 This document is distributed in 2021 by the COTA Project Consortium under an Attribution–ShareAlike Creative Commons license (CC BY-SA 4.0). This license allows you to remix, tweak, and build upon this work, as long as you credit the COTA Project Consortium and license your new creations under the identical terms |