Matematica Discreta II - Matematica e Informatica

Matematica Discreta II Lezione del giorno 22 novembre 2007 Algoritmo di fattorizzazione  di Pollard. Premettiamo alcune considerazioni su un argomento di Calcolo delle Probabilità: il cosiddetto paradosso dei compleanni. Siano n,m numeri naturali , S un insieme finito di cardinalità m e sia data una successione finita di n termini scelti in S (anche non distinti): a1, a2, ……, an in modo che gli ai siano scelti random in modo “uniforme” (dal punto di vista della probabilità) fra gli elementi di S, nel senso che per ogni indice i, ogni elemento dell’insieme S abbia la stessa probabilità 1/m di essere scelto come elemento ai : un esempio concreto si ha inserendo in un’urna m palline numerate da 1 ad m, fisicamente identiche, ed estraendo casualmente in successione n palline reinserendo ad ogni estrazione la pallina estratta nell’urna. Calcoliamo la probabilità che almeno 2 degli elementi della successione coincidano. Se n>m ovviamente è certo che ciò avverrà, quindi supponiamo nm. Calcoliamo dapprima la probabilità che tutti gli elementi della successione siano distinti. Fissato a1, la probabilità che a2 sia diverso da a1 è (m-1)/m; fissati a1,a2 distinti, la probabilità che a3 sia diverso da a1 e da a2 è (m-2)/m , quindi la probabilità che a1, a2, a3 siano tutti distinti è il prodotto [(m-1)/m][(m-2)/m]=(m-1)(m-2)/m2. Iterando il ragionamento si ottiene che la probabilità che a1, a2, ….., an siano tutti distinti è: [(m-1)(m-2)…..(m-n+1)]/mn-1 dunque la probabilità che almeno 2 degli elementi a1, a2, ….., an coincidano è una funzione delle variabili n,m, data da: p=p(n,m)=1-[(m-1)(m-2)…..(m-n+1)]/mn-1 (sempre nell’ipotesi nm) Con ragionamenti analitici, sfruttando lo sviluppo in serie di Taylor della funzione ex, si ottiene che una buona approssimazione per p(n,m) è: p(n,m)  1  e



n2 2m

da cui si ricava che, fissato m e fissato un valore di probabilità p con 0