Matematica Discreta Lezione del giorno 29 aprile 2009

Matematica Discreta

Lezione del giorno 29 aprile 2009

Il nostro obiettivo è quello di calcolare (nel caso peggiore) il numero di divisioni effettuate nell’algoritmo Euclideo, come funzione della “dimensione” dell’input (cioè del numero di cifre dell’input rappresentato in una base prefissata). A tale scopo ci serviremo di alcuni concetti preliminari.

Seconda forma del principio di induzione.

Ricordiamo il principio di induzione:

Principio di induzione: se P(n) è un predicato nella variabile n (dove n varia fra i numeri naturali) e se sono vere le seguenti 2 ipotesi:

a) P(1) è vero

b) per ogni naturale k: P(k) vero  P(k+1) vero allora P(n) è vero per ogni naturale n.

Tale principio è detto anche I

^a

forma del principio di induzione, in quanto vi è un’altra formulazione che ora dimostreremo:

II

^a

forma del principio di induzione: se P(n) è un predicato nella variabile n (dove n varia fra i numeri naturali) e se sono vere le seguenti 2 ipotesi:

a) P(1) è vero

b) per ogni naturale k>1: P(1), P(2), …., P(k-1) veri  P(k) vero allora P(n) è vero per ogni naturale n.

Dimostrazione:

Per assurdo supponiamo che esista qualche numero naturale che rende falso il predicato P: dunque è non vuoto l’insieme S dei numeri naturali x tali che P(x) è falso. Applicando l’assioma del minimo, esisterà un minimo s in S (quindi in particolare P(s) è falso). Si ha s>1 (per l’ipotesi a)). Poiché s è il minimo in S, i numeri naturali 1,2,….,s-1 (che sono <s) non appartengono all’insieme S:

1,2,…,s-1S

dunque P(1),P(2),…,P(s-1) sono veri, e da ciò segue che P(s) è vero (per l’ipotesi b)), (contraddizione perché P(s) è falso).

Osservazione : esistono delle versioni del principio di induzione (I

^a

e II

^a

forma) in cui la variabile n non assume tutti i valori naturali ma solo quelli compresi fra 1,2,….,m (dove m è un naturale fissato). La tesi in questo caso è “P(n) è vero per ogni n=1,2,….,m”, e la dimostrazione è simile a quelle precedenti.

Successione dei numeri di Fibonacci.

La successione F

0

,F

1

,F

2

,F

3

,……. dei numeri di Fibonacci è la successione di numeri naturali definita nel modo seguente:

F

0

=1; F

1

=1; per ogni indice n>1 F

n

=F

n-1

+F

n-2

(dunque, dall’indice n=2 in poi, ogni termine della successione si ottiene sommando i 2 termini che lo precedono).

Quindi F

2

=F

0

+F

1

=2; F

3

= F

1

+F

2

=3, F

4

= F

2

+F

3

=5, F

5

= F

3

+F

4

=8 etc…

Tale successione interviene in molti problemi combinatori, come nell’esempio che segue.

Esempio. Per ogni naturale n, dimostriamo che il numero delle parole di lunghezza n sull’alfabeto {0,1} che non contengono 2 cifre consecutive =1 è il numero di Fibonacci F

n+1

.

Per dimostrare tale affermazione basta usare la II

^a

forma del principio di induzione.

Per n=1 l’affermazione è banale: sono 2=F

2

le parole in questione (le parole 0 e 1).

Fissato k>1, supponiamo vera l’affermazione per i valori n=1,2,….,k-1 e dimostriamola vera per il valore n=k. Dunque la tesi è che il numero delle parole di lunghezza k sull’alfabeto {0,1} che non contengono 2 cifre consecutive =1 è il numero di Fibonacci F

k+1

.

Consideriamo una generica parola w di lunghezza k che non contiene 2 cifre consecutive =1.

Distinguiamo 2 casi:

1) se l’ultima cifra di w è 1, la parola w si ottiene da una parola s di lunghezza k-2 (che non contiene 2 cifre consecutive =1) aggiungendo come penultima cifra 0 e come ultima cifra 1. Poiché per l’ipotesi induttiva l’affermazione è vera per n=k-2, il numero delle parole s é F

