23 aprile 2002 Algoritmi e strutture dati1 Informazioni generali Fabrizio d'Amore o Tel.: 06...

23 aprile 2002Algoritmi e strutture dati 1

Informazioni generali

Fabrizio d'Amoreo Tel.: 06 49918333o Email:

[email protected]

o URL: www.dis.uniroma1.it/~damore

Ricevimento:o martedì, ore 14-16,

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

Testo adottatoo A. Drozdek. Algoritmi

e strutture dati in Java. Apogeo, 2001, Milano

Testo consigliato per integrazioni ed approfondimentio T. Cormen, C.

Leiserson, L. Rivest, R. Stein. Introduction to algorithms. 2a ed. The MIT Press, 2001, Cambridge

Algoritmi e strutture dati 2

Informazioni generali/2 Sito web del corso (http://www.dis.uniroma1.it/~

damore/asd/, in fase di attivazione) Java tutorial (http://java.sun.com/docs/books/tutorial/

), parte di una più ampia documentazione disponibile al sito che Sun dedica a Java (http://java.sun.com/)

API Java (http://java.sun.com/j2se/1.4/docs/api/index.html, scaricabile a partire da http://java.sun.com/j2se/1.4/download.html/)

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

P. Niemeyer e altri. Learning Java. O'REILLY D. Flanagan. Java in a nutshell. O'REILLY

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









http://java.sun.com/docs/books/tutorial/











http://java.sun.com/





http://java.sun.com/j2se/1.4/docs/api/index.html










http://java.sun.com/j2se/1.4/download.html/










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


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 Programmazione dinamica: introduzione ed

esempi


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;


Nel mondo reale.......

Gli algoritmi intervengono (in modo più o meno nascosto) in molti aspetti

Vari esempio Interneto DBMSo Motori di ricerca…..o Analisi della struttura del Web


Esempio: Routing in Internet

Astrazione usando grafi:

I nodi rappresentano router

Gli archi descrivono i link fisicio 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”:o Di solito significa

cammino a costo minimoo Possibili def. alternative


Esempio: Accesso a basi di dati

Obiettivo: rispondere rapidamente

Interrogazione

Data RecordData base

. .

.Interrogazione


Qualità di algoritmi e strutture dati

Efficienzao Tempo di esecuzioneo Spazio (quantità di memoria)

I due aspetti sono interdipendenti


Misura dell’efficienza - obiettivi

Indipendenza dall’implementazione

Generale (valida per ogni input, di

qualsiasi dimensione)

Misura indipendente dalla

piattaforma Hw/Sw Dipende dalla piattaforma Hw/SwIn generale: può essere poco rappresentativo


Modello di costo RAMRandom Access Machine

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

Assegnazione

Operazioni aritmetiche

Confronto

Lettura/Scrittura


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


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;

7

1

4

1

8

6

3

4

n=3 n=5


Esempio/2

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 che

implementato ogni istruzione è finitoo 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


Esempio/3Problema: 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


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 interio 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 ?


Algorithm arrayMax(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 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+(n-1)+1=4n+3

1

4

6

7

8


Analisi asintotica

Se si considerano tutte le costanti l’analisi può divenire eccessivamente complessa

In realtà interessa conoscere come varia il costo al variare della dimensione dell’input, a meno di costantio 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 trascura i fattori costanti L’analisi asintotica è influenzata dall’operazione

dominante di un algoritmo


Analisi asintotica/2

f(n), g(n) funzioni dagli interi ai reali f(n)=O(g(n)) se esistono c > 0 reale e una costante intera

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

tali che per ogni se f(n)=O(g(n)) e

f(n)=o(g(n)) se

se g(n)=o(f(n))

10 n

0nn )()( ncgnf ))(()( ngnf

)()( ncgnf 0nn 10 n

Θ(g(n))f(n) ))(()( ngnf

)(()( ngnf

0)()(

lim ng

nfn


Esempi

In base a tali definizioni, l’algoritmo arrayMax 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 D.: Cosa significa O(1)?D.: Cosa significa O(1)?



Operazione dominante di un algoritmo:

Un’ operazione di un algoritmo avente costo f(n) si dice dominante se, per ogni n, essa viene eseguita, nel caso peggiore di input di dimensione n, un numero di volte d(n) che soddisfa:

f(n) < a d(n) + b,

per opportune costanti a e b.

Es.: istruzione if (A[i]>currentMax) nell’algoritmo arrayMax(A, n)



Limiti dell’approccio "analisi asintotica del caso peggiore":

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


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;

Ordina in modo non-decrescenteInserisce l’elemento A[i] nella posizione corretta nel vettore ordinato A[0,…,i-1]Operazione dominante: una qualunque fra quelle eseguite nel for più internoD.: se la ricerca della posizione di A[i] in A[0,…,i-1] avvenisse con la ricerca binaria?

Ex: 5 4 3 2 1

i=0 5 4 3 2 1 0 confronti

i=1 4 5 3 2 1 1 confronto




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

)(2

)1()( 2

1

0

nOnn

infn

i


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)


Calcolo delle somme dei prefissi Dato un vettore di interi X[0....n-1], determinare le

componenti del vettore A[0...n-1] in modo tale che A[i]=X[0]+....+X[i-1]. Due algoritmi:

Algorithm prefix1(X, n)for (i=0; i<n; i++) {

A[i]=0;for (j=0; j<=i; j++)

A[i]=A[i]+X[j];}return A;

o O(n2)

Algorithm prefix2(X, n)A[0]=X[0];for (i=1; i<n; i++)

A[i]=A[i-1]+X[i];return A;

o O(n)


Progetto di algoritmi:metodologia "Divide et Impera" Il problema è risolto 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


Merge Sort

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)


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

void merge(int[] data, int first, int last) {

int mid = (first + last) / 2;

int i1 = 0, i2 = first, i3 = mid + 1;

int[] temp = new int[last – first + 1];

while (i2 <= mid && i3 <= last)

if (data[i2] < data[i3])

temp[i1++] = data[i2++];

else temp[i1++] = data[i3++];

while (i2 <= mid)


while (i3 <= last)


for (i1 = 0, i2 = first;

i2 <= last; data[i2++] = temp[i1++]);

}Costo dell’algoritmo Merge Sort:

2 )2/()2/(

1 )(

2

1

nncnfnf

ncnf


Equazioni di ricorrenza

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

Semplificazionio Argomenti non interio Condizioni al contorno: (1) per n piccolo

2 )2/()2/(

1 )(

2

1

nncnfnf

ncnf

2 )2/(2

1 )1()(

2 nncnf

nnf


Soluzione di equazioni di ricorrenza

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

Ex: Merge Sort: 212 , ,log)( cccncnnf

ncn

nccnncn

ncncn

ncnncnf

2

22

22

22

log

log

)2/(log

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


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)

23 aprile 2002 Algoritmi e strutture dati1 Informazioni generali Fabrizio d'Amore o Tel.: 06...

Documents

Transcript of 23 aprile 2002 Algoritmi e strutture dati1 Informazioni generali Fabrizio d'Amore o Tel.: 06...