Algorithmen


Computer in Form von Handys, Tablets, PCs, TV-Sticks, Smart-Watches,... begleiten heute unser Leben. In diesem Kapitel werden Sie lernen, wie man einem Computer beibringt, das zu tun, was man von ihm möchte. Ein Computer ist ein Gerät, das mit Hilfe von Elektronen gesteuert wird. Daher kennt ein Computer nur zwei Zustände:

  • 1 (elektrischer Strom an)
  • 0 (elektrischer Strom aus).

Aus dem Kapitel Codierung wissen Sie bereits, dass eine Folge von 1 und 0 ein Wort aus unserer Sprache codieren kann. Im ASCII-Code wird das Wort "Hallo" wie folgt notiert:

Hallo = 01001000 01100001 01101100 01101100 01101111

Auf die gleiche Weise kann man Anweisungen, die ein Computer ausführen soll codieren. Beispiel:

10110000 01100001

Diese Bit-Folge bedeutet: hole den Wert 97 aus dem Speicherbereich ax des Arbeitsspeichers (siehe Wikipedia: Assembler). Eine Folge von 1 und 0 kann sich unser Gehirn kaum merken. Mit nur zwei Zeichen einem Computer etwas beibringen zu wollen, wird nicht wirklich erfolgreich sein.

Daher werden die 1er und 0er, welche der Computer verarbeiten soll, für uns Menschen mit Zeichen und Worten dargestellt, die sich unser Gehirn merken kann. Die Anweisung 10110000 01100001 wird mit der Zeichenfolge mov al, 61h notiert. Dies ist die Maschinensprache, mit welcher ein Computer programmiert werden kann. Ein Programm in Maschinensprache sieht dann z.B. wie folgt aus:

    DATA    SEGMENT                 ;Beginn des Datensegments
    Meldung db  "Hallo Welt"        ;- Zeichenkette „Hallo Welt“
            db  13, 10              ;- Neue Zeile
            db  "$"                 ;- Zeichen, das INT 21h, Unterfunktion 09h als Zeichenkettenende verwendet
    DATA    ENDS                    ;Ende des Datensegments

    CODE    SEGMENT                 ;Beginn des Codesegments
    Anfang:                         ;- Einsprung-Label fuer den Anfang des Programms
            mov ax, DATA            ;- Adresse des Datensegments in das Register „AX“ laden
            mov ds, ax              ;  In das Segmentregister „DS“ uebertragen (das DS-Register kann nicht direkt mit einer Konstante beschrieben werden)
            mov dx, OFFSET Meldung  ;- die zum Datensegment relative Adresse des Textes in das „DX“ Datenregister laden
                                    ;  die vollstaendige Adresse von „Meldung“ befindet sich nun im Registerpaar DS:DX
            mov ah, 09h             ;- die Unterfunktion 9 des Betriebssysteminterrupts 21h auswaehlen
            int 21h                 ;- den Betriebssysteminterrupt 21h aufrufen (hier erfolgt die Ausgabe des Textes am Schirm)
            mov ax, 4C00h           ;- die Unterfunktion 4Ch (Programmbeendigung) des Betriebssysteminterrupts 21h festlegen
            int 21h                 ;- diesen Befehl ausfuehren, damit wird die Kontrolle wieder an das Betriebssystem zurueckgegeben
    CODE    ENDS                    ;Ende des Codesegments

    END     Anfang                  ;- dem Assembler- und Linkprogramm den Programm-Einsprunglabel mitteilen
                                    ;- dadurch erhaelt der Befehlszaehler beim Aufruf des Programmes diesen Wert

Quelle: Beispielprogramm aus Wikipedia zu Assembler

Aber auch dieses Programm wäre ohne die Kommentare an der Seite völlig unverständlich. Daher wurden Hochsprachen entwickelt, bei denen mit englischen Worten und Zeichen ein Programm geschrieben wird. Hilfsprogramme (Interpreter, Compiler,...) machen daraus die 1en und 0en, die der Computer verarbeiten kann.

