Ćwiczenia ASD 2 (propozycja zadań tablicowych)

1. Uporządkować następujące funkcje ze względu na rosnący rząd wielkości:
f1(n) = sqrt(n), f2(n) = lg n, f3(n) = 2 ⁿ , f3(n) = 3 ⁿ

2. Badanie zależności między złożonością , rozmiarem i czasem wykonania algorytmu.

Niech t będzie czasem potrzebnym do wykonania na komputerze Komp1 pewnego zadania o rozmiarze k przy pomocy algorytmu A, takiego, że T(A,n) = n ². Jakiego rozmiaru zadanie można zrealizować, w tym samym czasie t i przy pomocy tego samego algorytmu, na komputerze Komp2, który jest 100 razy szybszy? (oczywiście, zmieniając nieco pytanie lub parametry można otrzymać kilka nowych zadań)

3. Poprawność algorytmów. Dla każdego z zaproponowanych zadań zapisać algorytm bez instrukcji for. Sformułować warunek początkowy i końcowy. Uzasadnić poprawność. Wskazać niezmienniki. Obliczyć (oszacować) koszt.

· A1 - algorytm obliczania iloczynu skalarnego dwóch wektorów a i b.

· A2 - algorytm obliczania wartości wielomianu z definicji.

· A3 - algorytm obliczania wartości wielomianu metodą Hornera.

Pozostała część ćwiczeń powinna być poświęcona ozganizacji projektu, omówieniu menu.

Proszę też zapowiedzieć wejściówkę na następny tydzień. Będzie ona dotyczyła rzędów funkcji.

Uwagi do rozwiązań

Zadanie 1.

Możnaby np. pokazać przez indukcję, że 2 ⁿ < 3 ⁿ dla n>0 i skorzystać z definicji O, a w przypadku funkcji f1 i f2 skorzystać z twierdzenia o porównywaniu rzędów funkcji i policzyć

lim _x®µ lg x / Öx = lim (lg x)'/(Öx)' = 0.

Zadanie 2.

Szukamy takiego x, że na komputerze Komp2 mamy T(A,x)= x ² = t. Zadanie o rozmiarze x na komputerze 100 razy wolniejszym zajmie 100 razy więcej czasu, zatem wykonanie zadania o rozmiarze x na komputerze Komp1 zajmie 100t czasu. Prowadzi to do równości 100t = x ². Z warunków zadania wiemy, że T(A,k)= k ²= t. Czyli ostatecznie x ² = 100 k ² , a więc x = 10 *k.

Zadanie 3.

Ad.3.3 Algorytm Hornera

Niech p(x) będzie wielomianem a[0] x ⁰ + .... + a[n] x ⁿ. Wtedy można go przedstawić jako: p(x) = a[0] + x(a[1] + x( a[2] + ... + x( a[n-1] + x a[n])...)

Algorytm (ma liczyć wartość wielomianu w punkcie x0) można zapisać następująco:

{ wynik := a[n]; i := n;

while i>0 do /*niezmiennik wynik = Suma{ a[j] * x0 ^j-i : j =i...n}

i := i-1;

wynik := a[i ] + x0 * wynik;
od;

}