Distingueremo alcune classi di algoritmi in base alla loro complessità, ossia in base al numero di operazioni elementari, come funzione della taglia dell’input.

Matematica Discreta II

Lezione del giorno 18 ottobre 2007 Complessità degli algoritmi

Gli algoritmi di cui ci occuperemo avranno in input uno (o più) numeri naturali. Considereremo operazioni elementari in un algoritmo quelle di somma, sottrazione, prodotto, divisione con quoziente e resto.

In un algoritmo definiremo taglia dell’input il numero x di cifre dell’input stesso, rappresentato in una base fissata b (in generale b=2 o b=10): si dimostra facilmente che le definizioni che daremo sono indipendenti dalla base scelta per rappresentare l’input.

Distingueremo alcune classi di algoritmi in base alla loro complessità, ossia in base al numero di operazioni elementari, come funzione della taglia dell’input.

Se n=n(x) è il numero di operazioni elementari eseguite nell’algoritmo (in funzione di un input di taglia x) diremo che l’algoritmo ha complessità polinomiale se n=n(x) è  di una espressione polinomiale in x:

n  a

+a

x+a

x

+……+a

x

con a

costanti reali

Si può osservare che la complessità è riferita a una quantità (funzione della taglia x dell’input) che maggiora il numero di operazioni con input di taglia x, ma ciò non impedisce che per particolari valori dell’input il numero di operazioni sia molto minore del maggiorante previsto.

L’espressione polinomiale in x che maggiora n può essere sempre ridotta ad un solo monomio di grado massimo osservando che:

n  a

+a

x+a

x

+……+a

x

 a

x

+a

x

+a

x

+…..+a

x

= (a

+a

+a

+…..+a

)x

Dunque un algoritmo è di complessità polinomiale quando esistono c, k costanti reali (con k intero) tali che n=n(x)cx

(dove n è il numero di operazioni, x la taglia dell’input).

Diremo che un algoritmo ha complessità esponenziale se esistono c, k costanti reali tali che n=n(x)c

(dove come sopra n è il numero di operazioni, x la taglia dell’input).

Nota: esistono anche algoritmi di complessità diversa da polinomiale o esponenziale (subesponenziale etc.). Inoltre in molti testi il concetto di operazione elementare è definito riferendosi a operazioni sui singoli bits dell’input ma è facile verificare che si ottengono definizioni equivalenti a quelle precedenti.

Un algoritmo di complessità polinomiale non è in assoluto più efficiente di uno di complessità esponenziale, ma il maggiorante del numero di operazioni elementari cresce ovviamente molto meno rapidamente al crescere della dimensione dell’input.

Esempio:

Siano dati l’algoritmo A di complessità polinomiale con numero di operazioni elementari n=n(x) 

x

(in funzione della taglia x dell’input), e l’algoritmo B di complessità esponenziale con numero di

operazioni elementari s=s(n)  2

. Per un input di dimensione n=32 (cifre binarie) l’algoritmo A

esegue un massimo di 32

=2

operazioni, mentre l’algoritmo B ne esegue un massimo di 2

