PTO 2

4.-Dana jest procedura X

procedurę A(var/:array[l...łiJ of integer); procedurę }ty.A./:integcr); var imp.i integer; begin

whiłe J<^mk and k<i do

j' .Je*f.

(przesunięcie cykliczne ciągu    *

if Ą/]<^mt[k+1J then j*+ else begin

tmp:^MĄk+1J; for i:^mk downto j do l[i+I

end;

end;{ K)

procedurę Zfrjunteger):

var iinlfger,

begin

if i<j then begin

losuj ke 1};

Z(i.k)_tZ(k+\j)-. V{i.kJ)-

end; end; {Z} begin

W#);

end,W

a)    Co robi procedura XI

b)    Oszacuj jej pesymistyczną złożoność obliczeniową (w sensie symbolu 0). Odpowiedzi uzasadnij.

5. W historii problemu minimaksowego pełnego skojarzenia grafu spójnego znane są dwa najlepsze algorytmy: Al o złożoności Oim^fnlogn)

A2 o złożoności 0( n-Jnm )■

a)    Podaj przedział zmienności m (w sensie oszacowania asymptotycznego), dla którego algorytm drugi jest asymptotycznie szybszy od pierwszego.

Programista wpadł na pomysł zaimplcmentowania<obu powyższych algorytmów i napisał następującą procedurę;

p roccd u rc zagadka(G: graf);

begin

«:=liczba wierzchołków w G\

»r.=liczba krawędzi w G;    {/», n obliczane w stałym czasie)

if m<=»^J/k)g₂n then Al etse A2

end;

b)    Oszacuj czas działania zagadki dla przypadku grafu rzadkiego i grafu gęstego w funkcji n.