Arbeitsblatt: Skript Algorithmen/Programmieren

Name: Informatik 5./6. Klasse Algorithmen Programmieren 1. Weg durch das Labyrinth :) :) }:-) :-{} ;-) :-o :- :-( &:-) 8:-) B-) :) }:-) ;-) :-o :- :) :-{} B-) :) }:-) ;-) :-o :- :-( &:-) 8:-) :) :-{} B-) :) }:-) ;-) :-o :- :-( &:-) Folge dem Weg durch das Labyrinth und versuche einen Trick zu finden, wie man sich allgemein in Irrgärten zurechtfinden kann. Formuliere hier deine Vermutung, tausche sie mit einem Nachbarn aus und versuche, die Vermutung nachzuvollziehen. Überprüfe mithilfe dieses Irrgartens, ob der oben formulierte Trick auch hier funktioniert. 8:-) Welcher Tank wird zuerst voll? 2. Flussdiagramm Um später Computerprogramme schreiben zu können, ist es wichtig eine Methode zur Visualisierung der einzelnen Schritte und Entscheidungen in einem Programm zu haben. Zwei bekannte Methoden zur Visualisierung eines Programms sind das Flussdiagramm und das Struktogramm. Beispiel eines Flussdiagramms: Dabei gibt es unterschiedliche Verzweigungen: 3. Spielt eine Runde: Wer bin ich? Alle überlegen sich eine für alle bekannte Figur, Person, Tier oder Gegenstand (dein Lieblingsfussballer für die anderen vielleicht total unbekannt, aber z. B. Donald Duck kennen vermutlich alle). Schreibt den Namen eurer Figur verdeckt auf eine Haftnotiz-Zettel. Klebt euren Zettel an die Stirn eines anderen Mitspielers, ohne dass dieser den Namen selbst sehen kann. Ziel des Spiels ist es, den Namen auf seinem Zettel durch geschickte Fragen herauszufinden, die nur mit Ja oder Nein beantwortet werden können. Bin ich ein Mensch? Bin ich männlich? Bin ich ein Schauspiel er? Sobald eine Frage von der Gruppe mit NEIN beantwortet wird, ist der nächste Spieler an der Reihe. Glaubt der Spieler, der gerade an der Reihe ist, seine Figur herausgefunden zu haben, fragt er „Bin ich Donald Duck? und darf sich im Erfolgsfall seinen Notizzettel von der Stirn nehmen. Bei diesem Spiel kommt es auf eine gute Fragestrategie an. Durch welche Fragen kannst du möglichst viele Dinge ausschliessen? Zum Beispiel ist es sinnvoll zunächst allgemeinere Fragen wie „Bin ich weiblich? zu stellen, bevor man konkreter wird: „Bin ich eine Prinzessin? 4. An wen denkst du? –Spiel gegen den Computer Solltest du gerade ein Smartphone oder einen Computer zur Hand habe, spiele einige Runden mit dem Ratespiel Akinator und überlege dir, wie das Spiel funktioniert. Wie kann der Computer wissen, an wen du denkst? Wie wählt der Computer wohl seine nächste Frage aus? Schaffst du es, an eine Figur zu denken, die Akinator noch nicht kennt? 5. Binärsuche – schlau und schnell Computer sollen häufig aus Millionen von Informationen eine ganz bestimmte heraussuchen. In einer Kundendatenbank soll zum Beispiel Herr „Schmied herausgesucht werden. Statt nun jeden einzelnen Eintrag der Datenbank anzusehen und zu prüfen, ob es sich um Herrn Schmied handelt, verwendet die Datenbank einen cleveren Algorithmus. Herr Damit dieser angewendet werden kann, Schmied müssen zunächst alle Einträge alphabetisch geordnet werden – wie in einem Telefonbuch. Das Sortieren kann etwas dauern, aber auch dafür gibt es schlaue Algorithmen, die sehr effizient grosse Datenmengen sortieren können. Einmal sortiert, ist die Suche nach Herrn „Schmied aber nun viel einfacher. Man teilt den Bestand in zwei gleich grosse Hälften und schaut sich den mittleren Eintrag an. Dort steht zum Beispiel Frau „Pauli. Jetzt kann man schnell entscheiden, ob Herr „Schmied vor oder nach „Pauli kommt im Alphabet. In diesem Fall muss die ganze erste Hälfte nicht mehr angeschaut werden, da Schmied dort Herr garantiert nicht dabei sein wird.Annen Frau Pauli Mit der verbleibenden Hälfte wiederholen wir das Verfahren. Wieder wird die Auswahl in zwei gleich grosse Teile geteilt und der mittlere Eintrag angeschaut: Herr „Tegel. Jetzt wissen wir, dass der Eintrag in der ersten Hälfte liegen muss und müssen die zweite Hälfte nicht Frau mehr anschauen. Pauli Herr Tegel Das setzt sich solange fort, bis Herrn Schmied gefunden wurde. Bei einer Millionen Kunden müssen nur höchstens 19 Einträge angeschaut werden, bis garantiert der gesuchte Datensatz gefunden wird. Auch bei 100 Millionen Kunden steigt die Anzahl nötiger Einträge nur wenig an (25). Da man sich bei jeder Entscheidung für eine von zwei Hälfte entscheidet, bezeichnet man dieses Verfahren als Binärsuche. 6. Die Geschenke des Weihnachtsmanns Die Wichtel des Weihnachtsmanns haben dieses Jahr wieder Millionen von Geschenken für Kinder auf der ganzen Welt verpackt. Darunter auch 10‘000 rote Spielzeugautos mit Fernsteuerung. Nachdem alle Autos identisch verpackt wurden, fällt einem der Wichtel auf, dass eine Fernbedienung übriggeblieben ist. Oh nein, alle Geschenke noch einmal Nein, nein. Wir wiegen die Geschenke einfach ein paar Mal ab und finden so ganz Habt ihr eine Idee, wie die Wichtel das mit nur 15 Mal wiegen schaffen können und nach jedem Wiegen nur noch halb so viele Geschenke überprüfen müssen? Glossar: Algorithmus Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Programmieren bezeichnet die Tätigkeit, Computerprogramme zu erstellen. Das ist ein Teilbereich der Softwareentwicklung. Computerprogramme werden mit Hilfe einer Programmiersprache formuliert („codiert). Der Programmierer ‚übersetzt‘ dabei die vorgegebenen Anforderungen und Algorithmen in eine gewünschte Programmiersprache. Flow diagram Aus dem Englischen übersetzt Flussdiagramm ist ein Sammelbegriff für ein Diagramm, das einen Fluss oder eine Reihe Beziehungen in einem System darstellt. Flussdiagramme sind also Diagramme, die die einzelnen Schritte in einem Prozess aufzeigen. Trial and error „Versuch und Irrtum ist eine Methode, Probleme zu lösen, bei der so lange zulässige Lösungsmöglichkeiten versucht werden, bis die gewünschte Lösung gefunden wurde. Binärsuche Die binäre Suche ist ein Algorithmus, der auf einem Feld (also meist „in einer Liste) sehr effizient ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente in dem Feld entsprechend einer totalen Ordnungsrelation angeordnet („sortiert) sind, z.B. alphabetisch.