Informazioni generali
 Stefano Leonardi



Tel.: 06 49918341
Email: [email protected]
URL:
www.dis.uniroma1.it/~leon/didattica/asd
/
 Ricevimento:
Venerdì, ore 14-16, Dip.
Informatica e
Sistemistica, via Salaria
113 II piano, 00198 Roma
 Testo adottato:
 R. Sedgewick, Algoritmi in
Java, Addison Wesley
 Testi consigliati:
 C. Demetrescu, I. Finocchi, G.
Italiano. Algoritmi e
Strutture Dati in Java. Mc
Graw Hill, 2004.
 Cormen, Leiserson, Rivest,
Stein. Introduzione agli
algoritmi. Ed. Jackson libri
 Altro materiale:
 trasparenze del corso
 Libreria di Algoritmi e
Strutture Dati in Java
 documentazione su Java
disponibile in rete
1
Challenge Algoritmica
 http://www.dis.uniroma1.it/~damore/asd/challenge/c
hallenge.htm
 I primi 3 classicati ricevono un bonus di 2 punti per
l’esame.
2
Algoritmi e Strutture Dati
I.
Progetto ed Analisi di Algoritmi
3
Obiettivi
 Applicazioni della progettazione di algoritmi e
strutture dati
 Come si misura l’efficienza delle strutture dati e
degli algoritmi
 Come scegliere gli algoritmi e le strutture dati
adatti a risolvere in modo efficiente un problema
 Implementazione di algoritmi e strutture dati in
Java
4
Argomenti del corso
 Introduzione: efficienza e sua misura.
 Riepilogo sulle principali strutture dati di base:




liste, code, pile, alberi
Code di priorità
Dizionari (Alberi bilanciati, Tabelle Hash, etc..)
Aspetti avanzati degli algoritmi di ordinamento
Grafi
o Rappresentazione e algoritmi di visita
o Applicazioni della DFS
o Algoritmo di Dijkstra per il calcolo del percorso
minimo
o Minimo albero ricoprente
5
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++)
if (A[i] > currentMax)
currentMax = A[i];
return currentMax;
6
Nel mondo reale.......
 Gli algoritmi sono al cuore di innumerevoli
applicazioni informatiche
 Esempi
 Routing nternet
 DBMS
 Analisi e classificazione di documenti/Motori di
ricerca
 Ottimizzazione di progetti
 Etc. Etc. Etc.
7
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

Costi sugli archi (link) :
ritardo, livello di
congestione
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 Cammino “buono”:
 Di solito significa
cammino a costo minimo
 Possibili def. alternative
8
Esempio: Accesso a basi di dati
Interrogazione
Obiettivo: rispondere
rapidamente.
Interrogazione
...
Data base
Data Record
9
Qualità di algoritmi e strutture dati
 Efficienza
 Tempo di esecuzione
 Spazio (quantità di memoria)
I due aspetti sono interdipendenti
10
Come misurare l’efficienza?
10 ms
Programma A
Dati
Problema
Programma B
1 ms
 Perché B gira più velocemente ?
 Possiamo affermare che B sia “migliore” di A?
12
Misura dell’efficienza obiettivi
 Indipendenza dall’implementazione
 Generale (valida per ogni input, di
qualsiasi dimensione)
 Misura indipendente dalla piattaforma
Hw/Sw
13
Modello di costo RAM
Random Access Machine
Macchina che esegue le istruzioni in sequenza.
Insieme di operazioni primitive a costo unitario:
 Assegnazione
 A = 10; (costo 1)
 Op. aritmetiche
 A = B*C + D – 7; (costo 4)
 Test
 A == B (costo 1)
 Lettura/Scrittura
 System.out.println(A); (Costo 1)
14
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
15
Esempio
 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
