Specifica, progetto e verifica della correttezza di algoritmi
iterativi
Il metodo delle asserzioni
Ragionamenti su di un algoritmo
Ragionare sulla specifica di un algoritmo data con pre e post-condizioni serve a:
• (a posteriori) verificare la correttezza dell’algoritmo
• (a priori) costruire un algoritmo, a partire
da un’idea circa la soluzione, in modo che
sia corretto
Il metodo delle asserzioni (Floyd)
Divisione (n, m) Pre. n ≥ 0, m > 0
Post. ritorna q, r t.c. n = m q + r, 0 ≤ r < m r ← n
q ← 0
while r ≥ m do
r ← r − m q ← q + 1 { n = m q + r, 0 ≤ r }
{ n = m (q+1) + r − m, 0 ≤ r − m}
Asserzioni:
descrivono relazioni tra i valori delle
variabili, che devono valere
quando il controllo
raggiunge un certo
Le triple di Hoare
• Un comando ha la forma
C ::= x ← E | C ; C | if B then C |
if B then C else C | while B do C |
• Se ϕ e ψ sono asserzioni allora
ϕ C ψ ⇔ se i valori delle variabili soddisfano
ϕ prima di C e C termina, allora soddisfano ψ dopo C
tripla
Le triple di Hoare
Le triple di Hoare sono espressioni della logica formale, ma voi potete usare
asserzioni informali, purché
non ambigue!!!
Asserzioni per gli assegnamenti
{ x + ∆ > 0 } x ← x + ∆ { x > 0 }
{ ϕ (E)} (E può contenere x) x ← E
{ ϕ (x)}
{ ϕ ( E ) } x ← E { ϕ ( x ) } Assioma
Asserzioni per le sequenze
{y ≥ z}
y ← y – z {y ≥ 0}
x ← y {x ≥ 0}
{ ϕ } C 1
{ χ } (oppure χ′ se χ ⇒ χ′ ) C 2
{ ψ }
} {
; } {
} { }
{ } { }
{
1 2ψ ϕ
ψ χ
χ ϕ
C C
C C
} { } {
} { } {
ψ ϕ
ψ ψ
ψ ϕ
ϕ ϕ
C
C ′ ′ ⇒
′
⇒ ′
premesse
Asserzioni per la selezione
if x ≥ 0 then
z ← x {z = |x|}
else {x < 0}
z ← − x {z = |x|}
{z = |x|}
{ ϕ }
if B then { ϕ ∧ B}
C 1 { ψ } else { ϕ ∧ ¬ B}
C 2 { ψ } { ψ }
} {
else then
if } {
} {
} {
} {
} {
2 1
2
1 ψ
ϕ
ψ ϕ
ψ ϕ
C C
B
C B
C
B ∧ ¬
∧
Asserzioni per le iterazioni
while y > 0 do
{ ??????? } z ← z + x 2 y ← y − 1
Cosa mettere in un punto
attraversato tante
volte?
Asserzioni per le iterazioni
{n = m ⋅ q + r, 0 ≤ r}
while r ≥ m do
{n = m ⋅ (q+1) + r – m, 0 ≤ r – m}
r ← r − m q ← q + 1
{n = m ⋅ q + r, 0 ≤ r < m}
Qualcosa che, pur cambiando i valori delle variabili, resti
sempre vero!
Asserzioni per le iterazioni
{n = m ⋅ q + r ∧ 0 ≤ r}
while r ≥ m do
{n = m⋅(q+1) + r – m ∧ 0 ≤ r ∧ r ≥ m}
r ← r − m q ← q + 1
{n = m ⋅ q + r ∧ 0 ≤ r ∧ r < m }
{ ϕ }
while B do
{ ϕ ∧ B}
C { ϕ } { ϕ ∧ ¬ B}
} {
} {
} { } {
B C
do B while
C B
¬
∧
∧
ϕ ϕ
ϕ ϕ
invariante
Gli invarianti di ciclo
• invariante: asserzione vera prima di ogni esecuzione del corpo dell’iterazione
• l’invariante deve essere vero anche prima di entrare nel ciclo, dopo ogni esecuzione del corpo, all’uscita dal ciclo
L’ invariante è unico?
Gli invarianti di ciclo
• Un ciclo ha molti (infiniti) invarianti, per lo più triviali:
{0 = 0} è invariante di ogni ciclo
Qual è allora quello che mi
serve?
Gli invarianti di ciclo
• Un invariante è interessante se fa capire cosa avrà fatto il ciclo dopo la terminazione
• Quindi occorre che implichi la post-condizione del ciclo che desidero dimostrare
• A posteriori, trovare un invariante senza conoscere l’idea su cui si basa l’algoritmo è una strada in
salita!
(Ri)-costruire un algoritmo
• La via maestra per trovare un invariante: partire dall’idea su cui si basa l’algoritmo e ricostruirlo
Molto spesso l’invariante non è che una formulazione
precisa di quest’idea
Ricerca binaria
1. Definisci il problema
• Pre-condizioni: il vettore è ordinato
• Input: il valore cercato è 25
• Post-condizioni: ritorna l’indice del valore cercato (se presente).
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
20
1 8
Ricerca binaria
2. Individua l’invariante, pensando alla generica iterazione:
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Inv. : La ricerca è limitata ad un sottovettore t.c. se il valore cercato è presente, allora si trova in quel
sottovettore
Valore cercato: 25
Ricerca binaria
3. Cerca un modo per avvicinare la soluzione mantenendo vero l’invariante
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Passo: dividi il sottovettore in due parti (quasi) uguali;
Valore cercato: 43
Punto intermedio
Se si trova nel punto intermedio: stop
Ricerca binaria
3. Cerca un modo per avvicinare la soluzione mantenendo vero l’invariante
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Passo: dividi il sottovettore in due parti (quasi) uguali;
Valore cercato: 25
Punto intermedio
Se il valore cercato è < di quello nel punto
intermedio, può essere solo nella parte sinistra
Ricerca binaria
3. Cerca un modo per avvicinare la soluzione mantenendo vero l’invariante
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Passo: dividi il sottovettore in due parti (quasi) uguali;
Valore cercato: 54
Punto intermedio
Se il valore cercato è > di quello nel punto
intermedio, può essere solo nella parte destra
Ricerca binaria
4. Definisci in quale momento la computazione si deve fermare
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Quando si sia trovato il valore nel punto intermedio, ….
Valore cercato: 25 Punto intermedio
Ricerca binaria
4. Definisci in quale momento la computazione si deve fermare
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• …. oppure quando il sottovettore cui limitiamo la ricerca sia ridotto al vettore vuoto
Valore cercato: 23 Dovrebbe essere qui in mezzo: ma questo
intervallo è vuoto
Ricerca binaria
5. Definisci le condizioni iniziali della ricerca
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Il sottovettore cui la ricerca è limitata coincide con l’intero vettore
Valore cercato: 25
Ricerca binaria
6. Stabilisci i dettagli della codifica
95 91
88 83
74 72
60 53
51 49
43 36
25 21
21 18
13 6
5 3
1 20
• Il sottovettore cui la ricerca è limitata è compreso tra le posizioni i e j incluse
i j
• Il punto medio ha indice: (i + j) div 2
• Se i > j allora il sottovettore è vuoto
Ricerca binaria
7. Procedi alla pseudocodifica, usando le asserzioni, e principalmente l’invariante, come commenti
RicercaBinaria (V, n)
Pre. V è un vettore ordinato, n il valore cercato
Post. Ritorna m in [1..lunghezza(V)] se V[m] = n, 0 altrimenti i ← 1, j ← lunghezza(V)
trovato ← false
while i ≤ j and not trovato do
{Inv. Se n in V allora n in V[i..j], se trovato = true allora V[m] = n } m ← (i+j) div 2
if n = V[m] then trovato ← true
else if n < V[m] then {considero V[i.. m − 1]} j ← m − 1
sottovettore considerato
Costruire un algoritmo in modo che sia corretto
• La via maestra: formulare precisamente l’idea su cui si basera’ l’algoritmo
Molto spesso la formulazione precisa di quest’idea è
proprio l’invariante
Come si inventa un ciclo?
inizializzazione
while condizione do
corpo dell’iterazione 1
2
3
1. Per scrivere l’inizializzazione si deve sapere cosa deve fare il ciclo
2. Per scrivere la condizione (guardia) si deve conoscere cosa farà il corpo
L’ordine giusto
è l’opposto!
La generica iterazione
• Per individuare correttamente l’invariante non ci si deve porre agli estremi (inizio o
fine del ciclo) ma in un ideale punto medio:
la generica iterazione
Ordinamento per selezione
parte ordinata tutti gli el. di questa parte sono maggiori di quelli nella parte ordinata
i
indice del primo
elemento della parte da ordinare
Idea
V [1..n]
Ordinamento per selezione
i
Invariante
V [1..n]
• V [1 .. i − 1] ordinato
• se x in V [i .. n] ed y in V [1 .. i − 1] allora x ≥ y
Ordinamento per selezione
i
Passo
V [1..n] V [k] sia il minimo valore in V [i .. n]
k
Scambiando V[i] con V[k] l’invariante si mantiene con i ← i + 1:
Ordinamento per selezione
i
Passo
V [1..n] V [k] sia il minimo valore in V [i .. n]
k
Scambiando V[i] con V[k] l’invariante si mantiene con i ← i + 1:
• V [1 .. i] ordinato
• se x in V [i + 1 .. n] ed y in V [1 .. i ] allora x ≥ y
Ordinamento per selezione
i+1
Passo
V [1..n]
Inoltre la lunghezza della porzione ordinata è
aumentata, mentre la lunghezza di quella da ordinare
è diminuita
Ordinamento per selezione
i
Guardia (test di controllo)
V [1..n]
L’iterazione deve proseguire fintanto che i < n.
Quando i = n, V[i] è il massimo in V[1..n]
Ordinamento per selezione
i = 1
Inizializzazione
V [1..n]
La parte già ordinata è vuota: V[1.. 0]
Ordinamento per selezione
Pseudocodifica
SelectSort (V)
Pre. V[1..n] vettore di valori su un insieme linearmente ordinato (es. gli interi) Post. permuta sul posto gli elementi di V in ordine non decrescente
i ← 1
while i < n do
{inv. V[1..i −1] ordinato, gli el. in V[i..n] maggiorizzano quelli in V[1..i −1]}
k ← indice del minimo in V[i..n]
scambia V[i] con V[k]
i ← i + 1
Ordinamento per inserzione
parte ordinata Nessuna assunzione!
i
indice del primo
elemento della parte da ordinare
Idea
V [1..n]
Ordinamento per inserzione
i
Invariante
V [1..n]
• V [1 .. i − 1] ordinato
Ordinamento per inserzione
i
Passo
V [1..n]
Come fare per mantenere l’invariante?
Cercherò “il posto” in cui V[i]
dovrebbe stare
Ordinamento per inserzione
i
Passo
V [1..n]
quindi k in 2..i è il massimo indice t.c.
V[k − 1] ≤ V[i] & k < i ⇒ V[k] > V[i]
k
V[1] ≤ V[i] , V[2] ≤ V[i] …, V[k − 1] ≤ V[i]
V[k] > V[i]
Ordinamento per inserzione
i
Passo
V [1..n]
k
temp ← V[i] Salviamo il valore di V[i]
Ordinamento per inserzione
i
Passo
V [1..n]
k
Facciamo “slittare” V[k..i − 1]
su V[k + 1..i]
Ordinamento per inserzione
i
Passo
V [1..n]
k
V[k] ← temp Poniamo in V[k] il valore
salvato di V[i]
Ordinamento per inserzione
i
Guardia
V [1..n]
Prosegui fintanto che i ≤ n
Ordinamento per inserzione
i = 2
Inizializzazione
V [1..n]
• Il vettore V[1..1] è trivialmente ordinato
• i è l’indice del primo elemento della parte da
Ordinamento per inserzione
Pseudocodifica
InsertSort (V)
Pre. V[1..n] vettore di valori su un insieme linearmente ordinato (es. gli interi) Post. permuta sul posto gli elementi di V in ordine non decrescente
i ← 2
while i ≤ n do {inv.: V[1..i −1] ordinato, sia U= V[1..i −1]}
temp ← V[i], k ← I
while k ≥ 2 and V[k-1] > temp do {inv.: V[1..k-1] V[k+1..i] = U, V[k+1..i] sono > di temp}
V[k] ← V[k – 1], k ← k – 1 V[k] ← temp
{V[1..i] ordinato}
Accumulatori ed invarianti
• Quello iterativo è un metodo di calcolo
incrementale: ci si avvicina al risultato un passo dopo l’altro
• Un accumulatore è una variabile il cui valore rappresenta l’approssimazione corrente
• L’invariante deve allora spiegare in che
senso l’accumulatore approssima il risultato
Moltiplicazione
per somme successive
Moltiplicazione (x, n) Pre. n intero positivo Post. ritorna x ⋅ n
z ← 0, y ← n while y > 0 do
z ← z + x y ← y − 1 return z
2 X 3 = 2 + 2 + 2
