O-Kalkül und Schleifeninvariante |
28.04.2020, 09:18 | AriannaOH | Auf diesen Beitrag antworten » |
O-Kalkül und Schleifeninvariante 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. |
||
28.04.2020, 16:54 | 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... |
||
28.04.2020, 22:09 | 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. . |
||
28.04.2020, 22:18 | Finn_ | Auf diesen Beitrag antworten » |
@HAL: Siehe Hoare-Kalkül, speziell Schleifeninvariante. |
||
29.04.2020, 07:58 | 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 . |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|