Le procedure che abbiamo introdotto sino ad ora sono essenzialmente delle funzioni matematiche che specificano un valore che viene calcolato a partire da uno o più parametri. A differenze delle funzioni matematiche, le procedure definite al calcolatore devono essere anche efficienti, ovvero devono terminare la loro esecuzione in tempo breve. Vediamo ora un semplice esempio di cosa vuol dire avere una procedura efficiente.
Prendiamo per esempio la definizione matematica seguente:
$$\sqrt{x} = y \quad \mbox{ se e solo se }\quad y \geq 0 \mbox{ e } y^2 = x$$Queste definizione è corretta da un punto di vista matematico e potremmo usarla per controllare se un dato numero sia la radice quadrata di un altro. Tuttavia, questa definizione non descrive una procedura per calcolare la radice quadrata di un numero.
Per poter calcolare la radice quadrata di un numero abbiamo bisogno di un algoritmo che viene implementato con una o più procedure.
Se ci limitiamo a considerare i numeri interi, potremmo utilizzare la definizione precedente per trovare la radice quadrata di un numero intero positivo attraverso un'enumerazione esaustiva: per trovare la radice quadrata di $x$, possiamo provare tutti i numeri da $x$ a 1, e verificare ogni volta se il numero "tentativo" sia il quadrato dell'altro.
ESERCIZIO 2.1: Scrivere una procedura (funzione) che prende in input un numero intero maggiore o uguale a 1, e prova tutti i numeri da $x$ a 1. Se trova la radice quadrata esatta la restituisce, altrimenti restituisce $-1$.
In [1]:
def Enumerate(y, x):
# print(y)
if y == 0:
return -1
if x == y*y:
return y
return Enumerate(y-1, x)
In [2]:
print(Enumerate(16, 16))
In [3]:
print(Enumerate(15, 15))
DOMANDA: Come fare per trovare la radice quadrata di un numero reale positivo?
DOMANDA: Cosa vuol dire che due numeri reali sono uguali?
ESEMPIO: Come viene valutata l'espressione logica: $$\frac{1}{10}+\frac{1}{10}+\frac{1}{10} = \frac{3}{10}$$
In [4]:
1/10+1/10+1/10 == 3/10
Out[4]:
NOTA: Bisogna fare molta attenzione quando si usano i numeri reali al calcolatore!
Rivediamo quindi leggermente la definizione di radice quadrata, introducendo il concetto di tolleranza numerica. In pratica, cerchiamo un numero reale positivo tale che
$$\sqrt{x} = y \quad \mbox{ tale che } \quad |y^2 - x| < \epsilon, \quad y \geq 0 $$dove $\epsilon$ è una costante molto piccola, per esempio $10^{-7}$.
Potremmo cercare di migliorare la procedura di enumerazione esaustiva considerando che i numeri che stiamo controllando sono ordinati. Potremmo evitare di controllare tutti i numeri, uno alla volta, e potremmo cercare di fare dei "salti".
ESERCIZIO 2.2: Scrivere una procedura che, per trovare la radice quadrata di un numero, ogni volta divide l'intervallo di ricerca in due parti uguali, e continua ad esplorare solo la parte in cui effettivamente si può trovare la radice cercata.
In [5]:
def Abs(x):
if x < 0:
return -x
return x
def Istess(a,b):
return Abs(a-b) < 0.0001
def SqrtReals(x, a, b):
print(x, a, b)
y = (a+b)/2
if Istess(x, y*y):
return y
else:
if y*y > x:
return SqrtReals(x, a, y)
else:
return SqrtReals(x, y, b)
In [6]:
print(SqrtReals(36, 0, 36))
Il metodo più usato per calcolare la radice quadrata è il metodo di approssimazioni successive introdotto da Newton. Il metodo consiste nel trovare la soluzione attraverso aggiustamenti successivi di una soluzione tentativo: se abbiamo un valore $y$ che dovrebbe essere il valore tentativo della radice quadrata di un altro numero $x$ possiamo ottenere una approssimazione migliore facendo la media tra $y$ e $x/y$. Il metodo di Newtnon consiste quindi di partire da un $y_0$, e ad ogni iterazione di calcolare:
$$y_{i+1} = \frac{y_i + \frac{x}{y_i}}{2}$$ESEMPIO: Ricerca della radice quadrata di 2.
| Valore Tentativo $y$ | Quoziente $x/y$ | Media tra $y$ e $x/y$ |
|---|---|---|
| 1 | 2/1 | (1+2)/2=1.5 |
| 1.5 | 2/1.5=1.3333 | (1.3333+1.5)/2=1.4167 |
| 1.4167 | 2/1.4167=1.4118 | (1.4118 + 1.4167)/2=1.4142 |
| 1.4142 | ... | ... |
ESERCIZIO 2.3: Scrivere una o più procedure per trovare la radice quadrata di un numero, utilizzando il metodo di Newton scritto sopra.
In [7]:
def Newton(x, y):
# print(x, x/y, y)
if Istess(x, y*y):
return y
return Newton(x, (y+x/y)/2)
In [8]:
print(Newton(2, 1))
DOMANDA: è possibile trovare un criterio di arresto alternativo, che sia funzione dell'errore commesso nel calcolo della radice quadrata?
Studiamo ora come possiamo stimare l'errore del metodo di Newton, senza conoscere il valore esatto di $\sqrt{x}$. Chiamiamo $E_i$ l'errore di approssimazione che stiamo commettendo:
$$E_i = y_i - \sqrt{x}$$da cui
$$y_i = \sqrt{x} + E_i$$L'errore che commettiamo alla prossima iterazione, sarà pari a
$$E_{i+1} = y_{i+1} - \sqrt{x} = \frac{y_i + \frac{x}{y_i}}{2} - \sqrt{x}$$Facendo un po' di conti a partire dall'espressione precedente, si arriva a far vedere che
$$E_{i+1} = \frac{E_i^2}{2 y_i} > 0$$In pratica, dopo il primo tentativo $y_0$, tutti gli errori successivi saranno sempre positivi. Inoltre l'errore ad ogni iterazione diventa sempre più piccolo, in quanto
$$E_i = y_i - \sqrt{x} < y_i \quad \mbox{ e quindi } 0< \frac{E_i}{y_i} <1$$e inoltre
$$E_{i+1} = \frac{E_i^2}{2 y_i} = \frac{E_i}{y_i} \times \frac{E_i}{2} < \frac{E_i}{2}$$Riassumendo, abbiamo mostrato che l'errore diventa sempre più piccolo in quanto
$$0 < E_{i+1} < \frac{E_i}{2} < E_i.$$Vediamo ora come possiamo usare le espressioni precedenti per ottenere un criterio di arresto usando una stima sull'errore. Dalle relazioni precedenti abbiamo che
$$0 < y_{i+1} - \sqrt{x} < y_{i} - \sqrt{x}$$da cui
$$\sqrt{x} < y_{i+1} < y_{i}$$Se riprendiamo la definzione di errore ad una data iterazione, abbiamo che
$$E_i = y_i - \sqrt{x}= y_i - y_{i+1} + y_{i+1} -\sqrt{x} = (y_i - y_{i+1}) + E_{i+1} < (y_i - y_{i+1}) + \frac{E_{i}}{2}$$ovvero
$$E_{i+1} < \frac{E_i}{2} < y_i - y_{i+1}.$$In pratica, se si vuole calcolare la radice quadrata di un numero reale positivo con un margine di errore minore di $\epsilon < 0$, basterà verificare la condizione:
$$y_i - y_{i+1} < \epsilon.$$Possiamo provare a fare un piccolo confronto tra le tre funzioni trovate in termini di efficienza, andando a contare, per esempio, quante volte è stata chiamata la funzione ricorsiva. Per poterlo fare, basta aggiungere un parametro formale il quale viene incrementato di uno ogni volta che effettuiamo una chiamata ricorsiva. Tale valore puo' essere stampato a video prima di restituire il valore finale.
ESERCIZIO 2.4: Modificare le procedure precedenti per contare il numero di chiamate ricorsive con le tre procedure precedenti: (i) enumerazione esaustiva, (ii) metodo di bisezione, e (iii) metodo di Newton.
In [ ]:
# DA COMPLETARE