Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Maria De Falco » 1.Espansione di un numero naturale in base b e complessità computazionale delle operazioni elementari


Introduzione e notazioni

Nei corsi di Algebra del primo anno viene, di solito, costruito l’insieme {\symb Z}} dei numeri interi relativi. In tale insieme vengono inoltre introdotte la relazione d’ordine usuale e le consuete operazioni di somma + e di prodotto ·. Viene inoltre dimostrato il seguente risultato, noto come Algoritmo della divisione euclidea.

Siano n e m numeri interi tali che m sia diverso da 0. Allora esistono e sono univocamente determinati due numeri interi q ed r tali che n=mq+r e 0≤r<|m| .
I numeri q ed r si chiamano rispettivamente quoziente e resto della divisione euclidea di n per m.

Nel seguito, con i simboli {\symb N}}_0  e {\symb N} si indicheranno rispettivamente l’insieme dei numeri naturali e l’insieme dei numeri naturali positivi.

Osservazione 1.1

Se n \in {\symb N}}_0 e m \in {\symb N}}, allora, detto q il quoziente della divisione euclidea di n per m, si ha q≥0.
Dimostrazione
Se n<m, allora q=0;
Sia n≥m ⇒ detto r il resto della divisione euclidea di n per m, si ha r < n ⇒  mq = n – r >0 ⇒ q≥0.

Cambiamenti di base

E’ noto a tutti che nel nostro sistema numerico si utilizza come base il numero 10; i processori dei computer, invece, usano usano numeri scritti in base 2. Lo scopo della prima parte della lezione è arrivare ad introdurre il concetto di cambiamento di base.

Lemma 1.2

Siano b,n \in {\symb N}}. Allora esistono dei numeri naturali d0, …, dt tali che n=dtbt+…+d1b+d0 con 0≤di≤(b-1) ∀ i=0,…t.
Dimostrazione

Segue dall’Algoritmo della Divisione Euclidea che esistono due numeri naturali q1 e d0 tali che n=q1b+d0 con 0≤d0≤(b-1).
Si supponga di avere determinato per qualche j \in {\symb N}} dei numeri naturali
d0,…, dj-1,qj tali che

n=qjbj+dj-1bj-1+…+d1b+d0 con 0≤di≤(b-1)  ∀ i=0,…, j.

Se qj≤(b-1), basta porre t=j e dj=qj.
Se qj≥b, esistono due numeri naturali qj+1 e dj tali che qj=qj+1b+dj con 0≤dj≤(b-1). Allora

n=qj+1bj+1+djbj+dj-1bj-1+…+d1b+d0.

Iterando questo ragionamento, si dimostra l’esistenza dei numeri naturali d0, …, dt richiesti nell’enunciato.

Cambiamenti di base

Teorema 1.3

Sia b un numero naturale tale che b≥2.
Allora ∀ n \in {\symb N}} esistono e sono univocamente determinati un numero naturale positivo k e dei numeri naturali d0, …, dk-1 tali che

n=dk-1bk-1+…+d1b+d0 con 0≤di≤(b-1)  ∀ i=0,…, k-1 e dk-1≠0.

Dimostrazione

Per il Lemma 1.2 esistono un numero naturale positivo k e dei numeri naturali d0, …, dk-1 tali che n=dk-1bk-1+…+d1b+d0 con 0≤di≤(b-1)  ∀ i=0,…, k-1 e dk-1≠0.
Ne segue che bk-1≤n<bk ⇒ (k – 1) ≤ logbn < k ⇒ k = [logbn] + 1.

Si dimostrerà ora che i numeri k, d0, …, dk-1 sono univocamente determinati.

Cambiamenti di base

Si supponga ora che esistano un numero naturale positivo h e dei numeri naturali c0, …, ch-1 tali che
n=ch-1bh-1+…+c1b+c0 con 0≤ci≤(b-1)  ∀ i=0,…, h-1 e ch-1≠0.
Da quanto osservato prima segue che h=[logbn]+1=k.
Dunque, si ha dk-1bk-1+…+d1b+d0=ck-1bk-1+…+c1b+c0
Si proverà per induzione su k che di=ci  ∀ i=0,…, k-1.
Se k=1, d0=c0.
Sia k>1 e si supponga l’asserto vero per k-1.
(dk-1bk-2+…+d1) b+d0=n=(ck-1bk-2+…+c1) b+c0 ⇒ d0 e  c0 coincidono con il resto della divisione euclidea di n per b, mentre dk-1bk-2+…+d1 e  ck-1bk-2+…+c1 coincidono con il quoziente della divisione euclidea di n per b ⇒  d0=c0 , mentre l’ipotesi induttiva garantisce allora che di=ci  ∀ i=1,…, k-1.

