inf-schule | Algorithmen » Strukturierung – Ein schwierigeres Problem lösen

Strukturierung – Ein schwierigeres Problem lösen

Zielsetzung

Du hast in der Erkundung ein schwieriges Problem bearbeitet und gelöst. Jetzt werden wir dieses Problem noch einmal etwas genauer untersuchen und dabei wichtige Konzepte herausarbeiten.

Algorithmen und Programme

Eines der wichtigsten Ziele der Informatik ist es, Probleme automatisiert zu lösen. Dabei geht es darum, ein Lösungsverfahren so zu beschreiben, dass es auch von einer Maschine abgearbeitet werden kann. Weil eine Maschine nicht „mitdenkt“, muss die Beschreibung dafür sehr präzise sein.

Aufgabe 1: Verfahrensbeschreibungen untersuchen

Betrachte die folgenden Verfahrensbeschreibungen – alle beziehen sich auf das Problem aus der Erkundung. Welche von ihnen sind so präzise, dass sie (zumindest theoretisch) von einer Maschine abgearbeitet werden könnten? Begründe.

(a) Textuelle Beschreibung:

Laufe an den Bäumen vorbei, bis du auf einem Blatt stehst. 
Hebe das Blatt dann auf.

(b) Textuelle Beschreibung:

SOLANGE nicht auf einem Kleeblatt:
    WENN vor einem Baum:
        Baum/Baumreihe umlaufen
    SONST:
        Schritt weitergehen
Kleeblatt aufheben

SOLANGE nicht auf einem Kleeblatt:
    WENN vor einem Baum:
        links drehen
        Schritt weitergehen
        rechts drehen
        Schritt weitergehen
        SOLANGE rechts ein Baum:
            Schritt weitergehen
        rechts drehen
        Schritt weitergehen
        links drehen
    SONST:
        Schritt weitergehen
Kleeblatt aufheben

(d) Programmcode:

while not kara.onLeaf():
    if kara.treeFront():
        kara.turnLeft()
        kara.move()
        kara.turnRight()
        kara.move()
        while kara.treeRight():
            kara.move()
        kara.turnRight()
        kara.move()
        kara.turnLeft()
    else:
        kara.move()
kara.removeLeaf()

(e) Struktogramm:

struktorgramm

Aufgabe 2: Darstellungsarten für Algorithmen

Mehrere der Verfahrensbeschreibungen aus Aufgabe 1 sind präzise genug, dass auch eine Maschine sie ausführen könnte. Solche Verfahrensbeschreibungen heißen Algorithmen. Algorithmen, die in einer Programmiersprache verfasst sind, heißen Programme.

A. behauptet: „Die Verfahrensbeschreibungen (a) und (b) sind komplett nutzlos, weil sie zu unpräzise sind. Und (c) und (e) sind auch nutzlos; ohne Programmiersprache kann man sie ja gar nicht ausführen.“ B. erwidert: „Bei (a) und (b) stimme ich zu, aber die anderen beiden können trotzdem nützlich sein.“ C. geht noch einen Schritt weiter: „Auch (a) und (b) können beim Lösen des Problems hilfreich sein.“

Nimm dazu Stellung: Findest du für jede Verfahrensbeschreibung ein Argument, wozu man sie nutzen könnte?

Aufgabe 3: Bausteine von Algorithmen

In dieser Aufgabe geht es darum, die Bausteine von Algorithmen genauer zu untersuchen. Wenn du dir sicher bist, kannst du direkt den unteren Teil des Wissensspeichers nutzen.

In den vorangegangenen Kapiteln hast du drei Typen von Anweisungen kennengelernt: Elementare Anweisungen, Entscheidungsanweisungen (Fallunterscheidungen) und Wiederholungsanweisungen (while-Schleifen).

(a) Markiere im Struktogramm aus Aufgabe 1 (e) die einzelnen Anweisungstypen: In gelb die elementaren Anweisungen, in grün die Entscheidungsanweisungen und in rot die Wiederholungsanweisungen.

(b) Man kann Anweisungen ineinander „verschachteln“ – es wird also eine Anweisung Teil einer anderen komplexeren Anweisung. Finde im obigen Struktogramm je ein Beispiel für die folgenden Fälle:

Entscheidungsanweisung in einer Wiederholungsanweisung
Elementare Anweisung in einer Entscheidungsanweisung in einer Wiederholungsanweisung
Wiederholungsanweisung in einer Entscheidungsanweisung in einer Wiederholungsanweisung
Elementare Anweisung in einer Wiederholungsanweisung in einer Entscheidungsanweisung in einer Wiederholungsanweisung

Eine Verschachtelung kann man sehr gut mit Matroshkas, russischen Puppen, veranschaulichen: Dabei ist in einer äußeren Puppe eine innere Puppe enthalten. In dieser können weitere Puppen enthalten sein.

Beim Programmieren ist das genauso: So muss ja zum Beispiel innerhalb einer Wiederholungsanweisung etwas enthalten sein, was wiederholt wird. Das kann eine elementare Anweisung sein (das entspricht dann einer leeren Puppe), aber auch z.B. eine weitere Wiederholungsanweisung (das entspricht dann einer Puppe mit weiterem Inhalt).