Corso di Informatica
(Programmazione)
Lezione 3 (22 ottobre 2008)
Problemi e algoritmi
1
Il problema
Un problema P viene definito dai suoi
DATI IN INGRESSO e dalla sua
SOLUZIONE
Esempio
P: somma di due interi
DATI IN INGRESSO: due interi a e b
SOLUZIONE: somma s=a+b
2
Il problema
Istanza di un problema P
 realizzazione di particolari dati in
ingresso
Esempio
la coppia (2,3) è un’istanza del
problema P dell’esempio precedente a
cui corrisponde la soluzione 5
(2,3)  5
3
Il problema
Si definisca:
IP insieme delle istanze di P
SP insieme delle soluzioni di P
4
Il problema
Esempio per P=“somma di due interi”
(2,3)
(100,50)
SP
(4,1)
IP
5
150
5
Il problema
Dato un problema P, esiste una
relazione rP che lega gli elementi in IP
(istanze) agli elementi in SP (soluzioni)
 rP: IP -> SP
e che rappresenta quindi il problema P.
Nel caso di P=“somma di due interi” si ha che rP è
la funzione univoca:
s=rP(a,b)=a+b
6
Tipi di problemi
Decisione  SP={1,0} o SP={SI’, NO}
Esempio
P: problema del commesso
viaggiatore
INPUT: N città con le relative
distanze e un valore prefissato b
OUTPUT: esiste un percorso che
passa una sola volta per tutte le
città e che ha una lunghezza totale
minore di b?
7
Tipi di problemi
Ricerca 
Esempio
P: problema del commesso
viaggiatore (problema di ricerca)
INPUT: N città con le relative
distanze e un valore prefissato b
OUTPUT: trovare tutti i percorsi
che passano una sola volta per tutte
le città e che hanno una lunghezza
totale minore di b
8
Tipi di problemi
Enumerazione 
Esempio
P: problema del commesso
viaggiatore (problema di enumarazione)
INPUT: N città con le relative
distanze e un valore prefissato b
OUTPUT: contare tutti i percorsi
che passano una sola volta per tutte
le città e che hanno una lunghezza
totale minore di b
9
Tipi di problemi
Ottimizzazione 
Esempio
P: problema del commesso
viaggiatore (problema di ottimizzazione)
INPUT: N città con le relative
Questo è un
problema di minimo.
distanze
Da notare che
le soluzioni per una OUTPUT: trovare il percorso
data istanza
possono essere più che passa una sola volta per tutte
di una (esistono
le città e che ha minima lunghezza
cioè più percorsi
totale
che hanno una
lunghezza totale
minima)
10
L’algoritmo
Cos’è un algoritmo?
In Informatica è un metodo per
risolvere un problema e può
essere implementato, ovvero può
essere tradotto in un programma
attraverso un linguaggio di
programmazione
Un algoritmo esiste indipendentemente
dalla macchina che lo esegue!
11
L’algoritmo
Cos’è un algoritmo?
E’ una procedura, costituita da una
sequenza finita di operazioni
elementari, che trasforma un set
di dati iniziali (INPUT) in un set
di dati finali (OUTPUT)
12
L’algoritmo
Esempio di problema da risolvere
tramite un algoritmo
P: somma di 5 numeri interi
DATI IN INGRESSO: un set B={b1,
b2, b3, b4, b5} di 5 interi
SOLUZIONE: somma p=b1+b2+b3+b4+b5
13
L’algoritmo
Esempio
Algoritmo A:
B={b1, b2, b3, b4, b5}
1:
2:
3:
4:
5:
6:
7:
p=0
p=p+b1
p=p+b2
p=p+b3
p=p+b4
p=p+b5
stampo p
p
14
L’algoritmo
Un algoritmo in genere viene
rappresentato in pseudocodice, cioè in
un linguaggio, simile ad un linguaggio di
programmazione (codice), che però non
è direttamente compilabile o
interpretabile su un calcolatore. Spesso
lo pseudocodice è definito da una
sintassi Pascal-like o C-like
15
L’algoritmo
L’algoritmo precedente può essere riscritto in
pseudocodice Pascal-like:
Procedura Somma_interi(b1, b2, b3, b4, b5)
begin
p:=0
p:=p+b1
p:=p+b2
p:=p+b3
p:=p+b4
p:=p+b5
stampa p
end
16
L’algoritmo
Un algoritmo è composto da istruzioni
Istruzione  descrizione di una certa
operazione (l’algoritmo precedente è
composto da 7 istruzioni)
L’esecuzione di una certa istruzione è il
passo
17
L’algoritmo
Esempio
Procedura Raddoppia_Pari(a)
begin
SE a è pari{
1:
b:=a*2
2:
stampa b
}
La procedura è composta
altrimenti{
da 3 istruzioni e compie
3:
stampa a
2 passi se a in input
}
è pari, mentre
end
ne compie uno solo
se a in input è dispari
18
L’algoritmo
Un algoritmo deve:
 essere composto da un numero finito
