Algoritmi e strutture dati Definizioni
 Struttura dati: organizzazione sistematica dei dati e del
loro accesso
 Algoritmo: procedura suddivisa in passi che, eseguiti in
sequenza, consentono di eseguire un compito in tempo finito
(?)
 Esempio: Max. di un vettore di n elementi
Algorithm arrayMax(A, n)
currentMax=A[0];
for (i=0; i<n; i++) // inziare da i = 1?
if (A[i]>currentMax)
currentMax=A[i];
return currentMax;
Introduzione
1
Nel mondo reale.......
 Gli algoritmi intervengono (in modo più o meno
nascosto) in molti aspetti
 Vari esempi
o Internet
o DBMS
o Motori di ricerca…..
o Analisi della struttura del Web
Introduzione
2
Esempio: Routing in Internet
Protocollo di Routing
5
Obiettivo: determinare
“buon” cammino sorg.-dest
Astrazione usando grafi:
 I nodi rappresentano
router
 Gli archi descrivono i
link fisici
o
Costi sugli archi (link) :
ritardo, costo in €,
livello di congestione
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 Cammino “buono”:
o Di solito significa
cammino a costo minimo
o Possibili def. alternative
Introduzione
3
Esempio: Accesso a basi di dati
Interrogazione
Obiettivo: rispondere
rapidamente
Interrogazione
...
Data base
Data Record
Introduzione
4
Qualità di algoritmi e strutture dati
 Efficienza
o Tempo di esecuzione
o Spazio (quantità di memoria)
I due aspetti sono interdipendenti
Introduzione
5
Misura dell’efficienza obiettivi
 Indipendenza dall’implementazione
 Generale (valida per ogni input, di
qualsiasi dimensione)
 Misura indipendente dalla piattaforma
Hw/Sw
In generale: una misura dipendente dalla piattaforma
hw/sw è poco rappresentativa
Introduzione
7
Modello di costo RAM
Random Access Machine
Macchina che esegue le istruzioni in sequenza.
Insieme di operazioni primitive a costo unitario:
 Assegnazione
 Operazioni aritmetiche
 Confronto
 Lettura/Scrittura
Introduzione
8
Modello di costo/2
Costo di operazioni complesse:
 Ciclo: somma costo test di fino ciclo e costo corpo del
ciclo
 if…then…else: costo test più costo blocco istruzioni
che segue then o else (a seconda del caso)
 Attivazione di un metodo: somma dei costi di tutte le
istruzioni presenti nel metodo
Costo: somma di tutti i costi
Introduzione
9
Esempio/1
 Nel primo caso (vett. di 3
elementi) si ha costo 1
(ass.)+1 (ass. nel for) + 6
(test e incr. nel for) + 1
(test finale for) + 3 (test
if) + 1 (istruz. return) = 13
 Nel secondo caso si ha 1
(ass.) + 1 (ass. nel for) + 10
(test e incr. nel for) + 1
(test finale for) + 5 (test
if) + 1 (istr. ass. nell’if) + 1
(istruz. return) = 20
Algorithm arrayMax(A, n)
currentMax=A[0];
for (i=0; i<n; i++)
if (A[i]>currentMax)
currentMax=A[i];
return currentMax;
1
8
7
6
1
3
4
4
n=3
n=5
Introduzione
10
Modello di costo/3
Perché tale modello è accettabile?
 Il costo di istruzione è sempre valutato a meno di un
fattore costante (eventualmente grande) perché
o Il numero di operazioni elementari per ogni
istruzione è finito
o Ogni variabile occupa una quantità finita di
memoria e quindi i tempi di accesso a due variabili
diverse sono comunque legati da una costante
Vantaggi: prescinde dalla piattaforma Hw/Sw e dal
linguaggio di programmazione
Svantaggi: l’indicazione che si ottiene è qualitativa
Introduzione
11
Modello di costo/4
Problema: i risultati dipendono dal particolare input, anche per lo
stesso valore di n
 Si vuole una misura che dipenda dalla dimensione dell’input (n
nel nostro esempio) ma non dal particolare input considerato
 Possibile alternative:
o Analisi del caso peggiore (worst case): si considera il costo
di esecuzione nel caso peggiore (l'analisi del caso migliore è
in generale poco interessante)
o Analisi del caso medio: si considera il costo medio
dell’algoritmo rispetto ad una distribuzione dell’input
(richiede la conoscenza della distribuzione)
 In ogni caso occorre definire la dimensione dell’input
Nel seguito si considera l’analisi nel caso peggiore
Introduzione
12
Dimensione dell’input
 Per ogni problema va indicata la dimensione dell’input perché è
rispetto ad essa che si calcola il costo degli algoritmi
 Dipende dall’input, es.:
o Nr. componenti per il problema di ordinare un vettore di
interi
o Nr. di nodi e numero di archi per problemi su grafi
 La scelta deve essere ragionevole. Nei casi dubbi una misura
ragionevole è il numero di bit necessari a rappresentare l’input
 Esempio: se si considera il problema di determinare la
scomposizione in fattori primi di un numero intero allora la
dimensione dell’input è il numero di bit necessario a
rappresentare un intero.
D.: numero di bit necessario a rappresentare un intero < N ?
Introduzione
13
Analisi nel caso peggiore
(esempio)
 Nel caso peggiore gli
elementi sono ordinati in
maniera crescente
 In questa ipotesi l’istruzione
currentMax=A[i];
è eseguita n-1 volte.
 Il costo complessivo
dell’algoritmo è allora
(ragionando come nei casi
precedenti) 1+1+2n+1+n+(n1)+1=4n+3
Algorithm arrayMax(A, n)
currentMax=A[0];
for (i=0; i<n; i++)
if (A[i]>currentMax)
currentMax=A[i];
return currentMax;
1
4
6
7
8
Introduzione
14