Aufgaben: Eigenschaften von Algorithmen und Pseudocode

Nenne die algorithmischen Eigenschaften Endlichkeit, Eindeutigkeit und Terminierung und erkläre jede in einem Satz.

Eine Handlungsvorschrift lautet: „Rühre den Teig, bis er gut ist, und backe ihn dann eine Weile.“

1. a) Welche Eigenschaft eines Algorithmus ist verletzt?
2. b) Formuliere die Vorschrift so um, dass sie eindeutig ist.

Gegeben ist der Pseudocode:

setze zahl auf 10

solange zahl > 0:

    gib zahl aus

    setze zahl auf zahl - 2

1. a) Welche Zahlen werden ausgegeben?
2. b) Terminiert der Algorithmus? Begründe.

Gegeben ist der Pseudocode:

setze zahl auf 7

solange zahl ungleich 0:

    setze zahl auf zahl - 2

1. a) Verfolge die Werte von zahl in einer Tabelle für die ersten fünf Schritte.
2. b) Terminiert der Algorithmus? Begründe.
3. c) Ändere die Bedingung so, dass er für jeden positiven Startwert terminiert.

Schreibe in Pseudocode einen Algorithmus, der eine Zahl n einliest und die Summe aller Zahlen von 1 bis n ausgibt. Berechne die Ausgabe für n = 6 und begründe, dass der Algorithmus endlich ist.

Eine Anweisung für einen Bankautomaten lautet: „Wiederhole die PIN-Eingabe, bis sie richtig ist.“

1. a) Warum ist die Terminierung nicht garantiert?
2. b) Ergänze eine Regel, die Terminierung sicherstellt, und formuliere sie in Pseudocode.

Gegeben ist:

lies a

lies b

solange b ungleich 0:

    setze r auf a mod b

    setze a auf b

    setze b auf r

gib a aus

1. a) Führe den Algorithmus für a = 48 und b = 18 aus und gib alle Zwischenwerte an.
2. b) Welche Aufgabe löst der Algorithmus?
3. c) Begründe, warum er für natürliche Zahlen terminiert.

Ein Kollege behauptet: „Der folgende Algorithmus ist ein gültiger Algorithmus, obwohl er nie hält.“

setze x auf 1

solange wahr:

    setze x auf x * 2

1. a) Erkläre, welche Eigenschaften ein Algorithmus nach der Definition erfüllen muss.
2. b) Beurteile die Behauptung. Gibt es Algorithmen, bei denen Nichtterminierung beabsichtigt ist (z. B. ein Betriebssystem)?
3. c) Wie unterscheidet man dann Endlichkeit der Beschreibung und Terminierung der Ausführung?

Entwirf in Pseudocode einen Algorithmus, der in einer Liste von n Zahlen das Maximum bestimmt.

1. a) Schreibe den Algorithmus auf.
2. b) Prüfe ihn an der Liste (4, 9, 2, 9, 5) mit Wertetabelle.
3. c) Begründe Eindeutigkeit, Endlichkeit und Terminierung für deinen Algorithmus.