Zadania

return (fatsc); end;

i napisz, czy jest ona wielomianowa, .superwiełomiaoowa, wykładnicza, czy superwykładniczn. T(l)=c. T(n)=(2T(n/2)+c)n=2nT(n/2)+cn, T(u/2)=2 n/2 T{n/4)^c n/2,

T(n/4)=... itd. ...

C(n^A(icg₌n^ 1 ))=C(rr log₂n)

36. Stosując wyszukiwanie sekwencyjne w tablicy nieposortowanej bądź binarne w tablicy posortowanej wybieramy

pomiędzy czasem wyszukiwania, a czasem przetwarzania wstępnego. Jak wiele wyszukiwań binarnych trzeba

wy konać w najgorszym przypadku danych w tablicy n-elementowej, żeby opłaci! sie czas potrzebny na wstępne

posortowanie tablicy ? Przyjmując, że współczynniki proporcjonalności złożoności są równe 1, odpowiedź sformułuj

w terminach oszacowań asymptotycznych.

dla szukania binarnego    S^log^n

dła szukania sekwencyjnego S=n

sortowanie    nlogin

k - liczba wyszukać, dla których opłaca się sortować

klogm-fnlog^kn, k (iog_In-n)=-nlog₂tk k (n-log^^nlogin,

k=(nlog2n)/Cn-log₂n)^}og₂n - przy tej wartości opłaca się sortować

37. Dana jest sieć N czyii graf z obciążonymi krawędziami. Problem znalezienia najkrótszej drogi w N jest trywialny (wy starczy zbadać wszystkie krawędzie), natomiast problem znalezienia najdłuższej możliwej drogi jest trudny obliczeniowo. Udowodnij, że jest on NP-tradny. procedurepółharriltcnowski(G:graph):boolean; begin n - net

wprowadź graf G do sieci N ustaw wagę krawędzi na 1

if LP(N)=n-I ihen    (hamiltonowski ji)

rerum (true); cIsc

rerum (false);

end.

38. Problem Największy Wspólny Podgraf (NAYP) zdefiniowany jest następująco : “Dane są 2 grafy Gi i G- oraz próg p; czy' zawierają one identyczny podgraf G rozmiaru >p ?7.

Udowodnij, że Klika a NWP.

V(G) - wierzchołki (rząd grafu), E(G) - rozmiar grafu procedurę KJika(G:graph;n.k:integer):boolean; var G. igraph;

iir.teger;

begin

Gj‘.graf pełny rzędu k i:=(k/l);(k/2) - liczba krawędzi if(NWP(Gj,G,i)) then rerum (true) clse rerum (false);

end;

\ 39. Dana jest macierz zero-jedynkowa A={a_:i], i,j=ł, 2, n. Naszkicuj algorytm rozpoznający, czy jest to macierz sąsiedztwa wierzchołków grafu zwykłego i oblicz jego złożoność obliczeniową

Graf zwykły nie ma cykli w pojedynczym wierzchołku, więc macierz sąsiedztwa musi mieć same zera na przekątnej i musi być symetryczna względem tej przekątnej, procedurę grrifewykiy(n:integer;M:matri.\):boolean; begin

for i:- [ to n co begin

it (A[i.i)<>0) theu return (faisc); for j:=i~I to n do