#separator:tab #html:true #tags:algorithms-and-programs-quiz #columns:Vorderseite Rückseite

Jemand hält farbige Karten hoch, und du befolgst vier Schritte: auf die Karte schauen, entscheiden, welche Farbe sie hat, ihr Zeichen notieren, auf die nächste Karte warten. Was macht diese Anleitung zu einem Algorithmus?

  1. Dass sie sich auf einen Computer übertragen ließe, denn nur was ein Rechner ausführen könnte, zählt als Algorithmus.
  2. Dass die Schritte so genau beschrieben sind, dass man sie ausführen kann, ohne zu verstehen, wozu sie dienen.
  3. Dass sie aus wenigen, überschaubaren Schritten besteht, die man sich ohne Aufschreiben merken kann.
  4. Dass sie in einer Programmiersprache aufgeschrieben ist, denn erst eine feste Syntax macht aus einer Anleitung einen Algorithmus.

Was einen Algorithmus ausmacht, ist die Genauigkeit seiner Schritte, nicht die Maschine und nicht die Sprache.

Worin liegt der Unterschied zwischen einem Algorithmus und einem Programm?

  1. Ein Programm ist die fortgeschrittene Stufe eines Algorithmus, die erst nötig wird, wenn ein Problem für die Bearbeitung von Hand zu groß ist.
  2. Ein Algorithmus beschreibt, wie gerechnet wird; ein Programm legt fest, wie die Daten dafür gespeichert und verwaltet werden.
  3. Ein Programm ist derselbe Ablauf, aber so vollständig aufgeschrieben, dass eine Maschine ihn ausführen kann.
  4. Es gibt keinen wesentlichen: Beide sind eindeutige Schrittfolgen, und welches Wort man benutzt, hängt vom Fachgebiet ab.

Ein Programm ist eine Liste von Anweisungen, die ein Computer genau und der Reihe nach befolgt; es darf sich also nicht darauf verlassen, dass jemand Gemeintes ergänzt.

Was siehst du an der Lampe, wenn dieses Programm läuft?

lamp.set_color(255, 0, 0)
time.sleep(1)
lamp.set_color(0, 0, 255)
  1. Eine Sekunde Rot, danach Blau.
  2. Rot und Blau gleichzeitig, also Violett.
  3. Nur Blau, weil die erste Zeile übersprungen wird.
  4. Nur Rot: Die Lampe behält die erste Farbe, die sie bekommt, bis das Programm endet.

Der Computer führt die Zeilen in der Reihenfolge aus, in der sie stehen, und jede ändert den Zustand, den die nächste vorfindet.

Jemand wundert sich: „Die Lampe wird nie rot, dabei steht es doch da!“ Was ist los?

lamp.set_color(255, 0, 0)
lamp.set_color(0, 0, 255)
  1. Die erste Zeile enthält einen Fehler, den die Maschine stillschweigend überspringt; sonst müsste Rot zu sehen sein.
  2. Die zweite Zeile ersetzt die erste, bevor diese läuft: Bei zwei gleichartigen Befehlen gilt nur der letzte.
  3. Rot leuchtet, aber nur für einen winzigen Bruchteil einer Sekunde; ohne Pause ist das für das Auge unsichtbar.
  4. Die Lampe reagiert träge: Bei zwei so schnell folgenden Befehlen kommt nur der letzte an, der erste geht in der Hardware verloren.

Ein Computer wartet nur dort, wo das Programm es ihm sagt.

Welche Rolle spielt der Teil (255, 0, 0) in dieser Zeile?

lamp.set_color(255, 0, 0)
  1. Er sagt, welche Lampe angesprochen wird: Die drei Zahlen kennzeichnen, welche von mehreren Lampen gemeint ist.
  2. Er sagt, mit welchen Werten die Anweisung ausgeführt wird: voller Rotanteil, kein Grün, kein Blau.
  3. Er ist eine Notiz für Lesende, die den gewünschten Rotanteil erklärt; ausgeführt wird nur der Teil vor der Klammer.
  4. Er sagt, wie lange die Anweisung läuft: 255 Millisekunden lang, danach ist die Lampe wieder aus.

Eine Anweisung nennt ein Ding, was damit geschehen soll und mit welchen Werten; andere Werte ändern das Ergebnis, während die Anweisung dieselbe bleibt.

Welchen Vorteil bringt die erste Zeile, bright = 255?

bright = 255
lamp.set_color(bright, 0, 0)
time.sleep(1)
lamp.set_color(bright, bright, 0)
  1. Das Programm läuft schneller, weil die Maschine den Wert nur einmal lesen muss statt bei jedem Aufruf neu.
  2. Ohne sie bliebe die Lampe dunkel, denn erst diese Zeile schaltet die Helligkeit auf den Höchstwert.
  3. Die Helligkeit lässt sich an genau einer Stelle ändern statt an jeder Verwendung.
  4. Namen sind Pflicht: Eine Anweisung wie set_color nimmt nur benannte Werte an, keine nackten Zahlen in der Klammer.

Ein Wert mit einem Namen gibt dir eine Stelle zum Ändern statt vieler.

Wie lange läuft dieses Programm ungefähr, und was zeigt die Lampe?

colors = [(255, 0, 0), (0, 255, 0),
          (0, 0, 255), (255, 255, 0)]
for r, g, b in colors:
    lamp.set_color(r, g, b)
    time.sleep(1)
  1. Eine Sekunde: Die Schleife zeigt alle vier Farben gleichzeitig.
  2. Etwa vier Sekunden: vier Durchläufe, in denen je eine Farbe eine Sekunde lang leuchtet.
  3. Unendlich: Eine for-Schleife läuft, bis man sie abbricht.
  4. Vier Sekunden, aber nur die letzte Farbe, Gelb, ist je zu sehen.