AlgorithmarrayMax(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
16
Perché il modello è accettabile?
MUL B,C
ADD A,B
A=A+B*C;
B
A
C
Ogni istruzione
corrisponde a una
sequenza finita di
istruzioni macchina
Ogni variabile occupa
una quantità finita di
memoria e quindi i
tempi di accesso a due
variabili sono legati da
una costante
N finito (es. 32 o 64 )
17
Vantaggi e svantaggi
 Vantaggi: prescinde dalla
piattaforma Hw/Sw e dal
linguaggio di programmazione
 Svantaggi: l’indicazione che si
ottiene è qualitativa
18
Quale input considerare?
 La misura deve dipendere dalla dimensione dell’input
(n nel nostro esempio) ma non dal particolare input
considerato
 Possibile alternative:
 Analisi del caso peggiore: si considera il costo di
esecuzione nel caso peggiore
 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
19
Dimensione dell’input
 In generale: No. bit necessari a rappresentare l’input
 Esempio (calcolo del Max. in un array di n interi)
 n interi finiti (< MAXINT)
 log(MAXINT) bit per rappresentare ogni valore.
 Poiché MAXINT è una costante in pratica, il
numero di bit necessari a rappresentare un intero
è costante (es. 32)
 Quindi: dimensione input è proporzionale a n
 A volte le cose possono non essere così ovvie (si
pensi al problema di indovinare un numero proposto
nell’ultima slide)
20
Analisi nel caso peggiore
(esempio)
 Nel caso peggiore l’elemento
massimo è l’ultimo
 In questa ipotesi l’istruzione
currentMax=A[i];
è eseguita n-1 volte.
 Il costo complessivo
dell’algoritmo è allora
1(ass)+1(ass for)+2n(test ed
increm for)+2(n-1)(test e
ass. if)+1(test finale for)
+1(resturn)=4n+3
AlgorithmarrayMax(A, n)
currentMax=A[0];
for (i=0; i<n; i++)
if (A[i]>currentMax)
currentMax=A[i];
return currentMax;
1
4
6
3
8
21
Analisi asintotica
 Se si considerano tutte le costanti l’analisi
può divenire eccessivamente complessa
 Interessa conoscere il costo al variare della
dimensione dell’input, a meno di costanti
 Motivo: il costo è comunque calcolato a
meno di costanti, per le ipotesi fatte circa
il modello
 Un’analisi di questo tipo è detta asintotica
 L’analisi asintotica è influenzata
dall’operazione dominante di un algoritmo
22
Analisi asintotica/2
 f(n), g(n) funzioni dagli interi ai reali
 f(n)=O(g(n)) se esiste c>0 reale, e una costante intera n0  1
tali che, f (n)  cg (n) per ogni n  n
0





f (n)  ( g (n)) se esiste c>0 reale, e una costante intera n0  1
tali che, f ( n)  cg ( n) per ogni n  n0
f (n)  ( g (n)) se f(n)=O(g(n)) e f (n)  ( g (n))
f(n)=o(g(n)) se, per ogni c>0, esiste n0>0 tale che
lim f/g0
per ogni n  n0 (attenzione alle differenze!!)
f (n)   ( g (n)) se g(n)=o(f(n))
In base a tali definizioni, l’algoritmo AlgorithmarrayMax ha costo
O(n)
23
Istruzione dominante
 Un’ operazione o istruzione si dice
dominante se il numero d(n) di volte che
essa è eseguita nel caso peggiore di input di
dimensione n soddisfa:
f(n)<=a d(n) + b,
dove f(n) è la complessità dell’algoritmo nel
caso peggiore ed a e b sono costanti
opportune
 Es.: istruzione if (A[i]>currentMax) in
AlgorithmarrayMax(A, n)
24
Esempi
 In base a tali definizioni, l’algoritmo
AlgorithmarrayMax ha costo
(n)
 f(n)= 3n2+10 n = O(n2)
Per c=4 e n0>=10, 3n2+10 n <= 4 n2
1 2
 f (n)  n  3n  (n 2 )
2
Per c1= 1/14, c2= 1/2, n0>=7,
1 2
c1n  n  3n  c2 n 2
2
2
25
Analisi asintotica/3
Limiti dell’approccio:
 Le costanti nascoste possono essere molto
grandi: un algoritmo con costo 1050n è lineare
ma potrebbe essere poco pratico
 Comportamento nel caso di istanze “piccole”
(es. 3n contro n2)
 Il caso peggiore potrebbe verificarsi
raramente
26
Analisi di Insertion Sort
Algorithm insertionSort(A, n)
for (i=0; i<n; i++) {
tmp=A[i];
for (j=i; j>0 && tmp<A[j-1];
j--)
A[j]=A[j-1];
A[j-1] = tmp;
}
return A;
Inserisce l’elemento A[i]
nella posizione corretta
nel vettore ordinato
A[0,…,i-1]

Ex:
54321
i=0
i=1
i=2
i=3
i=4
54321
45321
34521
23451
12345
0 confronti
1 confronto
2 confronti
3 confronti
4 confronti
n1
f (n)  i n(n 1) /2 O(n 2 )
i 0
Ex:
12345
f(n)= n
27
Esempi
class esercizio {
public void Ex1(int n) {
int a, i;
for (i=0; i<n;i++)
a=i;
}
public void Ex2(int n) {
int a, i;
for (i=0; i<n*n;i++)
a=i;
}
public void Ex3(int n) {
int a, i, j;
for (i=0; i<n;i++)
for (j=0; j<=i;j++)
a=i;
}
}
Valutare la complessità
dei tre metodi
Complessità di Ex3:
1+2+....+n=O(n2)
28
Metodo Divide et Impera
 Il problema è risolto ricorsivamente
attraverso la sua scomposizione in problemi
di taglia inferiore
 Divide: Problema suddiviso in un numero di
sottoproblemi di taglia inferiore
Impera: Sottoproblemi risolti
ricorsivamente o direttamente se di
dimensione piccola a sufficienza
Combina: Le soluzioni dei sottoproblemi
sono combinate per ottenere la soluzione al
problema originale
30
Merge Sort A[0...n]
A[0...n/2-1]
A[n/2...n-1]
Suddividi A in due sottovettori di dim. n/2
A[0...n/2-1]
A[n/2...n-1]
MergeSort A[0...n/2-1]
Si suppone n pari
per semplicità
MergeSort A[n/2...n-1]
Merge
A ordinato
31
Merge Sort/2
void mergesort(int[] A, int first, int last)
{
if (first < last) {
int mid = (first + last) / 2;
mergesort(A, first, mid);
mergesort(A, mid+1, last);
merge(A, first, last);
}
}
32
Merge Sort A[0...n] /3
 Divide: divide gli n elementi da ordinare in due
sottosequenze da n/2 elementi. Costo: O(n)
Impera: ordina ricorsivamente usando il merge
sort le due sottosequenze. Costo: 2f(n/2)
Combina: fonde le due sottosequenze ordinate.
Costo: O(n)
 La ricorsione termina quando si hanno solo due
elementi da ordinare. Costo:O(1)
 Costo dell’algoritmo Merge Sort:
 (1), n  2
f ( n)  
 2 f (n / 2)   ( n), n  2
33
L’array
[1 8 6 4 10 5 3 2 22]
ordinato
con mergesort
34
Merge
void merge(int[] data, int first, int last) {
int mid = (first + last) / 2;
int i1 = 0, i2 = first, i3 = mid + 1;
while (i2 <= mid && i3 <= last)
if (data[i2] <data[i3])
temp[i1++] = data[i2++];
else temp[i1++] = data[i3++];
while (i2 <= mid)
temp[i1++] = data[i2++];
while (i3 <= last)
temp[i1++] = data[i3++];
for (i1 = 0, i2 = first;
i2 <= last; data[i2++] = temp[i1++]);
}
35
Equazioni di ricorrenza
 Tempo di esecuzione di algoritmi ricorsivi descritti
con equazioni di ricorrenza. Ex: MergeSort:
c1, n  1

f (n)  
2 f (n / 2)  c2n, n  2
 Semplificazioni:
 Argomenti non interi.
 (1), n  2
f ( n)  
 f ( n / 2)  f ( n / 2)   (n), n  2

Condizioni al contorno:
 (1) per n piccolo
36
Soluzione di equazioni di ricorrenza
 Metodo per sostituzione. Si tenta una soluzione
g(n) e si verifica se soddisfa l’equazione di
ricorsione.
 Dimostrazione per induzione.
 Base dell’induzione: f(1)≤g(1)
 Ipotesi induttiva: f(n/2) ≤g(n/2)
 Passo induttivo: f(n) ≤g(n)
 Per Merge Sort:
g (n)  cn log n  a
37
Soluzione equazioni di ricorreza
per Merge Sort
 Base:
f (1)  c1  g (1)  a
f ( n / 2)  g ( n / 2)
 Ipotesi induttiva:
 Passo induttivo:
f (n)  2 g (n / 2)  c2 n
 2c(n / 2) log( n / 2)  c2 n  2a
 cn log( n / 2)  c2 n  2a
 cn log n  cn  c2 n  2a
 cn log n  a
c1  c2  c
38
Esercizi/1
1.
Mostrare che la soluzione di
f(n)=f(n/2)+f(n/2)+1 è O(n)
2. Mostrare che la soluzione di
f(n)=2f(n/2+10)+n è O(nlog n)
39
f(n)=f(n/2)+f(n/2)+1
 Ipotesi: f(n)<=g(n)=cn
f(n/2)+f(n/2)+1<=cn/2 + cn/2 +1 = cn +1 NO!
 Ipotesi: f(n)<=g(n)=cn-b
f(n/2)+f(n/2)+1<=cn/2-b + cn/2-b +1
= cn -2b+1  b>=1
40
f(n)=2f(n/2+10)+n
 Rinominiamo n+20= m. Quindi:
f(m)=2f(m/2)+m-20
 Ipotesi: f(m)<=g(m)=cmlogm
f(m)<=2c (m/2) (log m-1)+m-20<=cm log m
se c>=1
Quindi: f(n)<=g(n)=(n+20)log(n+20)
41
Esercizi/2
 Mostrare che la soluzione di
f(n)=f(n/2)+1 è O(log n)
42
Esercizi/3
 Si consideri il problema della ricerca in un
vettore di interi: dato il vettore A[1..n] ed
un intero k, si vuole stabilire se k sia tra
gli elementi di A o meno
 Considerato il classico algoritmo basato
sulla ricerca binaria, si mostri che esso
ha complessità O(log n)
43
Esercizi/4

Si consideri il problema di “indovinare” un numero
intero nel numero minimo di tentativi: ad ogni
tentativo, l’algoritmo propone un valore ad un
oracolo, che conosce il numero da indovinare.
L’oracolo risponde dicendo se il numero proposto
sia maggiore, minore o uguale a quello da
indovinare (nell’ ultimo caso il gioco termina).
 Si proponga un algoritmo efficiente e se ne
esprima la complessità temporale in funzione
del generico numero N da indovinare
44