Analiza algorytmu Euklidesa

Należy udowodnić że algorytm zawsze kończy obliczenia.

Zacznijmy od obserwacji, że algorytm Euklidesa w niestandardowym modelu liczb naturalnych może nie zakończyć obliczeń.

Na jakich podstawach ma się oprzeć dowód własności stop algorytmu?

Algorytmiczne aksjomaty liczb naturalnych:

(N1) $$\color{blue} (\forall n) (n+1 \neq 0 )$$

(N2) $$\color{blue} (\forall n)(\forall m)(n+1=m+1 \Rightarrow n=m)$$

(N3) $$\color{blue} (\forall n)[m:=0; \mathbf{while}\ m \neq n\ \mathbf{do}\ n:=n+1\ \mathbf{od}](m=n)$$

Możemy zdefiniować relacje mniejszości

Definicja $$\color{blue} x\lty\ \stackrel{df}{\equiv}\ \neg (x=y) \wedge \left[\begin{array}{l} r:=0; \\ \mathbf{while}\ r\neq x \land r \neq y \\ \mathbf{do} \\ \quad r:=r+1 \\ \mathbf{od} \end{array} \right](r=x)$$

Definicja $$\color{blue} x\leq y\ \stackrel{df}{\equiv}\ \left[\begin{array}{l} r:=0; \\ \mathbf{while}\ r\neq x \land r \neq y \\ \mathbf{do} \\ \quad r:=r+1 \\ \mathbf{od} \end{array} \right](r=x)$$

oraz operację odejmowania

Definicja

Jeśli

$$\color{blue} y \lt x$$ to operacja odejmowania jest określona tak

$$\color{blue} x \stackrel{.}{-}y\ \stackrel{df}{\equiv}\ \left[\begin{array}{l} r:=y;\ q:=0; \\ \mathbf{while}\ r \neq x \ \mathbf{do} \quad r:=r+1;\ q:=q+1 \ \mathbf{od}; \\ \end{array} \right] (wynik = q)$$

i operację dodawania

Definicja Operacja dodawania jest określona tak

$$\color{blue} x + y\ \stackrel{df}{\equiv}\ \left[\begin{array}{l} r:=x;\ q:=0; \\ \mathbf{while}\ q \neq y \ \mathbf{do} \quad r:=r+1;\ q:=q+1 \ \mathbf{od}; \\ \end{array} \right] (wynik = r)$$

Lemat (aksjomat Archimedesa)

Jeśli

$$\color{blue} 0\ltn \lt m$$ to $$\color{blue} \left[\begin{array}{l} r:=n; \\ \mathbf{while}\ r \leq m \ \mathbf{do} \quad r:=r+n; \ \mathbf{od}; \\ \end{array} \right] (r\gtm)$$

Dowód własności stop algorytmu Euklidesa

Gdyby algorytm Euklidesa miał obliczenie nieskończone dla pewnych liczb naturalnych n i m to stanowiłoby to zaprzeczenie aksjomatu (N3) liczb naturalnych.

W algorytmie występuje pętla zewnętrzna i dwie po kolei pętle wewnętrzne. W każdym przypadku obliczenia pętli wewnętrznych są skończone. Wynika to wprost z aksjomatu (N3). Nieco trudniej jest zauważyć, że obliczenie pętli wewnętrznej jest także skończone. Wychodząc z drugiej pętli wewnętrznej osiągnęliśmy większą z dwu liczb n, m zaczynając od zera i dodając pracowicie jeden. W każdym kolejnym wykonaniu instrukcji iterowanych w pętli zewnętrznej większa z liczb n,m jest zmniejszana bo

$$\color{blue} n \neq m$$ . Więc, po conajwyżej $$\color{blue} max(n,m)$$ powtórzeniach pętli zewnętrznej, algorytm Euklidesa, w tej postaci, zatrzyma się. Ale po kolei: Z aksjomatu (N3) wynika, że

$$\{ r:=0; \mathbf{while} \ r\neq n\ \mathbf{do}\ r:=r+1\ \mathbf{od}\} \ r=n$$

Wykorzystując następującą regułę wnioskowania

$$\frac{\alpha \Rightarrow \beta}{\mathbf{while}\ \beta\ \mathbf{do}\ K\ \mathbf{od}\ \neg \beta \Rightarrow \mathbf{while}\ \alpha\ \mathbf{do}\ K\ \mathbf{od}\ \neg \alpha}$$

wnioskujemy, że

$$\{ r:=0; \mathbf{while} \ r\neq n \land r\neq m\ \mathbf{do}\ r:=r+1\ \mathbf{od} \} \ (r=n \lor r=m)$$

Z założenia

$$n \neq m$$ wynika, że

$$\{ r:=0; \mathbf{while} \ r\neq n \land r\neq m\ \mathbf{do}\ r:=r+1\ \mathbf{od} \} \ (r=min(n, m))$$

Udowodniliśmy więc, że

$$\left \{\begin{array}{l} \mathbf{if}\ n\neq m\\ \mathbf{then} \\ \quad r:=0;\\\quad \mathbf{while} \ r\neq n \land r\neq m\ \mathbf{do}\ r:=r+1\ \mathbf{od}; \\ \quad \mathbf{if}\ r=n\\ \quad \mathbf{then}\\ \qquad n\_mniejsze:=true;\ max:=m\\\quad \mathbf{else}\\ \qquad n\_mniejsze:=false;\ max:=n\\\quad \mathbf{fi};\\ \mathbf{fi} \end{array} \right \} \ ((r=n \land n\ltm)\lor (r=m \land m\gtn )\land max=\mathrm{max}(n,m))$$

Jeszcze raz korzystamy z aksjomatu (N3)

$$\{ r:=0; \mathbf{while} \ r\neq max \ \mathbf{do}\ r:=r+1\ \mathbf{od}\} \ r=max$$

$$\left \{\begin{array}{l} \mathbf{if}\ n\neq m\\ \mathbf{then} \\ \quad r:=0;\\ \quad \mathbf{while} \ r\neq n \land r\neq m\ \mathbf{do}\ r:=r+1\ \mathbf{od}; \\ \quad \mathbf{if}\ r=n\\ \quad \mathbf{then}\\ \qquad n\_mniejsze:=true;\ max:=m\\ \quad \mathbf{else}\\ \qquad n\_mniejsze:=false;\ max:=n\\ \quad \mathbf{fi};\\ \quad r:=0;\\ \quad \mathbf{while} \ r\neq max \ \mathbf{do}\ r:=r+1\ \mathbf{od} \\ \mathbf{fi} \end{array} \right \} \ ( r=max \land max=\mathrm{max}(n,m))$$

Skorzystam z prawa przerwania i wznowienia podróży

$$\left \{\begin{array}{l} r:=0;\\ \mathbf{while} \ r\neq \mathrm{max}(n,m) \\ \mathbf{do}\\ \quad r:=r+1 \\ \mathbf{od}; \\ \end{array} \right \} \ ( r=\mathrm{max}(n,m)) \equiv \left \{\begin{array}{l} r:=0;\\ \mathbf{while} \ r\neq min(n,m) \\ \mathbf{do}\\ \quad r:=r+1\\ \mathbf{od}; \\ \mathbf{if}\ r=n\\ \mathbf{then}\\ \quad n\_mniejsze:=true;\\ \quad max:=m\\ \mathbf{else}\\ \quad n\_mniejsze:=false;\\ \quad max:=n\\ \mathbf{fi};\\ \mathbf{while} \ r\neq max \\ \mathbf{do}\\ \quad r:=r+1\\ \mathbf{od} \\ \end{array} \right \} \ ( r=\mathrm{max}(n,m))$$

by uzyskać

$$\left \{\begin{array}{l} \mathbf{if}\ n\neq m\\ \mathbf{then} \\ \quad r:=0;\\ \quad \mathbf{while} \ r\neq n \land r\neq m\ \mathbf{do}\ r:=r+1\ \mathbf{od}; \\ \quad \mathbf{if}\ r=n\\ \quad \mathbf{then}\\ \qquad n\_mniejsze:=true;\ max:=m\\ \quad \mathbf{else}\\ \qquad n\_mniejsze:=false;\ max:=n\\ \quad \mathbf{fi};\\ \quad q:=0 \\ \quad \mathbf{while} \ r\neq max \\ \quad \mathbf{do}\\ \qquad r:=r+1;\ q:=q+1\\ \quad \mathbf{od} \\ \mathbf{fi} \end{array} \right \} \left( \begin{array}{l} ( r=max \land max=\mathrm{max}(n,m)) \land \\ ((n\_mniejsze \land q=m-n)\lor(\neg n\_mniejsze \land n=n-m))\end{array} \right)$$

w tym programie wstawiam instrukcję

if n\_mniejsze then m:=q else n := q fi

$$\left \{\begin{array}{l} \mathbf{if}\ n\neq m\\ \mathbf{then} \\ \quad r:=0;\\ \quad \mathbf{while} \ r\neq n \land r\neq m\ \mathbf{do}\ r:=r+1\ \mathbf{od}; \\ \quad \mathbf{if}\ r=n\\ \quad \mathbf{then}\\ \qquad n\_mniejsze:=true;\ max:=m\\ \quad \mathbf{else}\\ \qquad n\_mniejsze:=false;\ max:=n\\ \quad \mathbf{fi};\\ \quad q:=0 \\ \quad \mathbf{while} \ r\neq max \\ \quad \mathbf{do}\\ \qquad r:=r+1;\ q:=q+1\\ \quad \mathbf{od}; \\ \quad \mathbf{if}\ n\_mniejsze\ \mathbf{then}\ m:=q\ \mathbf{else}\ n := q \ \mathbf{fi}; \\ \mathbf{fi} \end{array} \right \} \ ( r=max \land max=\mathrm{max}(n,m))$$

Dowód poprawności algorytmu Euklidesa

Należy wykazać, że wynik algorytmu Euklidesa to największy wspólny dzielnik.

Z postaci programu widać, że wynik jest największą liczbą

$$n$$ , mniejszą od $$max(x,y)$$ taką, że ... $$n|x$$ i $$n|y$$ . Algorytm wyznacza ciąg par $$\{\langle n_i, m_i \rangle\}$$ taki, że

$$\langle n_1,m_1 \rangle = \langle x,y \rangle$$

$$\langle n_{i+1},m_{i+1} \rangle = \begin{cases} \langle n_{i}-m_{i},m_{i} \rangle & \text{gdy}\ n_i\gtm_i \\ \langle n_{i},m_{i}-n_i \rangle & \text{gdy}\ n_i\ltm_i \\ \mbox{niezdefiniowany} & \text{gdy}\ n_i=m_i \end{cases}$$

zachodzi przy tym

$$NWD( n_{i+1},m_{i+1})= NWD( n_{i},m_{i})$$

Ciąg wartości

$$\mathrm{max}( n_{i},m_{i})$$ jest ciągiem ściśle malejącym.

przejdź do algorytmu Euklidesa

powrót do wybrane przykłady