Un algoritmo realizza una relazione funzionale tra i valori di input e quelli di output
F = { (s, s’) }
per ogni s esiste una e una sola coppia (s, s’).
Esempio: un algoritmo che calcola il quadrato di un numero naturale è descritto dal seguente insieme di coppie:
{ (0, 0), (1, 1), (2, 4), (3, 9), (4, 16) . . . } .
Specifica di un algoritmo: espressione non ambigua dei requisiti funzionali che l’algoritmo deve soddisfare.
insieme di coppie infinito
predicati della logica per caratterizzare le coppie di input/output
{ (x, z) / x ∈ N & z = x . x }
Specifica di A è una coppia di predicati:
< p-in(x), p-out(x, z)>, dove:
• p-in(x): predicato di input di A, specifica i
vincoli cui devono soddisfare i valori forniti per le variabili di input (il dominio delle variabili);
• p-out(x, z): predicato di output di A, specifica la relazione di input / output.
Algoritmo A
variabili di input: x1, x2, . . . , xn ( x )
variabili di output: z1, z2, . . .,zk ( z )
quadrato di un numero naturale p-in(x) ≡ x ≥ 0
p-out(x, z) ≡ z = x
.x
quoziente e il resto della divisione di x1 per x2 p-in(x1, x2) ≡ x1 ≥ 0 & x2 > 0
p-out(x1, x2, z1, z2) ≡ x1 = z1
.x2 + z2 & 0 ≤ z2 < x2 moltiplicazione di x1 per x2
p-in(x1, x2) ≡ x1 ≥ 0 & x2 ≥ 0
p-out(x1, x2, z) ≡ z = x1
.x2
Correttezza parziale
Dato un algoritmo A e una specifica
< p-in(x), p-out(x, z)>
A si dice parzialmente corretto rispetto alla specifica se
“per ogni valore a delle variabili di input x, che soddisfa il predicato di input, se l’algoritmo termina, termina con valore b per le variabili di output z, che soddisfa il
predicato p-out(a, b)”.
Terminazione
Dato un algoritmo A e un predicato di input p-in(x), si dice che A termina su p-in(x) se per ogni valore a
delle variabili di input x, che soddisfa il predicato di
input, l’algoritmo termina.
Correttezza totale
Dato un algoritmo A e una specifica
< p-in(x), p-out(x, z)>
A si dice totalmente corretto rispetto alla specifica se
è parzialmente corretto rispetto alla specifica e termina
sul predicato di input.
La correttezza parziale di un algoritmo A rispetto alla specifica <p-in(x), p-out(x, z)> è espressa dalla
Formula di correttezza di Hoare :
p-in(x) p-out(x, z) { } A { } { p-in(x) }
A
{ p-out (x, z) }
Verifica della correttezza parziale
{ p-in(x1, x2) ≡ x1 ≥ 0 & x2 ≥ 0 }
{ p-out(x1, x2, z) ≡ z = x1
.x2 }
Prodotto
{ p-in(x) ≡≡ x ≥≥ 0 }
{ p-out(x, z) ≡≡ z > 0 } 1 z ← x
2 z ← z + 1
3 return z
Incremento (x)
“per ogni valore ≥ 0 assunto da x alla chiamata del metodo, al rientro il valore di z sarà > 0”
{ p-in(x) ≡≡ x ≥≥ 0 }
{ p-out(x, z) ≡≡ z > 0 } 1 z ← x
2 z ← z + 1 3 return z Incremento (x)
{ x ≥≥ 0 }
{ z > 0 } z > 0
z +1 > 0
x +1 > 0
x ≥ 0
{ }
{ p-out(x, z) ≡≡ z = x } 1 if x ≥ 0
then
2 z ← x
else
3 z ← - x
4 return z modulo (x)
{ z ≥≥ 0 & (z = x ∨∨ z = - x) }
{ x ≥≥ 0 & z ≥≥ 0 & z = x}
{ x < 0 & z > 0 & z = - x}
p-in(x) ≡ true
{ x ≥≥ 0 }
{ x < 0 }
z = x ≡≡ z ≥≥ 0 & (z = x ∨∨ z = - x)
{ x ≥≥ 0 & z ≥≥ 0 & z = x}
then
z ← x
else
z ← - x
{ z ≥≥ 0 & (z = x ∨∨ z = - x) } { x < 0 & z > 0 & z = - x}
{ x ≥≥ 0 }
{ x < 0 } x < 0 & -x > 0 & -x = - x
x ≥ 0 & x ≥ 0 & x = x
{x1 ≥≥ 0 & x2 ≥≥ 0 }
{z = x1
.x2 }
moltiplicazione (x1, x2) y ← x1
z ← 0
while y > 0 do
z ← z + x2
y ← y - 1
return z
{x1 ≥ 0 & x2 ≥ 0 }
moltiplicazione (x1, x2)
y ← x1 z ← 0
{z = x1
.x2 }
while y > 0 do z ← z + x2 y ← y - 1 return z
{x1
.x2 = y
.x2 + z & y ≥ 0}
x1 . x2 = x1 . x2 + 0 & x1 ≥ 0
{x1 ≥ 0 & x2 ≥ 0}
{x1 ≥ 0 & x2 ≥ 0 }
moltiplicazione (x1, x2) y ← x1
z ← 0
{z = x1
.x2}
while y > 0 do z ← z + x2 y ← y - 1 return z
{x1 . x2 = y . x2 + z & y ≥ 0}
{x1 . x2 = y . x2 + z & y > 0}
{x1
.x2 = y . x2 + z & y ≥ 0}
z ← z + x2 y ← y - 1
{x1 . x2 = y . x2 + z & y > 0}
x1 . x2 = (y-1) . x2 + x2 + z & y-1 ≥ 0
{x1
.x2 = y . x2 + z & y ≥ 0}
{x1 ≥ 0 & x2 ≥ 0}
moltiplicazione (x1, x2) y ← x1
z ← 0
{z = x1.x2}
while y > 0 do z ← z + x2 y ← y - 1
return z
{ x1.x2 = y.x2 + z & y ≥ 0 }
{ x1.x2 = y.x2 + z & y > 0}
E dopo l’esecuzione del while, se termina:
{ x1.x2 = y.x2 + z & y ≥ 0 } { x1.x2 = y.x2 + z & y = 0 }
Difficoltà: esprimere il predicato che si mantiene vero durante l’esecuzione del ciclo:
Invariante di ciclo
45 19 44 19 43 19
1 19
855 . . . . . . 3 19 2 19
y: valori della prima colonna z : somma parziale
y
z
x1 x x2 y x x2 z
Ad esempio:
855 = 3 x 19 + 798
Moltiplicazione alla russa
z: somma parziale
y1: valori della prima colonna y2: valori della seconda colonna
x1 x x2 y1 x y2 z
19 76 --- 152 --- 608 855
45 19
22 38
11 76
5 152
2 304
1 608
y1 y2
y1
y2
z
Ad esempio:
855 = 5 x 152 + 95
while y1 > 0 do
if y1 is odd then z ← z + y2 y1 ← y1 div 2
y2 ← y2 + y2
return z
molt-russa (x1, x2) y1 ← x1
y2 ← x2 z ← 0
{ x1 ≥ 0 & x2 ≥ 0 }
{ x1.x2 = y1.y2 + z & y1 ≥ 0 }
{ x1.x2 = y1.y2 + z & y1 > 0 }
{ z = x1.x2 }
{ x1.x2 = y1.y2 + z & y1 = 0 }
{ x1.x2 = y1.y2 + z & y1 ≥ 0 }
y1 ← x1 y2 ← x2 z ← 0
{ x1.x2 = y1.y2 + z & y1 ≥ 0 } { x1 ≥ 0 & x2 ≥ 0 }
x1 . x2 = x1.x2 + 0 & x1 ≥ 0
if y1 is odd then
z ← z + y2 y1 ← y1 div 2
y2 ← y2 + y2
{ x1.x2 = y1.y2 + z & y1 > 0 }
{ x1.x2 = y1.y2 + z & y1 > 0 & y1 dispari}
{ x1.x2 = y1. y2 + z & y1 ≥ 0 }
(y1 div 2) . (y2 + y2) + z se y1 pari (y1 div 2) . (y2 + y2) + (z + y2) se y1 dispari x1.x2 =
& y1 div 2 ≥ 0
2n x m = n x 2m
(2n + 1) x m = 2n x m + m = n x 2m + m
x1.x2 = y1.y2 + z & y1 > 0
(y1 div 2) . (y2 + y2) + z se y1 pari (y1 div 2) . (y2 + y2) + (z + y2) se y1 dispari x1.x2 =
y1.y2 = (y1 div 2) . (y2 + y2) se y1 pari y1.y2 = (y1 div 2) . (y2 + y2) + y2 se y1 dispari
while y1 > 0 do
if y1 is odd then z ← z + y2 y1 ← y1 div 2
y2 ← y2 + y2 return z
molt-russa (x1, x2) y1 ← x1
y2 ← x2 z ← 0
{ x1 ≥ 0 & x2 ≥ 0 }
{ z = x1.x2 }
{ x1.x2 = y1. y2 + z & y1 ≥ 0 }
{ x1 ≥ 0 & x2 > 0 }
{ x1 = q . x2 + r & 0 ≤ r < x2 } q ← 0
r ← x1
while r ≥ x2 do q ← q + 1
r ← r - x2
return (q, r) divisione (x1, x2)
{ x1 = q . x2 + r & 0 ≤ r & x2 > 0 }
{ x1 = q . x2 + r & 0 ≤ r & x2 > 0 & r ≥ x2 }
{ x1 = q . x2 + r & 0 ≤ r & x2 > 0 } { x1 = q . x2 + r & 0 ≤ r & r < x2 }
x1 ≥ 0 & x2 > 0
x1 = 0 . x2 + x1 & 0 ≤ x1 & x2 > 0 q ← 0
r ← x1
q ← q + 1 r ← r - x2
x1 = q . x2 + r & 0 ≤ r & x2 > 0 & r ≥ x2
x1 = (q + 1) . x2 + (r - x2) & 0 ≤ (r - x2) & x2 > 0 }
supponiamo che: - gli estremi a e b siano numeri naturali - a ≤ b
- “passo” uno.
il costrutto for e` equivalente a:
i ← a
while i ≤ b do S
i ← i + 1
Il costrutto for: for i ← a to b do S
Massimo (A, n)
current-max ← A[0]
for i ← 1 to n-1 do
if current-max < A[i]
then current-max ← A[i]
return current-max { n ≥ 1 }
{ current-max è il massimo tra gli elementi di A } { current-max ≥ A[j], per ogni j, 0 ≤ j < n }
{ current-max ≥ A[j], per ogni j, 0 ≤ j < i } i ← 1
while i < n do
i ← i + 1
n = length[A]
Poly-eval (A, x, n) y ← 1
result ← A[0] i ← 1 for i ← 1 to n do
y ← y • x
result ← result +A[i] • y i ← i +1 return result
P(x) = a0 + a1x+ … + anxn
{ result = A[0] + A[1] • x + ... + A[i-1] • xi-1 & y = xi-1
}
{ result = A[0] + A[1] • x + ... + A[n] • xn
}
{ n ≥ 1}
n = grado del polinomio
Horner (A, x, n)
result ← A[n] i ← n - 1 for i ← n - 1 downto 0 do
result ← result • x + A[i] i ← i - 1 return result
P(x) = a0 + x (a1+ … + x (an-1+ x an))…)
{result = A[i+1] + A[i+2] x + ... + A[n] xn-(i+1) } { n ≥ 1}
{result = A[0] + A[1] • x + ... + A[n] • xn
}
{result = A[i+1] + A[i+2] x + ... + A[n] xn-(i+1) }
Metodi ricorsivi
Massimo-ricorsivo (A, n) if n = 1
then current-max ← A[0]
return current-max y ← Massimo-ricorsivo (A, n-1) current-max ← max (y, A[n-1]) return current-max
T(n) = h se n = 1
T(n-1) + k altrimenti { n ≥ 1}
{ current-max è il massimo tra gli elementi di A}
n = length[A]
{ n = 1}
current-max ← A[0]
return current-max
{current-max è il massimo tra gli elementi di A}
n = 1
A[0] è il massimo tra gli elementi di A
{ current-max è il massimo tra gli elementi di A}
y ← Massimo-ricorsivo (A, n-1) current-max ← max (y, A[n-1]) return current-max
{ n > 1}
La correttezza viene verificata supponendo che la chiamata interna “funzioni bene” e dimostrando che le modifiche subite dalle variabili rendono vero il predicato.
y ← Massimo-ricorsivo (A, n-1) current-max ← max (y, A[n-1]) return current-max
{ n > 1}
{ current-max è il massimo tra gli elementi di A}
Supponiamo che Massimo-ricorsivo su un numero di elementi < n lavori correttamente:
{ n > 1}
y ← Massimo-ricorsivo (A, n-1)
{ current-max è il massimo tra gli elementi di A[0..n-2]}
return current-max { n > 1}
{ current-max è il massimo tra gli elementi di A}
y ← Massimo-ricorsivo (A, n-1)
current-max ← max (y, A[n-1])
{ current-max è il massimo tra gli elementi di A[0..n-2] }
{ current-max è il massimo tra gli elementi di A[0..n-1] }
La dimostrazione di correttezza per i metodi ricorsivi viene fatta per induzione sul numero di chiamate.
DI-Massimo-ricorsivo (A, p, r)
if p = r then current-max ← A[p]
return current-max
if p = r-1 then
if A[p] < A[r] then current-max ← A[r]
return current-max
else current-max ← A[p]
return current-max q ← (p + r)/2
current-max-1 ← DI-Massimo-ricorsivo (A, p, q) current-max-2 ← DI-Massimo-ricorsivo (A, q +1, r) current-max ← max(current-max1, current-max2) return current-max
{ current-max è il massimo tra gli elementi di A}
{ p ≥ 0 & r ≥ 0 & p ≤ r}
La correttezza e` facile da verificare.
Piu` difficile valutarne la complessita`
Anche per l’algoritmo ricorsivo la complessita` e` Θ(n), come per l’algoritmo iterativo visto in precedenza.
esprimiamo la complessita` come relazione di ricorrenza:
