Strukturelemente von Algorithmen
Als Strukturelemente von Algorithmen werden diejenigen Muster bezeichnet, nach denen die Befehle eines Algorithmus verknüpft werden können. Hier werden die Strukturelemente zunächst allgemein vorgestellt; später werden Beispiele im Pseudocode und in speziellen Programmiersprachen angegeben.
Einordnung des Artikels
- Einführung in die Informatik
- Einführung in die Programmierung
- Strukturelemente von Algorithmen
- Einführung in die Programmierung
Was sind Strukturelemente von Algorithmen?
Die wichtigsten Eigenschaften von Algorithmen wurden ausführlich besprochen, insbesondere:
- Ein komplexer Vorgang wird in elementare Schritte zerlegt.
- Diese Schritte müssen in einer streng einzuhaltenden Reihenfolge abgearbeitet werden.
Um selber Algorithmen entwickeln zu können, muss noch geklärt werden, wie die elementaren Anweisungen miteinander verknüpft werden können - diese Verknüpfungen nennt man die Strukturelemente von Algorithmen. Um nicht zu abstrakt zu argumentieren, sollen die relevanten Strukturelemente am Beispiel eines Kochbuchs vorgestellt werden.
| Elementare Operationen | Bringen Sie das Wasser zum Kochen |
| Sequenz | Bringen Sie das Wasser zum Kochen; geben Sie dann die Nudeln hinein |
| Parallele Ausführung | Rühren Sie die Nudeln gelegentlich um, während Sie die Zwiebeln schneiden |
| Bedingung | Falls die Soße zu dick ist, mit Wasser verdünnen |
| Alternative | Streuen Sie entweder Basilikum oder Schnittlauch darüber |
| Mehrfachalternative | Servieren Sie dazu Kirschsaft, Rotwein oder ein kühles Bier |
| Schleife (Iteration) | Rühren Sie solange bis sich das Pulver aufgelöst hat |
| Rekursion | Halbieren Sie den Sellerie; falls die Stucke größer als 1 cm sind, halbieren Sie die Stücke nochmals usw. |
| Unterprogramm | Dazu passt eine Soße nach dem Rezept auf Seite 13 |
Aufgabe:
Finden Sie ein treffenderes Beispiel für eine Schleife!
Die Rekursion erscheint sehr gekünstelt und so nicht verständlich. Das Paradebeispiel für eine Rekursion ist die Fakultät:
n! = n*(n-1)! 1! = 1
Auch diese beiden Zeilen erscheinen schwer verständlich, aber mit ihnen wird eindeutig definiert, wie man für eine natürliche Zahl n die Fakultät von n berechnet.
Auf den ersten Blick wirkt die Definition nichtssagend: Eine Fakultät wird durch eine Fakultät berechnet - die Definition erscheint so sinnlos wie
Rechts ist da, wo der Daumen links ist.
Oder so nichtssagend wie der Eintrag in einem Informatikerlexikon:
Rekursion: siehe Rekursion.
Aufgaben:
- Obige Definition der Fakultät nennt man auch die rekursive Definition der Fakultät. Versuchen Sie eine iterative Definition der Fakultät zu geben!
- Versuchen Sie eine allgemeine Definition von Rekursion oder speziell einer rekursiven Funktion zu geben - eine Definition, die mehr aussagt als siehe Rekursion!
Kontrollstrukturen
Dass elementare Operation und Sequenz Strukturelemente eines Algorithmus sind, ist selbstverständlich: im einfachsten Fall ist ein Algorithmus die Aneinanderreihung von elementaren Rechenschritten.
Die parallele Ausführung von Operationen wird hier nicht weiter verfolgt, sie gehört zu den anspruchsvolleren Programmiertechniken, da sie eine besondere Fehlerquelle besitzt: Der sogenannte dead lock, der meist zu einem Programmabsturz führt. Allerdings wird die parallele Programmierung immer wichtiger, wenn Programme, die hohe Rechenleistung erfodern, tatsächlich mehrere Kerne eines Prozessors nutzen sollen.
Aufgabe:
Was versteht man unter einem dead lock?
Warum tritt er nur bei der parallelen Programmierung auf?
Die weiteren Strukturelemente von Algorithmen, also Bedingung, Alternative, Mehrfachalternative, Schleife, Rekursion, Unterprogramm werden auch als Kontrollstrukturen bezeichnet.
In der Definition von Algorithmus wurde betont, dass nach jedem Befehl eindeutig feststehen muss, welcher Befehl als nächster auszuführen ist. Bei einer Sequenz von Befehlen ist klar, dass die Abarbeitung beim nächsten Befehl der Sequenz weitergeht. Bei den Kontrollstrukturen ist dies oft nicht auf den ersten Blick ersichtlich. Achten Sie später beim Programmieren darauf, wie die Kontrollstrukturen den nächsten Befehl festlegen.
Aufgabe:
Beschreiben Sie welche Rolle der Befehlszähler (PC = program counter) im Zusammenhang mit Kontrollstrukturen spielt!