Ćwiczenia ASD 3 (propozycja zadań tablicowych)

1. Zaproponować algorytm wyliczania części całkowitej logarytmu przy podstawie 3 dla dowolnej liczby naturalnej. Sformułować warunek początkowy i końcowy. Wskazać niezmiennik pętli. Uzasadnić poprawność. Oszacować złożoność algorytmu.

2. Co robi następujący algorytm ? Zakładam, że rozważamy go w strukturze liczb naturalnych.

{ r:= x; q := 0;
while r³y do
r := r-y;
q := q+1;
od;

}

Znaleźć niezmiennik pętli. Sformułować warunek początkowy i końcowy. Policzyć koszt wykonania algorytmu dla dowolnych x, y.

Uwagi do rozwiązań:

Ad. Zad1.
Algorytm może wyglądać następująco:

{ m:= 3; wynik := 0;
while m £ n do
m := m*3; wynik := wynik +1
od
}

WP ={n>0}, WK={wynik = ëlog ₃ nû}

Niezmiennik pętli : m= 3 ^wynik+1

Rozmiar danych k = w tym przypadku może to być np. liczbą cyfr w binarnej reprezentacji liczby n, czyli k= lg n. Złożoność algorytmu T(k)= Q(ëlog ₃ 2 ^kû}= Q(k)

Ad. Zadanie 2
Uwaga na przypadek y =0.

WP = { x*y>0} WK={ r = x mod y, q = x div y}. Niezmiennik x= q*y +r

Operacja dominująca +-. Koszt = 2 (x div y)

Wejściówka

Proponuję, żeby pytania wejściówki dotyczyły porównywania rzędów funkcji i złożoności.

Przykładowe zadania

1.(np za 3punkty) Dla każdej z wymienionych funkcji ustalić jej rząd, a następnie uporządkować funkcje ze względu na ich rosnący rząd wielkości.

f1(n) = (n⁵ +3n+5)/( (n+1)(n-1)), f2(n) = (n⁴ +3n+5)/2 ^2lgn , f3(n) = lg(n!), f4(n) = lg3 ⁿ

2.(za 2 punkty)

Jakiego rozmiaru zadanie można zrealizować na pewnym komputerze w czasie t przy pomocy algorytmu A o złożoności T(A,n) = n ³, jeśli wiadomo, że ten sam algorytm, na komputerze 64 razy wolniejszym wykonuje w czsie t zadanie o rozmiarze k.