Matematica Discreta
Lezione del giorno 24 aprile 2009
Sappiamo che, dato un qualunque monoide A (rispetto ad una operazione *), il suo sottoinsieme A*, contenente gli elementi simmetrizzabile, è un gruppo rispetto alla stessa operazione.
In particolare, dato il monoide Zm={[0], [1], …., [m-1]} delle classi di congruenza modulo m (rispetto all’operazione di prodotto di classi), abbiamo dimostrato che gli elementi simmetrizzabili sono le classi con rappresentante a compreso fra 1,2,…..,m-1, tali che a,m siano coprimi.
Dunque il sottoinsieme degli elementi simmetrizzabile di Zm : Zm* = {[a] Zm / a=1,2,….,m-1; a,m coprimi}
È un gruppo, rispetto all’operazione di prodotto di classi: ovviamente la sua cardinalità coincide con la funzione di Eulero (m) del modulo m:
Zm* = (m)
Abbiamo anche dimostrato che, per calcolare il simmetrico di una classe [a] rispetto al prodotto di classi in Zm (se tale simmetrico esiste cioè se mcd(a,m)=1) l’algoritmo è il seguente: si rappresenta 1=mcd(a,m) come combinazione lineare 1=ax+my di a,m con coefficienti interi relativi x,y (che si trovano con l’algoritmo Euclideo) ed il simmetrico di [a] coincide con [x].
Usando la simbologia moltiplicativa, il simmetrico [x] di [a] si chiama inverso di [a] e si indica in generale con [a]-1.
Ricordiamo i dettagli dell’algoritmo Euclideo delle divisioni successive.
Siano dati i numeri naturali a,b (con a>b): si effettua una prima divisione di a (dividendo) per b (divisore) ottenendo quoziente q1 e resto r1, dove q1, r1 sono interi 0, con r1<b; si effettuano poi successive divisioni con la regola seguente: effettuata la divisione numero k, se il resto è 0 l’algoritmo si arresta, mentre se il resto è >0 si effettua un’ulteriore divisione numero k+1, in cui il dividendo e il divisore sono rispettivamente il divisore e il resto della divisione numero k; l’ultimo resto non nullo è il mcd(a,b).
Schematizzando:
a=bq1+r1 (q10, 0<r1<b) b=r1q2+r2 (q20, 0<r2<r1) r1=r2q3+r3 (q30, 0<r3<r2) .
.
rn-3=rn-2qn-1+rn-1 (qn-10, 0<rn-1<rn-2) rn-1=mcd(a,b) rn-2=rn-1qn+rn (qn0, rn=0)
Parallelamente si possono calcolare i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by nel modo seguente:
si costruiscono le 2 successioni di numeri interi relativi
s0 ,s1,…..,sn ; t0,t1,….,tn (dove n é il numero di divisioni dell’algoritmo Euclideo) ponendo
s0=1, s1=0, si=si-2-si-1qi-1 (per ogni i>1);
t0=0, t1=0, ti=ti-2-ti-1qi-1 (per ogni i>1)
dove qi-1 è il quoziente della divisione numero (i-1) nell’algoritmo Euclideo.
Basta poi porre x=sn ,y=tn per avere i coefficienti x, y (x è il coefficiente di a; y quello di b).
Esempio.
Verifichiamo se [33] è simmetrizzabile in Z89 in caso affermativo calcoliamone il simmetrico.
Calcoliamo il mcd(88,33). Utilizzando l’algoritmo Euclideo si effettuano n=5 divisioni con i seguenti valori di quoziente e resto:
q1=2, r2=23; q2=1, r2=10; q3=2, r3=3; q4=3, r4=1; q5=3, r5=0
Si conclude che mcd(89,33)=r4=1, dunque [33] è simmetrizzabile in Z89 .
Calcolando le successioni si, ti si ottiene s5=-10, t5=27, dunque la rappresentazione di 1 come combinazione lineare di 89,33 è 1=89x+33y, con x= -10, y=27.
In particolare si ottiene che [33] è simmetrizzabile in Z89 con simmetrico [27] (perché 27 è il coefficiente di 33 nella combinazione lineare).
Nel rappresentare in forma digitale (per esempio in un computer) le classi di:
Zm={[0], [1], …., [m-1]}
possiamo limitarci ad utilizzare solo i valori numerici dei rappresentanti:
Zm={0, 1, …., m-1}.
Ma quando (con tale identificazione classe-numero) si calcolano i risultati delle operazioni di somma e prodotto in Zm si deve avere l’accortezza (se il risultato è >m-1) di considerare la sua riduzione modulo m: la riduzione modulo m di un intero relativo x è l’unico numero intero a compreso fra 0,1.,,,,,m-1 tale che [a]=[x] (cioè tale che ax (mod m)).
Tale riduzione di x modulo m si indica con il simbolo xmodm
Sappiamo per esempio che, se x>0, tale riduzione è il resto della divisione di x per m.
Per esempio 21mod8=5, 28mod7=0 etc…
Dunque per costruire la tavola dell’operazione di somma o prodotto di Zm={0, 1, …., m-1} si fanno corrispondere ordinatamente alle m righe e alle m colonne i numeri 0,1,….,m-1 e nella casella all’incrocio fra riga del numero a e colonna del numero b si inserisce la riduzione (a+b)modm (oppure per il prodotto (ab)modm).
Esempio. La tavola dell’operazione di prodotto di classi in Z4 (già costruita nella lezione precedente) con l’identificazione di ogni classe con il numero che la rappresenta diventa:
0 1 2 3 0
1 2 3
Complessità degli algoritmi
Gli algoritmi di cui ci occuperemo avranno in input uno (o più) numeri naturali: un tipico esempio è l’algoritmo Euclideo delle divisioni successive, in cui in input vi sono 2 numeri naturali a,b e in output viene calcolato il mcd(a,b).
Vogliamo determinare una misura della “complessità” di un algoritmo (e quindi indirettamente del tempo di calcolo). Considereremo operazioni elementari in un algoritmo quelle di somma, sottrazione, prodotto, divisione con quoziente e resto, e calcoleremo la complessità dell’algoritmo in base al numero di operazioni elementari eseguite nell’algoritmo stesso per produrre l’output.
Vogliamo però dare anche una misura della “dimensione” dell’input: poiché le operazioni elementari vengono in genere eseguite (anche con gli usuali metodi scolastici) sulle singole cifre dell’input, è abbastanza logico definire dimensione dell’input uguale al numero di cifre dell’input,
0 0 0 0
0 1 2 3
0 2 0 2
0 3 2 1
rappresentato in una prefissata base b>1 (spesso b=10, oppure b=2, soprattutto nel caso di mezzi di calcolo informatici)
Potremmo allora definire la complessità un algoritmo A come quella funzione f(n) della dimensione n dell’input che coincide con il numero di operazioni elementari eseguite da A quando l’input ha dimensione n.
Tale definizione non sarebbe però univoca, perché potrebbe avvenire che per input diversi (ma con eguale dimensione) il numero di operazioni elementari eseguite sia differente.
Allora una definizione più precisa è la seguente:
complessità di un algoritmo A è la funzione f(n) della dimensione n dell’input che coincide con il numero di operazioni elementari eseguite da A quando l’input ha dimensione n, nel caso peggiore (cioè nel caso in cui il numero di operazioni elementari sia il maggiore possibile, per tutti gli input di dimensione n).
Poiché la complessità f(n) sarà spesso non facile da calcolare con esattezza, ci limiteremo a misurarne la “velocità di crescita”, confrontando f(n) con funzioni conosciute.
In particolare diremo che un algoritmo ha complessità polinomiale se esistono due costanti C,k>0 tali che f(n) Cxn per ogni n (dove n indica sempre la dimensione dell’input).
Diremo invece che un algoritmo ha complessità esponenziale se esistono due costanti C,k>0 (con k>1) tali che f(n)Ckn .
Nota: esistono anche algoritmi di complessità diversa da polinomiale o esponenziale (subesponenziale etc.), che non tratteremo.
Un algoritmo di complessità polinomiale non è in assoluto più veloce di uno di complessità esponenziale, ma il numero di operazioni elementari cresce molto più velocemente se la complessità è esponenziale.
Esempio:
Siano dati l’algoritmo A di complessità f1(n)=n7 (complessità polinomiale), e l’algoritmo B di complessità f2(n)=2n (complessità esponenziale). Per un input di dimensione n=32 (quindi con 32 cifre) l’algoritmo A esegue 327=(25)7=235 operazioni elementari, mentre l’algoritmo B ne esegue 232 (quindi un numero inferiore): se ogni operazione è eseguita in 1 milionesimo di secondo, l’algoritmo A impiega un massimo di circa 9 ore e mezza, l’algoritmo B circa 1 ora e 12 minuti (quindi B è più veloce di A). Ma per un input di dimensione doppia n=64 (quindi con 64 cifre), l’algoritmo A esegue 647 operazioni (in circa 52 giorni), ma l’algoritmo B esegue 264 operazioni (in circa 585.00 anni !!!!!).