Das letzte Programm kann dann mit folgender Anweisung in der Hochsprache JavaScript aufgeschrieben werden:

alert("Hallo Welt");

Ein Handy kann inzwischen auf unfassbar vielfältige Weise Daten verarbeiten und darstellen. Sie können sich vorstellen, dass die Vielfalt der Anweisungen, um einem Computer so etwas beizubringen, beliebig vielfältig sind. Daher hat man in den letzten Jahren eine Methode entwickelt, der den Einstieg in die Programmierung deutlich vereinfachen soll:

Anweisungen werden als grafische Blöcke dargestellt, die man in einem Programm zusammenstellt. So muss man sich nicht die Anweisungen und deren Schreibweise in einer bestimmten Programmiersprache merken, sondern man kein ein Programm grafisch zusammenstellen. Aus dem grafischen Programm wird ein Programm in Hochsprache erzeugt, das der Computer in 1en und 0en umwandelt und dann ausführen kann.

Beispielsweise kann man mit folgenden Blöcken eine Zeichenfläche anlegen und darin einen Kreis zeichnen lassen:

Die gleichen Anweisungen in JavaScript sehen wie folgt aus:

Wenn die Anweisungen in einer Programmiersprache getippt werden, kann man Tippfehler machen, einen Befehl versehentlich falsch schreiben oder man erinnert sich nicht mehr an den Befehl. Das Programmieren mit einer selbst getippten Programmiersprache ist für Anfänger mühsam. In diesem Kurs werden Sie daher zuerst mit der Blocksprache programmieren lernen und später können Sie die Programme selbst tippen.

Aufgabe

Führe das folgende Programm aus, indem Du auf Play klickst.

Super, wir können den Computer mit Hilfe von JavaScript und p5.js etwas auf den Monitor schreiben lassen! Was genau machen diese beiden Anweisungen?

  • Mit textSize(32); wird dem Computer gesagt, dass alle Texte ab jetzt mit der Schriftgröße 32 auf den Monitor geschrieben werden sollen.
  • Mit text("Hallo", 10, 40); sagt man dem Computer, dass er den Text "Hallo" an der Stelle x = 10 und y = 40 auf den Monitor schreiben soll.
  • Beachte, dass jede Anweisung mit einem Strich-Punkt ; beendet werden.

Grundbaustein 1: Anweisung

Das grundlegendste Element eines Algorithmus ist die Anweisung. Anweisungen kennen Sie als Schülerin und Schüler zur Genüge. Eltern, Lehrkräfte, Trainer*innen,... alle wollen Ihnen sagen, was Sie zu tun haben. Das wird erst besser, wenn Sie volljährig sind. Aber auch dann haben Sie noch Chefs, Behörden,... von denen Sie Anweisungen bekommen.

In diesem Kurs können Sie bald selbst ausgiebig Anweisungen geben. Ihr Anweisungsempfänger wird der Computer sein. Sie haben bestimmt bereits ausgiebig Computern Anweisungen gegeben (z.B. "versende eine Mitteilung an Bob mit der Info, dass ich später komme,...").

Leider ist ein Computer nicht sehr intelligent, er kann lediglich sehr schnell 1 und 1 addieren. Damit ein Smartphone eine Mitteilung versenden kann, muss ein Programm programmiert worden sein, das dem Computer nur mit einer 1 und einer 0 klar macht, wie er eine Mitteilung versenden kann. Diesen Job erledigen Programmierinnen und Programmierer, die dafür spezielle Apps programmieren (Snapchat, Whatsapp, SimsMe,...). Sie werden bald sehen, wie das funktioniert.

Eine Anweisung nennt eine bestimmte Tätigkeit, die ausgeführt werden soll.

Beispiel: "Bring den Müll raus"

