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.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

Was sind Strukturelemente von Algorithmen?

Die wichtigsten Eigenschaften von Algorithmen wurden ausfĂŒhrlich besprochen, insbesondere:

  1. Ein komplexer Vorgang wird in elementare Schritte zerlegt.
  2. 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:

  1. Obige Definition der FakultÀt nennt man auch die rekursive Definition der FakultÀt. Versuchen Sie eine iterative Definition der FakultÀt zu geben!
  2. 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!