Eine Schleife ist eine Schreibweise: Dieselben Zeilen laufen einmal je Wert, ein Durchlauf nach dem anderen.

Wie lange läuft dieses Programm insgesamt, ungefähr?

colors = [(255, 0, 0), (255, 255, 0), (0, 0, 255)]
for r, g, b in colors:
    lamp.set_color(r, g, b)
    if (r, g, b) == (255, 255, 0):
        time.sleep(3)
    else:
        time.sleep(1)
  1. 3 Sekunden
  2. 9 Sekunden
  3. 5 Sekunden
  4. 4 Sekunden

Eine Bedingung wird in jedem Durchlauf neu geprüft, deshalb hängt der Ablauf vom jeweiligen Wert ab.

Aus welchen Bausteinen ist jedes Programm gebaut? Kreuz alle an, die dazugehören. (Mehrere richtige Antworten möglich.)

  1. Anweisungen, die nacheinander laufen.
  2. Werte, die einen Namen bekommen.
  3. Wiederholung.
  4. Bedingungen: Etwas geschieht nur, wenn etwas zutrifft.

Alle vier zusammen sind das ganze Baumaterial: Abfolge, benannte Werte, Wiederholung und Bedingung.

"

Dein Programm bricht mit dieser Meldung ab. Was fängst du damit an?

Traceback (most recent call last):
  File ""blink.py"", line 7, in <module>
    lamp.set_colour(255, 0, 0)
AttributeError: 'Lamp' object has no attribute 'set_colour'. Did you mean: 'set_color'?
  1. Der Rechner ist abgestürzt; nach einem Neustart läuft das Programm meist wieder, denn solche Meldungen kommen und gehen.
  2. Die Meldung nennt Datei, Zeile und Ursache: In Zeile 7 steht set_colour, das es nicht gibt; gemeint war set_color.
  3. Das Programm überfordert den Rechner; die Meldung zeigt, dass er beim Ausführen von Zeile 7 nicht mehr mitgekommen ist.
  4. Die Meldung ist eine Warnung, die du überlesen kannst: Das Programm läuft nach Zeile 7 weiter, und die Lampe leuchtet trotzdem.
"

Der Computer hat ausgeführt, was dastand, und meldet genau, wo er hängen geblieben ist; die letzte Zeile der Meldung nennt die Ursache.

Wann endet dieses Programm?

while True:
    lamp.set_color(255, 0, 0)
    time.sleep(1)
    lamp.set_color(0, 0, 255)
    time.sleep(1)
  1. Wenn beide Farben einmal gezeigt wurden, denn dann ist der Körper der Schleife vollständig abgearbeitet.
  2. Nach einer Weile von selbst, wenn die Maschine merkt, dass nichts Neues passiert.
  3. Nie: Die Bedingung ist immer wahr, und der Körper der Schleife hat keinen Ausweg.
  4. Nach einer festen Zahl von Wiederholungen, denn jede Schleife hat eine eingebaute Obergrenze, damit die Maschine nicht hängen bleibt.

Eine Schleife endet nur, wenn ihr Ende erreichbar ist; while True ohne Ausweg läuft für immer.

Beim Zahlenraten zwischen 1 und 100 führen zwei Verfahren sicher zum Ziel: alle Zahlen einzeln abfragen (bis zu 99 Fragen) oder den Bereich halbieren (höchstens 7 Fragen). Was folgt daraus?

  1. Nur das Halbieren verdient den Namen Algorithmus; das einzelne Abfragen ist bloßes Ausprobieren ohne Verfahren.
  2. Eine Lösung kann richtig und trotzdem unbrauchbar sein; Verfahren vergleicht man nach ihrem Aufwand.
  3. Bei modernen Computern spielt der Unterschied keine Rolle mehr, weil beide Verfahren ohnehin in Sekundenbruchteilen fertig sind.
  4. Das langsame Verfahren ist sicherer, weil es jede Zahl ausdrücklich prüft, und deshalb vorzuziehen.

Entscheidend ist, wie der Aufwand mit der Größe des Problems wächst.

Sechs Personen sortieren sich nach diesen Regeln der Größe nach: auf den rechten Nachbarn schauen, tauschen, wenn man größer ist, am Ende der Reihe wieder links anfangen. Woran erkennt dieser Ablauf, dass er fertig ist?

  1. Nach genau einem Durchgang durch die Reihe, denn dann hat jede Person ihren Nachbarn einmal geprüft.
  2. Wenn die Personen sehen, dass die Reihe sortiert aussieht.
  3. An einem vollständigen Durchgang, in dem niemand mehr getauscht hat.
  4. Gar nicht von selbst: Wie bei jeder Wiederholung von vorn muss jemand von außen abbrechen, sobald die Reihe stimmt.

Bubblesort endet nach seiner eigenen Regel: einem Durchgang ohne Vertauschung.

Was zeigt die Lampe, wenn dieses Programm läuft?

lamp.set_color(255, 0, 0)
lamp.set_color(0, 0, 255)
time.sleep(1)
  1. Eine Sekunde Rot, dann Blau: Das time.sleep(1) gehört erkennbar zur roten Phase.
  2. Eine Sekunde Blau, dann Rot: Die Pause hält die zuletzt gesetzte Farbe fest, und die erste Zeile wird danach nachgeholt.
  3. Rot nur für einen Sekundenbruchteil, dann eine Sekunde Blau.
  4. Das Programm ist fehlerhaft und startet nicht, weil time.sleep(1) als letzte Zeile nicht erlaubt ist.

Es fehlt keine Zeile, und trotzdem macht die Reihenfolge ein anderes Programm daraus.