Informazioni generali Fabrizio d'Amore o Tel.: 06 49918333 o 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 23 aprile 2002 Testo adottato o A. Drozdek. Algoritmi e strutture dati in Java. Apogeo, 2001, Milano Testo consigliato per integrazioni ed approfondimenti o T. Cormen, C. Leiserson, L. Rivest, R. Stein. Introduction to algorithms. 2a ed. The MIT Press, 2001, Cambridge Algoritmi e strutture dati 1 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 Algoritmi e strutture dati 2 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 23 aprile 2002 Algoritmi e strutture dati 3 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 23 aprile 2002 Algoritmi e strutture dati 4 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; 23 aprile 2002 Algoritmi e strutture dati 5 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 23 aprile 2002 Algoritmi e strutture dati 6 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 23 aprile 2002 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 Algoritmi e strutture dati 7 Esempio: Accesso a basi di dati Interrogazione Obiettivo: rispondere rapidamente Interrogazione ... Data base 23 aprile 2002 Data Record Algoritmi e strutture dati 8 Qualità di algoritmi e strutture dati Efficienza o Tempo di esecuzione o Spazio (quantità di memoria) I due aspetti sono interdipendenti 23 aprile 2002 Algoritmi e strutture dati 9 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/Sw In generale: può essere poco rappresentativo 23 aprile 2002 Algoritmi e strutture dati 11 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 23 aprile 2002 Algoritmi e strutture dati 12 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 23 aprile 2002 Algoritmi e strutture dati 13 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 23 aprile 2002 n=5 Algoritmi e strutture dati 14 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 è 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 23 aprile 2002 Algoritmi e strutture dati 15 Esempio/3 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 23 aprile 2002 Algoritmi e strutture dati 16 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 ? 23 aprile 2002 Algoritmi e strutture dati 17 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 23 aprile 2002 Algoritmi e strutture dati 18 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 costanti o 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 23 aprile 2002 Algoritmi e strutture dati 19 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 n0 1 tali che f (n ) cg (n ) per ogni n n0 f (n ) ( g (n )) se esistono 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 ) f(n)=o(g(n)) se lim 0 n g (n ) f (n ) ( g (n ) se g(n)=o(f(n)) 23 aprile 2002 Algoritmi e strutture dati 20 Esempi In base a tali definizioni, l’algoritmo arrayMax 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 D.: Cosa significa O(1)? 2 Algoritmi e strutture dati 21 Analisi asintotica/3 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) 23 aprile 2002 Algoritmi e strutture dati 22 Analisi asintotica/4 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 23 aprile 2002 Algoritmi e strutture dati 23 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] = tmp; } return A; Ordina in modo non-decrescente Inserisce l’elemento A[i] nella posizione corretta nel vettore ordinato A[0,…,i-1] Operazione dominante: una qualunque fra quelle eseguite nel for più interno D.: se la ricerca della posizione di A[i] in A[0,…,i-1] avvenisse con la ricerca binaria? 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( n 1) f ( n) i O( n 2 ) i 0 2 n 1 Ex: 12345 f(n)= n Algoritmi e strutture dati 24 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) Algoritmi e strutture dati 25 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) 23 aprile 2002 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) Algoritmi e strutture dati 26 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 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 23 aprile 2002 Algoritmi e strutture dati 27 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) 23 aprile 2002 Algoritmi e strutture dati 28 Merge Sort 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); } } Costo dell’algoritmo Merge Sort: 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) temp[i1++] = data[i2++]; while (i3 <= last) temp[i1++] = data[i3++]; for (i1 = 0, i2 = first; i2 <= last; data[i2++] = temp[i1++]); } c f (n ) 1 f ( n / 2) f ( n / 2) c2n 23 aprile 2002 n 1 n 2 Algoritmi e strutture dati 29 Equazioni di ricorrenza Tempo di esecuzione di algoritmi ricorsivi descritti con equazioni di ricorrenza. Ex: MergeSort: c f (n ) 1 f ( n / 2) f ( n / 2) c2n n 1 n 2 Semplificazioni o Argomenti non interi o Condizioni al contorno: (1) per n piccolo (1) f (n ) 2f (n / 2) c2n 23 aprile 2002 n 1 n 2 Algoritmi e strutture dati 30 Soluzione di equazioni di ricorrenza Metodo per sostituzione. Si tenta una soluzione e si verifica se soddisfa l’equazione di ricorsione. f (n ) cn log n , c c , c Ex: Merge Sort: 2 f (n ) 1 2 2c (n / 2) log2 (n / 2) c2n cn log2 (n / 2) c2n cn log2 n cn c2n cn log2 n Algoritmi e strutture dati 31 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 dati 32