An optimal search procedure


Ratko Tošić




U radu je posmatran sledeći problem: (P) U skupu $X=\{x_1,x_2,\dots,x_n\}$ su tačno dva neispravna (nepoznata) elementa. Naš cilj je da identifikujemo oba neispravna elementa testirajući ispravnost nekih podskupova $A$ skupa $X$, pri čemu za skup $A$ kažemo da je neispravan ako sadrži barem jedan neispravan element. Svaki pojedinačni test informiše nas o ispravnosti testiranog skupa, ali u slučaju neispravnosti ne i o broju neispravnih elemenata u njemu. Kriterijum optimalnosti istražnog postupka (strategije) je minimum maksimalnog broja testova za identifikaciju dvostruke neispravnosti. Ako maksimalan broj testova optimalne strategije obeležimo sa $l_2(n)$, tada važi: extsc{Teorema.} Neka je \begin{equation} t_k=F_{[\frac k2]}+2^{[\frac k2]}+(1+(-1)^{k+1})\cdot2^{\frac{k-5}2} \end{equation} za $k=2,3,\dots$, gde je $F_j$ $j$-ti član Fibonačijevog niza \begin{equation} F_1=1, F_2=1; F_j=F_{j-1}+F_{j-2}\quad(j=3,4,\dots). \end{equation} Tada je $l_2(t_k)=k$. Dokaz je konstruktivan i omogućava efektivno nalaženje optimalne strategije. Za one prirodne brojeve $n$, koji nisu članovi niza (1), dobija se optimalna ili skoro optimalna strategija, tj. takva koja zahteva samo jedan test više od optimalne strategije.