Algorithmen und informatisches Denken

Schreibe den Algorithmus als Liste nummerierter Schritte auf, um ein Käsebrot zu machen, sodass eine Person, die noch nie eines gemacht hat, ihn ohne Zweifel befolgen kann. Überprüfe deine Liste und kontrolliere, ob keine Schritte fehlen, die du als selbstverständlich vorausgesetzt hast.

Bestimme im Rezept „Spiegelei braten“ die Eingabe (die Zutaten und Utensilien), die Verarbeitung (die Schritte mit Herd und Pfanne) und die Ausgabe (das Ergebnis). Erkläre, warum es beim Schreiben klarer Algorithmen hilft, so zu denken.

Ein Rezept sagt: „Rühre die Soße, bis sie dick wird.“ Erkläre, warum ein Algorithmus immer enden muss und was passieren könnte, wenn die Soße nie dick würde. Formuliere diesen Schritt so um, dass der Koch nicht für immer weiterrührt.

Diese Schritte des Algorithmus „zur Schule gehen“ sind durcheinander: (a) das Klassenzimmer betreten, (b) aufstehen, (c) frühstücken, (d) das Haus verlassen, (e) sich anziehen, (f) zur Schule gehen. Bringe sie in die richtige Reihenfolge und ergänze den Algorithmus um eine Entscheidung: Was ist zu tun, wenn es beim Verlassen des Hauses regnet?

Lies diesen Algorithmus: (1) nimm das Kartenspiel, (2) solange noch Karten in der Hand sind, gib jedem Spieler eine Karte, beginnend links von dir, (3) wenn keine Karten mehr übrig sind, sage „verteilt“. Erkläre in einem Satz, was der Algorithmus tut, und gib an, welcher Teil die Wiederholung ist und wann sie endet.

Erstelle eine Ablaufverfolgung (Trace) dieses Algorithmus mit $n = 7$: (1) beginne mit dem Wert $n$, (2) wiederhole dreimal: addiere 2, (3) subtrahiere 5, (4) gib das Ergebnis aus. Notiere den Wert nach jedem Schritt, gib das Endergebnis an und erkläre, was eine Ablaufverfolgung ist und wozu man sie von Hand durchführt.

Schreibe den Algorithmus, um zu zählen, wie viele Personen durch die Klassenzimmertür kommen, wobei du nur eine Variable „Zähler“ verwendest, die bei 0 beginnt: Was tust du jedes Mal, wenn jemand hereinkommt, woher weißt du, wann du mit dem Zählen aufhören sollst, und welchen Wert hat der Zähler am Ende?

Die Abbildung zeigt mit ineinandergesteckten Blöcken den Algorithmus einer automatischen Leselampe, die sich nur einschalten soll, wenn es wenig Licht gibt, aber ein Block fehlt.

Gib an, welchen Block du in die Lücke setzen würdest, und erkläre mit eigenen Worten Schritt für Schritt, wie der vollständige Algorithmus funktioniert.

Viele Alltagsgeräte folgen Algorithmen. Wähle zwei aus dieser Liste – Waschmaschine, Mikrowelle, Ampel – und beschreibe für jedes, welche Daten es erhält (Eingabe), was es entscheidet oder wiederholt (Verarbeitung) und was es am Ende tut (Ausgabe).

Zum Sortieren eines Kartenspiels gibt es mehrere verschiedene Algorithmen, und manche sind schneller als andere. Erkläre an einem Beispiel aus dem Alltag, dass dasselbe Problem von mehreren Algorithmen gelöst werden kann und was es bedeutet, dass einer „besser“ ist als ein anderer.

Ein Rezept sagt: „Gib Salz dazu und lass es eine Weile bei mittlerer Hitze kochen.“ Erkläre, warum ein Computer diese Anweisung nicht befolgen könnte, und formuliere sie als präzisen Algorithmusschritt um, mit Mengen, Zeiten und der Angabe, wie man überprüft, dass der Schritt beendet ist.

Dieser Algorithmus „Wäsche waschen“ enthält einen Fehler: (1) die gesamte Wäsche in die Waschmaschine geben, weiße und bunte zusammen, (2) Waschmittel hinzufügen, (3) das lange Programm mit heißem Wasser wählen, (4) aufhängen. Finde zwei problematische Schritte, erkläre, was bei jedem schiefgehen kann, und schreibe den korrigierten Algorithmus mit einem vorherigen Sortierschritt auf.

Zerlege das Problem „das Schuljahresabschlussfest organisieren“ in vier kleinere Teilprobleme und schreibe für jedes zwei konkrete Schritte zur Lösung auf. Erkläre, welchen Vorteil es hat, ein großes Problem auf diese Weise aufzuteilen.

