Lektion 2.1

Algorithmen und Kontrollstrukturen

19 min Lesezeit

Du erklärst deinem Cousin, wie man ein Spiegelei macht. „Mach es halt fertig“ hilft ihm nicht. Du musst genau sagen: Pfanne auf den Herd, Öl hinein, warten, bis es heiß ist, Ei aufschlagen und so weiter. Eine Maschine ist noch strenger als dein Cousin, denn sie kann nicht raten, was du meinst.

Im Alltag folgst du ständig solchen Anleitungen: Rezepte, Spielregeln, Wegbeschreibungen. Auch hinter Navi und Suchmaschine stecken genaue Anleitungen. Wie muss eine Anleitung aussehen, damit eine Maschine sie ausführen kann? Und wie baust du sie aus wenigen Bausteinen zusammen?

Definition

Algorithmus und seine Eigenschaften

Ein Algorithmus ist eine Schrittfolge, die eine Aufgabe löst. Jeder einzelne Schritt heißt Anweisung. Ein Algorithmus für eine Maschine braucht vier Eigenschaften:

EigenschaftBedeutungSchlechtes Beispiel
eindeutigJeder Schritt ist genau beschrieben, nichts bleibt offen.„Rühre, bis es gut aussieht.“
ausführbarJeder Schritt lässt sich wirklich durchführen.„Geh durch die Wand zur Tür.“
endlichEr hört nach endlich vielen Schritten auf.„Schreibe alle Zahlen der Reihe nach auf.“
allgemeinEr löst alle Aufgaben einer Art, nicht nur eine einzelne.„Rechne 3 + 4“ statt „Addiere zwei beliebige Zahlen“

Ein Rezept erfüllt das oft nur halb („eine Prise Salz“ ist nicht eindeutig). Ein Programm ist ein Algorithmus in einer Form, die ein Computer ausführen kann.

Definition

Sequenz, Verzweigung und Wiederholung

Aus diesen Bausteinen, den Kontrollstrukturen, baust du jeden Algorithmus:

  • Sequenz: Anweisungen laufen nacheinander in fester Reihenfolge. Die Reihenfolge zählt: Erst die Socken, dann die Schuhe.
  • Verzweigung: Der Algorithmus wählt je nach Bedingung einen Weg. Eine Bedingung ist eine Aussage, die wahr oder falsch ist, zum Beispiel „es regnet“ oder „alter ist kleiner als 6“. Man schreibt: falls Bedingung, dann Anweisungen, sonst andere Anweisungen.
  • Wiederholung: Anweisungen laufen mehrfach. Bei fester Anzahl heißt es „wiederhole 4 mal“. Mit Bedingung heißt es „wiederhole, solange Bedingung“: Die Bedingung wird vor jedem Durchlauf geprüft, und es geht weiter, solange sie wahr ist. Wird sie nie falsch, läuft der Algorithmus ewig. Das ist eine Endlosschleife und verletzt die Eigenschaft „endlich“.
Definition

Variable

Eine Variable ist ein Speicherplatz mit einem Namen, in dem ein Wert liegt. Stell dir eine Schachtel mit Aufschrift vor. Du kannst den Wert lesen und ändern. Wenn du einen neuen Wert hineinlegst, ist der alte weg. Mit „setze punkte auf 0“ legst du einen Startwert fest. Mit „ändere punkte um 1“ erhöhst du den Wert um 1. So merkt sich ein Programm Zwischenergebnisse, zum Beispiel einen Punktestand.

Definition

Programme als Blöcke und als Tabelle

In einer blockbasierten Programmierumgebung (zum Beispiel Scratch) steckst du ein Programm aus bunten Blöcken zusammen. Es gibt Blöcke für Sequenz, Verzweigung, Wiederholung und Variablen. Weil die Blöcke nur an passenden Stellen einrasten, gibt es keine Tippfehler. Hier schreiben wir Programme als Tabelle: Jede Zeile ist ein Block. Die Spalte „Einrückung“ zeigt, wie tief der Block in einem anderen steckt, zum Beispiel in einer Wiederholung.

Beispiel

Variable und Wiederholung mit fester Anzahl

Was sagt dieses Programm?

ZeileEinrückungAnweisung
10setze zahl auf 2\texttt{setze zahl auf 2}
20wiederhole 3 mal\texttt{wiederhole 3 mal}
31setze zahl auf zahl mal 2\texttt{setze zahl auf zahl mal 2}
40sage zahl\texttt{sage zahl}