Bevor Sie eine solche Anweisung ausführen können, müssen Sie die Bedeutung der Worte kennen. Diese dürften Sie während Ihrer Kindheit gelernt haben.

  • Müll ist das, was man nicht mehr braucht und nicht aufheben möchte. Er befindet sich meistens in speziellen Behältern, den Mülleimern.
  • rausbringen bedeutet, dass draussen irgendwo eine große Mülltonne sein müsste, in die der Müllbeutel geworfen wird.
  • Jetzt muss Ihnen noch klar sein, welcher Müll in welche Tonne geworfen wird, auch das müssten Ihre Eltern Ihnen beigebracht haben.

Sie sehen, eine kurze Anweisung kann viel Wissen voraussetzen, damit sie richtig ausgeführt wird.


Grundbaustein 2: Sequenz

Viele Vorgänge in unserer Lebenswirklichkeit erfordern viele einzelne Schritte. Angenommen, Sie haben sturmfreie Bude, weil Ihre Eltern über das Wochenende verreist sind und Sie möchten zum Frühstück gerne ein hartgekochtes Ei essen. Im Internet finden Sie folgende Anleitung, die aus einer Sequenz (Aneinanderreihung) von Anweisungen besteht:

Beispiel: Hartgekochtes Ei

  • Bringe Wasser zum Kochen
  • Lege das rohe Ei vorsichtig mit Hilfe eines Esslöffels in das kochende Wasser
  • Lass das Ei 10 Minuten im kochenden Wasser kochen
  • Lass dann solange kaltes Wasser über das Ei fließen, bis dessen Temperatur angenehm ist.

Je komplexer eine Vorgang ist, desto mehr Anweisungen benötigt man, um diesen zu beschreiben. Man benötigt auch immer mehr Wissen, um bei den einzelnen Anweisungen zu verstehen, was man tun soll.


Grundelement 3: Verzweigung

In vielen Situationen kommt es vor, dass ein Algorithmus für verschiedene Situationen unterschiedlich abläuft. Dafür gibt es den Grundbaustein Verzweigung.

Beispiel: Wäsche waschen

Am sturmfreien Wochenende ist eine Party ganz leicht aus dem Ruder gelaufen und Sie müssen die Kissenüberzüge vom Sofa waschen. Auf dem Etikett steht "Buntwäsche 40°".

Auf der Waschmaschine steht dummerweise nichts von "Buntwäsche 40°". Als Programm haben Sie die Auswahl zwischen Baumwolle, Pflegeleicht, Feinwäsche, Wolle und Seide. Sie müssen eine Entscheidung treffen und je nach Entscheidung wird der Überzug sauber und unbeschädigt oder er wird sauber und dabei beschädigt oder er bleibt unbeschädigt, wird aber nicht sauber.

Sie entscheiden sich dafür, dass Sie der Meinung sind, dass der Bezug aus Baumwolle ist. Nachdem Sie das Baumwollprogramm eingestellt haben, verlangt die Waschmaschine weitere Entscheidungen:

  • Verschmutzungsgrad der Wäsche
  • Temperatur
  • Drehzahl beim Schleudern

Sie wählen das aus, was Sie für sinnvoll halten und hoffen, dass die Kissenbezüge sauber und unbeschadet die Waschmaschine verlassen werden.

Sie sehen, der Algorithmus, welcher die Waschmaschine steuert, erwartet von Ihnen einige Entscheidungen. Je nach Entscheidung läuft der Algorithmus anders ab. Man sagt, der Algorithmus verzweigt sich.


Grundbaustein 4: Schleife

Ein weiterer Grundbaustein eines Algorithmus ist die Schleife. Manche Sequenzen werden nach einer Verzweigung wiederholt.

Beispiel: Pfannkuchen

