Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Programmazione strutturata
Metodologia top - down
• elemento minimo di un vettore
• sort per straight selection
Copyright © 2006-2009 by Claudio Salati.
Lez. 3
1
PROGRAMMAZIONE STRUTTURA
•
Opera top-down (e eventualmente per raffinamenti successivi
(stepwise refinement))
•
DI UN PROBLEMA SONO NOTI PREMESSA E CONSEGUENZA
•
GLI STATEMENT UTILIZZABILI SONO DATI
• e' data la loro semantica
• sono date le loro regole di s/composizione
•
SE IL PROBLEMA NON E' RISOLUBILE CON UNA SINGOLA
ISTRUZIONE, L'UNICA COSA POSSIBILE E' SCOMPORLO IN
PROBLEMI PIU' SEMPLICI
• secondo le regole della sintassi / semantica degli statement
utilizzabili
• determinando ad ogni stato di scomposizione premessa e
conseguenza di ogni sotto-problema
•
PREMESSE E CONSEGUENZE DEVONO ESSERE COERENTI
FRA LORO, E CON LA SINTASSI/SEMANTICA DEGLI
STATEMENT UTILIZZATI PER SCOMPORRE IL PROBLEMA 2
PROGRAMMAZIONE STRUTTURA
•
AD ESEMPIO, SE SI USA LA REGOLA DI SCOMPOSIZIONE
"SEQUENZA" DEL BLOCCO (linguaggio C):
// {P}
{
// il blocco e' l'espansione di S
// {P1}, e dovra' essere {P}  {P1}
// {P}
S1;
S;
// {C1}  {P2}, in effetti {C1}  {P2}
// {C}
diventa
S2;
// {C2}, e dovra' essere {C2}  {C}
}
// {C}
3
PROGRAMMAZIONE STRUTTURA
•
UTILIZZANDO RICORSIVAMENTE LA STRATEGIA SI
RICONDUCE IL PROBLEMA ORIGINALE A PROBLEMI
ELEMENTARI RISOLUBILI DIRETTAMENTE

•
Cioe’ risolubili utilizzando una singola istruzione semplice
del linguaggio
POICHE' IL PROBLEMA E' STATO RISOLTO APPLICANDO
NELLA PROGETTAZIONE LE STESSE REGOLE CHE SI
UTILIZZEREBBERO PER LA VERIFICA A POSTERIORI DEL
PROGRAMMA, QUESTA NON E' PIU' NECESSARIA
4
PROGRAMMAZIONE STRUTTURA
•
N. Wirth:
Le tecniche di costruzione di un programma si basano su un
unico principio:
scomporre l'azione necessaria per risolvere un
problema in azioni piu' semplici, e
suddividere di conseguenza il problema in
sottoproblemi
•
N.B.: in realta' cio' non e' piu' sempre strettamente vero, ma e'
vero per il tipo di problemi che affrontiamo in questo corso
5
PROGRAMMAZIONE STRUTTURA
• ogni passo di suddivisione deve verificare le seguenti condizioni:
• la scomposizione avviene secondo le regole sintattiche e
semantiche delle istruzioni del linguaggio di programmazione
utilizzato;
• la suddivisione scelta da' luogo a sottoproblemi piu' vicini agli
strumenti disponibili, cioe' a sottoproblemi risolubili piu'
direttamente nel linguaggio di programmazione;
• la soluzione dei sottoproblemi conduce alla soluzione
generale.
• e' un procedimento che puo' richiedere backtracking se si finisce
in un sottoproblema non risolubile o troppo complesso
• e' un procedimento dall'alto verso il basso (top-down)
6
ALTRE METODOLOGIE
• In pratica si usa e si usera' sempre di piu' il procedimento
inverso:
 costruire programmi assemblando sottoprogrammi gia' a
