Teoria dei numeri e Crittografia: lezione del 24 marzo 2011 Algoritmi
Gli algoritmi che studieremo nel corso saranno per lo più algoritmi aritmetici relativi ai numeri naturali: ognuno di essi è un procedimento composto da un valore in entrata (input) costituito da uno (o più) numeri naturali, da un numero finito di passaggi (steps), e da un valore in uscita (output) costituito da uno (o più) numeri (non necessariamente naturali) oppure da una affermazione relativa all’input (del tipo “si”o “no”, “vero” o “falso” etc…)
Esempi di algoritmi aritmetici:
a) algoritmo della divisione: input a,b (numeri naturali); steps: si calcolano 2 interi non negativi q,r tali che a=bq+r, con r<b; si esce con output q (quoziente), r (resto)
b) test di primalità “ingenuo”: input n (numero naturale >1); steps: per i=2,3,…,n-1 si verifica se i è divisore di n; se per qualche i la verifica è positiva si esce con output “n non è primo”, altrimenti si esce con output “n è primo”
Complessità di un algoritmo
La complessità di un algoritmo è una misura delle risorse necessarie per eseguirlo: al giorno d’oggi ogni algoritmo viene eseguito da un computer.
Ci interesseremo solo di complessità “temporale” (quindi relativa al tempo di esecuzione dell’algoritmo) e non per esempio di quella “spaziale” (relativa allo spazio occupato nella memoria del computer dai dati, anche temporanei, utilizzati durante l’esecuzione dell’algoritmo).
I dati numerici coinvolti in un algoritmo saranno rappresentati in base 2 cioè in forma binaria.
Ricordiamo un ben noto risultato aritmetico (che dimostreremo formalmente in seguito): fissato un numero naturale b>1 (base), ogni numero naturale a si può rappresentare (in modo unico) nella forma
a=a
k-1b
k-1+a
k-2b
k-2+…+a
1b
1+a
0b
0(detta rappresentazione di a in base b) dove gli a
i(cifre) sono numeri interi tali che 0a
ib-1, e dove a
k-1≠0.
In tale caso si usa la simbologia m=(a
k-1, a
k-2,….,a
1, a
0)
b.
In particolare (scegliendo la base b=2) ogni numero naturale a ha una rappresentazione binaria della forma
a=a
t2
t+a
t-12
t-1+…+a
12
1+a
02
0dove gli a
i(cifre binarie o bits) assumono come valori possibili 0,1, e dove a
k-1=1.
Data la rappresentazione del numero naturale a in base b>1 a=a
k-1b
k-1+a
k-2b
k-2+…+a
1b
1+a
0b
0il numero naturale k (coincidente con il numero di cifre usate nella rappresentazione) è detto lunghezza di a in base b ed è indicato con il simbolo L
b(a).
Nel caso di rappresentazione binaria useremo semplicemente il simbolo L(a) invece di L
2(a), e parleremo di lunghezza di a, sottintendendo la base 2.
La lunghezza k=L
b(a) di a in base b si può caratterizzare con la seguente proprietà:
b
k-1 a < b
k(quindi k è il più grande dei numeri naturali che soddisfano la proprietà b
k-1 a).
Infatti basta osservare che a=a
k-1b
k-1+a
k-2b
k-2+…+a
1b
1+a
0b
0 a
k-1b
k-1 b
k-1(perchè a
0,a
1,….,a
k-20 ed a
k-11) e che (essendo le cifre a
i (b-1)) si ha anche:
a(b-1)(b
k-1+b
k-2+…+b
1+b)=(b
k-1)<b
k.
Da ciò segue anche che se k=L
b(a) si ha:
k-1 log
b(a) < k
dunque k-1 è il più grande intero log
b(a), ossia la parte intera di log
b(a):
k-1 = log
b(a) L
b(a) = k = log
b(a) +1
In particolare nel caso b=2 la lunghezza di a è L(a) = log
2(a) +1 .
Se vogliamo dare una “stima” del tempo necessario affinché un algoritmo venga eseguito, e quindi della sua “complessità” di calcolo, dobbiamo scegliere delle operazioni “elementari”, che fungano da “unità di misura” e mediante le quali si possano costruire tutte le altre operazioni eseguite nei diversi algoritmi; sceglieremo come operazione elementare l’operazione di somma sui singoli bits con riporto (carry). Tale operazione, dati 2 bits da sommare x,y=0,1 e fissato un valore c=0,1 del carry, calcola il bit risultato x+y e il nuovo valore c
1del carry, secondo le regole esposte nella seguente tabella:
Nella prima e seconda colonna vi sono rispettivamente il valore del bit x e il valore del bit y; nella terza colonna il valore c del carry prima della somma;
nella quarta il valore del bit somma x+y; nella quinta il nuovo valore aggiornato c
1del carry dopo la somma. Per esempio se x=1, y=0 e se il carry (prima della somma) è c=1, allora dalla quarta riga si ricava il bit somma x+y=0 (quarta colonna), e il valore aggiornato del carry c
1=1 (quinta colonna).
Formalmente l’operazione di somma sui singoli bits con riporto é una funzione:
BitSum: {0,1}x{0,1}x{0,1} {0,1}x{0,1} definita da BitSum(x,y,c)=(x+y,c
1)
e in genere essa è implementata nell’hardware nel processore centrale (CPU) del computer.
Se trascuriamo il tempo che il computer impiega per altri tipi di operazioni più veloci (accesso alla memoria, operazioni di shift, confronto fra bits, scrittura di bits etc..) possiamo ragionevolmente supporre che il tempo totale dell’algoritmo sia proporzionale al numero di operazioni elementari eseguite (secondo una costante di proporzionalità che all’incirca coincide con il tempo impiegato dal computer per eseguire una operazione elementare).
(Nota: E’ ovvio che la nostra scelta dell’operazione BitSum come operazione elementare è dovuta al fatto che ci occuperemo di algoritmi di tipo “aritmetico”. Per altre categorie di algoritmi potrebbe essere invece opportuno una scelta diversa: per esempio per gli algoritmi di ordinamento (sorting) sarebbe opportuno scegliere come operazioni elementari quelle di confronto di bits e di accesso alla memoria per la lettura e scrittura dei dati da ordinare).
E’ opportuno che la nostra stima sia funzione della “grandezza” dell’input, e dunque dobbiamo scegliere un modo per misurare quest’ultima: poiché le operazioni elementari agiscono sui singoli bits, è naturale ricorrere al già visto concetto di lunghezza di un numero naturale nella sua rappresentazione binaria, cioè al numero di bits 0,1 utilizzati per rappresentarlo.
Dato un algoritmo A potremmo allora definire il valore Time
A(x) come il numero di operazioni elementari eseguite dall’algoritmo A quando l’input ha lunghezza x: in questo modo moltiplicando tale valore per il tempo impiegato dal computer per svolgere una singola operazione elementare potremmo ottenere una stima abbastanza valida del tempo impiegato per eseguire l’algoritmo, sempre quando l’input ha lunghezza x.
Tale definizione non sarebbe però univoca perché due diversi input di eguale lunghezza x potrebbero dar luogo a un diverso numero di operazioni elementari nell’esecuzione dell’algoritmo.
x y c x+
y c
1