di istruzioni e terminare in un numero
finito di passi, ovvero deve essere
finito
 essere realizzabile
 gestire tutte le situazioni che si
possono verificare durante la sua
esecuzione, ovvero deve essere
completo
19
L’algoritmo
Un algoritmo deve:
 essere riproducibile, ovvero gli stessi
dati in input devono dare in esecuzioni
successive gli stessi dati in output
 essere corretto
 essere efficiente
Vedere il seguito…
20
Correttezza di un algoritmo
Dato un algoritmo A, si
definisca:
IA insieme degli input di A
OA insieme degli output di A
21
Correttezza di un algoritmo
Dato un algoritmo A, esiste una
relazione rA che lega gli elementi in IA
(input) agli elementi in OA (output)
 rA: IA -> OA
e che rappresenta quindi l’algoritmo A.
Nel caso di A=“somma di 5 interi” si ha che rA è la
funzione univoca:
p=rA(b1,b2,b3,b4,b5)=b1+b2+b3+b4+b5
22
Correttezza di un algoritmo
Un algoritmo A rappresentato da una
relazione rA: IA->OA si definisce corretto
per un problema P, rappresentato da una
relazione rP: IP->SP, se e solo se rA
“coincide” con rP. Cioè se ad ogni input i in
IA corrisponde un output o che è anche la
soluzione di P per l’ingresso fornito da i.
Attenzione al “coincide” che non è in senso stretto!
Per i problemi di ottimizzazione ad esempio basta che l’algoritmo trovi
anche solo una delle possibili soluzioni ottime (di minimo o di massimo)
23
Efficienza di un algoritmo
L’efficienza di un algoritmo è misurata in
termini del tempo di computazione e dello
spazio di memoria che userebbe se venisse
implementato ed eseguito su di una macchina
di riferimento ipotetica.
Un algoritmo è tanto più efficiente quanto
meno tempo e spazio spreca.
La misura di efficienza (in tempo e spazio)
viene in genere espressa in funzione della
dimensione n dell’input
24
Efficienza di un algoritmo
Esempio di tempo T di computazione funzione
della dimensione n dell’input
Procedura Somma_interi(b1, b2, b3, b4, b5)
begin
La dimensione n dell’input è il numero di
p:=0
interi b1, b2, b3, b4, b5 (n=5) che è costante
per ogni input possibile.
p:=p+b1
Immaginando di implementare ed eseguire
p:=p+b2
la procedura su una macchina di riferimento
p:=p+b3
(modello) che esegue ogni istruzione
in un tempo unitario, si ha che il tempo di
p:=p+b4
computazione T per ogni input è:
p:=p+b5
T=n+2  le n=5 istruzioni di assegnamento
p:=p+bi, l’istruzione p:=0 e l’istruzione
stampa p
“stampo p”. Di conseguenza si ha che T è
end
costante per ogni input.
n=5  costante sull’intero insieme IA
25
Efficienza di un algoritmo
Esempio di tempo T di computazione funzione
della dimensione n dell’input
Procedura Stampa(a)
begin
Per a volte
stampa “ciao” e vai a capo
end
La dimensione n dell’input è l’intero a (n=a) che non è costante per ogni input.
Immaginando di implementare ed eseguire la procedura su una macchina
di riferimento (modello) che esegue ogni istruzione in un tempo unitario,
si ha che il tempo di computazione T per un input a è: T=n=a  viene eseguita a volte
l’istruzione di stampa. Di conseguenza si ha che T è funzione lineare di a.
E’ evidente che non ci sono due input che hanno la stessa dimensione
n=a  non costante sull’insieme IA
26
Efficienza di un algoritmo
Esempio di dimensione n dell’input
Procedura Commesso_viaggiatore(insieme_di_città)
begin
…
end
La dimensione n dell’input è il numero N delle città  n=N.
Il tempo di computazione dell’algoritmo sarà funzione di N.
In questo caso due input diversi possono anche avere la stessa
dimensione. Ad esempio i1={Roma, Napoli Pisa} e
i2={Milano, Genova, Venezia} che hanno n=N=3
n=N  non costante sull’insieme IA
27
Efficienza di un algoritmo
Indicando con TA(x) il tempo che l’algoritmo
A impiega a processare l’input x
appartenente a IA, si definisce complessità
in tempo nel caso peggiore la grandezza:
TAP(n)=max{TA(x) tale che |x|=n}
cioè per ogni valore di n, TAP(n) è il massimo
tra i tempi di computazione degli input x che
hanno dimensione n  |x|=n
28
Efficienza di un algoritmo
Indicando con TA(x) il tempo che l’algoritmo A
impiega a processare l’input x appartenente a
IA, si definisce complessità in tempo nel
caso medio la grandezza:
TAM
 n 
 T  x
