Algorithmen und Kontrollstrukturen
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?
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:
| Eigenschaft | Bedeutung | Schlechtes Beispiel |
|---|---|---|
| eindeutig | Jeder Schritt ist genau beschrieben, nichts bleibt offen. | „Rühre, bis es gut aussieht.“ |
| ausführbar | Jeder Schritt lässt sich wirklich durchführen. | „Geh durch die Wand zur Tür.“ |
| endlich | Er hört nach endlich vielen Schritten auf. | „Schreibe alle Zahlen der Reihe nach auf.“ |
| allgemein | Er 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.
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“.
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.
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.
Variable und Wiederholung mit fester Anzahl
Variable und Wiederholung mit fester Anzahl
Was sagt dieses Programm?
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 0 | |
| 3 | 1 | |
| 4 | 0 |
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:
| Stand | zahl |
|---|---|
| Start | 2 |
| nach Durchlauf 1 | 4 |
| nach Durchlauf 2 | 8 |
| nach Durchlauf 3 | 16 |
Danach sagt Zeile 4 den Wert 16.
Wiederholung mit Bedingung
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?
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 0 | |
| 3 | 0 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 0 |
Du gehst das Programm von Hand durch:
| Stand | geld | wochen |
|---|---|---|
| Start | 20 | 0 |
| nach Durchlauf 1 | 25 | 1 |
| nach Durchlauf 2 | 30 | 2 |
| nach Durchlauf 3 | 35 | 3 |
| nach Durchlauf 4 | 40 | 4 |
| nach Durchlauf 5 | 45 | 5 |
| nach Durchlauf 6 | 50 | 6 |
Vor einem siebten Durchlauf prüft der Computer: Ist 50 kleiner als 50? Nein. Die Wiederholung endet, und das Programm sagt 6.
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.
Ein Flussdiagramm lesen
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:
| Nr | Form | Inhalt | Weiter bei |
|---|---|---|---|
| 1 | Oval | Start | 2 |
| 2 | Raute | Ist alter kleiner als 6? | ja: 3, nein: 4 |
| 3 | Rechteck | setze preis auf 0 | 7 |
| 4 | Raute | Ist alter kleiner als 18? | ja: 5, nein: 6 |
| 5 | Rechteck | setze preis auf 4 | 7 |
| 6 | Rechteck | setze preis auf 8 | 7 |
| 7 | Oval | Ende: sage preis | keiner |
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.
Einen Fehler finden und beheben
Einen Fehler finden und beheben
Eine Spielfigur soll ein Quadrat mit 50 Schritten Seitenlänge laufen. Beim Test fehlt die vierte Seite.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 |
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.
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.
Der Computer errät, was gemeint ist
Der Computer errät, was gemeint ist
„Ich schreibe nur ‚zeichne ein Haus‘. Das versteht der Computer schon.“
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.
Eine Variable merkt sich alle Werte
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.“
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
Welche Anweisung verletzt die Eigenschaft „endlich“?
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?
Du hast 12 Euro und sparst jede Woche 4 Euro, bis du mindestens 30 Euro hast. Nach wie vielen Wochen hörst du auf?
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?
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?