1

Informazioni generali

Luca Becchetti• Tel.: 06 49918335• Email:

becchett@dis.uniroma1.it

• URL: www.dis.uniroma1.it/~becchett

Ricevimento:• Latina: martedì e

giovedì, ore 9.00-9.45• Roma: mercoledì, ore

10-12, Dip. Informatica e Sistemistica, via Salaria 113 II piano, 00198 Roma

Testo adottato: • R. Sedgewick, Algoritmi

in Java, Addison Wesley• Ingegneria 2000, via

della polveriera 15 (S. Pietro in vincoli), tel. 06 4744169/06 4746609

Testi consigliati:• T. Cormen e altri.

Introduzione agli algoritmi. Ed. Jackson libri

Altro materiale: documentazione su Java disponibile in rete

2

Informazioni generali/2 Java tutorial:

http://java.sun.com/docs/books/tutorial/ Il Java tutorial è parte di una più ampia

documentazione disponibile al sito Sun API Java: la documentazione è disponibile al sito:

http://java.sun.com/products/jdk/1.2/docs/api/index.html e può essere scaricata a partire da: http://java.sun.com/products/jdk/1.2/docs/

J. Bishop: Java gently – Corso introduttivo. Addison - Wesley

P. Niemeyer e altri. Learning Java. O'REILLY

D. Flanagan. Java in a nutshell. O'REILLY

3

Obiettivi

A cosa serve la 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 Aspetti avanzati degli algoritmi di ordinamento Grafi

Rappresentazione e algoritmi di visita Algoritmo di Dijkstra per il calcolo del percorso minimo 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 intervengono (in modo più o meno nascosto) in molti aspetti

Esempi• Internet• DBMS • Motori di ricerca• Struttura del Web• Analisi di documenti

7

Esempio: Routing in Internet

Astrazione usando grafi:

I nodi rappresentano router

Gli archi descrivono i link fisici Costi sugli archi

(link) : ritardo, costo in € 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

8

Esempio: Accesso a basi di dati

Obiettivo: rispondere rapidamente.

Interrogazione

Data RecordData base

. .

.

Interrogazione

9

Qualità di algoritmi e strutture dati

Efficienza• Tempo di esecuzione• Spazio (quantità di memoria)

I due aspetti sono interdipendenti

11

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

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

14

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

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;

7

1

4

1

8

6

3

4

n=3 n=5

16

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

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 (v.

problema nell’ultima slide)

20

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+1+(n-1)+1+2(n-1)+1=4n+1

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 tali che f(n)≤cg(n) per ogni n>n0

f(n)=(g(n)) se esiste c>0 reale, e una costante intera n0 tali che, f(n)>c g(n) per ogni n>n0

Si osservi che f(n)=O(g(n)) implica g(n)=(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

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 ≤−≤

25

Analisi asintotica/3

Limiti dell’analisi asintotica: 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 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] = 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

)(2

)1()( 2

1

0

nOnn

infn

i

=−==∑−

=

27

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)

29

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

30

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

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:

⎩⎨⎧

>+=

=2),()2/(2

2),1()(

nnnf

nnf

θ

θ

33

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

34

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

}

35

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(θ

36

Soluzione di equazioni di ricorrenza

Metodo per sostituzione. Si tenta una soluzione e si verifica se soddisfa l’equazione di ricorsione.

Ex: Merge Sort: 21,,log)( cccaancnnf ≥≥+≤

ancn

anccnncn

ancncn

ancnncnf

+≤++−≤++≤

++≤

log log

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

2

2

2

aancncf =+≤= log)1( 1

37

Esercizi

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

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

38

Esercizi/2

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)

39

Esercizi/3

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