Muster erkennen heißt, die Regel zu finden, die sich wiederholt. Finde das Muster dieser drei Folgen und formuliere es als klare Regel: (a) 5, 10, 15, 20, …, (b) 100, 90, 80, 70, …, (c) Montag: 1 Liegestütz, Dienstag: 2, Mittwoch: 4, Donnerstag: 8, … Gib an, welcher Wert jeweils als Nächstes käme.

Der U-Bahn-Plan zeichnet nicht die reale Stadt: Er lässt Entfernungen, Kurven und Straßen weg und behält nur Haltestellen und Verbindungen. Erkläre anhand dieses Beispiels, was Abstraktion ist, und wende sie dann auf den Plan deiner Schule an: Welche drei Dinge würdest du aufnehmen und welche drei weglassen?

Du kannst es auf Papier machen und ein Foto mit deiner Antwort senden.

Du suchst das Wort „Fledermaus“ in einem Wörterbuch mit 500 Seiten. Vergleiche diese beiden Algorithmen: auf der ersten Seite aufschlagen und Seite für Seite weitergehen, oder in der Mitte aufschlagen und jeweils die Hälfte verwerfen, die nicht infrage kommt. Erkläre, welcher effizienter ist, warum er nur funktioniert, wenn die Seiten geordnet sind, und schätze, wie viele „Aufschläge“ jede Methode benötigt.

Zwei Personen bereiten gemeinsam das Frühstück für vier Gäste vor: Es müssen Kaffee gekocht, Brot getoastet, Saft gepresst und der Tisch gedeckt werden. Verteile die Aufgaben auf die beiden und beachte dabei die Abhängigkeiten (der Kaffee kann nicht serviert werden, bevor er gekocht ist). Erkläre, welche Aufgaben gleichzeitig erledigt werden können und welche nicht, und gib die Reihenfolge an.

Der Algorithmus einer Kantine gibt jedem Gast ein Brötchen aus, funktioniert aber nicht, wenn es mehr Gäste als Brötchen gibt. Erkläre, was ein „Grenzfall“ in einem Algorithmus ist, schlage vor, wie sich die Ausgabe in dieser Situation verhalten sollte, und formuliere den problematischen Schritt so um, dass der Algorithmus nicht mehr scheitert.

Ein Geldautomat hat nur Geldscheine zu $20\ \text{€}$ und sein Algorithmus teilt den gewünschten Betrag in Scheine auf. Erkläre, was passiert, wenn jemand $75\ \text{€}$ abhebt, warum das ein Grenzfall ist, und formuliere die Regeln des Automaten so um, dass er immer eine sinnvolle Antwort gibt.

Entwirf den vollständigen Algorithmus mit nummerierten Schritten, die Entscheidungen und Wiederholungen enthalten, für eine Fußgängerampel mit Taster: Was geschieht, vom Drücken des Tasters bis zur Rückkehr der Ampel in ihren Ausgangszustand, einschließlich der Zeiten jeder Lichtphase.

Stell dir ein Programm vor, das Tic-Tac-Toe spielt. Beschreibe die Strategie, der es in jedem Zug folgen würde: Welche Daten des Spielfelds muss es betrachten, in welcher Reihenfolge, und welche Regeln würdest du verwenden, um zu entscheiden, wohin der Spielstein gesetzt wird? Du musst keinen Code schreiben: Die Regeln in natürlicher Sprache genügen.

Die Abbildung zeigt mit ineinandergesteckten Blöcken das Grundgerüst eines Spiels, in dem eine geheime Zahl erraten werden soll. In der Schleife fehlt jedoch ein Baustein, damit das Spiel dem Spieler Hinweise gibt.

Beschreibe, welchen Block (oder welche Blöcke) du in die Lücke setzen würdest, damit das Spiel dem Spieler sagt, ob seine Zahl größer oder kleiner als die geheime Zahl ist, und erkläre die vollständige Funktionsweise des Algorithmus: Was wird wiederholt, wann endet er und was passiert, wenn der Spieler gleich beim ersten Versuch richtig rät?

Für das Recycling im Klassenraum werden zwei Algorithmen vorgeschlagen: (a) Jeden Tag trennt die zuständige Person den gesamten Müll des Tages in die drei Behälter, und (b) jede Woche sortiert reihum ein Zweierteam das Angesammelte. Bewerte beide anhand der Kriterien Gesamtzeit, Sortierfehler und Verteilung des Aufwands und entscheide dich begründet für einen.