Home

Federica EU

1/15

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 d₀, …, d_t tali che n=d_tb^t+…+d₁b+d₀ con 0≤d_i≤(b-1) ∀ i=0,…t.
Dimostrazione

Segue dall’Algoritmo della Divisione Euclidea che esistono due numeri naturali q₁ e d₀ tali che n=q₁b+d₀ con 0≤d₀≤(b-1).
Si supponga di avere determinato per qualche j $\in$ ${\symb N}}$ dei numeri naturali
d₀,…, d_j-1,q_j tali che

n=q_jb^j+d_j-1b^j-1+…+d₁b+d₀ con 0≤d_i≤(b-1) ∀ i=0,…, j.

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

n=q_j+1b^j+1+d_jb^j+dj_-1b^j-1+…+d₁b+d₀.

Iterando questo ragionamento, si dimostra l’esistenza dei numeri naturali d₀, …, d_t 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 d₀, …, d_k-1 tali che

n=d_k-1b^k-1+…+d₁b+d₀ con 0≤d_i≤(b-1) ∀ i=0,…, k-1 e d_k-1≠0.

Dimostrazione

Per il Lemma 1.2 esistono un numero naturale positivo k e dei numeri naturali d₀, …, d_k-1 tali che n=d_k-1b^k-1+…+d₁b+d₀ con 0≤d_i≤(b-1) ∀ i=0,…, k-1 e d_k-1≠0.
Ne segue che b^k-1≤n<b^k ⇒ (k – 1) ≤ log_bn < k ⇒ k = [log_bn] + 1.

Si dimostrerà ora che i numeri k, d₀, …, d_k-1 sono univocamente determinati.

Cambiamenti di base

Si supponga ora che esistano un numero naturale positivo h e dei numeri naturali c₀, …, c_h-1 tali che
n=c_h-1b^h-1+…+c₁b+c₀ con 0≤c_i≤(b-1) ∀ i=0,…, h-1 e c_h-1≠0.
Da quanto osservato prima segue che h=[log_bn]+1=k.
Dunque, si ha d_k-1b^k-1+…+d₁b+d₀=c_k-1b^k-1+…+c₁b+c₀
Si proverà per induzione su k che d_i=c_i ∀ i=0,…, k-1.
Se k=1, d₀=c₀.
Sia k>1 e si supponga l’asserto vero per k-1.
(d_k-1b^k-2+…+d₁) b+d₀=n=(c_k-1b^k-2+…+c₁) b+c₀ ⇒ d₀ec₀coincidono con il resto della divisione euclidea di n per b, mentre d_k-1b^k-2+…+d₁e c_k-1b^k-2+…+c₁ coincidono con il quoziente della divisione euclidea di n per b ⇒ d₀=c₀, mentre l’ipotesi induttiva garantisce allora che d_i=c_i ∀ 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=d_k-1b^k-1+…+d₁b+d₀ con 0≤d_i≤(b-1) ∀ i=0,…, k-1 e d_k-1≠0, si scrive anche

n=(d_k-1…,d₁d₀)_boppure n=(d_k-1,…,d₁,d₀)_b

e tale espressione viene chiamata espansione di n in base b; si dice che i numeri d_k-1,…,d₁,d₀ 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 b^k-1≤n<b^k; 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 è [log_bn]+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,…, b^k-1} definita ponendo f((a_k-1,…,a₀))=a_k-1b^k-1+…+ a₀

è biettiva.
Dimostrazione
Si proverà ora che f è suriettiva.
Sia n $\in$ { 0,…, b^k-1} ⇒ n ha al più k cifre in base b ⇒ dall’espansione (d_h-1…,d₁d₀)_b di n in base b, si ottiene la k-pla (0,…,0,d_h-1,…,d₀) $\in$ { 0,…, b-1}^k .
Dunque si ha f( (0,…,0,d_h-1,…,d₀))=0·b^k-1+…+0·b^h+d_h-1b^h-1+…+d₁b+d₀=d_h-1b^h-1+…+d₁b+d₀=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
∀ (n₁,…,n_r) $\in$ X tale che n₁,…,n_r≥B, si ha f((n₁,…,n_r))≤C·g((n₁,…,n_r)).
Se f è limitata da g si scrive f((n₁,…,n_r))=O(g((n₁,…,n_r)))

Esempi di cambiamenti di base

531=75·7 +6 = (10·7 +5)·7+6=10·7²+5·7+6=(1·7+3)·7²+5·7+6=7³+3·7²+5·7 +6 e quindi 531=(1356)₇

121=60·2 +1=(30·2)·2 +1=30·2²+1=(15·2)·2² +1=15·2³+1=(7·2 +1)·2³+1=7·2⁴+2³+1 =
=(3·2 +1)· 2⁴+2³+1=3·2⁵+2⁴+2³+1 =(1·2+1)·2⁵+2⁴+2³+1=2⁶+2⁵+2⁴+2³+1 e quindi 121=(1111001)₂

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)₂+(1)₂=(10)₂, 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(k²);
eseguire n-m ha complessità O(k);
eseguire la divisione euclidea di n per m ha complessità O(k·l) e quindi O(k²)

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)²);
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)²).

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)³).
Dimostrazione
Sia k il numero di cifre binarie di n ⇒ 2^k-1≤n<2^k. 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]$ =(1c_l-2…c₀)₂; si determineranno ora, una alla volta, le cifre c_l-2,…, c₀

Complessità delle principali operazioni

Sia x₁ il numero l-bit (10…0)₂ e sia y₁ il numero l-bit (110…0)=x₁+2^l-2; si calcoli y₁².
Se y₁²>n, allora c_l-2=0, mentre se y₁²≤n, allora c_l-2=1.
Si supponga di aver determinato le cifre c_l-2,…,c_l-i; si determinerà ora la cifra c_l-i-1.
Sia x_i il numero l-bit (1…c_l-i 0…0) e sia y_i il numero l-bit (1…c_l-i 1…0)=x_i+2^l-i-1; si calcoli y_i².
Se y_i²> n, allora c_l-i-1=0, mentre se y_i²≤ n allora c_l-i-1=1″

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

Esempi di estrazione di radice in base 2

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

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

$[\sqrt{(11001)_2}]$ ha 3 cifre binarie;
quindi $[\sqrt{(11001)_2}]$ =(11c₀)₂.
(110)² =(100100)₂ > (11001)₂ ⇒ c₁=0
(101)² =(11001)₂ ⇒ c₀=1
$\sqrt{(11001)_2}$ =(101)₂

Esempi di estrazione di radice in base 2

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

Poiché n=(10011)₂ ha 5 cifre binarie,
$[\sqrt{(10011)_2}]$ ha 3 cifre binarie;
quindi $[\sqrt{(10011)_2}]$ =(1c₁c₀)₂
(110)² =(100100)2 > (10011)₂ ⇒ c₁ =0
(101)² =(11001)2 > (10011)₂ ⇒ c₀ =0
$\sqrt{(11001)_2}]$ =(100)₂