k-1

, e quindi anche il numero di parole w è F

k-1

.

2) se l’ultima cifra di w è 0, la parola w si ottiene da una parola t di lunghezza k-1 (che non contiene 2 cifre consecutive =1) aggiungendo come ultima cifra 0. Poiché per l’ipotesi induttiva l’affermazione è vera per n=k-1, il numero delle parole t é F

k

, e quindi anche il numero di parole w è F

k

.

In totale il numero delle parole w di lunghezza k che non contengono 2 cifre consecutive =1 si ottiene sommando quelle dei casi 1) e 2), ottenendo alla fine F

k

+F

k-1

=F

k+1

(tesi).

Per esempio il numero delle parole di lunghezza 4 sull’alfabeto {0,1} che non contengono 2 cifre consecutive =1 è il numero di Fibonacci F

4+1

=F

5

=8 (in effetti tali 8 parole sono 0000, 0001, 0010, 0100, 1000, 1010, 0101, 1001).

Il numero d’oro.

Ricordiamo alcuni concetti geometrici: se AB è un segmento di estremi A,B è di lunghezza a (con a numero reale >0), si chiama parte aurea del segmento AB un segmento AC (dove C è un punto interno ad AB) tale che la lunghezza x di AC sia media proporzionale fra a e la lunghezza (a-x) del segmento CB. La lunghezza x della parte aurea AC di AB soddisfa dunque la proporzione:

a : x = x : (a-x)

da cui si ricava x

²

+ax-a

²

= 0, e risolvendo l’equazione di 2° grado:

x = a(-1 ⁵ )/2

Essendo x la lunghezza di un segmento, si ha x>0, e l’unico valore accettabile è x = a(-1+ 5 )/2 (perché a(-1- 5 )/2 è <0) , da cui:

a/x = 2/(-1+ 5 )

Moltiplicando numeratore e denominatore per 1+ 5 (per razionalizzare il denominatore) si ha:

a/x = ( ⁵ +1)/2  1,61 (è il cosiddetto rapporto aureo o numero d’oro).

Il concetto di parte aurea di un segmento ha molte applicazioni geometriche: per esempio il lato del decagono regolare ha la stessa lunghezza della parte aurea del raggio della circonferenza circonscritta.

Se  indica il numero d’oro, possiamo notare che , essendo x è soluzione di x

²

+ax-a

²

= 0, dividendo per x

²

si ottiene che  = a/x soddisfa l’identità:

1 +  - 

²

= 0 da cui:



²

= 1+ (*)

Numero d’oro e successione di Fibonacci.

Il numero d’oro ha una relazione con la successione dei numeri di Fibonacci F

n

.

Calcolando le potenze di base  ad esponente naturale e confrontandole con alcuni valori di F

n

, osserviamo che le potenze di base  sembrano alternarsi con i numeri di Fibonacci :

F

1

=1 < 

¹

 1,61 < F

2

=2 < 

²

 2,6 < F

3

=3 < 

³

 4,2 < F

4

=5 e si può congetturare che si abbia :

F

n

< 

ⁿ

< F

n +1

(**) per ogni numero naturale n.

Possiamo dimostrare che ciò è vero, ragionando per induzione (II

^a

forma). Per n=1 abbiamo già notato che (**) è vero:

F

1

=1 < 

¹

 1,61 < F

2

=2

Fissato k>1, supponiamo vera l’affermazione (**) per n=1,….,k-1, e dimostriamola vero per n=k:

dunque la tesi è che F

k

< 

^k

< F

k +1

.

Poiché (**) è per ipotesi vero in particolare per n=(k-1), n=(k-2), si ha:

F

k-1

< 

^k-1

< F

k

F

k-2

< 

^k-2

< F

k-1

da cui, sommando, si ha:

F

k

= F

k-1

+F

k-2

< 

^k–1

+ 

^k–2

< F

k

+F

k-1

= F

k+1

Ma dalla (*) segue che:



^k–1

+ 

^k–2

= 

^k–2

(1+) = 

^k–2



²

= 

^k

quindi la tesi. Abbiamo perciò dimostrato che la (**) é vera per ogni numero naturale n.

Siano a,b numeri naturali e supponiamo a>b. Se m è il numero di divisioni successive nell’algoritmo Euclideo, utilizzato per calcolare il mcd(a,b), tali m divisioni sono schematizzate come al solito nel modo seguente:

a=bq

1

+r

1

(q

1

0, 0<r

1

<b) b=r

1

q

2

+r

2

(q

2

0, 0<r

2

<r

1

) r

1

=r

2

q

3

+r

3

(q

3

0, 0<r

3

<r

2

) .

. .

r

m-3

=r

m-2

q

m-1

+r

m-1

(q

m-1

0, 0<r

m-1

<r

m-2

) r

m-2

=r

m-1

q

m

+r

m

(q

m

0, r

m

=0)

(ricordiamo che l’ultima successione ha resto nullo, e si ha r

m-1

=mcd(a,b), perché mcd(a,b) è il resto della penultima divisione, l’ultima fra quelle con resto non nullo).

Per costruzione si ha :

a > b > r

1

> r

2

> …….. > r

m-1

> 0=r

m

.

Da ciò deduciamo che in particolare i quozienti q

i

sono tutti non nulli (se fosse per assurdo q

1

=0, dalla prima divisione di avrebbe a=r

1

contraddizione; se fosse per assurdo q

2

=0, dalla seconda divisione di avrebbe b=r

2

contraddizione etc….). Dunque tutti i quozienti q

i

sono 1.

Poniamo per omogeneità r

0

=b (in modo che la prima divisione sia a=r

0

q

1

+r

1

) e dimostriamo che si ha:

r

m-n

 F

n

per ogni numero naturale n=1,2,…..,m .

Ragioniamo per induzione (II

^a

forma, nella versione limitata ai valori n=1,2,….,m di cui si è parlato sopra).

Per n=1 si ha (essendo r

m-1

>0) : r

m-1

 1; ma F

1

=1, dunque r

m-1

 F

1

, dunque l’affermazione è vera per n=1.

Fissato k>1, supponiamo che r

m-n

 F

n

sia vero per tutti gli n=1,2,…,k-1 e dimostriamolo vero per

n=k: la tesi è dunque che r

m-k

 F

k

.

Essendo per ipotesi vera l’affermazione in particolare per n=k-1, n=k-2, si ha:

r

m-k+1

 F

k-1

, r

m-k+2

 F

k-2

Ricavando il resto r

m-k

dalla divisione numero m-k+2 si ha (tenendo conto che, come osservato sopra, il quoziente é q

m-k+2

1):

r

m-k

= r

m-k+1

q

m-k+2

+r

m-k+2

 r

m-k+1

+r

m-k+2

 F

k-1

+ F

k-2

= F

k

e si ha la tesi. Dunque è vero che:

r

m-n

 F

n

per ogni numero naturale n=1,2,……,m .

In particolare, per n=m, si ha b = r

0

 F

m

, ma 

^m-1

< F

m

(per la proprietà già dimostrata che lega i numeri di Fibonacci alle potenze del numero d’oro ), dunque 

^m-1

< b, ossia (estraendo il logaritmo in base 10):

(m-1)log

10

 < log

10

b

Poiché log

10

  0,206>1/5 si ottiene (m-1)/5 < (log

10

b) da cui (m-1)< 5(log

10

b) ossia:

m < 5(log

10

b)+1

Se n è il numero di cifre nella rappresentazione dell’input b in base 10 sappiamo che : 10

^n-1

 b< 10

ⁿ

e dunque log

10

b < n, da cui m < 5n+1, ed essendo m,n numeri naturali:

m  5n.

In pratica quindi il numero m di divisioni nell’algoritmo Euclideo non è superiore al quintuplo del numero di cifre (in base 10) dell’input b (dove b è individuato come il più piccolo dei numeri a,b di cui si sta calcolando il massimo comune divisore).

Per esempio se il numero naturale a ha 1000 cifre in base 10, ed il numero naturale b ha 100 cifre in

base 10, per calcolare il mcd(a,b) l’algoritmo Euclideo esegue al più 500 divisioni.