1

Informazioni generali

Stefano Leonardi Tel.: 06 49918341 Email:

leon@dis.uniroma1.it 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

2

Challenge Algoritmica

http://www.dis.uniroma1.it/~damore/asd/challenge/challenge.htm

I primi 3 classicati ricevono un bonus di 2 punti per l’esame.

3

Algoritmi e Strutture Dati

I.

Progetto ed Analisi di Algoritmi

4

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

5

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 DFSo Algoritmo di Dijkstra per il calcolo del percorso minimo

o Minimo albero ricoprente

6

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;

7

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.

8

Esempio: Routing in Internet

Astrazione usando grafi:

I nodi rappresentano router

Gli archi descrivono i link fisici Costi sugli archi (link) : ritardo, livello di congestione

Obiettivo: determinare “buon” cammino sorg.-

dest.

Protocollo di Routing

A

ED

CB

F

2

2

13

1

1

2

53

5

Cammino “buono”: Di solito significa cammino a costo minimo

Possibili def. alternative

9

Esempio: Accesso a basi di dati

Obiettivo: rispondere rapidamente.

Interrogazione

Data RecordData base

.

.

.

Interrogazione

10

Qualità di algoritmi e strutture dati

Efficienza Tempo di esecuzione Spazio (quantità di memoria)

I due aspetti sono interdipendenti

12

Come misurare l’efficienza?

Perché B gira più velocemente ? Possiamo affermare che B sia “migliore” di A?

Programma A

Problema

Programma B

10 ms

1 ms

Dati

13

Misura dell’efficienza - obiettivi

Indipendenza dall’implementazione

Generale (valida per ogni

input, di qualsiasi dimensione)

Misura indipendente dalla

piattaforma Hw/Sw

14

Modello di costo RAMRandom Access Machine

Assegnazione

Op. aritmetiche

Test

Lettura/Scrittura

A = 10; (costo 1) A = B*C + D – 7; (costo 4)

A == B (costo 1)

System.out.println(A);

(Costo 1)

Macchina che esegue le istruzioni in sequenza.Insieme di operazioni primitive a costo unitario:

15

Modello di costo/2Costo 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

16

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;

7

1

4

1

8

6

3

4

n=3 n=5

17

Perché il modello è accettabile?

A=A+B*C;MUL B,CADD A,B

AB

C

N finito (es. 32 o 64 )

Ogni istruzionecorrisponde a una sequenza finita di istruzioni macchina

Ogni variabile occupauna quantità finita dimemoria e quindi i tempi di accesso a duevariabili sono legati da una costante

18

Vantaggi e svantaggi

Vantaggi: prescinde dalla piattaforma Hw/Sw e dal linguaggio di programmazione

Svantaggi: l’indicazione che si ottiene è qualitativa

19

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

20

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)

21

AlgorithmarrayMax(A, n)currentMax=A[0]; for (i=0; i<n;

i++) if (A[i]>currentMax)

currentMax=A[i];return currentMax;

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

1

4

6

3

8

22

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 costantiMotivo: 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

23

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 tali che, per ogni

se esiste c>0 reale, e una costante intera tali che, per ogni

se f(n)=O(g(n)) e f(n)=o(g(n)) se, per ogni c>0, esiste n0>0 tale

che lim f/g0 per ogni (attenzione alle differenze!!)

se g(n)=o(f(n)) In base a tali definizioni, l’algoritmo

AlgorithmarrayMax ha costo O(n)

10 ≥n

0nn≥)()( ncgnf ≤))(()( ngnf Ω=

)()( ncgnf ≥ 0nn≥10 ≥n

))(()( ngnf Θ= ))(()( ngnf Ω=

0nn≥))(()( ngnf ω=

24

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)

25

Esempi

In base a tali definizioni, l’algoritmo AlgorithmarrayMax ha costo

f(n)= 3n2+10 n = O(n2)

Per c=4 e n0>=10, 3n2+10 n <= 4 n2

Per c1= 1/14, c2= 1/2, n0>=7,

)(nΘ

)(321

)( 22 nnnnf Θ=−=

2

2

22

1 321

ncnnnc ≤−≤

26

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

27

Analisi di Insertion SortAlgorithm 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: 5 4 3 2 1

i=0 5 4 3 2 1 0 confronti

i=1 4 5 3 2 1 1 confronto

i=2 3 4 5 2 1 2 confronti

i=3 2 3 4 5 1 3 confronti

i=4 1 2 3 4 5 4 confronti

Ex: 1 2 3 4 5 f(n)= n

€

f (n) = ii= 0

n−1

∑ =n(n −1) /2 =O(n2)

28

Esempiclass 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)

30

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 inferioreImpera: Sottoproblemi risolti ricorsivamente o direttamente se di dimensione piccola a sufficienzaCombina: Le soluzioni dei sottoproblemi sono combinate per ottenere la soluzione al problema originale

31

Merge Sort A[0...n]

Si suppone n pari per semplicità

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] MergeSort A[n/2...n-1]

Merge

A ordinato

32

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); }}

33

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: ⎩

⎨⎧

>+=

=2),()2/(2

2),1()(

nnnf

nnf

θ

θ

34

L’array [1 8 6 4 10 5 3 2 22]ordinatocon mergesort

35

Mergevoid 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++]);

}

36

Equazioni di ricorrenza

Tempo di esecuzione di algoritmi ricorsivi descritti con equazioni di ricorrenza. Ex: MergeSort:

Semplificazioni: Argomenti non interi.

Condizioni al contorno: per n piccolo

⎩⎨⎧

≥+=

=2 ,)2/(2

1 ,)(

2

1

nncnf

ncnf

⎡ ⎤ ⎣ ⎦⎩⎨⎧

>++=

=2),()2/()2/(

2),1()(

nnnfnf

nnf

θ

θ

)1(θ

37

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: ancnng += log)(

38

Soluzione equazioni di ricorreza per Merge Sort

Base: Ipotesi induttiva: Passo induttivo:

agcf =≤= )1()1( 1)2/()2/( ngnf ≤

ancn

anccnncn

ancncn

ancnnc

ncngnf

+≤++−≤++≤

++≤+≤

log 2log 2)2/(log

2)2/(log)2/(2 )2/(2)(

2

2

2

2

ccc ≤+ 21

39

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)

40

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

41

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>=1Quindi: f(n)<=g(n)=(n+20)log(n+20)

42

Esercizi/2

Mostrare che la soluzione di f(n)=f(n/2)+1 è O(log n)

43

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)

44

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