Asd 01 Algoritmi E Strutture Dati

Prof. Pier Luca Lanzi

Algoritmi e Strutture DatiIntroduzione


Riferimenti

Questo materiale è tratto dalle trasparenzedel corso Introduction to Algorithms (2005-fall-6046) tenuto dal Prof. Leisersonall’MIT (http://people.csail.mit.edu/cel/)

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, Second Edition, The MIT Press, Cambridge, Massachusetts London, EnglandMcGraw-Hill Book Company

Queste trasparenze sono disponibili sui sitihttp://webspace.elet.polimi.it/lanzihttp://www.slideshare.net/pierluca.lanzi

2

http://webspace.elet.polimi.it/lanzi

Algoritmi & strutture dati


Cos’è un algoritmo?

“Sequenza di passi, definiti con precisione, che portano allarealizzazione di un compito”

La sequenza di passi deve essere finita e deve portare ad un risultato

Le istruzioni devono essere eseguibili materialmente e devono essere espresse in modo non ambiguo

Un algoritmo deve essere comprensibileal suo esecutore, corretto, ed efficiente

Forniscono descrizione astratta di un metodo (procedimento) per giungere alla soluzione di un dato problema

4


Un po’ di storia

Al-Khwārizmī, astronomo e matematicoPersiano, nell’825 scrive il trattato“On Calculation with Hindu Numerals”

Tradotto in latino nel XII secolo, come “Algoritmi de numero Indorum”

“Algoritmi” era la traduzione del nomedell’autore (Al-Khwārizmī) ma il termineè stato frainteso come il plurare Latino algorismus

Nel 1240, il termine è usato in nel manuale “Carmen de Algorismo” di Alexandre de Villedieu.

Francobollo emesso il 6 Settembre 1983 dall’Unione Sovietica per commemorare il “compleanno di

Al-Khwārizmī's (780-850)

5


Quali sono gli obiettivi del corso?

Analisi degli algoritmi noti per il design di algoritmi nuovi

Analisi degli algoritmi

Performance (velocità)

Utilizzo delle risorse (memoria e comunicazione)

Ci sono molti altri aspetti (non trattati qui):

Correttezza, robustezza, mantenibilità

Modularità, sicurezza, facilità d’uso

6

Analisi e design di algoritmi


7

Perchè algoritmi e performance?

La performance spesso determina

il confine tra quello che è possibile e

quello che non è possibile fare

L’analisi degli algoritmi ci aiuta

a capire il concetto di scalabilità


Scalabilità?

Prof. Lanzi corre i 100m in 12s In quanto corre la maratona?

8


Esempio: Ricerca di un elemento

Dato un elenco contenente n oggetti, cercarese un oggetto x è presente

L’elenco non è ordinato

Caso migliore? Quello che cerco è il primo

Caso peggiore? Ho n elementi e quello che cerco è l’ultimo

Caso medio? Circa n/2

9

x? x? x? x? x? x!


Codifica in C++

bool linear_find(int v[], int n, int x)

{

int i;

for (i=0; i<n && v[i]!=x; i++);

if (i==n)

return false;

else return true;

}

10


Esempio: Ricerca di un elemento

Supponiamo ora che l’elenco sia ordinatoalfabeticamente

Esempio: l’elenco del telefono o un dizionario

Caso migliore? Quello che cerco è il primo

Caso peggiore?

Caso medio?

11

A B C ... N ... ... ... Z

Rossi?


Codifica in C++

bool binary_find(int v[], int n, int x)

{

int l = -1;

int r = n; // l, r are beyond array bounds

while (l+1 != r) { // Stop when l, r meet

int i = (l+r)/2; // Check middle

if (x < array[i]) r = i; // Left half

if (x == array[i]) return true; // Found it

if (x > array[i]) l = i; // Right half

}

return false; // Search value not in array

}

12


13

E le strutture dati?

Gli algoritmi lavorano su dati che vengono

organizzati secondo una certa struttura

Se la struttura è efficiente

allora gli algoritmi sono più efficienti


14

La ricerca binaria è sempre più efficiente?


Struttura Dati?

Organizzazione o collezione di elementi (o record) su cui siapossibile processare le informazioni, effettuare una ricerca, ecc.

La scelta della struttura dati e dell’algoritmo adeguati puòridurre i tempi di esecuzione da giorni a pochi secondi. Lo stesso vale per altre risorse.

Efficienza: una soluzione è efficiente se risolve un problemadato entro i vincoli di memoria e tempo di esecuzionerichiesti.


Quale Struttura Dati?

Tre semplici passi

Analizzare il problema per determinare i vincoli sulle risorseche è necessario soddisfare (Memoria? Velocità? Entrambi?)

Determinare quali sono le operazioni che devono esseresupportate quantificando le risorse per ogni operazione

Selezionare la struttura dati che meglio soddisfa i requisiti

Alcune domande,

I dati sono inseriti tutti all’inizio o mano a mano?

È possibile cancellare degli elementi?

I dati sono processati sequenzialmente o in ordinequalunque?


17

Ogni struttura dati ha costi/benefici

Raramente c’è una soluzione

che va bene in tutte le situazioni

Costo per memorizzare un elemento,

tempo di esecuzione per le operazioni di base,

effort per l’implementazione

Prof. Pier Luca LanziL1.18

Ordinamento

Input: sequenza a1, a2, …, an di numeri.

Output: permutazione a'1, a'2, …, a'n che soddisfi

la relazione a'1 a'2… a'n

Esempio:

Input: 8 2 4 9 3 6

Output: 2 3 4 6 8 9


Insertion Sort

INSERTION-SORT (A, n) ⊳ A[1 . . n]

for j ← 2 to n

do key ← A[ j]

i ← j – 1

while i > 0 and A[i] > key

do A[i+1] ← A[i]

i ← i – 1

A[i+1] = key

“pseudo codice”

sorted

i j

key

A:

1 n


Esempio di Insertion Sort

8 2 4 9 3 6



8 2 4 9 3 6



8 2 4 9 3 6

2 8 4 9 3 6



8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6



8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6



8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

2 3 4 8 9 6



8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

2 3 4 8 9 6

2 3 4 6 8 9 Fatto!


Tempo di Esecuzione

Dipende dall’input

Dal numero di elementi

Dallo stato del vettore, una sequenza già ordinatarichiede meno tempo

Calcolare il tempo di esecuzione parametrizzandolo rispettoal numero di elementi di input (vettori più piccoli richiedonomeno tempo)

Cerchiamo limiti superiori al tempo di esecuzione dato chedanno una garanzia sul tempo massimo richiesto


Quale Tipo di Analisi?

Caso Pessimo (worst-case): (tipico)

T(n) tempo massimo per un input di n elementi

Caso Medio (average-case): (raramente disponibile)

T(n) tempo medio per un input di n elementi

Problema: Qual è la distribuzione degli input?

Caso Migliore (best-case): (non informativo)

Algoritmi lenti possono essere molto veloci in casiparticolarmente favorevoli

L1.32


Quale Tempo di Esecuzione?

Qual è T(n) nel caso pessimo per l’insertion sort?

Dipende dalla velocità della macchina su cui viene eseguito

Velocità relativa (diversi algoritmi, stessa macchina)

Velocità assoluta (su macchine differenti)

L1.33

Non considerare una particolare macchina

Studiare T(n) per n → ∞

Analisi Asintotica

Analisi asintotica


Andamento Asintotico per T(n) 35


Computer più veloci o algoritmi più veloci?

T(n) n n’ Change n’/n

10n 1,000 10,000 n’ = 10n 10

20n 500 5,000 n’ = 10n 10

5n log n 250 1,842 10 n < n’ < 10n 7.37

2n2 70 223 n’ = 10n 3.16

2n 13 16 n’ = n + 3 -----

Quanto guadagno se compero

un calcolatore 10 volte più veloce?


37

Per a, b > 1 qualsiasi

na cresce più velocemente di logb n

(meglio logaritmico che polinomiale)

na cresce più velocemente di log nb

(meglio potenza di un logaritmo che un polinomio)

an cresce più velocemente nb

(meglio polinomiale che esponenziale)


Analisi Asintotica: Notazione O-grande

Definizione: sia T(n) una funzione non-negativa, T(n) è O(f(n)) se esistono due costanti positive c ed n0 taliche T(n) <= cf(n) per ogni n> n0

Per tutti i gli insiemi di dati di input grandi a sufficienza, (n>n0), l’algoritmo termina la sua esecuzione in meno dicf(n) passi (nel caso migliore, medio, o peggiore).

La notazione O-grande indica un limite superiore a T(n)

Esempio: se T(n) = 3n2 allora T(n) è in O(n2)

Ovviamente siamo interessati al minimo limite superiore, se T(n) = 3n2 è O(n3), ma preferiamo O(n2)


Analisi Asintotica: Notazione Ω-grande

Definizione: sia T(n) una funzione non-negativa, T(n) è Ω(g(n)) se esistono due costanti positive c ed n0 taliche T(n) >= cg(n) per ogni n> n0

Per tutti i gli insiemi di dati di input grandi a sufficienza, (n>n0), l’algoritmo ha bisogno almeno di cg(n) passi (nelcaso migliore, medio, o peggiore).

La notazione Ω-grande indica un limite inferiore a T(n)

Esempio: se T(n) = 2n2+n allora T(n) è in Ω(n2)

Ovviamente siamo interessati al massimo limite inferiore, T(n) = 2n2+n è Ω(n), ma preferiamo Ω(n2)


Analisi Asintotica: Notazione Θ-grande

Definizione: se T(n) è Ω(h(n)) e anche O(h(n)) alloraT(n) è Θ(h(n))

Ovvero, se esistono due costanti c1 e c2, ed n0 tali chec1g(n) ≤ f(n) ≤ c2g(n) per ogni n>n0


Vero asintoticamente!

Non dovremmo ignorare glialgoritmi che sonoasintoticamente lenti

Nelle situazioni reali bisognaspesso bilanciare obiettivicontrapposti

Tipico esempio, performance vs. complessità

n

T(n)

n0

Analisi Asintotica

Per n grande, un algoritmo (n2) è sempre

più veloce di un algoritmo (n3)


Andamento Asintotico per T(n) 42


Regole di Semplificazione

Se f(n) è O(g(n)) e g(n) è O(h(n)), allora f(n) è O(h(n))

Se f(n) è O(kg(n)) per ogni k>0, allora f(n) è O(g(n))

Se f1(n) è O(g1(n)) ed f2(n) è O(g2(n)), allora (f1 + f2)(n) è O(max(g1(n), g2(n)))

Se f1(n) è O(g1(n)) ed f2(n) è O(g2(n)),allora f1(n)f2(n) è O(g1(n)g2(n))

In breve, eliminare i termini di ordine inferiore, ignorare le costanti.


Esempi di Analisi Asintotica

Esempio 1:

a = b;

Esempio 2:

sum = 0;

for (i=1; i<=n; i++)

sum += n;



Esempio 3:

sum = 0;

for (i=1; i<=n; j++)

for (j=1; j<=i; i++)

sum++;

for (k=0; k<n; k++)

A[k] = k;



Esempio 4:

sum1 = 0;

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

sum1++;

sum2 = 0;

for (i=1; i<=n; i++)

for (j=1; j<=i; j++)

sum2++;



Esempio 5:

sum1 = 0;

for (k=1; k<=n; k*=2)

for (j=1; j<=n; j++)

sum1++;

sum2 = 0;

for (k=1; k<=n; k*=2)

for (j=1; j<=k; j++)

sum2++;


Strutture di Controllo

Istruzione while: viene analizzato come il ciclo for

Istruzione if: complessità del blocco più costoso

Istruzione switch: complessità del caso più costoso

Chiamata a subroutine: complessità della subroutine


Qual è la Complessità Insertion Sort

INSERTION-SORT (A, n) ⊳ A[1 . . n]

for j ← 2 to n

do key ← A[ j]

i ← j – 1

while i > 0 and A[i] > key

do A[i+1] ← A[i]

i ← i – 1

A[i+1] = key


Analisi Asintotica dell’Insertion Sort

Caso Peggiore:

Caso Medio:(tutte le possibili permutazioni siano equiprobabili)

È un algoritmo veloce?

Si, per n piccoli

No, per n grandi

50

n

j

n)/j()n(T2

22

n

j

n)j()n(T2

2


Cosa Succede Se Abbiamo Più Parametri?

Calcoliamo la frequenza di tutti i C colori in un’immagine di P pixel

for (i=0; i<C; i++) // Initialize count

count[i] = 0;

for (i=0; i<P; i++) // Look at all pixels

count[value(i)]++; // Increment count

sort(count); // Sort pixel counts

Se usiamo P come parametri, allora T(n) = (P log P).

È più accurato T(n) = (P + C log C).


Merge Sort

MERGE-SORT A[1 . . n]

1. If n = 1, done.

2. MERGE-SORT A[ 1 . . n/2 ]

3. MERGE-SORT A[ n/2 +1 . . n ]

4. merge the two sorted arraysA[ 1 . . n/2 ] and A[ n/2 +1 . . n ]

Punto chiave: il merge dei due vettori


Merge di Due Vettori Ordinati

20

13

7

2

12

11

9

1



20

13

7

2

12

11

9

1

1



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9

9


12

11


20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9

9

20

13



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9

9

20

13

12

11

11



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9

9

20

13

12

11

11

20

13

12



20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9

9

20

13

12

11

11

20

13

12

12


12


20

13

7

2

12

11

9

1

1

20

13

7

2

12

11

9

2

20

13

7

12

11

9

7

20

13

12

11

9

9

20

13

12

11

11

20

13

12

Il merge è Θ(n)


Insertion Sort vs Merge Sort

InsertionSort

Ha un approccio incrementale

A[1..j-1] ordinato, aggiungi A[j]

MergeSort

Ha un approccio divide-et-impera

Divide: Divide il vettore di n elementi in due array di n/2 elementi

Impera: Chiama il MergeSort ricorsivamente su i due array

Combina: Fa il merge delle due sequenze ordinate

67


Analisi Asintotica del Merge Sort

Calcolare T(n) = 2T(n/2) + cn, dove c > 0 è una constante




T(n)




T(n/2) T(n/2)

cn




cn

T(n/4) T(n/4) T(n/4) T(n/4)

cn/2 cn/2



Calcolare T(n) = 2T(n/2) + cn, dove c > 0 è una costante

cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)




cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)

h = log n




cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)

h = log n

cn




cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)

h = log n

cn

cn




cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)

h = log n

cn

cn

cn

…


n elementi



cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)

h = log n

cn

cn

cn

(n)

…


n elementi



cn

cn/4 cn/4 cn/4 cn/4

cn/2 cn/2

(1)

h = log n

cn

cn

cn

(n)

Total (n log n)

…


79

Θ(nlogn) cresce più lentamente di Θ(n2)

Asintoticamente il merge sort è

meglio dell’insertion sort

In pratica il merge sort

è conveniente per n>30


Notazioni o & ω

La notazione O-grande e Ω-grande sono basate sulledisuguaglianze ≤ e ≥

La notazione o-piccolo e ω sono basate su disuguaglianzestrette < e >

80

Sommario


Sommario

Algoritmo: “Sequenza di passi, definiti con precisione, cheportano alla realizzazione di un compito”

Struttura Dati: Organizzazione o collezione di elementi (o record) su cui sia possibile processare le informazioni, effettuare una ricerca, ecc.

La scelta della struttura dati e dell’algoritmo adeguati puòridurre i tempi di esecuzione da giorni a pochi secondi.

Analisi asintotica su performance (tempo di esecuzione T(n)) notazione O, Ω, e Θ

Esempi di Insertion Sort and Merge Sort

Asd 01 Algoritmi E Strutture Dati

Technology

Transcript of Asd 01 Algoritmi E Strutture Dati