1. Sortowanie poprzez wstawianie do drzewa BST i obejście tego drzewa w porządku preorder.

1.1 Definicja drzewa BST i przykłady.

1.2 Algorytm wstawiania wartości do drzewa BST

1.3 Algorytm obejścia preorder drzewa BST

1.3 Algorytm sortowania poprzez kolejne wstawianie elementów do drzewa BST

i obejście preorder - przykład.

2. Zaprogramowanie algorytmów

3. Wstęp do niezmienników

3.1 Reguły logiki poprawności prostych programów iteracyjnych

• Reguła dla instrukcji podstawienia - przykłady

• Reguła dla instrukcji składania - przykłady

• Reguła dla instrukcji warunkowej „if then „ oraz dla „if then else”

• Niezmiennik i reguła dla instrukcji „while”

3.2 Przykłady

3.2.1 Potęgowanie - algorytm zwykły i binarny

/* n>=0 && x!=0 */

z = 1; i = 0;

while (i<n) /* z = xⁱ && i ≤ n */

{ z = z ∗ x;

i++;

}

/* z = xⁿ */

/* n>=0 && x!=0 */

z = 1; i = n; p = x;

while (i != 0) /* z ∗ pⁱ = xⁿ */

{ if( i%2 != 0) z = z ∗ p;

p = p ∗ p; i = i/2;

}

/* z = xⁿ */

3.2.2 Część całkowita pierwiastka z n - algorytm zwykły i binarny

/* n ≥ 0 */

p=0;

while ( (p+1)² ≤ n ) /* p² ≤ n */

{ p++;

}

/* p = część całkowita pierwiastka kwadratowego z n */

/* n>0 */

q =1;

while ( (2∗q)² ≤ n ) /* q∗q ≤ n */

{ q = 2∗q; };

/* q² ≤ n && (2∗q)² > n */

p = q;

while ( q != 1 ) /* p² ≤ n && (p+q)² > n */

{ q = q/2;

if( (p+q)² ≤ n ) p = p+q;

}

/* p = część całkowita pierwiastka kwadratowego z n */

3.2.3 Obliczanie największego wspólnego dzielnika - zwykły algorytm poprzez kolejne odejmowanie i algorytm binarny obliczania największego wspólnego dzielnika

/* a ≥ 1 && b ≥ 1 */

p = a; q = b;

while ( p != q ) /* nwd(a,b) = nwd(p,q) */

{ if( p>q ) p = p-q else q = q-p ;

}

/* p = nwd(a,b) */

Algorytm Binarny Euklidesa obliczania największego wspólnego dzielnika

/* a>0 && b>0 */

p = a; q = b; f = 1;

/* nwd(a,b) = f∗nwd(p,q) */

while ( p%2 = = 0 && q%2 = = 0) /* nwd(a,b) = f∗nwd(p,q) */

{ p = p/2; q = q/2; f = f∗2; };

/* nwd(a,b) = f∗nwd(p,q) && ( p%2 != 0 | | q%2 != 0 ) */

while ( p%2 = = 0 ) /* nwd(a,b) = f∗nwd(p,q) && ( p%2 != 0 | | q%2 != 0 ) */

{ p = p/2; };

/* nwd(a,b) = f∗nwd(p,q) && p%2 != 0 */

while (q%2 = = 0 ) /* nwd(a,b) = f∗nwd(p,q) && p%2 != 0 */

{ q = q/2; };

/* nwd(a,b) = f∗nwd(p,q) && p%2 != 0 && q%2 != 0 */

t = p - q;

/* nwd(a,b) = f∗nwd(p,q) && t = p - q && p%2 != 0 && q%2 != 0 */

while (t != 0 ) /* nwd(a,b) = f∗nwd(p,q) && t = p - q && p%2 != 0 && q%2 != 0 */

{ while ( t%2 = =0 )

/* nwd(a,b) = f∗nwd(p,q) && ( t>0 ⇒ nwd(t,q) = nwd(p,q)) &&

niezmiennik pętli dla t && ( t<0 ⇒ nwd(p,-t) = nwd(p,q)) &&

&& p%2 != 0 && q%2 != 0 */

{ t = t/2; };

/* . . . poprzedni niezmiennik && t nieparzyste . . . */

if (t>0) p=t; else q=-t;

/* nwd(a,b) = f∗nwd(p,q) && p%2 != 0 && q%2 != 0 */

t = p-q;

/* nwd(a,b) = f∗nwd(p,q) && t = p - q && p%2 != 0 && q%2 != 0 */

}

/* nwd(a,b) = f*p; */

---