x n
A
In
cioè per ogni valore di n, TAM(n) è la media dei
tempi di computazione degli input x che hanno
dimensione n  |x|=n e |In| numero degli
input di dimensione n
29
Efficienza di un algoritmo
In genere, dato un algoritmo A si vuole
vedere cosa succede alle sue funzioni TAP(n)
e a TAM(n) al tendere di n all’infinito. Si
vuole cioè indagare il comportamento
asintotico di A.
Analogo discorso può essere fatto per
misurare lo spazio di memoria che
l’algoritmo usa su un’ipotetica macchina
modello.
30
Efficienza di un algoritmo
Gli algoritmi efficienti sono quelli per cui la
funzione TA(n) (TAP o TAM) è un polinomio di
grado k>=0:
TA(n)=a0+a1n1+a2n2+…+aknk
Per k=0  tempo costante
Per k=1  tempo lineare
All’aumentare di k l’algoritmo A diventa sempre
più oneroso dal punto di vista computazionale
31
Efficienza di un algoritmo
Tempi di calcolo su input di varie dimensioni (prima riga) per sei
algoritmi che hanno una complessità pari a n (lineare), nlog2n
(logaritmica), n2 (polinomiale), n3 (polinomiale), 2n (esponenziale), 3n
(esponenziale)
Si supponga che la macchina di riferimento esegua un’operazione
elementare (istruzione) in 1 microsecondo (10-6 secondi).
Notazioni: ms (microsecondi), ms (millisecondi), s (secondi), mn (minuti), h
(ore), g (giorni), a (anni), c (secoli)
Da: A. Bertoni e M. Goldwurm, Progetto e Analisi di Algoritmi, Rapporto Interno n. 230-98,
Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano
32
Problematiche degli algoritmi
SINTESI
 dato un problema P, progettare
(disegnare) un algoritmo A che risolva P
ANALISI
 dato un algoritmo A per un problema P,
dimostrare che A risolve P (è corretto) e
valutare le risorse (tempo e spazio)
utilizzate da A
33