PROBABILITA' DI NON COLLISIONE


Il calcolo della probabilita' di non collisione in un archivio dipende dall'ampiezza dell'archivio e dal numero di elementi da inserire.
Poniamo: n=ampiezza dell'archivio,
x=numero di elementi da inserire.
La probabilita' di non collisione e':
al 1mo inserimento e' n/n,
al 2do inserimento e' (n-1)/n,
al 3zo inserimento e' (n-2)/n,
:
:
al x-esimo inserimento e' [n-(x-1)]/n.
Quindi la probabilita' di non avere NESSUNA collisione con x inserimenti in un archivio di ampiezza n e'= n/n*(n-1)/n*(n-2)/n*..........*[n-(x-1)]/n (=pnc).
pnc=probabilita' di non collisione
Con dei passaggi matematici:
ln(pnc)=ln(n/n)+ln[(n-1)/n]+............+ln[(n-(x-1))/n] con ln=logaritmo naturale
=ln1+ln(1-1/n)+..............+ln[1-(x-1)/n]
Sapendo che matematicamente ln(1-y)=-y-(y^2)/2!-(y^3)/3!-............ e che la parte piu' importante e' -y allora:
ln(pnc)=-1/n-2/n-3/n-.........-(x-1)/n (ricordati che ln(n/n)=0)
Sapendo che -1/n-2/n-.......-(x-1)/n=-[x(x-1)]/2*n allora ln(pnc)=-[x(x-1)]/2*n.
In conclusione pnc=e^-[x(x-1)]/2*n.
Un esempio.
n=365, x=23 pnc=e^-[23(23-1)]/2*365=e^-0,693150685=0,5
La probabilita' di collisione e' 1-pnc.

ALTRO CASO


Se voglio sapere quanti inserimenti posso effettuare in un archivio del quale conosco l'ampiezza mantenendo una pnc=> di un preciso valore devo risolvere la seguente disequazione:
-[x(x-1)]/2*n=>ln(pnc)

Conoscendo sia l'ampiezza dell'archivio (n), sia la probabilia' di non collisione (pnc) da rispettare devo calcolare il numero massimo di inserimenti possibili (x). Con dei passaggi matematici:
-[x(x-1)]/2*n=>ln(pnc)
-[x(x-1)]-2*n*ln(pnc)=>0
x(x-1)+2*n*ln(pnc)<=0
x<=[1+-(1-8*n*ln(pnc))^0,5]/2
sapendo che x non puo' essere un numero negativox<=[1+(1-8*n*ln(pnc))^0,5]/2 (con x=>0) .
Un esempio:
n=365 pnc=0,5
ln(pnc)=-0,693147181 8*n*ln(pnc)=-2024
x<=[1+(1-(-2024))^0,5]/2<=[1+2025^0,5]/2<=[1+45]/2<=23
In un archivio di ampiezza 365 per avere una probabilita' di non collisione di 0,5 posso fare al massimo 23 inserimenti.

CLICCARE QUI PER RITORNARE AD HASHED FILES