disposizione (o generati da toolkit di programmazione)
• anche perche' nella maggior parte dei casi la situazione non e'
quella di dovere costruire piccoli programmi per risolvere
problemi difficili, ma piuttosto quella di dovere costruire grandi
programmi per problemi "facili" ma voluminosi
• i problemi difficili si trovano risolti in letteratura e nelle librerie
• si utilizza quindi un procedimento dal basso verso l'alto
(bottom-up)
7
Es. 1: Selezione dell'elemento minimo di un vettore
•
Dato un vettore v di N elementi interi, N1, determinare l'indice
dell'elemento (di un elemento) minimo.
•
Premessa:
P = { N1, int v[N] }
•
Conseguenza:
C = { N1, int v[N], 0iMin<N, j=0..N-1 : v[j]  v[iMin] }
•
La premessa dichiara l'esistenza di un vettore v formato da N
elementi interi, con N 1.
•
La conseguenza dichiara che l'elemento di indice iMin del
vettore e' tale per cui tutti gli elementi del vettore hanno valore
maggiore o uguale ad esso.
•
Notare che non tutte le proprieta' sono considerate nel progetto,
e.g.: non viene dimostrato (ma si assume come scontato) che il
8
vettore in uscita e' identico a quello in ingresso.
Es. 1: Selezione dell'elemento minimo di un vettore
•
Strategia:
• si devono (e' necessario) esaminare tutti gli elementi del
vettore;
• si scandisce ordinatamente il vettore, esaminandone un
elemento alla volta, a partire dal suo primo elemento;
• si tiene memorizzato l'indice dell'elemento minimo tra quelli
esaminati fino a quel momento;
• si confronta l'elemento sotto esame con quello minimo trovato
fino a quel momento
(se l'elemento sotto esame e' minore di questo e' anche
minore di tutti gli altri gia' esaminati).
•
Progettazione:
• poiche' esaminiamo in sequenza gli elementi del vettore
definiremo una iterazione sugli elementi del vettore stesso;
• il nucleo della funzione sara' quindi costituito da una
istruzione while.
9
Es. 1: Selezione dell'elemento minimo di un vettore
•
Situazione all'(i+1)-esima iterazione del ciclo:
vettore v
v[0]
... v[iMin] ...
v[i]
iMin
i
v[i+1]
...
v[N-1]
i+1
indice dell'elemento che si andra' ad esaminare
v[0]..v[i]
tratto del vettore gia' esaminato
i
indice dell'ultimo elemento che abbiamo
esaminato
iMin
indice dell'elemento minimo del tratto di vettore
gia' esaminato
10
Es. 1: Selezione dell'elemento minimo di un vettore
•
Complessita' del problema:
• per potere stabilire quale e' l'elemento minimo e' necessario che
ogni elemento sia esaminato almeno una volta.
• il problema richiede almeno tanti passi quanti sono gli elementi del
vettore:
se n e' la dimensione del vettore la complessita' del problema e' di
ordine n (si scrive (n): e' un lower-bound).
•
Complessita' dell'algoritmo proposto:
• ogni elemento viene esaminato (confrontato) una e una sola volta.
• l'algoritmo prevede tanti passi quanti sono gli elementi del vettore:
se n e' la dimensione del vettore la complessita' dell'algoritmo e' di
ordine n (si scrive O(n) : e' un upper-bound).
• pertanto l'algoritmo proposto e' ottimo, non ci possono essere
algoritmi migliori (al massimo ci potranno essere codifiche piu' o
meno attente e algoritmi altrettanto efficienti).
11
Selezione dell'elemento minimo di un vettore: il torneo
•
Si potrebbe fare diversamente? Si', si potrebbe organizzare un
torneo ad eliminazione!
• Possiamo suddividere il vettore in coppie di elementi e
confrontare tra loro gli elementi di ciascuna coppia;
• I vincitori del primo round possono essere di nuovo abbinati in
tante coppie, e gli elementi di ogni coppia confrontati tra loro;
• Si puo' procedere cosi' fino ad individuare il vincitore assoluto.
•
Complessita' dell'algoritmo
• Il primo round comporta n/2 confronti, il secondo round n/4
confronti, … In generale, il k-esimo round comporta n/2k
confronti.
• Quanti round sono necessari? log2n
• Complessita' complessiva:
log
2n
1
n
* k n

1

2
k

1
12
Parentesi: sommatoria della progressione geometrica
n
aa*x...
a*xn 
a*xk 
k0
n
n
k
1
k
1
a
a*xk ax*
a*xk1
n
1
n
ax*
a*x ax*
a*x a*x
k
k0
k
k0
n

1
1

x
a
*
x
a
*

1

x
k

0
n
n1
k
13
Complessita’ dell’algoritmo del torneo
m1
1

x
k
a
*
x
a*

1 x
k 0
m
•
a=n
•
m = log2n
•
x=½
•
La sommatoria inizia da 1 e non da 0
log2n
1
n* k n*

2
k 1
n*
1 21
*n
1/2
1
1
21log2n
1
1
2
log2n
1
n* k

2
k 1
n
 n  2 * n * 2 * n 1  n  n 1
2*n
14
Selezione dell'elemento minimo di un vettore: il torneo
•
Torneo ad eliminazione: esercizio
• Scrivere in C una funzione che implementi l'algoritmo del
torneo ad eliminazione per trovare l'indice dell'elemento
minimo di un vettore.
• E' piu' facile/naturale una implementazione ricorsiva o una
iterativa?
• Come si puo' dimostrare la correttezza di un programma
ricorsivo?
• Come potreste indicare la complessita' del programma che
avete scritto in funzione del numero di elementi del vettore?
N.B.: non pensate all'algoritmo ma alla funzione C che avete
scritto
15
Selezione dell'elemento minimo di un vettore: il torneo
•
Torneo ad eliminazione: soluzione
unsigned min (int v[], unsigned from,
unsigned to) {
if (from == to) return from;
unsigned mid = (from+to)/2;
unsigned min1 = min(v, from, mid);
unsigned min2 = min(v, mid+1, to);
if (v[min1]<=v[min2]) return min1;
else return min2;
}
• Complessita'
T(n) = cost + 2 * T(n/2)
T(1) = cost
se T>1
16
Elemento minimo di un vettore: per tentativi .1
• Si potrebbe fare altrimenti (peggio)?
• Si', procedendo per tentativi.
• Confronto in sequenza ciascun elemento del vettore con tutti
gli altri (il primo elemento con tutti gli altri, poi il secondo
elemento con tutti gli altri, …) fino a che non ne trovo uno che
e' minore o uguale a tutti, cioe' che e' un elemento minimo.
• Se n e' la dimensione del vettore, ogni elemento che viene
esaminato e' sottoposto a n-1 confronti, e se l'elemento minimo
e' l'ultimo posso dovere esaminare tutti gli n elementi del
vettore. In totale posso dovere fare n*(n-1) confronti.
• Se n e' la dimensione del vettore la complessita' di questo
algoritmo e' di ordine n2 (si scrive O(n2)).
17
Elemento minimo di un vettore: per tentativi .2
• Esercizio
• Scrivere in C una funzione che implementi questo algoritmo.
• Con quale conformazione di dati in ingresso il programma che
avete scritto manifesta il suo comportamento peggiore?
• Se siete fortunati quanti confronti sono necessari? E in media?
• Come puo’ essere migliorato questo algoritmo pur senza
cambiare la strategia?
• Devo veramente confrontare un elemento con gli elementi
che lo precedono?
• Devo veramente confrontare un elemento con tutti gli
elementi che lo seguono?
18
Es. 1: Selezione dell'elemento minimo di un vettore
int findMinEl(int N, int v[]) {
// P = { N1, int v[N] }
•
•
•
•
Ciclo while
la premessa del ciclo (l’invariante del ciclo) deve
descrivere la situazione indicata nella strategia
all'inizio si suppone di avere gia' esaminato il vettore nel
tratto v[0]..v[0], e di avere quindi iMin==0: e' ovvio che
v[0] e' l'elemento minimo del sotto-vettore v[0]..v[0]
si inizia quindi l'analisi dal secondo elemento, se c'e‘
(N.B.: l’esistenza del primo elemento [di almeno un
elemento] e’ garantita dalle precondizioni P
// C = { N1, int v[N], 0iMinN-1,
//
j=0..N-1: v[j]v[iMin] }
return iMin;
}
0.1
0.2
0.3
19
Es. 1: Selezione dell'elemento minimo di un vettore
•
Notare che fino dall'inizio, e ad ogni iterazione, abbiamo gia' in
mano l'elemento minimo.
•
Solo che all'inizio, e fino a che non ho raggiunto la fine del ciclo
(cioe' fino a che non ho finito di scandire l'intero vettore),
l'elemento selezionato non e' il minimo dell'intero vettore ma
solo di una sua parte, il prologo gia' esaminato.
•
Notare anche che l’elemento minimo iniziale (quello costruito
dall’inizializzazione del ciclo) e’ “banale”:
l’elemento minimo di un (sotto)vettore di lunghezza 1 e’ l’unico
elemento presente nel (sotto)vettore!
•
Quello che deve fare il ciclo e':
• mantenere valido l'invariante (possiedo l'elemento minimo)
• arrivando a rendere falsa la condizione di controllo del ciclo
(devo ancora esaminare degli elementi del vettore).
20
Es. 1: Selezione dell'elemento minimo di un vettore
int findMinEl(int N, int v[]) {
2.1
// P = { N1, int v[N] }
int i = 0;
2.2
int iMin = 0;
2.3
// P1 = { N1, int v[N], 0iMini,
//
0iN-1, j=0..i: v[j]v[iMin] }
while ( B ) {
2.4
// P2 = P1  B
S;
2.5
// P3 : deve essere uguale o implicare P1
}
2.6
// P1  B
// C = { N1, int v[N], 0iMinN-1,
//
j=0..N-1: v[j]v[iMin] }
return iMin;
2.7
}
2.8
21
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto del test B:
•
si vuole che: { P1  B }  C
•
si vuole che il test risulti FALSO quando ho gia' scandito l'intero
vettore, VERO altrimenti
• quando e' che ho scandito l'intero vettore? Quando i=N-1
• quando e' che mi restano ancora elementi da scandire?
Quando i<N-1
•
poniamo:
B ::= (i < N-1)
{ P1  B } =
{ N1, int v[N], 0iMini, 0iN-1, j=0..i: v[j]v[iMin], i  N-1 } =
{ N1, int v[N], 0iMini, j=0..i: v[j]v[iMin], i =N-1 } =
{ N1, int v[N], 0iMinN-1, j=0..N-1: v[j]v[iMin], i =N-1 } =
C
22
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S:
•
a questo punto e' nota anche P2:
P2 = { P1  B } =
{ N1, int v[N], 0iMini, 0iN-1, j=0..i: v[j]v[iMin], i < N-1 }
•
ad ogni iterazione e' necessario:
1. estendere il sottovettore prefisso gia' esaminato;
2. mantenere l'invariante del ciclo per il sottovettore prefisso esteso.
•
estendere il sottovettore prefisso gia' esaminato equivale a
incrementare i (e’ sicuramente possibile perche’ i<N-1).
•
cio' corrisponde al fatto che durante l'iterazione si va ad esaminare
un nuovo elemento.
•
N.B.: Prima si progetta B poi si puo' progettare S.
Infatti, e' solo quando si conosce B che si puo' indicare la
precondizione di S.
23
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S (regola di s/composizione: blocco):
// P2 = { P1  B }
//
= { N1, int v[N], 0iMini,
//
0i<N-1, j=0..i: v[j]v[iMin]}
i = i+1;
// P4 = { N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin]}
S2;
// P3 : deve essere uguale o implicare P1
•
infatti, sostituendo (i+1) a i in P4 si ottiene P2.
•
N.B.:
• prima invento P4 in base a quello che voglio fare
• poi, in base a P2 e P4, invento i=i+1; (in base alla
semantica intuitiva dell'assegnamento)
• quindi la verifico utilizzando la sua semantica formale.
24
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S:
•
sostituisco (i+1) a i in P4:
{ N1, int v[N], 0iMin<(i+1),
0<(i+1)N-1, j=0..(i+1)-1: v[j]v[iMin] }
=
{ N1, int v[N], 0iMini,
0i<N-1, j=0..i: v[j]v[iMin] }
= P2
25
Es. 1: Selezione dell'elemento minimo di un vettore
int findMinEl(int N, int v[]) {
3.1
// P = { ... }
int i = 0; int iMin = 0;
3.2
// P1 = { N1, int v[N], 0iMini,
//
0iN-1, j=0..i: v[j]v[iMin] }
while ( i < N-1 ) {
3.3
// P2={N1, int v[N], 0iMini,
//
0i<N-1, j=0..i: v[j]v[iMin]}
i += 1;
3.4
// P4={N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin]}
S2; // P3 : deve essere uguale o implicare P1 3.5
}
3.6
// C = { ... }
return iMin;
3.7
}
3.8
26
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S2:
•
dobbiamo avere un valore di iMin valido anche considerando il
sottovettore v[0]..v[i] (cioe' anche l'elemento v[i])
•
si hanno due casi (quindi, regola di s/composizione: if):
1.
v[i] < v[iMin]
2.
v[i]  v[iMin]
// P4 = { N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin]}
if (v[i]<v[iMin])
S2-1;
else
S2-2;
// P3 : deve essere uguale o implicare P1,
// sia nel caso then che nel caso else
27
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S2:
•
considerando la regola per le ramificazioni
// P4 = { N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin]}
if (v[i]<v[iMin])
// P5={ N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin],
//
v[i]<v[iMin]}
S2-1;
else // (v[i]>=v[iMin])
// P6={ N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin],
//
v[i]v[iMin]}
S2-2;
// P3
28
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S2:
• P6 = { N1, int v[N], 0iMin<i, 0<iN-1,
j=0..i-1: v[j]v[iMin],
v[i]v[iMin] }
= { N1, int v[N], 0iMin<i, 0<iN-1,
j=0..i: v[j]v[iMin] }
•
quindi: P6  P1
•
quindi S2-2 non deve fare niente, puo' essere uno statement
vuoto, e l'istruzione if-then-else puo' collassare in una istruzione
if-then
29
Es. 1: Selezione dell'elemento minimo di un vettore
Progetto dell'istruzione S2-1:
•
assumiamo P3 = P1
// P4 = { N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin]}
if (v[i]<v[iMin])
// P5={ N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin],
//
v[i]<v[iMin]}
S2-1;
// P3 = { N1, int v[N], 0iMini,
//
0iN-1, j=0..i: v[j]v[iMin] }
•
definiamo quindi S2-1 come iMin = i; e verifichiamo
30
Es. 1: Selezione dell'elemento minimo di un vettore
Verifica dell'istruzione S2-1:
•
sostituendo i a iMin in P3 si ottiene
{ N1, int v[N], 0ii,
0iN-1, j=0..i: v[j]v[i] }
•
che e' implicata da
P5 = { N1, int v[N], 0iMin<i,
0<iN-1, j=0..i-1: v[j]v[iMin],
v[i]<v[iMin]}
essendo ovviamente v[i]v[i] e, per transitivita',
j=0..i-1: v[j]>v[i]
•
notare che con cio' abbiamo implicitamente completato la
verifica della regola dell'if-then
31
Es. 1: Selezione dell'elemento minimo di un vettore
int findMinEl(int N, int v[]) {
1
// P = { N1, int v[N] }
int i = 0; int iMin = 0;
2
// P1 = { N1, int v[N], 0iMini,
//
0iN-1, j=0..i: v[j]v[iMin] }
while ( i < N-1 ) {
3
i += 1;
4
// P4={N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin]}
if ( v[i] < v[iMin] )
5
iMin = i;
6
}
7
// C = { N1, int v[N], 0iMinN-1,
//
j=0..N-1: v[j]v[iMin] }
return iMin;
8
}
9
32
Es. 1: Selezione dell'elemento minimo di un vettore
int findMinEl(int N, int v[]) {
1
// P = { N1, int v[N] }
int i = 0; int iMin = 0;
2
// P1 = { N1, int v[N], 0iMini,
//
0iN-1, j=0..i: v[j]v[iMin] }
while ( i < N-1 ) {
3
// P2 ={ N1, int v[N], 0iMini,
//
0i<N-1, j=0..i: v[j]v[iMin] }
i += 1;
4
// P4 = {N1, int v[N], 0iMin<i,
//
0<iN-1, j=0..i-1: v[j]v[iMin] }
if ( v[i] < v[iMin] )
5
// P5 = { N1, int v[N], 0iMin<i, 0<iN-1,
//
j=0..i-1: v[j]v[iMin], v[i]<v[iMin]}
iMin = i;
// end if
6
// P3 = { N1, int v[N], 0iMini,
//
0iN-1, j=0..i: v[j]v[iMin] }
}
7
// C = { N1, int v[N], 0iMinN-1, j=0..N-1: v[j]v[iMin]}
return iMin;
}
8
9
33
Es. 1: Selezione dell'elemento minimo di un vettore
Terminazione dell'algoritmo
•
QUALE GRANDEZZA N POSSIAMO DEFINIRE CHE
• sia MONOTONA DECRESCENTE all'esecuzione del ciclo,
e
• sia tale che se la condizione risulta vera allora e' N 0?
•
SIA N = (N-1-i)-1
• LO STATEMENT 4,
i = i + 1;
GARANTISCE N
MONOTONA DECRESCENTE
• i<N-1  (N-1-i)-1  0, cioe` N  0
•
MENO FORMALMENTE BASTA NOTARE CHE i E'
MONOTONA CRESCENTE ED N E' COSTANTE, E CHE IL
CICLO TERMINA QUANDO iN-1
34
Es. 2: Ordinamento di un vettore
•
Dato un vettore di N elementi interi, N1, ordinarlo in modo non
decrescente
•
Premessa:
P = { N1, int v[N] }
•
Conseguenza:
C = { N1, int v[N], j=0..N-2 : v[j]  v[j+1] }
•
La premessa dichiara l'esistenza di un vettore v formato da N
elementi interi, con N 1.
•
La conseguenza dichiara che ogni elemento di v (che abbia un
elemento successivo) e' minore o uguale dell'elemento successivo.
•
Notare che non tutte le proprieta' sono considerate nel progetto, e.g.:
non viene dimostrato che il vettore in uscita contiene gli stessi
elementi di quello in ingresso.
35
Es. 2: Sort di un vettore, strategia straight-selection
•
Strategia:
• Si seleziona l'elemento minimo tra gli N elementi di v e lo si
mette al primo posto (scambiandolo di posto con l'elemento
v[0]);
• poi si seleziona l'elemento minimo tra gli ultimi N-1 elementi
di v e lo si mette al secondo posto (scambiandolo di posto
con l'elemento v[1]);
• poi si seleziona l'elemento minimo tra gli ultimi N-2 elementi
di v e lo si mette al terzo posto (scambiandolo di posto con
l'elemento v[2]);
• e cosi' via, fino a che si sono posizionati in modo ordinato
tutti gli elementi di v.
• Ovviamente, tutto cio' lo faccio all'interno di un ciclo che
scandisce N-1 volte il vettore v.
•
Esercizio: perche' un ciclo di N-1 (e non di N) iterazioni?
36
Es. 2: Sort di un vettore, strategia straight-selection
•
Situazione all'(i+1)-esima iterazione del ciclo:
vettore v
v[0] .. v[i-1] ordinato
v[i]
...
v[N-1]
i
v[0]..v[i-1]
Tratto del vettore gia' ordinato in modo non
decrescente.
Non solo gli elementi del sottovettore v[0]..v[i-1]
sono ordinati tra loro: ciascuno di essi e'  di
tutti gli elementi del sottovettore v[i]..v[N-1]
i
Indice della posizione nel vettore per la quale
voglio selezionare l'elemento minimo all'interno
del sottovettore non-ordinato v[i]..v[N-1]
37
Es. 2: Sort di un vettore, strategia straight-selection
• Progettazione:
•
Gli elementi del vettore ordinato risultato sono determinati in
sequenza (a partire dagli elementi del vettore in ingresso), da
quello di indice 0 a quello di indice N-1.
•
Per cui definiremo una iterazione sulle posizioni del vettore
risultante (regola di s/composizione: while).
 Il nucleo del programma sara' quindi costituito da una
istruzione while.
•
La premessa dell'istruzione while (cosi' come il suo
invariante) deve descrivere la situazione esistente all'inizio di
ciascuna iterazione secondo la strategia che stiamo seguendo;
•
All'inizio della prima iterazione supporremo di avere un
sottovettore gia' ordinato di lunghezza 0 (il sottovettore vuoto
v[0]..v[-1]).
38
Es. 2: Sort di un vettore, strategia straight-selection
void straightSelection(int N, int v[]) {
1.1
// P= { N1, int v[N] }
int i = 0;
1.2
// P1={N1, int v[N], 0iN-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k])}
while ( B ) {
1.3
// P2 = P1  B
S;
1.4
// P3 : deve essere uguale a P1
}
1.5
// P1  B
// C= { N1, int v[N],
//
j=0..(N-1)-1: v[j]v[j+1] }
return;
1.6
}
1.7
39
Es. 2: Sort di un vettore, strategia straight-selection
Progetto del test B:
•
si vuole che: { P1  B }  C
•
poniamo:
B ::= (i < N-1)
{ P1  B } =
{ N1, int v[N], 0iN-1, j=0..(i-1)-1: v[j]v[j+1],
(m=0..i-1, k=i..N-1: v[m]v[k]), iN-1 } =
{ N1, int v[N], j=0..(i-1)-1: v[j]v[j+1],
(m=0..i-1, k=i..N-1: v[m]v[k]), i =N-1 } =
{ N1, int v[N], j=0..((N-1)-1)-1: v[j]v[j+1],
(m=0..(N-1)-1, k=(N-1)..N-1: v[m]v[k]), i =N-1 } =
{ N1, int v[N], j=0..N-3: v[j]v[j+1],
m=0..N-2: v[m]v[N-1], i =N-1 } 
C
•
N.B.: abbiamo applicato la 1.a regola di implicazione
40
Es. 2: Sort di un vettore, strategia straight-selection
void straightSelection(int N, int v[]) {
2.1
// P = { N1, int v[N] }
int i = 0;
2.2
// P1={N1, int v[N], 0iN-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k])}
while (i < N-1) {
2.3
// P2={N1, int v[N], 0i<N-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1,k=i..N-1: v[m]v[k])}
S; // P3, che deve implicare P1
2.4
}
2.5
// C = { N1, int v[N],
//
j=0..(N-1)-1: v[j]v[j+1] }
return;
2.6
}
2.7
41
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S:
•
ad ogni iterazione e' necessario incrementare i,
•
ma prima di fare cio' bisogna:
• selezionare l'elemento minimo del sottovettore non ordinato
v[i]..v[N-1] e
• metterlo all'i-esimo posto di v, scambiandolo con l'elemento v[i]
•
notare che se (N==1) l'istruzione S; del ciclo while non viene
eseguita nemmeno una volta:
• in questo caso il vettore v ha un unico elemento, v[0],
• ed e' quindi intrinsecamente ordinato!
•
abbiamo quindi deciso di scomporre S; in tre sotto-istruzioni
tramite la regola di s/composizione blocco:
S;

con S3 ::= i = i+1;
{ S1; S2; S3; }
42
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S:
void straightSelection(int N, int v[]) {
int i = 0;
// P1={N1, int v[N], 0iN-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k])}
while (i < N-1) { // P2= { P1  i<N-1 }
S1;
// P4
S2;
// P5
i = i + 1;
//P3
}
return;
}
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
43
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S:
•
P5 si ricava da P3 (cioe' da P1) e dall'istruzione i=i+1;
•
Assumiamo P3 = P1(i>0); sostituendo i+1 a i in P3 si ottiene:
P5 =
{ N1, int v[N], 0<(i+1)N-1,
j=0..((i+1)-1)-1: v[j]v[j+1],
( m=0..(i+1)-1,
k=(i+1)..N-1: v[m]v[k] ) }=
{ N1, int v[N], 0i<N-1,
j=0..i-1: v[j]v[j+1],
( m=0..i,
k=(i+1)..N-1: v[m]v[k] ) }
44
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S:
•
di S1; si e' detto che deve identificare l'elemento minimo del
sottovettore v[i]..v[N-1]:
 noi abbiamo gia' una funzione che fa questo lavoro!
•
IN GENERALE UN PROGRAMMA E' COMPOSTO DI
SOTTOPROGRAMMI
•
UNA VOLTA CHE
• UN SOTTOPROGRAMMA E' VERIFICATO,
• SE NE SODDISFANO LE PRECONDIZIONI, E
• LA SUA CONSEGUENZA CI VA BENE,
NON E' NECESSARIO RIVERIFICARLO TUTTE LE VOLTE
CHE LO SI USA
45
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S1:
•
definiamo S1 come:
 int kMin = i + findMinEl(N-i, &v[i]);
•
poiche' P2 garantisce i<N-1, le precondizioni di findMinEl()
sono soddisfatte (v[i]..v[N-1] e' un vettore con almeno 2
elementi);
•
pertanto la conseguenza di findMinEl() garantisce che
v[kMin] sia l'elemento minimo del vettore di N-i elementi
v[i]..v[N-1]
•
possiamo quindi assumere che sia
P4 = P2  (k=i..N-1: v[kMin]v[k])
46
Ridefinizione di findMinEl()
• In realta' findMinEl() e' utilizzabile nel contesto di
straightSelection() solo grazie alla debolezza della
nozione di array in C; infatti :
• cio' che le passiamo in ingresso non e' un vettore, ma
l'indirizzo di un elemento di un vettore v[], che noi
consideriamo essere il primo elemento del (sotto)vettore di
lunghezza N-i di cui vogliamo localizzare l'elemento
minimo;
• e cio' che ritorna findMinEl() e' l'indice dell'elemento
minimo relativamente all'inizio del (sotto)vettore (cioe'
all'elemento di indice i del vettore),
• e se vogliamo l'indice dell'elemento minimo del sottovettore
v[i]..v[N-1] all'interno di v[] dobbiamo sommare i
a quanto tornato da findMinEl();
47
Ridefinizione di findMinEl()
•
meglio sarebbe ridefinire findMinEl() in modo da liberarsi
dalla dipendenza linguistica dal C, e da farci ritornare
direttamente l'indice dell'elemento minimo relativo all'inizio del
vettore v[] .
int findMinEl(int from, int to, int v[]);
// P= { 0fromto, int v[size] : tosize-1 }
// C= { 0fromto, int v[size] : tosize-1,
//
•
k=from..to: v[return]v[k] }
Esercizio:
• riscrivere findMinEl() esplicitando premessa,
conseguenza e invariante del ciclo che realizza la funzione
48
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S2:
// P2={N1, int v[N], 0iN-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k])}
int kMin = i + findMinEl(N-i, &v[i]);
// P4={N1, int v[N], 0i<N-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k]),
//
k=i..N-1: v[kMin]v[k]}
S2;
// P5={N1, int v[N], 0i<N-1,
//
j=0..i-1: v[j]v[j+1],
//
(m=0..i, k=(i+1)..N-1: v[m]v[k])}
i = i + 1;
// P3={N1, int v[N], 0<iN-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k])} 49
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S2:
•
definiamo S2 come:
{ int temp = v[kMin];
v[kMin] = v[i];
v[i] = temp; }
e verifichiamo che P4 derivi correttamente da P5.
•
notiamo come in P5 si possa riscrivere
{ (m=0..i, k=(i+1)..N-1: v[m]v[k]) }
come (ovviamente e': v[i]v[i])
{ (m=0..i-1, k=(i+1)..N-1: v[m]v[k]),
k=i..N-1: v[i]v[k] }
1
1.1
1.2
e
{ j=0..i-1: v[j]v[j+1] }
2
come
{ j=0..i-2: v[j]v[j+1],
m=0..i-1: v[m]v[i] }
2.1
2.2
50
Es. 2: Sort di un vettore, strategia straight-selection
Verifica dell'istruzione S2:
•
riscrivendo P5 (fondendo 1.1 e 2.2):
{ N1, int v[N], 0i<N-1,
j=0..i-2: v[j]v[j+1],
(m=0..i-1, k=i..N-1: v[m]v[k]),
k=i..N-1: v[i]v[k] }
•
e scambiando tra loro v[i] e v[kMin]:
{ N1, int v[N], 0i<N-1,
j=0..i-2: v[j]v[j+1],
( m=0..i-1, k=i..N-1: v[m]v[k] ),
k=i..N-1: v[kMin]v[k] }
= P4
51
Es. 2: Sort di un vettore, strategia straight-selection
Progetto dell'istruzione S2 - alternativa:
•
avremmo anche potuto definire S2 come:
if (kMin!=i) {
int temp = v[kMin];
v[kMin] = v[i];
v[i] = temp;
}
•
infatti, se kMin==i P4P5
52
Es. 2: Sort di un vettore, strategia straight-selection
void straightSelection(int N, int v[]) {
// P= { N1, int v[N] }
int i = 0;
// P1={N1, int v[N], 0iN-1,
//
j=0..(i-1)-1: v[j]v[j+1],
//
(m=0..i-1, k=i..N-1: v[m]v[k])}
while (i < N-1) {
int kMin = i + findMinEl(N-i, &v[i]);
int temp = v[kMin];
v[kMin] = v[i];
v[i] = temp;
i = i + 1;
}
// C= { N1, int v[N],
//
j=0..(N-1)-1: v[j]v[j+1] }
return;
}
1
2
3
4
5
6
7
8
9
10
11
53
Es. 2: Sort di un vettore, strategia straight-selection
Terminazione dell'algoritmo
•
La terminazione dell'algoritmo e' garantita perche':
• E' garantita la terminazione del ciclo di selezione dell'elemento
minimo
(gia' dimostrato)
• E' garantita la terminazione del ciclo esterno poiche'
•
N e' costante,
•
i e' monotona crescete ad ogni iterazione,
e quindi la condizione di controllo del while sara'
necessariamente falsificata (in particolare, dopo N-1 iterazioni)
• Formalmente, la funzione monotona decrescente di
terminazione e': N = N-2-i
54
Es. 2: Sort di un vettore, strategia straight-selection
Complessita' dell'algoritmo
•
Quanti passi (confronti) richiede l'algoritmo?
– N-1 confronti (all'interno di findMinEl()) durante la
prima iterazione del ciclo esterno;
– N-2 confronti durante la seconda iterazione del ciclo
esterno;
– e cosi' via …
•
cioe' un numero di confronti pari a
N  1N


N

i


N-1
i1
2
•
quindi l'algoritmo e' di complessita' O(n2)
•
si puo' fare di meglio? Si'!
55