Cambiamenti di base

Definizione 1.4
Sia b un numero naturale tale che b≥ 2.
(1) Sia n un numero naturale positivo.
Se n=dk-1bk-1+…+d1b+d0 con 0≤di≤(b-1)  ∀ i=0,…, k-1 e dk-1≠0, si scrive anche

n=(dk-1 …,d1 d0)b oppure n=(dk-1 ,…,d1 ,d0)b

e tale espressione viene chiamata espansione di n in base b; si dice che i numeri dk-1 ,…,d1 ,d0 sono le cifre di n in base b e che n è un numero di k cifre in base b.
(2) Si pone anche 0=(0)b e tale espressione viene chiamata espansione di 0 in base b; 0 ha un’unica cifra in base b, che è uguale a 0.
Osservazione 1.5
Segue da quanto visto finora che se b è un numero naturale tale che b ≥ 2 e k \in {\symb N}, allora:

  • se k>1, i numeri di k cifre in base b sono tutti e soli i numeri n tali che bk-1≤n<bk; invece i numeri di una cifra in base b sono tutti e soli i numeri n tali che 0≤n<b
  • se n è un numero naturale positivo, il numero di cifre di n in base b è [logbn]+1

Cambiamenti di base

La prossima proposizione, immediata conseguenza del Teorema 1.3, verrà frequentemente applicata nel seguito.
Proposizione 1.6
Siano b e k numeri naturali positivi con b ≥ 2.
Allora la funzione

f:{ 0,…, b-1}k → { 0,…, bk-1} definita ponendo f((ak-1,…,a0))=ak-1bk-1+…+ a0

è biettiva.
Dimostrazione
Si proverà ora che f è suriettiva.
Sia n \in { 0,…, bk-1} ⇒ n ha al più k cifre in base b ⇒ dall’espansione (dh-1…,d1d0)b di n in base b, si ottiene la k-pla  (0,…,0,dh-1,…,d0) \in { 0,…, b-1}k .
Dunque si ha f( (0,…,0,dh-1,…,d0))=0·bk-1+…+0·bh+dh-1bh-1+…+d1b+d0=dh-1bh-1+…+d1b+d0=n.
Ne segue che f è suriettiva, e quindi anche biettiva perché dominio e codominio sono equipotenti.

Complessità computazionale e notazione O grande

Definizione 1.7
Sia un numero naturale positivo; ogni cifra di n in base 2 è detta cifra binaria oppure bit (abbreviazione di “binary digit”) di n. Se n ha k cifre binarie, si dice anche che n è un k-bit.
Definizione 1.8
Si chiama operazione elementare oppure operazione bit ogni singola operazione svolta su una cifra binaria nello svolgimento di un algoritmo che opera su uno o più numeri in base 2.
Definizione 1.9
Si chiama complessità computazionale di un algoritmo il numero di operazioni elementari eseguite dall’algoritmo stesso una volta scritti in base 2 i numeri su cui l’algoritmo opera.
Definizione 1.10
Sia r>0 e siano f e g due funzioni aventi come dominio uno stesso sottoinsieme X di {\hbox {\symb N}} _0 \; ^r e il cui codominio è un sottoinsieme dell’insieme dei numeri reali.
Si dice che f è limitata da g se esistono due numeri positivi B e C tali che
∀ (n1,…,nr) \in X tale che  n1,…,nr≥B, si ha f((n1,…,nr))≤C·g((n1,…,nr)).
Se f è limitata da g si scrive  f((n1,…,nr))=O(g((n1,…,nr)))

Esempi di cambiamenti di base

531=75·7 +6 = (10·7 +5)·7+6=10·72+5·7+6=(1·7+3)·72+5·7+6=73+3·72+5·7 +6 e quindi 531=(1356)7

 

121=60·2 +1=(30·2)·2 +1=30·22+1=(15·2)·22 +1=15·23+1=(7·2 +1)·23+1=7·24+23+1 =
=(3·2 +1)· 24+23+1=3·25+24+23+1 =(1·2+1)·25+24+23+1=26+25+24+23+1 e quindi 121=(1111001)2

Operazioni in base 2

Siano n, m numeri naturali; sia b un numero naturale tale che b ≥ 2 , si considerino le espansioni di n e di m in base b. Se b=10, gli algoritmi attraverso i quali si eseguono m+n, n-m (se n≥m),  n·m,  la divisione euclidea di n per m (se n≥m) sono noti dalla scuola primaria; qualunque sia il valore di b, gli algoritmi per eseguire le suddette operazioni sono analoghi a quelli relativi al caso che sia b=10.
In particolare, nel caso che sia b=2, si tenga presente che (1)2+(1)2=(10)2 , sicché se in una somma ci sono in colonna due cifre uguali ad 1, la cifra risultante dalla somma è 0, con il riporto di 1.
In figura vengono riportati alcuni esempi di operazioni in base 2.


