Problemi e algoritmi
Il “che cosa” e il “come”
Il “che cosa” ed il “come”
• Problema: descrive “che cosa” si deve calcolare
• Specifica (di un algoritmo): descrive “che cosa” calcola un algoritmo
• Algoritmo: descrive “come” effettuare un calcolo
NOTA: in pratica, quando si deve realizzare
un’applicazione software puo’ essere non
banale identificare quali sono i problemi.
Il “che cosa” ed il “come”
Problema:
1. dati x, y, z, … così e così
istanza
Il “che cosa” ed il “come”
Problema:
1. dati x, y, z, … così e così 2. trovare u, v, w .. tali che …
criterio per
riconoscere
la risposta
Il “che cosa” ed il “come”
Esempio (Massimo comun divisore: MCD).
Dati due interi positivi non entrambi nulli
n ed m, determinare un intero positivo k tale che:
1. k divide sia n che m;
2. per ogni divisore comune h di n ed m, h divide k.
istanza
criterio per riconoscere
la risposta
Multipli e Divisori
Sugli interi sono definite le relazioni:
• n è multiplo di m se esiste k ≥ 1 tale che
• m divide n se n è multiplo di m: m|n
Proprieta’. m|n e n|m implica n = m.
Dim.
mk n =
| 1
| ⇒ = ⇒ = =
=
⇒
=
⇒ n nhk h k
nh m
m n
mk n
n
m
Il “che cosa” ed il “come”
Esempio (Ordinamento: Sorting)
Dato un intero positivo n ed una sequenza
di n elementi di un insieme A linearmente ordinato, trovare una permutazione π di ordine n tale che:
A a
a 1 ,..., n ∈
) ( )
2 ( )
1
(
a a
na π ≤ π ≤ L ≤ π istanza
criterio per
riconoscere
la risposta
Ordini lineari e non-lineari
• Un ordine parziale su un insieme A è una relazione binaria riflessiva, simmetrica e transitiva.
{ } a, b
{ } a { } b { } { } { } { } a ⊄ b ∅ , b ⊄ a
< L
<
< 1 2 0
Esempio di ordine lineare:
elementi tutti confrontabili
Esempio di ordine non lineare:
esistono elementi non
confrontabili
Il “che cosa” ed il “come”
Esempio (Cammino minimo)
Date una mappa stradale che riporti località, strade e lunghezze dei percorsi,
ed una coppia di località raggiungibili l’una dall’altra,
trovare un percorso che renda minima la lunghezza.
criterio per riconoscere la risposta
istanza
Il “che cosa” ed il “come”
Quindi un problema è una relazione (binaria) R, ossia una collezione di coppie
Le cui istanze sono in
∈ R risposta
istanza,
R è sempre univoca?
{ x x y R y }
R
dom ( ) = : , ∈ per qualche
Univocità
• è univoca (o funzionale) se per ogni
B A
R ⊆ ×
B b
b A
a ∈ , 1 , 2 ∈
2 1
2 1 , ,
, b a b R b b
a ∈ ⇒ =
R
a b
c
La relazione R è:
• MCD: univoca, perché se k | h e h | k, allora h = k.
• Sorting: univoca solo se non ci sono ripetizioni. Ci sono due risposte per l’istanza
7, 5, 22, 5:
{ 1 a 3 , 2 a 1 , 3 a 4 , 4 a 2 } { e 1 a 3 , 2 a 2 , 3 a 4 , 4 a 1 }
• Cammini minimi: in generale non univoca. Ci possono essere più percorsi di lunghezza minima.
anche se producono lo stesso 5, 5, 7, 22.
Il “che cosa” ed il “come”
• Algoritmo: è una descrizione che illustra
passo passo, ovvero in modo da poter essere (e)seguita meccanicamente, “come”
ottenere un risultato (output) date certe
informazioni di partenza (input).
Il “che cosa” ed il “come”
• Un algoritmo è deterministico: se eseguito più volte sullo stesso input, fornisce sempre lo stesso output.
Dunque ad ogni algoritmo possiamo associare una funzione di input-output:
output input
F ( ) =
Il “che cosa” ed il “come”
• Un algoritmo risolve un problema R se la sua funzione di input-output F associa una risposta ad ogni istanza di R:
F sceglie una risposta per ogni istanza (ma le risposte possono essere più d’una se R
non è univoca).
) ( ogni
per
) (
, F x R x dom R
x ∈ ∈
La codifica di un algoritmo
• Un algoritmo e’ descrivibile in piu’ modi:
1. In una lingua naturale: “dati n ed m, siano a = max (n, m) e b = min (n, m); dividi
progressivamente a per b, e se il resto è nullo ritorna b, altrimenti poni a = b, b = a mod b e calcola il nuovo resto.”
Pro: per capire mi basta conoscere l’italiano
Contro: potenzialmente
ambiguo, non mostra
la sua struttura
La codifica di un algoritmo
Un algoritmo e’ descrivibile in piu’ modi:
2. Con diagrammi di flusso: Pro: intuitivo e preciso
Contro: non strutturato, non adatto per la ricursione
a ← max (n, m), b ← min (n, m)
b = 0
r = 0 r ← a mod b
a ← b, b ← r
return a
return b
+ +
−
−
Si usava
un tempo
La codifica di un algoritmo
• Un algoritmo e’ descrivibile in piu’ modi:
3. Usando un linguaggio di programmazione:
int MCD (int n, int m) { int a, b, r;
if (n > m) {a = n, b = m;};
else {a = m, b = n;}
if (b == 0) return a;
r = a % b;
while (r != 0)
{ a = b; b = r; r = a % b;}
return b;
}
Contro: criptico; molti dettagli oscurano la
struttura dell’algoritmo;
dipende dalla scelta del linguaggio
Pro: lo posso
provare su un
computer
La codifica di un algoritmo
• Un algoritmo e’ descrivibile in piu’ modi:
4. Con uno pseudocodice:
MCD (n, m) a ← max (n, m) b ← min (n, m)
if b = 0 then return a else r ← a mod b
while r ≠ 0 do a ← b b ← r
r ← a mod b return b
