Matematica Discreta
Lezione del giorno 24 aprile 2009
Sia m un numero naturale che, rappresentato in una base prefissata b>1, abbia un numero n di cifre (si intende che n è il minimo numero di cifre utilizzate per rappresentare m in base b, quindi non vi sono cifre “superflue” uguali a 0 a sinistra, e la prima cifra a sinistra è dunque non nulla).
Se an-1,an-2,……,a1,a0 sono le n cifre di m in base b si ha:
m = an-1bn-1+an-2bn-2+…….+a1b1+a0b0 (con tutte le cifre ai con valori fra 0,1,…,b-1, e con an-10) Supponiamo per esempio la base b=2 (rappresentazione “binaria” di m).
Allora:
m = an-12n-1+an-22n-2+…….+a121+a020 (con tutte le cifre ai con valori 0,1, e con an-10 cioè an-1=1) Dunque:
m = 2n-1+an-22n-2+…….+a121+a020
Poiché la quantità an-22n-2+…….+a121+a020 è 0 si ha certamente:
m 2n-1
Ma inoltre, poiché ogni cifra ai é 1, si ha anche:
m = 2n-1+an-22n-2+…….+a121+a020 2n-1+2n-2+…….+21+20 = 2n-1
(dove l’ultima eguaglianza 2n-1+2n-2+…….+21+20 = 2n-1 si dimostra facilmente applicando il principio di induzione). Dunque si ha:
m < 2n
In totale, se n è il numero di cifre di m in base 2:
2n-1 m < 2n
Un risultato analogo si può dimostrare per una qualunque base b>1: se n è il numero di cifre di m in base b:
bn-1 m < bn
Per esempio se m ha 4 cifre in base b=10 allora:
1000 = 103 m < 104 = 10000
dunque i possibili valori di m sono da 1000 a 9999.
Esaminiamo un esempio di algoritmo per calcolarne la complessità.
Supponiamo di volere verificare se un numero m naturale >1 è primo o non è primo: gli algoritmi che risolvono tale problema sono detti “test di primalità”.
Poiché m è primo se m non ha divisori non banali d (con 1<d<n) si potrebbe implementare il seguente algoritmo come test di primalità:
1) si prende in input il valore m>1
2) per d=2,3,…..,m-1 si effettua la divisione di m per d
3) se per qualcuno dei valori d il resto della divisione è 0 (dunque si è trovato un divisore non banale d di m) l’algoritmo termina con output “m non è primo”; se invece per tutti i valori d il resto della divisione è sempre diverso da 0, l’algoritmo termina con output “m è primo”
Il numero delle divisioni effettuate nell’algoritmo (nel caso peggiore) è uguale al numero di valori d nel ciclo dell’istruzione 2), dunque è =m-2.
Se n è il numero di cifre dell’input m in base 2 (la cosiddetta dimensione di m), la funzione f(n) che calcola il numero di operazioni elementari effettuate nell’algoritmo per un input di dimensione n, soddisfa:
f(n) < m < 2n (ricordando quanto detto sopra)
Dunque la complessità di tale algoritmo è esponenziale (perché f(n) Ckn dove le costanti C,k sono C=1, k=2): non è un algoritmo “efficiente”.
Tale test di primalità “ingenuo” si può rendere anche più efficiente con vari accorgimenti, ma fino a pochi anni fa non era stato trovato nessun test di primalità di complessità polinomiale. Nel 2002 i matematici indiani Agrawal, Kayal, Saxena pubblicarono l’articolo “Primes in P” in cui veniva implementato per la prima volta un test di primalità di complessità polinomiale (anche se il test ha attualmente tempi di calcolo troppo alti per avere un uso pratico).
Ci domandiamo: qual è la complessità dell’algoritmo Euclideo delle divisioni successive ?
Sappiamo che esso risolve vari problemi: dati i numeri naturali a,b permette di calcolare il mcd(a,b) e calcola i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by; inoltre, data una classe di congruenza [a] modulo m, permette di calcolare (se esiste) il simmetrico di [a] rispetto all’operazioni di prodotto di classi.
In pratica la domanda è la seguente: nel caso peggiore, qual è il numero di divisioni effettuate nell’algoritmo Euclideo ?