Operazioni in base 2

Sulle osservazioni precedenti si basa la seguente proposizione, della quale non viene riportata una dimostrazione formale. 
Proposizione 1.11 (senza dimostrazione)
Siano n, m numeri naturali positivi tali che n≥m.
Se n è un k-bit e m è un l-bit, allora

  • eseguire n+m ha complessità O(k);
  • eseguire n·m ha complessità O(k·l) e quindi O(k2);
  • eseguire n-m ha complessità O(k);
  • eseguire la divisione euclidea di n per m ha complessità O(k·l) e quindi O(k2)

Complessità delle principali operazioni

Proposizione 1.12  Siano n,m \in {\symb N}. Allora

  • eseguire n+m ha complessità O(logn + log m);
  • eseguire n·m ha complessità O(logn · logm);
  • se n≥m, eseguire n·m ha complessità O((logn)2);
  • se n≥m, eseguire n-m ha complessità O(logn);
  • se n≥m, eseguire la divisione euclidea di n per m ha complessità O(logn · logm) e quindi O((logn)2).

Dimostrazione
L’asserto segue in modo immediato dalla Proposizione 1.11, tenendo conto di quanto affermato nella Definizione 1.5 sul numero di cifre di un numero espanso in una base b.

Complessità delle principali operazioni

Proposizione 1.12
Sia n \in {\symb N}. Il calcolo di [\sqrt n] ha complessità O((logn)3).
Dimostrazione
Sia k il numero di cifre binarie di n ⇒ 2k-1 ≤n<2k. Ne segue che
2^{\frac{k-1}{2}}\leq \sqrt n < 2^{\frac{k}{2}}.

Sia l il numero di cifre binarie di [\sqrt n].
Se k è pari, si ha
2^{\frac{k}{2}-1}< \sqrt n < 2^{\frac{k}{2}} ⇒ 2^{\frac{k}{2}-1}\leq [\sqrt n] < 2^{\frac{k}{2}} ⇒ l=\frac{k}{2}.
Se k è dispari, si ha
2^{\frac{k+1}{2}-1} \leq \sqrt n < 2^{\frac{k+1}{2}} ⇒ 2^{\frac{k+1}{2}-1}\leq [\sqrt n] < 2^{\frac{k+1}{2}} ⇒ l=\frac{k+1}{2}.
Sia [\sqrt n]=(1cl-2…c0)2; si determineranno ora, una alla volta, le cifre cl-2 ,…, c0

Complessità delle principali operazioni

Sia x1 il numero l-bit (10…0)2 e sia y1 il numero l-bit (110…0)=x1+2l-2  ; si calcoli y12.
Se y12 > n, allora cl-2=0, mentre se y12≤n, allora cl-2=1.
Si supponga di aver determinato le cifre cl-2,…,cl-i; si determinerà ora la cifra cl-i-1.
Sia xi il numero l-bit (1…cl-i 0…0) e sia yi il numero l-bit (1…cl-i 1…0)=xi+2l-i-1  ; si calcoli yi2.
Se yi> n, allora cl-i-1=0, mentre se yi2 ≤ n allora cl-i-1=1″

Per determinare ogni cifra sono stati eseguiti una somma che ha complessità O(l) e un prodotto che ha complessità O(l2),  per una complessità totale di O(l)+O(l2)=O(l2).
Quindi l’algoritmo ha complessità O(l)·O(l2)=O(l3) e quindi O((logn)3), perché l=O(k) e k=O(logn)

Esempi di estrazione di radice in base 2

Si calcoli [\sqrt{(11001)_2}].

Poiché n=(11001)2 ha 5 cifre binarie,

[\sqrt{(11001)_2}] ha 3 cifre binarie;
quindi [\sqrt{(11001)_2}]=(11c0)2.
(110)2 =(100100)2 > (11001)2 ⇒ c1=0
(101)2 =(11001)2 ⇒ c0=1
\sqrt{(11001)_2}=(101)2

Esempi di estrazione di radice in base 2

Si calcoli [\sqrt{(10011)_2}].

Poiché n=(10011)2 ha 5 cifre binarie,
[\sqrt{(10011)_2}] ha 3 cifre binarie;
quindi [\sqrt{(10011)_2}]=(1c1c0)2
(110)2 =(100100)2 > (10011)2 ⇒ c1 =0
(101)2 =(11001)2 > (10011)2 ⇒ c0 =0
\sqrt{(11001)_2}]=(100)2

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion