egzamin2009 2

.1 •

Korzystając z algorytmu programowania dynamicznego znajdź optymalne upakowanie plecaka. Do pracy załącz

swoje obliczenia.    .    . . ‘    ’

/

6.    (pkt. 1) Elementy zbioru X={xń, x_n_i , ...Xj } zostały włożone na stos S w kolejności x_n, x_n._l5 ...xi. Zaznaczyć właściwą liczbę operacji push i pop w procesie usuwania elementu x, z S. Po wykonaniu operacji usunięcia na stosie S powinny znajdować się następujące elementy': x_n, x_n_i,..., x,+i, Xj.i,Xi (element xj znajduje się na górze stosu).

(a)    2*(i-l) operacji push + i operacji pop

(b)    2*(n-i) operacji push +    1 operacja pop .

(c)    (i -l) operacji push + i operacji pop

(d)    inna odpowiedź (jaka?)

7.    (pkt. 4) Niech A będzie następującym algorytmem

bfegin

p:-2; bool := true;

while (p*p <n+l and bool) do

if n mod p = 0 then bool :- false fi;

P P+l od end

i    *

(a) Podać niezmiennik pętli while występującej w tym algorytmie wiedząc, że n jest liczbą naturalną. Uzasadnić wybór.

(b)    Podać warunek końcowy preCond tąk, aby algorytm A był poprawny względem specyfikacji (preCond} A {postCond}, gdzie preCond ={n>l, n jest liczbą naturalną}.

(c)    Uzasadnić poprawność algorytmu A względem wybranej w punkcie poprzednim specyfikacji.

(d)    Oszacować asymptotyczna złożoność obliczeniową algorytmu.

8. (pkt. 2) Dla poniższej sieci połączeń między' miastami wyznaczyć minimalną ścieżkę ź miasta a do k, posługując strategią programowania dynamicznego. Podaj wszystkie optymalne rozwiązania. Do odpowiedzi załącz każdy z kroków wykonanych przez siebie obliczeń.