08-Formulazione di algoritmi

Sommario
! Metodi di risoluzione dei problemi
! Esempi di formulazione di algoritmi
! Proprietà degli algoritmi: correttezza ed efficienza
Formulazione di algoritmi
Elementi di Informatica
Docente: Giorgio Fumera
Testo di riferimento:
Ceri et al., “Informatica: arte e mestiere”
Corso di Laurea in Edilizia
Facoltà di Architettura
A.A. 2009/2010
2
Risoluzione di problemi
Alcune linee guida
Un possibile approccio generale alla formulazione di un
algoritmo per la risoluzione di un dato problema:
! Ricerca di tecniche di risoluzione di problemi: attività di
interesse generale, non limitata all’informatica
"
! Ma a tutt’oggi è un’arte piuttosto che una scienza...
"
! In matematica si è dimostrato che non esiste un
procedimento generale di risoluzione di problemi che sia
esso stesso un algoritmo (se esistesse, tutti i problemi
matematici potrebbero essere risolti da un calcolatore...)
"
"
3
capire il problema (quali sono i dati di ingresso e il risultato
desiderato), eliminando i dettagli inutili e individuando le
informazioni essenziali per la sua soluzione (astrazione)
se possibile, scomporre il problema in più sottoproblemi
indipendenti e più semplici da risolvere, e sfruttare
problemi simili che siano stati già risolti
procedere per tentativi costruendo la soluzione a livelli di
dettaglio via via maggiore (inizialmente anche in linguaggio
naturale), fino ad arrivare a operazioni esprimibili nel
linguaggio di programmazione scelto (approccio top-down,
cioè dal generale al particolare)
tradurre l'intero algoritmo nel linguaggio scelto
4
Esempi di formulazione di algoritmi
Di seguito si presentano alcuni esempi di formulazione di algoritmi,
espressi nello pseudo-linguaggio considerato in questo corso, per la
risoluzione di semplici problemi
Uno degli scopi di questi esempi è mettere in evidenza due fasi ben
separate nel processo di fomulazione di algoritmi espressi in un
qualsiasi linguaggio formale:
" la prima fase consiste nel comprendere il problema e trovarne un
procedimento risolutivo in linguaggio naturale,
indipendentemente dal linguaggio che si dovrà poi usare per
descrivere tale procedimento
" la seconda fase consiste nel “tradurre” nel linguaggio considerato
il procedimento risolutivo espresso inizialmente in linguaggio
naturale. In questa fase si deve ricordare che:
– tutti i dati di ingresso devono essere acquisiti e memorizzati in
variabili attraverso l'istruzione read
– tutti i risultati devono essere stampati per mezzo
dell'istruzione print
Massimo di una sequenza di numeri
Problema: trovare il massimo di una sequenza di numeri
interi avente lunghezza qualsiasi, nota solo nel momento
in cui l’algoritmo sarà eseguito
"
"
5
Una possibile strategia di risoluzione: leggere uno alla
volta ciascun numero della sequenza, e tener traccia del
numero più grande tra quelli già letti
Nota bene: questo procedimento, come quelli degli
esempi successivi, non fa riferimento a un esecutore
particolare, né a un particolare linguaggio di descrizione
di algoritmi!
6
Rappresentazione di un numero in base due
Soluzione
Questa è una possibile codifica
dell’algoritmo che realizza il
procedimento descritto
precedentemente in linguaggio
naturale
La lunghezza della sequenza viene
memorizzata nella variabile m
I numeri della sequenza vengono
memorizzati (uno alla volta) in n
Il numero più grande tra quelli già
letti viene memorizzato in max, a cui
viene inizialmente assegnato il valore
del primo numero della sequenza
Per “contare” i numeri da leggere si
usa la variabile i
dati di partenza: la lunghezza della sequenza e i suoi
elementi
risultato: il numero più grande della sequenza
Determinare le cifre della rappresentazione in base due di
un dato numero intero
variabili: m, n, i e max
memorizzano numeri interi
"
"
read (m)
read (n)
max # n
i#1
while (i < m) do {
read (n)
if (n > max) then { max # n }
i#i +1
}
print (max)
7
dati di partenza: un numero intero
risultato: la sequenza di cifre della sua rappresentazione in
base due
Un possibile procedimento è quello delle divisioni
successive per due, già descritto a proposito della codifica
binaria di informazioni numeriche
8
Soluzione
Il valore del numero da
rappresentare viene memorizzato
nella variabile n, che verrà
successivamente usata per
memorizzare i quozienti delle
divisioni per due
A ogni passo, il resto della divisione
per due viene memorizzato in r e
stampato
Massimo comun divisore
Determinare il massimo comun divisore tra due numeri
naturali positivi
variabili: n e r memorizzano
numeri interi
"
"
read (n)
if (n = 0) then { print (0) }
else {
while (n > 0) do {
r # n mod 2
print (r)
n#n/2
}
}
dati di partenza: una coppia di numeri naturali positivi
risultato desiderato: il loro m.c.d.
Sfruttando la definizione di m.c.d. tra due numeri m e n
(il più grande intero che sia divisore di entrambi), una
possibile soluzione consiste nel considerare tutti i numeri
tra 1 e il più piccolo tra m e n, tenendo traccia
dell’ultimo numero, tra quelli già considerati, che sia
divisore sia di m che di n
9
Soluzione
I due numeri vengono
memorizzati nelle variabili m e n
I numeri da 1 al più piccolo tra m
e n vengono memorizzati nella
variabile d
Il più grande divisore di m e n tra
quelli già considerati viene
memorizzato nella variabile mcd
Per determinare se un numero è
divisore di un altro si usa
l’operatore mod (resto della
divisione intera)
10
Una soluzione alternativa
Un procedimento meno banale (noto come algoritmo di
Euclide) si basa sul seguente teorema di Euclide:
variabili: m, n, i e mcd, numeri interi
"
read (m)
read (n)
d#1
while (d ! m and d ! n) do {
if ((m mod d = 0) and (n mod d = 0))
then { mcd # d }
d#d+1
}
print (mcd)
"
"
se m = n, allora MCD(m,n) = m = n
se m > n, allora MCD(m,n) = MCD(m–n,n)
se m < n, allora MCD(m,n) = MCD(m,n–m)
Si assuma ora che m > n, e si indichi con s il valore m–n. Il
ragionamento precedente può essere applicato alla coppia
s,n: MCD(m,n) = MCD(m–n,n) = MCD(s,n):
"
"
"
se s = n, MCD(s,n) = s = n
se s > n, MCD(s,n) = MCD(s–n,n)
se s < n, MCD(s,n) = MCD(s,n–s)
...
11
12
Una soluzione alternativa
Una soluzione alternativa
Continuando ad applicare questo procedimento, si
otterranno prima o poi due numeri identici, e quindi il
m.c.d. cercato
Ecco come l’algoritmo di
Euclide può essere codificato
nel nostro pseudo-linguaggio
read (m)
read (n)
while (m $ n) do {
if (m > n) then { m # m – n }
else { n # n – m }
}
print (m)
È ora chiaro che il MCD tra due numeri può essere
calcolato nel modo seguente
"
"
variabili: m e n memorizzano numeri
interi
se i due numeri sono identici, il loro valore coincide con il
m.c.d. tra i due numeri di partenza
in caso contrario, sostituire il numero maggiore con la
differenza tra esso e il minore, e tornare al punto
precedente
13
Numeri primi
14
Soluzione
Determinare se un dato numero naturale sia primo
Si assume che il risultato debba
essere stampato sotto forma di
messaggio (“Il numero è primo”
oppure “Il numero non è primo”)
Il numero da analizzare viene
memorizzato nella variabile n
I numeri da 1 a n/2 vengono
memorizzati nella variabile d
La variabile primo viene usata per
tener traccia del fatto che si siano
trovati divisori di n. Si è scelto di
assegnare a primo il valore 0 in caso
affermativo, 1 in caso negativo. Per
questo motivo, il valore iniziale di
primo deve essere 1
Come nel caso del m.c.d., si può sfruttare la definizione:
un numero n è primo se non ha altri divisori oltre 1 e se
stesso
Un possibile procedimento consiste quindi nel considerare
tutti i numeri tra 2 e n – 1, e verificare se almeno uno di
essi sia divisore di n (a questo scopo è sufficiente
considerare i numeri tra 2 e n/2): in caso affermativo n
non è primo, altrimenti è primo
15
variabili: n, d e primo memorizzano
numeri interi
read (n)
d#2
primo # 1
while (d ! n/2) do {
if (n mod d = 0) then { primo # 0 }
d#d+1
}
if (primo = 1)
then { print (“Il numero è primo”) }
else { print (“Il numero non è primo”) }
16
Radice quadrata
Soluzione
Determinare la parte intera della radice quadrata di un
dato numero reale non negativo
Si potrebbe usare il noto procedimento per calcolare la
radice quadrata di un numero reale, che però è
complicato da esprimere in termini delle operazioni
elementari del nostro linguaggio...
Un procedimento più semplice si basa sull’osservazione
che la parte intera della radice quadrata di x è il più
grande numero intero r tale che r2 ! x
Per trovare tale numero è sufficiente considerare gli interi
0, 1, 2, ..., fino a trovarne uno il cui quadrato sia
maggiore di x: il risultato cercato è allora il numero che
precede l’ultimo considerato
17
Ricerca di un elemento in una sequenza
Il numero di cui si deve calcolare la
parte intera della radice quadrata
viene memorizzato nella variabile x
I numeri da considerare come
possibili radici intere, 0,1,2,...,
vengono memorizzati nella variabile r
Al termine dell’istruzione iterativa
while-do il valore di r è maggiore di
una unità rispetto al risultato
desiderato
variabili: x memorizza numeri
reali, r numeri interi
read (x)
r#0
while (r % r ! x) do { r # r + 1 }
print (r – 1)
18
Soluzione (1)
Un problema che ricorre in molte applicazioni pratiche è il
seguente: data una sequenza S di valori (numeri, nomi, o
dati più complessi), determinare se un valore X sia presente
in essa
L'algoritmo più immediato consiste nello scorrere la
sequenza dal primo all'ultimo elemento, confrontando ogni
elemento con il valore cercato
Nell'esempio seguente si mostra una possibile soluzione nel
caso in cui la sequenza sia composta da 100 numeri interi,
e il risultato dell'algoritmo debba essere il messaggio “È
presente” oppure “Non è presente”
19
Si è scelto di memorizzare la
sequenza in un array. Il valore
da cercare viene memorizzato
nella variabile x
Poi si confrontano gli elementi
dell'array con quello che si sta
cercando, e si usa la variabile
trovato in modo simile alla
variabile primo dell'algoritmo
visto in precedenza per i numeri
primi
variabili: x, trovato e i memorizzano numeri
interi; s è un array di 100 numeri interi
i#1
while (i ! 100) do {
read (s[i])
i#i+1
}
read (x)
i#1
trovato # 0
while (i ! 100) do {
if (s[i] = x) then { trovato # 1 }
i#i+1
}
if (trovato = 1) then { print (“È presente”) }
else { print (“Non è presente”) }
20
Soluzione (2)
Una soluzione alternativa, più
“efficiente” della prima: se si
trova un elemento uguale a
quello cercato, non è necessario
analizzare gli elementi
successivi
Per terminare l'istruzione
iterativa non appena si trova
l'elemento cercato, è possibile
aggiungere una condizione sul
valore di trovato
Ricerca di un elemento in una sequenza ordinata
variabili: x, trovato e i memorizzano numeri
interi; s è un array di 100 numeri interi
i#1
while (i ! 100) do {
read (s[i])
i#i+1
}
read (x)
i#1
trovato # 0
while (i ! 100 and trovato = 0) do {
if (s[i] = x) then { trovato # 1 }
i#i+1
}
if (trovato = 1) then { print (“È presente”) }
else { print (“Non è presente”) }
21
Soluzione
E se sapessimo che i numeri della sequenza sono ordinati
(in senso crescente o decrescente)?
Ovviamente la soluzione precedente funziona anche in
questo caso. Si può però fare di meglio
Supponiamo che i numeri siano ordinati in senso
crescente. Se scorrendo gli elementi della sequenza (dal
più piccolo al più grande) non abbiamo ancora trovato
quello cercato, ma ne troviamo uno maggiore, allora
siamo sicuri che quello cercato non è presente, e
possiamo evitare di continuare la ricerca tra gli elementi
restanti
22
Ricerca di un elemento in una sequenza ordinata
variabili: x, trovato e i memorizzano numeri interi; s
è un array di 100 numeri interi
Un algoritmo alternativo può essere formulato prendendo
spunto dal modo in cui cerchiamo il nome di una persona
all'interno dell'elenco telefonico (che è un elenco ordinato
di nomi).
Schematizzando un po', noi non scorriamo l'elenco dal
primo nome fino a quello cercato, ma lo apriamo in
corrispondenza della pagina centrale e poi decidiamo se
proseguire la ricerca nella metà precedente o in quella
successiva; quindi apriamo la metà scelta in corrispondenza
della sua pagina centrale, e così via.
Questo algoritmo è detto algoritmo di ricerca binaria.
i#1
while (i ! 100) do {
read (s[i])
i#i+1
}
read (x)
i#1
trovato # 0
while (i ! 100 and trovato = 0 and s[i] ! x) do {
if (s[i] = x) then { trovato # 1 }
i#i+1
}
if (trovato = 1) then { print (“È presente”) }
else { print (“Non è presente”) }
23
24
Ricerca di un elemento in una sequenza ordinata
Soluzione
Questo procedimento può essere descritto più precisamente come segue. Si ha
una sequenza di N elementi ordinati in senso crescente (si supponga che siano
numeri interi). In ogni passo si indica con i e j la posizione del primo e
dell'ultimo elemento dela sottosequenza sulla quale proseguire la ricerca.
All'inizio i=1 e j=N.
Finché la sottosequenza contiene almeno un elemento (cioè finché i ! j), si
ripetono le seguenti operazioni:
" si considera l'elemento centrale della sequenza, indicato con c, la cui
posizione è data da pc=(i+j)/2 (si considera la parte intera della divisione)
"
"
"
Nel nostro pseudo-linguaggio
l'algoritmo può essere scritto in
questo modo.
Per brevità si omettono le
istruzioni di lettura della
sequenza di numeri, identiche
agli esempi precedenti.
se n = c, abbiamo trovato l'elemento e l'algoritmo termina
se n > c, l'elemento da cercare può trovarsi solo tra gli elementi successivi a
c; quindi la prossima sottosequenza da considerare è quella il cui primo
elemento è in posizione i = pc+1 e l'ultimo nella posizione j
se n < c, l'elemento da cercare può trovarsi solo tra gli elementi precedenti
c; quindi la prossima sottosequenza da considerare è quella il cui primo
elemento è nella posizione i, e l'ultimo nella posizione j = pc-1
Se l'ultima sottosequenza è vuota (i>j), l'elemento non è presente
variabili: x, trovato, i, j, p: numeri interi; s è
un array di 100 numeri interi
(lettura della sequenza)
read (x)
i#1
j # 100
trovato # 0
while (i ! j and trovato = 0) do {
p # (i+j)/2
if (s[p] = x) then { trovato # 1 }
if (s[p] < x) then { i # p + 1 }
if (s[p] > x) then { j # p - 1 }
}
if (trovato = 1) then { print (“È presente”) }
else { print (“Non è presente”) }
25
Algoritmi di ordinamento
26
Scomposizione in sottoproblemi
Ordinare (in senso crescente o decrescente) una sequenza
di numeri di lunghezza data
La necessità di ordinare una sequenza di elementi secondo
un criterio dato ricorre in molte applicazioni
Tra i diversi algoritmi di ordinamento esistenti, nel seguito
si considera l’algoritmo noto come selection sort, che può
essere sinteticamente descritto come segue:
per ordinare una data sequenza in senso crescente (o
decrescente), scambiare l’elemento “più piccolo” (o il
“più grande”) con il primo della sequenza, e riapplicare lo
stesso procedimento agli elementi della nuova sequenza
successivi al primo
27
Per arrivare alla formulazione dell’algoritmo nel nostro
pseudo-linguaggio è utile scomporlo in sottoproblemi più
semplici, secondo l’approccio top-down descritto in
precedenza. Comiciamo con il descrivere l’algoritmo in
modo più preciso, ma sempre in linguaggio naturale:
Data una sequenza di almeno due elementi:
1. cercare l’elemento più piccolo (o il più grande)
2. scambiare tale elemento con il primo della sequenza
3. se la sequenza contiene più di due elementi,
riapplicare l’intero procedimento agli elementi successivi
28
Scomposizione in sottoproblemi
Scomposizione in sottoproblemi
Proviamo ora a descrivere l’algoritmo in termini delle
operazioni esprimibili nel nostro pseudo-linguaggio, assumendo
che gli elementi della sequenza vengano memorizzati in una
variabile array. Data la relativa complessità dell’algoritmo, è
conveniente esprimere inizialmente le istruzioni sia nello
pseudo-linguaggio che in linguaggio naturale:
leggere gli elementi della sequenza;
while (la sequenza considerata contiene più di un elemento) do {
cercare l’elemento più piccolo (più grande);
scambiare tale elemento con il primo della sequenza;
considerare la sequenza meno il primo elemento;
}
stampare gli elementi della sequenza ordinata;
Nell’algoritmo appena descritto si possono individuare tre
sottoproblemi:
"
"
"
leggere/scrivere gli elementi di una sequenza
cercare l’elemento più piccolo (più grande) di una sequenza
scambiare due elementi di una sequenza
Ora cerchiamo di formulare un algoritmo per ciascuno di
questi sottoproblemi usando solo istruzioni del nostro
pseudo-linguaggio
Successivamente “metteremo insieme” le diverse parti
per arrivare all’algoritmo che risolva il problema iniziale
29
Primo sottoproblema: soluzione
30
Secondo sottoproblema: soluzione
Lettura/scrittura degli elementi di una sequenza (tramite
una variabile array)
Questo problema è già stato risolto in un esempio
precedente: sfruttiamo la stessa sequenza di istruzioni
Assumendo che la lunghezza della sequenza sia 100:
i#1
while (i ! 100) do {
read (s[i]) (oppure: print (s[i]) )
i#i+1
}
(si assume che s sia una variabile array composta da 100
elementi, e i una variabile che memorizza numeri interi)
Ricerca dell’elemento più piccolo di una sequenza memorizzata in
una variabile array
Dato che tale elemento dovrà poi essere scambiato con il primo della
sequenza, ciò che alla fine interessa non è il suo valore, ma la sua
posizione (il suo indice) all’interno della sequenza. L’algoritmo
proposto si basa sulla logica seguente: si scorrono gli elementi della
sequenza e si tiene traccia dell’indice del più piccolo tra quelli già
considerati (la ricerca dell’elemento più grande segue una logica
simile)
min # 1
i#2
while (i ! 100) do {
if ( s[i] < s[min] ) then { min # i }
i#i+1
}
31
32
Terzo sottoproblema: soluzione
Soluzione del problema principale
Scambiare due elementi di una variabile array, dei quali siano
noti gli indici
Si assuma che gli indici siano memorizzati nelle variabili a e b.
Si può essere tentati di scrivere le due istruzioni di
assegnamento:
s[a] # s[b]
s[b] # s[a]
Ma dopo l’esecuzione della prima, il valore di s[a] andrebbe
perso... È quindi necessaria una terza variabile ausiliaria
(chiamiamola temp) per memorizzare il valore di s[a]:
temp # s[a]
s[a] # s[b]
s[b] # temp
Cerchiamo ora di scrivere l’intero algoritmo “mettendo
insieme” le diverse parti. Si noti che questo potrebbe
richiedere qualche piccola modifica agli algoritmi dei
singoli sottoproblemi
La modifica principale è dovuta alla realizzazione
dell’istruzione indicata informalmente come “considera la
sequenza meno il primo elemento”, che si trova
all’interno di una istruzione iterativa while-do
"
"
si userà una variabile (chiamata i nell’algoritmo) per
memorizzare l’indice del primo elemento della
sottosequenza considerata a ogni iterazione
questo implica che nella ricerca del minimo di una
sottosequenza si dovranno scorrere i suoi elementi a partire
da quello di indice i + 1
33
34
Soluzione del problema principale
variabili: i, j, min e temp
memorizzano numeri
interi;
s è un array di 100 numeri
interi
i#1
while (i ! 100) do {
read (s[i])
i#i+1
}
i#1
while (i < 100) do {
min # i
j#i+1
while (j ! 100) do {
if (s[j] < s[min]) then { min # j }
j#j+1
}
if (min $ i) then {
temp # s[i]
s[i] # s[min]
s[min] # temp
}
i # i +1
}
i#1
while (i ! 100) do {
print (s[i])
i#i+1
}
35
Proprietà degli algoritmi:
correttezza ed efficienza
36
Correttezza
Verificare la correttezza di un algoritmo
Un algoritmo per la soluzione di un dato problema si dice
corretto se, per ogni istanza del problema
"
"
! Non esiste una procedura generale: è un’area di ricerca
molto attiva dell’informatica
termina in un numero finito di passi
fornisce la soluzione desiderata
! Per algoritmi semplici (come quelli di interesse per questo
corso) si può procedere ragionando caso per caso. Alcuni
possibili approcci:
Come si verifica la correttezza di un algoritmo?
Soluzione apparentemente semplice, ma impraticabile:
eseguire l’algoritmo per tutte le istanze del problema...
"
"
il numero di istanze può essere infinito, o comunque molto
grande
e se per qualche istanza l’algoritmo non termina? (nota: si
può dimostrare che non esiste una procedura generale per
determinare se un dato algoritmo, per una data istanza,
termini oppure no...)
"
"
cercare di capire qual è la logica seguita dall’algoritmo per
risolvere il problema considerato
individuare le istanze del problema che potrebbero
costituire casi particolari, e verificare se sono trattate in
modo corretto
37
Esempio (1)
38
Esempio (1)
L’algoritmo seguente dovrebbe verificare se i numeri
memorizzati nell’array v (composto da 5 elementi) sono
ordinati in senso non decrescente, stampando 1 in caso
affermativo, 0 altrimenti. L’algoritmo è corretto?
Un esame dell’algoritmo rivela che esso è basato sulla
logica seguente: gli elementi dell’array sono ordinati in
senso non decrescente se ogni elemento (a parte l’ultimo)
è minore o uguale al successivo
Il risultato viene memorizzato nella variabile risposta
Il valore di risposta viene modificato a ogni iterazione
dell’istruzione while-do, a seconda del risultato del
confronto tra la coppia di elementi in esame
i#1
while (i < 5) do {
if (v[i] ! v[i + 1]) then { risposta # 1 } else { risposta # 0 }
i#i+1
}
print (risposta)
Ma questo significa che l’algoritmo non è corretto, poiché
il risultato dipenderà solo dall’ordinamento dell’ultima
coppia (es.: si esegua l’algoritmo con la sequenza
5,4,3,1,2)
39
40
Esempio (1)
Esempio (2)
Una possibile versione corretta (la prova è lasciata come
esercizio)
Si assuma che v sia un array composto da 10 numeri interi
e che n memorizzi numeri interi. L’algoritmo seguente
dovrebbe stampare il numero di coppie di elementi
distinti di v la cui somma sia pari al valore di n.
L’algoritmo è corretto?
risposta # 1
i#1
while (i < 5) do {
if (v[i] > v[i + 1]) then { risposta # 0 }
i#i+1
}
print (risposta)
s#0
i#1
while (i < 10) do {
if (v[i] + v[i + 1] = n) then { s # s + 1 }
i # i+1
}
print (s)
41
Esempio (2)
42
Efficienza
Si può osservare che l’algoritmo non esamina tutte le coppie di
elementi distinti dell’array, ma solo le coppie di elementi
adiacenti: se ne conclude che non è corretto
Una possibile versione corretta:
Un algoritmo si dice più efficiente di un altro se perviene
alla soluzione di uno stesso problema
"
"
s#0
i#1
while (i < 10) do {
j#i+1
while (j ! 10) do {
if (v[i] + v[j] = n) then { s # s + 1 }
j#j+1
}
i # i+1
}
print (s)
in un numero inferiore di “passi” (cioè “più velocemente”)
oppure usando una minore quantità di “risorse”
(principalmente il numero di celle di memoria usate per
memorizzare i dati intermedi dell’elaborazione)
L’efficienza è legata al concetto di complessità
computazionale di un algoritmo
"
"
43
complessità temporale: tempo necessario per risolvere un
dato problema (oppure numero di “passi” da eseguire)
complessità spaziale: quantità di memoria richiesta
dall’algoritmo
44
Efficienza
Efficienza
In genere la complessità temporale dipende dalla
particolare istanza di un problema
Gli algoritmi vengono caratterizzati in base ai valori di
complessità valutati nei tre casi seguenti
"
"
"
La complessità di un algoritmo può dipendere da due fattori
! Il valore dei dati di ingresso
es.: il numero di operazioni richieste dall’algoritmo di
Euclide per calcolare il massimo comun divisore tra due
numeri dipende dai valori dei due numeri
caso migliore (best case): corrisponde alle istanze per le
quali la complessità è la più bassa
caso medio (average case): è il valor medio (in senso
statistico) della complessità rispetto a tutte le possibili
istanze
caso peggiore (worst case): corrisponde alle istanze per le
quali la complessità è la più alta
! La “dimensione” dei dati di ingresso
es.: il numero di operazioni richieste dall’algoritmo
selection sort per ordinare una sequenza di numeri dipende
dalla lunghezza della sequenza (oltre che dai valori degli
elementi della sequenza)
! Nella valutazione di un algoritmo ha maggiore importanza
la complessità nel caso peggiore
45
Valutare l’efficienza di un algoritmo
46
Esempio (1)
Unità di misura: di norma si considera il numero di operazioni
richieste dall’algoritmo
Calcolo del minimo comune multiplo tra due numeri m e n
Un possibile algoritmo: scandire tutti i numeri tra max{m,n} e m%n,
fermandosi non appena si trovi un multiplo comune di m e n
Una possibile “traduzione” nel nostro linguaggio:
if (m > n) then { mcm # m } else { mcm # n }
Ma cosa si intende esattamente per “operazione”?
" quali operazioni si devono considerare? (aritmetiche, di
assegnamento, valutazione di espressioni condizionali,
lettura/scrittura?)
" si deve assegnare lo stesso peso a ogni tipo di operazione? (per
es., nei calcolatori reali di norma le operazioni su numeri reali
richiedono più tempo rispetto alle corrispondenti operazioni su
numeri interi)
while ( ((mcm mod m $ 0) or (mcm mod n $ 0)) and (mcm < m%n) )
do { mcm # mcm + 1 }
print (mcm)
La valutazione può essere approssimata caso per caso tenendo conto
del tipo di operazione predominante in un dato algoritmo. Per
esempio, le operazioni logico-aritmetiche (anche quelle facenti parte
di espressioni condizionali), oppure le espressioni condizionali
47
La complessità di questo algoritmo può essere valutata in termini del
numero di ripetizioni dell'istruzione iterativa. Nel caso peggiore il
m.c.m è proprio m%n: questo richiede l’esame di m%n – max{m,n} +
1 numeri. La complessità temporale è dunque proporzionale a m%n –
max{m,n} + 1
Nota: in questo caso la complessità dipende dai valori dei dati
48
Esempio (1)
Esempio (2)
L’algoritmo precedente può essere reso più efficiente
osservando che, poiché si cerca un multiplo comune, è
sufficiente considerare solo i multipli di max{m,n}
nell’intervallo indicato. Per es., se m > n, si potranno
considerare solo i valori m, 2m, 3m, ..., n%m
Algoritmo di ordinamento selection sort: l’essenza consiste nel
confronto tra un elemento in una posizione data e tutti quelli nelle
posizioni successive, da ripetere per tutte le posizioni tranne l’ultima
Data una sequenza di n elementi
" al primo passo si eseguono n–1 confronti
" al secondo passo se ne eseguono n–2
" ...
" al n–1-esimo passo si esegue un solo confronto
Il numero di confronti, con cui si può approssimare la complessità
temporale, è dunque
(n–1)%(n–2)%...%2 = n%(n–1)/2
L'algoritmo precedente può essere modificato così:
if (m > n) then { max # m } else { max # n }
mcm # max
while ( ((mcm mod m $ 0) or (mcm mod n $ 0)) and (mcm < m%n) )
do { mcm # mcm + max }
print (mcm)
Nota: questo è un esempio di dipendenza della complessità dalla
dimensione dei dati
Nel caso peggiore saranno quindi esaminati solo min{m,n}
numeri invece che m%n – max{m,n} + 1
49
Esempio (3)
Esempio (3)
Ricerca di un elemento in una sequenza ordinata
In precedenza si sono visti due algoritmi: ricerca sequenziale e ricerca
binaria
Nell'algoritmo di ricerca sequenziale l’operazione principale è il
confronto di ogni elemento della sequenza con quello cercato. È
facile verificare che nel caso peggiore la complessità temporale,
indicata di seguito con Cs, è n, dove n è la lunghezza della sequenza.
Ora possiamo mostrare che l'algoritmo di ricerca binaria è più
efficiente. Il caso peggiore è quello in cui si arriva a una
sottosequenza di un solo elemento, che si verifica se
" l’elemento cercato non è presente
" oppure coincide con il primo o con l’ultimo elemento della
sequenza
50
Anche l’algoritmo di ricerca binaria si basa su una successione di
confronti tra coppie di numeri
Per valutarne la complessità (indicata nel seguito con Cb) si può
osservare che in ogni passo si considera una sequenza di lunghezza
pari alla metà (circa) di quella del passo precedente. Indicando con p
il numero totale di passi (incognito), e quindi di confronti da
eseguire:
" primo passo: sequenza di n elementi
" secondo passo: sequenza di (circa) n/2 elementi
" terzo passo: sequenza di (circa) n/4 = n/22 elementi
" ...
" p-esimo passo: sequenza di (circa) n/2p–1 = 1 elementi
Si ricava immediatamente che p & log2n + 1
51
52
Esempio (3)
Problemi “intrattabili”
La complessità dei due algoritmi è dunque proporzionale a
"
ricerca sequenziale: Cs = n
"
ricerca binaria: Cb & log2n + 1
Poiché n ! log2n + 1 per n " 1, si può concludere che il
secondo algoritmo è più efficiente del primo
Per avere un’idea della differenza, si consideri il numero
di confronti per alcuni valori crescenti di n
"
n = 10: Cs = 10, Cb = 4
"
n = 102: Cs = 102, Cb = 7
"
n = 103: Cs = 103, Cb = 10
"
n = 106: Cs = 106, Cb = 20 ...
La complessità computazionale può essere determinante per
distinguere problemi la cui soluzione è nota solo in teoria, o può
essere ottenuta anche in concreto
Esistono molti problemi di interesse sia teorico che pratico per i quali
l’unico algoritmo noto si basa sulla elencazione di tutte le possibili
soluzioni (metodo della “forza bruta”). Per esempio, questo
approccio è stato seguito nella prima versione dell'algoritmo per il
calcolo del m.c.m. mostrata in precedenza (basata sull'analisi di tutti
i possibili risultati)
Ingenuamente, si può pensare che tali problemi siano risolvibili
usando calcolatori “sufficientemente” veloci
In realtà, spesso si scopre che al crescere della dimensione del
problema la complessità di un algoritmo basato sulla “forza bruta”
supera la capacità di qualsiasi calcolatore esistente (e futuro, almeno
se basato sulla tecnologia attuale)
53
Esempio
54
Esempio
Un esempio molto noto e studiato è il problema del
commesso viaggiatore (traveling salesman problem):
trovare il percorso più breve per visitare n città date,
partendo e tornando in una data città X, e passando una sola
volta per ognuna delle altre
(l’interesse per questo problema non è solo teorico: molti
problemi pratici sono equivalenti a esso)
Metodo della “forza bruta”: elencare tutti i possibili
percorsi che rispettino i vincoli dati, e tra questi cercare
il più breve
Si supponga che ogni città sia collegata direttamente a
ciascuna delle altre: quanti sono i possibili percorsi?
Non è difficile verificare che il loro numero è il seguente:
n! = n%(n–1)%(n–2)%...%2
Per avere un’idea della complessità di un algoritmo basato sulla
forza bruta per il problema del commesso viaggiatore, si
considerino gli esempi seguenti
" 10 città: 10! = 3628800 possibili percorsi
" 20 città: 20! & 1018, cioè un miliardo di miliardi di possibili
percorsi!
" 50 città: 50! & 1081 possibili percorsi...
(nota: il numero stimato di atomi nell’universo è circa
1080...)
Per problemi con queste caratteristiche è necessario un
compromesso tra l'efficienza di un algoritmo e la sua ottimalità
(cioè la garanzia di trovare la soluzione migliore): ci si deve
“accontentare” di un algoritmo che fornisca una soluzione
subottima, purché raggiungibile in un tempo ragionevole
55
56