Zeile 1 legt zahl = 2 fest. Zeile 3 steht eingerückt in der Wiederholung und läuft dreimal. Du notierst den Wert nach jedem Durchlauf:

Standzahl
Start2
nach Durchlauf 14
nach Durchlauf 28
nach Durchlauf 316

Danach sagt Zeile 4 den Wert 16.

Beispiel

Wiederholung mit Bedingung

Du hast 20 Euro und sparst jede Woche 5 Euro, bis du mindestens 50 Euro hast. Nach wie vielen Wochen ist das Ziel erreicht?

ZeileEinrückungAnweisung
10setze geld auf 20\texttt{setze geld auf 20}
20setze wochen auf 0\texttt{setze wochen auf 0}
30wiederhole, solange geld kleiner als 50\texttt{wiederhole, solange geld kleiner als 50}
41a¨ndere geld um 5\texttt{ändere geld um 5}
51a¨ndere wochen um 1\texttt{ändere wochen um 1}
60sage wochen\texttt{sage wochen}

Du gehst das Programm von Hand durch:

Standgeldwochen
Start200
nach Durchlauf 1251
nach Durchlauf 2302
nach Durchlauf 3353
nach Durchlauf 4404
nach Durchlauf 5455
nach Durchlauf 6506

Vor einem siebten Durchlauf prüft der Computer: Ist 50 kleiner als 50? Nein. Die Wiederholung endet, und das Programm sagt 6.

Definition

Flussdiagramm und Struktogramm

Algorithmen kann man zeichnen. Im Flussdiagramm verbinden Pfeile verschiedene Formen: ein Oval für Start und Ende, ein Rechteck für eine Anweisung und eine Raute für eine Verzweigung mit zwei Ausgängen „ja“ und „nein“. Im Struktogramm stehen Kästchen untereinander. Jede Anweisung ist ein Kästchen. Eine Verzweigung ist ein Kästchen mit zwei Spalten für „ja“ und „nein“. Eine Wiederholung ist ein Kästchen mit Kopfzeile, in dem die wiederholten Anweisungen eingerückt stehen. Beide Darstellungen zeigen den Ablauf, ohne dass du eine Programmiersprache brauchst.

Beispiel

Ein Flussdiagramm lesen

Ein Schwimmbad (ausgedachte Preise): Kinder unter 6 Jahren zahlen nichts, Personen von 6 bis 17 Jahren zahlen 4 Euro, ab 18 Jahren zahlen sie 8 Euro. Das Flussdiagramm, als Tabelle geschrieben:

NrFormInhaltWeiter bei
1OvalStart2
2RauteIst alter kleiner als 6?ja: 3, nein: 4
3Rechtecksetze preis auf 07
4RauteIst alter kleiner als 18?ja: 5, nein: 6
5Rechtecksetze preis auf 47
6Rechtecksetze preis auf 87
7OvalEnde: sage preiskeiner

Welchen Weg gehen Alter 5, Alter 12 und Alter 18?

Alter 5: Nr 2 ist ja, weiter zu Nr 3, der Preis ist 0 Euro. Alter 12: Nr 2 ist nein, weiter zu Nr 4. Dort ist es ja, also Nr 5 und 4 Euro. Alter 18: Nr 2 ist nein, Nr 4 ist ebenfalls nein, also Nr 6 und 8 Euro.

Gute Testfälle liegen an den Grenzen. Alter 6: Nr 2 ist nein, denn 6 ist nicht kleiner als 6. Nr 4 ist ja. Der Preis ist 4 Euro. Alter 17 zahlt ebenfalls 4 Euro.

Beispiel

Einen Fehler finden und beheben

Eine Spielfigur soll ein Quadrat mit 50 Schritten Seitenlänge laufen. Beim Test fehlt die vierte Seite.

ZeileEinrückungAnweisung
10wiederhole 3 mal\texttt{wiederhole 3 mal}
21gehe 50 Schritte\texttt{gehe 50 Schritte}
31drehe dich um 90 Grad nach rechts\texttt{drehe dich um 90 Grad nach rechts}

