• Non ci sono risultati.

Matematica Discreta Lezione del giorno 4 maggio 2009

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Matematica Discreta Lezione del giorno 4 maggio 2009"

Copied!
2
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 2 pagine )

Testo completo

(1)

Matematica Discreta

Lezione del giorno 4 maggio 2009

Abbiamo dimostrato che, dati 2 numeri naturali a,b con a>b, il numero m di divisioni eseguite dall’algoritmo Euclideo per calcolare il mcd(a,b) non è superiore al quintuplo del numero di cifre (in base 10) dell’input b.

Notiamo che tale limite superiore può anche essere raggiunto: per esempio nel caso a=144, b=89, facendo i calcoli si verifica che il numero di divisioni effettuate è m=10 (si ottiene alla fine che mcd(144,89)=1), dunque m è uguale esattamente al quintuplo del numero di cifre di b=89 in base 10. Possiamo anche notare che i numeri 144, 89 sono numeri di Fibonacci: precisamente 89=F

10

, 144=F

11

.

Se n è il numero di cifre in base 10 dell’input b, e se f(n) indica il numero di operazioni elementari eseguite dall’algoritmo Euclideo, si ha dunque f(n)  5n: dunque l’algoritmo Euclideo per il calcolo del mcd(a,b) ha complessità polinomiale (perché f(n)  Cn

k

, dove le costanti C,k hanno il valore C=5, k=1).

Se vogliamo poi calcolare anche i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by, dobbiamo anche costruire le successioni di numeri interi relativi:

s

0

,s

1

,…..,s

m

; t

0

,t

1

,….,t

m

(dove m é il numero di divisioni dell’algoritmo Euclideo) ponendo

s

0

=1, s

1

=0, s

i

=s

i-2

-s

i-1

q

i-1

(per ogni i>1);

t

0

=0, t

1

=0, t

i

=t

i-2

-t

i-1

q

i-1

(per ogni i>1)

dove q

i-1

è il quoziente della divisione numero (i-1) nell’algoritmo Euclideo.

Basta poi porre x=s

m

,y=t

m

per avere i coefficienti x, y (x è il coefficiente di a; mentre y é quello di b).

Questo algoritmo comporta (oltre alle m divisioni dell’algoritmo Euclideo) l’esecuzione di un prodotto e una differenza per il calcolo di ognuno dei termini s

2

,…..,s

m

; t

2

,…..,t

m

(i termini s

0

,s

1

,t

o,

t

1

sono già fissati) per un totale di m+4(m-1) operazioni elementari. Dunque il numero di operazioni elementari per il calcolo dei coefficienti x,y è m+4(m-1)=5m-4<5m25n (sempre se n indica il numero di cifre di b in base 10). Anche questo algoritmo per il calcolo dei coefficienti x,y ha dunque complessità polinomiale.

Poiché tale algoritmo permette di calcolare il simmetrico (rispetto al prodotto di classi) di una classe di congruenza [a] modulo m (nel caso in cui essa sia simmetrizzabile cioè se mcd(a,m)=1), anche il calcolo del simmetrico di una classe di congruenza si può effettuare con un algoritmo di complessità polinomiale (quindi con un algoritmo “efficiente”).

Potenza di un elemento di un gruppo ad esponente intero non negativo.

Siano A un gruppo rispetto all’operazione * ed aA un elemento fissato.

Per ogni numero naturale kN definiamo la potenza a

k

di a con esponente k nel modo seguente:

a

k

= a*a*….*a (dove il numero degli operandi coincide con l’esponente k) Dunque:

a

1

=a, a

2

=a*a, a

3

=a*a*a etc…

(notare che la validità della proprietà associativa ci permette di non specificare come si associano gli operandi: per esempio a

3

=(a*a)*a = a*(a*a)).

Estendiamo poi convenzionalmente la definizione di potenza anche al caso di un esponente nullo, definendo: a

0

= e (elemento neutro di A).

(2)

Esempi:

1) Consideriamo il gruppo delle classi di congruenza modulo 20 rispetto all’operazione di somma di classi:

Z

20

= { [0],[1],[2],[3],….,[19] } e fissiamo a=[3].

Allora per esempio:

[3]

3

=[3]+[3]+[3]=[3+3+3]=[9]

[3]

8

=[3]+[3]+[3]+[3]+[3]+[3]+[3]+[3]=[3+3+3+3+3+3+3+3]=[24]=[4]