Algorithmus für das Ausbacken von 5 Pfannenkuchen:

  • Rühren Sie nach Rezept einen Pfannkuchenteig zusammen
  • Nehmen Sie eine Pfanne und erhitzen diese mit Stufe 6
  • Geben Sie etwas Backfett in die Pfanne
  • Geben Sie eine Kelle Teig in die Pfanne
  • Wenden Sie den Pfannkuchen, wenn der Teig durchgebacken ist
  • Nehmen Sie nach 2 min den Pfannkuchen aus der Pfanne
  • Geben Sie etwas Backfett in die Pfanne
  • Geben Sie eine Kelle Teig in die Pfanne
  • Wenden Sie den Pfannkuchen, wenn der Teig durchgebacken ist
  • Nehmen Sie nach 2 min den Pfannkuchen aus der Pfanne
  • Geben Sie etwas Backfett in die Pfanne
  • Geben Sie eine Kelle Teig in die Pfanne
  • Wenden Sie den Pfannkuchen, wenn der Teig durchgebacken ist
  • Nehmen Sie nach 2 min den Pfannkuchen aus der Pfanne
  • Geben Sie etwas Backfett in die Pfanne
  • Geben Sie eine Kelle Teig in die Pfanne
  • Wenden Sie den Pfannkuchen, wenn der Teig durchgebacken ist
  • Nehmen Sie nach 2 min den Pfannkuchen aus der Pfanne
  • Geben Sie etwas Backfett in die Pfanne
  • Geben Sie eine Kelle Teig in die Pfanne
  • Wenden Sie den Pfannkuchen, wenn der Teig durchgebacken ist
  • Nehmen Sie nach 2 min den Pfannkuchen aus der Pfanne
  • ...

Das ist unübersichtlich. Eleganter kann man es wie folgt formulieren:

Algorithmus für das Ausbacken von 5 Pfannenkuchen:

  • Rühren Sie nach Rezept einen Pfannkuchenteig zusammen
  • Nehmen Sie eine Pfanne und erhitzen diese mit Stufe 6
  • Wiederholen Sie folgende Anweisung 5 mal:
    • Geben Sie etwas Backfett in die Pfanne
    • Geben Sie eine Kelle Teig in die Pfanne
    • Wenden Sie den Pfannkuchen, wenn der Teig durchgebacken ist
    • Nehmen Sie nach 2 min den Pfannkuchen aus der Pfanne

Grundbausteine im Ablaufdiagramm

Am Beispiel des Siebs von Eratosthenes sollen die verschiedenen Elemente nochmals farblich unterschieden werden:

Abbildung 1

Quelltext: eratosthenes_farbe.zip

Sie können natürlich die Farben wählen, wie Sie möchten, solange Sie die Zuordnung festlegen und mitteilen.

Aufgabe 1:

Treffen Sie sich als das Team, mit dem Sie den Einkauf in einem Onlineshop als Algorithmus beschrieben haben.

Färben Sie das von Ihnen erstellte Ablaufdiagramm zum Einkauf in einem Onlineshop mit yEd Live, indem Sie für eine Anweisung, eine Sequenz, eine Verzweigung und eine Schleife jeweils eine andere Farbe verwenden. Definieren Sie die Farbgebung in einer Legende.

Speichern Sie das von Ihnen veränderte Ablaufdiagramm als GraphML-Datei mit dem Namen onlineshopping_farbe_name1_name2_name3.graphml und als Grafik mit dem Namen onlineshopping_farbe_name1_name2_name3.png in Ihrem Teamordner, wobei Sie für name1,... Ihre Namen einsetzen und lassen Sie Ihre Lösung der Lehrkraft zukommen.

(Wert: 5 XP)


Anwendungsbeispiel: Getränkeautomat

Aufgabe 2:

Erstellen Sie mit yEd Live für folgende Situation ein passend gefärbtes Ablaufdiagramm, indem Sie für eine Anweisung, eine Sequenz, eine Verzweigung und eine Schleife jeweils eine andere Farbe verwenden.

Ein Getränkeautomat bietet folgende Getränke zum Kauf an:

  • Wasser (50 Ct)
  • Limo (1 €)
  • Saft (1 €)

Sie kaufen von jedem Getränk eine Flasche.

Speichern Sie das von Ihnen erstellte Ablaufdiagramm als GraphML-Datei mit dem Namen getraenkeautomat_name.graphml und als Grafik mit dem Namen getraenkeautomat_name.png in Ihrem Teamordner, wobei Sie für name Ihren Namen einsetzen und lassen Sie Ihre Lösung der Lehrkraft zukommen.

(Wert: 10 XP)