(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. Ma per un input

di dimensione doppia n=64 (cifre binarie), l’algoritmo A esegue un massimo di 64

operazioni

(circa 52 giorni), l’algoritmo B un massimo di 2

operazioni (circa 585.00 anni !!!).

Per la soluzione di alcuni problemi matematici sono già stati trovati algoritmi di complessità polinomiale: per esempio nel campo dei test di primalità (algoritmi che, dato in input un naturale n>1, escono con output “n è primo” oppure “n non è primo”) è stato trovato nel 2002 un algoritmo detto AKS (autori Agrawal, Kayal, Saxena) di complessità polinomiale.

Per la soluzione di altri problemi esistono algoritmi di complessità esponenziale (o subesponenziale) ma, a tutt’oggi, non sono disponibili algoritmi di complessità polinomiale (anche se in futuro potrebbero essere implementati, sempre che ne esistano): uno di questi casi riguarda gli algoritmi di fattorizzazione, che, dato in input un naturale n>1, calcolano in output la lista dei fattori primi di n.

Tornando al gruppo Z

* degli elementi simmetrizzabili del monoide Z

rispetto al prodotto, poiché esso contiene tutte le classi [a] con a=1,2,….,m-1, tali che a,m sono coprimi, la sua cardinalità coincide con la ben nota funzione di Eulero (m).

Ricordiamo che, se è nota la fattorizzazione di m in prodotto di potenze di numeri primi distinti:

m = p

p

...p

allora è possibile calcolare facilmente la funzione di Eulero di m mediante la formula (ottenuta applicando il principio di inclusione-esclusione):

(m) = m(1-1/p

)(1-1/p

)……(1-1/p

)= p

 1 p

 1 ...p

 1 _(p

_-1)(p

_-1)…..(p

_-1).

Viceversa la conoscenza del valore (m) può portare al calcolo dei fattori primi di m: per esempio se m=pq è il prodotto di 2 primi distinti p,q, allora (m)=(p-1)(q-1)=pq-(p+q)+1=m-(p+q)+1, da cui si ottiene il sistema somma-prodotto nelle incognite p,q:

pq = m

p+q=m+1-(m)

e si possono calcolare p,q come soluzioni dell’equazione di 2° grado x

-(p+q)x+pq=0.

Da quanto precede si deduce che il problema della fattorizzazione di m e quello del calcolo di (m) hanno la stessa complessità: attualmente non esiste un algoritmo di complessità polinomiale per il calcolo di (m).

Sottogruppi di un gruppo.

Siano A un gruppo (in notazione moltiplicativa con neutro 1

, e con simmetrico x

=inverso di x, per ogni elemento x) e B un suo sottoinsieme non vuoto.

Diremo che B è sottogruppo di A se B è chiuso rispetto all’operazione di A e se B anch’esso gruppo, rispetto alla stessa operazione di A, quindi se valgono le proprietà:

1) chiusura di B: dati x,yB si ha xyB 2) associativa in B

3) esistenza di un neutro in B

4) per ogni elemento xB esistenza dell’inverso di x in B

Notiamo che la 2) è superflua, in quanto la proprietà associativa già vale in A.

Riguardo alla 3) e alla 4) dimostreremo che l’elemento neutro di B (se esiste) coincide con l’elemento neutro di A, e che , dato l’elemento xB, l’inverso di x in B (se esiste) coincide con l’inverso di x in A.

Premettiamo una proprietà importante di ogni gruppo A, detta legge di cancellazione:

a) se x,y,zA e se xz=yz, allora x=y (legge di cancellazione a destra)

b) se x,y,zA e se zx=zy, allora x=y (legge di cancellazione a sinistra)

Per dimostrare per esempio la a) si può moltiplicare a destra per z

ottenendo, per l’associativa:

(xz)z

= (yz)z

; x(zz

) = y(zz

) ; x1

= y1

; x = y (analogo ragionamento per dimostrare la b)).

Tornando alle condizioni 1),2),3),4) del sottogruppo B, come premesso osserviamo che:

- se B ha elemento neutro 1

, si ha 1

=1

; infatti dalle eguaglianze 1

1

=1

=1

1

si ottiene la tesi (per cancellazione a sinistra di 1

)

- se un elemento xB ha inverso x’ in B, allora x’=x

(dove x

indica il simmetrico di x in A):

infatti dalle eguaglianza xx’=1

=1

=xx

si ottiene la tesi (per cancellazione a sinistra di x).

Riassumendo, per verificare se B è sottogruppo del gruppo A, si devono verificare le seguenti proprietà:

1) chiusura di B: dati x,yB si ha xyB 2) il neutro di A appartiene a B

3) per ogni elemento xB, l’inverso x

di x in A appartiene a B

Queste 3 proprietà si possono ridurre ad una sola, come dimostra il seguente:

Teorema.

Se B è un sottoinsieme non vuoto del gruppo A: B è sottogruppo di A  x,yB si ha xy

B Dimostrazione:

: Se x,yB, per la proprietà 3) dei sottogruppi si ha y

B, e per la proprietà 1) si ottiene xy

B.

: Dimostriamo le proprietà 1),2),3) dei sottogruppi.

2) : Preso un generico elemento bB, e posto x=b, y=b, dall’ipotesi segue xy

=bb

=1

B 3) : Preso un generico elemento bB, e posto x=1

B, y=b, dall’ipotesi segue xy

=1

b

= b

B 1) : Presi i generici elementi b,cB, e posto x=b, y=c

B, dall’ipotesi segue xy

=b(c

)

= bcB Esempio:

Considerato il gruppo dei razionali non nulli Q*=Q-{0} rispetto al prodotto, e il sottoinsieme B

contenente tutte le potenze 2

di base 2 ed esponente k intero relativo, si ha che B è sottogruppo di

Q* in quanto x=2

,y=2

B si ha xy

=2

B .