(la riduzione di 24 modulo 20 è 4, perché 4 è il resto della divisione di 24 per 20) [3]

0

=[0] (perché [0] è l’elemento neutro).

Consideriamo invece il gruppo delle classi di congruenza modulo 20 che sono simmetrizzabili rispetto all’operazione di prodotto di classi:

Z

20

* = {[1],[3],[7],[9],[11],[13],[17],[19]}

e fissiamo di nuovo a=[3].

Allora per esempio:

[3]

3

=[3][3][3]=[333]=[27]=[7]

[3]

0

=[1] (perché [1] è l’elemento neutro).

2) Consideriamo il gruppo F(X)* delle funzioni biunivoche da un insieme X in sé stesso, dove X={a,b,c} ha cardinalità 3, rispetto all’operazione di composizione di funzioni.

Fissiamo la funzione biunivoca f: X  X definita da f(a)=b, f(b)=c, f(c)=a.

Si ha allora:

f

2

=ff dove ff: X  X è la funzione biunivoca definita da:

(ff)(a)=f(f(a))=f(b)=c, (ff)(b)=f(f(b))=f(c)=a, (ff)(c)=f(f(c))=f(a)=b Invece:

f

3

=fff=f

2

f dove f

3

=f

2

f: X  X è la funzione biunivoca definita da:

(f

2

f)(a)=f

2

(f(a))=f

2

(b)=a, (f

2

f)(b)=f

2

(f(b))=f

2

(c)=b, (f

2

f)(c)=f

2

(f(c))=f

2

(a)=c

dunque la funzione f

3

coincide con la funzione identical i

X

: X  X (che è anche elemento neutro del gruppo F(X)*).

Per le potenze di un elemento a di un gruppo A valgono le stesse proprietà delle potenze numeriche:

comunque presi gli interi non negativi h,kZ si ha:

1) (a

h

)*(a

k

)=a

h+k

2) (a

h

)

k

=a

hk

Dimostriamo per esempio la 1), distinguendo 3 casi e in ognuno di essi dimostrando la tesi:

caso 1: h=0; allora (se e è il neutro di A) (a

h

)*(a

k

)=(a

0

)*(a

k

)=e*(a

k

)=a

k

=a=a

0+k

=a

h+k

; caso 2: k=0 (dimostrazione simile)

caso 3: h,k>0; allora (a

h

)*(a

k

)=(a*a*…*a)*(a*a*…*a) (dove nella prima parentesi vi sono h operandi, nella seconda k operandi), dunque (a

h

)*(a

k

)=a*a*…*a (con un totale di h+k operandi) e si conclude che (a

h

)*(a

k

)=a

h+k

anche in questo caso.

La dimostrazione della 2) segue uno schema simile.

Riferimenti

Scarica adesso ( DOC - 2 pagine - 38.50 KB )

Documenti correlati

Matematica Discreta Lezione del giorno 15 gennaio 2009

Fissato un intero m (detto modulo) abbiamo definito una relazione di equivalenza nell’insieme Z dei numeri interi relativi, detta congruenza aritmetica modulo m: in tale

Matematica Discreta Lezione del giorno 15 aprile 2009

2) Se l’elemento xA è simmetrizzabile con simmetrico x’A, allora anche x’ è simmetrizzabile con simmetrico x (perché xx’=x’x=e). Rispetto a tale operazione, per

Matematica Discreta Lezione del giorno 18 marzo 2009

L’ipotesi che il grafo sia semplice implica che il contorno di una faccia ha almeno 3 archi (un contorno con 2 soli archi implica che i 2 archi uniscono la stessa coppia di

Matematica Discreta Lezione del giorno 22 aprile 2009

Nella lezione precedente abbiamo osservato che se un insieme A é dotato di operazione , e se in A é anche definita una relazione di equivalenza R compatibile con l’operazione 

Matematica Discreta Lezione del giorno 23 gennaio 2009

Nella definizione più formale di grafo, abbiamo detto che esiste una funzione (detta funzione di adiacenza) dall’insieme A degli archi all’insieme V 2 di tutti gli insiemi

Matematica Discreta Lezione del giorno 23 marzo 2009

- nei cammini di lunghezza minima fra coppie di vertici coinvolti in tale accoppiamento, si costruiscono archi “gemelli” di quelli originali e si

Matematica Discreta Lezione del giorno 24 aprile 2009

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

Matematica Discreta Lezione del giorno 24 aprile 2009

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