3b138c6b90bcd17amed

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

6. (pki I) Elementy zbioru X-{xł, Xr,i, ...x_t } zostały włożone na stos S w kolejności x«. x„.,, ...x₍. Zaznaczyć właściwą liczbę operacji pusli r pop w procesie usuwania elementu x, z S. Po wykonaniu operacji usunięcia na stosie S pow inny znajdować sic następujące elementy: x,. x„,.....xx,.,,... x, (element Xj znajduje się na górze stosu).

0    operacji push + i operacji pop

<b) 2*łn-i)cpcracji push +■ l operacja pop

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

(d)    imui odpowiedź (jaka?)

? (pkt. 11 Niech A będzie następującym algorytmem bagin

p:«2; bool := ~rue;

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

lt n uiod p « 0 then bool :=> falsc fi;

P P+l srd end

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

(b)    Podać warunek końcowy prcCond tąk, aby algorytm A był poprawny względem specyfikacji {prcCond} A (postCond), gdzie prcCond ={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ę z miasta a do k, posługując strategią programowania dynamicznego. Podaj wszystkie optymalne rozwiązania. I>o odpowiedzi załącz, każdy z kroków wykonanych przez siebie obliczeń

!Uwaga. Na ocenę bardzo dobrą należy uzyskać co najmniej l⁴ punktów. Na cccnc dostateczną należy uzyskać 7 [punktów.    _ I