Ein Programm entsteht in fünf Schritten: Aufgabe verstehen, Algorithmus entwerfen, in Blöcken umsetzen, mit bekannten Fällen testen und Fehler beheben. Hier zeigt der Test den Fehler. Du gehst das Programm von Hand durch: Die Figur läuft drei Seiten und dreht sich dreimal, dann endet die Wiederholung. Ein Quadrat hat vier Seiten, also muss die Wiederholung 4 mal laufen. Nach der Änderung testest du noch einmal: Die Figur läuft vier Seiten und steht wieder am Start.

Definition

Algorithmen in der Gesellschaft

Algorithmen steuern viele Dinge um dich herum: Navigations-Apps berechnen Routen, Ampeln schalten nach Regeln, Videodienste empfehlen dir, was du als Nächstes ansehen sollst. Algorithmen arbeiten schnell, ermüden nicht und machen bei gleichen Daten dieselben Schritte.

Dem steht gegenüber: Ein Algorithmus tut nur, was in ihm steht. Sind die Regeln oder die Daten einseitig, sind es auch die Ergebnisse. Empfehlungen können dir immer ähnliche Inhalte zeigen. Bei wichtigen Entscheidungen, etwa bei Bewerbungen oder Krediten, sollten Menschen nachprüfen können, wie ein Ergebnis zustande kam, und die Verantwortung behalten.

Häufige Fehler

Der Computer errät, was gemeint ist

„Ich schreibe nur ‚zeichne ein Haus‘. Das versteht der Computer schon.“

Richtig ist

Ein Computer führt genau das aus, was dasteht, und nicht mehr. Du musst jeden Schritt eindeutig beschreiben: Wie groß, wo, in welcher Reihenfolge? Rate nie, dass die Maschine etwas „schon richtig macht“. Teste es.

Häufige Fehler

Eine Variable merkt sich alle Werte

„Nach setze zahl auf 5 und setze zahl auf 7 steht in zahl sowohl die 5 als auch die 7.“

Richtig ist

Eine Variable hat zu jedem Zeitpunkt genau einen Wert. Wenn du einen neuen Wert hineinlegst, ist der alte überschrieben. Nach den beiden Anweisungen steht in zahl nur die 7. Willst du den alten Wert behalten, brauchst du eine zweite Variable.

Zusammenfassung

  • Ein Algorithmus ist eine Schrittfolge zur Lösung einer Aufgabe. Er soll eindeutig, ausführbar, endlich und allgemein sein.

  • Die Bausteine sind Sequenz, Verzweigung und Wiederholung. Die Wiederholung gibt es mit fester Anzahl und mit Bedingung.

  • Eine Bedingung ist wahr oder falsch. Wird die Bedingung einer Wiederholung nie falsch, entsteht eine Endlosschleife.

  • Eine Variable ist ein benannter Speicherplatz mit genau einem Wert, den man ändern kann.

  • Flussdiagramm und Struktogramm zeigen den Ablauf: Raute oder Kästchen mit zwei Spalten für die Verzweigung, Rechtecke für Anweisungen.

  • Ein Programm entsteht durch Entwerfen, Umsetzen, Testen und Fehlerbeheben. Du gehst es dabei von Hand durch und notierst die Variablenwerte.

  • Algorithmen sind in der Gesellschaft allgegenwärtig. Sie tun nur, was in ihnen steht, und ihre Ergebnisse müssen Menschen prüfen können.

Übungen

Aufgabe 1Multiple Choice

Welche Anweisung verletzt die Eigenschaft „endlich“?

Aufgabe 2Numerisch

Ein Programm lautet: Setze summe auf 0. Setze n auf 1. Wiederhole, solange n kleiner als 5 ist: Ändere summe um n, ändere n um 1. Sage summe. Welche Zahl sagt das Programm?

Aufgabe 3Numerisch

Du hast 12 Euro und sparst jede Woche 4 Euro, bis du mindestens 30 Euro hast. Nach wie vielen Wochen hörst du auf?

Aufgabe 4Numerisch

Das Schwimmbad ändert seine Regel: Kinder unter 8 Jahren zahlen nichts, Personen von 8 bis 17 Jahren zahlen 4 Euro, ab 18 Jahren zahlen sie 8 Euro. Wie viel Euro zahlt jemand, der genau 8 Jahre alt ist?

Aufgabe 5Freitext

Ein Programm lautet: Setze zahl auf 1. Wiederhole, solange zahl kleiner als 10 ist: Sage zahl. Was geht schief, und wie behebst du den Fehler?