O-Kalkül und Schleifeninvariante

Neue Frage »

AriannaOH Auf diesen Beitrag antworten »
O-Kalkül und Schleifeninvariante
Meine Frage:
Ich habe folgenden Algorithmus (im Latex-Code):

$Data: p,q \in \mathbb{N_{>0}}$\\
$Result: (d,f)\in \mathbb{N_0}x \mathbb{N_0}$\\
\\
$d \leftarrow 0$\\
$f \leftarrow q$\\
$g \leftarrow 1$\\
$while $ $ q-g \cdot p \geq 0 do$\\
w--- $d \leftarrow g$\\
w--- $g \leftarrow g+1$\\
w--- $f \leftarrow q-d \cdot p$\\
$return (d,f)$\\


Dabei gehören die drei Zeilen nach dem while Befehl zur Schleife (mit w--- markiert).

1. Berechne das O-Kalkül für den Worst-Case für die Laufzeit in Abhängigkeit von $q$.
2. Nenne und beweise eine Schleifeninvariante für die while-Schleife. Diese soll $q$ in Abhängigkeit von $p$ beschreiben. $q \geq p$.
Liebe Grüße Ari.

Meine Ideen:
Bitte helft mir schnellstmöglich, ich habe leider absolut keine Ahnung was ich tun soll.
Ich habe angefangen mich in die Themen einzulesen, jedoch hat es nichts gebracht.
Vielen Dank.
HAL 9000 Auf diesen Beitrag antworten »

Ich weiß nicht, wass du mit Schleifeninvariante meinst. Ich kann nur analysieren, was der obige Code eigentlich inhaltlich anstellt: Er berechnet (auf ziemlich ineffiziente Weise) Quotient und Rest der Division , d.h., es ist am Ende

mit

Die Laufzeit umfasst genau Schleifendurchläufe, d.h., bei großen Quotientenwerten dauert die Rechnung geradezu ewig...
Finn_ Auf diesen Beitrag antworten »

Data: ;
Result:




while do



end
return

1. Berechne das O-Kalkül für den Worst-Case für die Laufzeit in Abhängigkeit von .
2. Nenne und beweise eine Schleifeninvariante für die while-Schleife. Diese soll in Abhängigkeit von beschreiben. .
Finn_ Auf diesen Beitrag antworten »

@HAL: Siehe Hoare-Kalkül, speziell Schleifeninvariante.
HAL 9000 Auf diesen Beitrag antworten »

Ah, ja. Na dann ist offenbar mit der Schleifeninvariante gemeint, wobei das von mir erwähnte erst am Ende des Algorithmus erfüllt ist. Eine zweite Schleifeninvariante ist natürlich auch noch .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »