Corso di Perfezionamento - Modelli di calcolo e analisi di algoritmi01]Modelli.pdf ·...

Il concetto di AlgoritmoAnalisi di Algoritmi

Corso di PerfezionamentoModelli di calcolo e analisi di algoritmi

Maria Rita Di Berardini1

1Dipartimento di Matematica e InformaticaUniversita di Camerino

11 febbraio 2009

Maria Rita Di Berardini Corso di Perfezionamento


algoritmi, programmi e strutture dati

Il concetto di “algoritmo”

In maniera informale, un algoritmo e definito come una seriecompleta e non ambugua di regole (passi, operazioni, ... ) checonsentono di risolvere un dato problema computazionale.

Un problema computazionale e caratterizzato dai dati di cui sidispone all’inizio (dati in ingresso, o valori in input) e dairisultati che si vogliono ottenere (valori in output)

Risolve un problema computazionale significa fornire unmetodo, ossia un algoritmo, che consenta di ottenere irisultati attesi a partire da un certo insieme di dati in input




Un po di storia

Etimologia:Il termine algoritmo significa procedimento di calcolo. Deriva daltermine latino medievale algorismus, che a sua volta deriva dalnome del matematico persiamo Abu Jafar Mohammad ibn-Musaal-Khowarismi, vissuto nel IX (?) secolo

Algoritmi nella storia

Algoritmi di tipo numerico sono studiati da babilonesi e indiani

Algoritmi in uso ancora oggi sono stati studiati da matematici greci2000 anni fa – Algor. di Euclide per il MCD, algoritmi geometrici,




Algoritmo Euclideo per il calcolo del MCD

Siano a e b due numeri interi non entrambi pari a zero. Ilmassimo comun divisore tra a e b (MCD(a, b)) e il piu grandenumero naturale per il quale possono essere divisi sia a che b.

Proprieta del MCD:

se a = b allora MCD(a, b) = ase a > b allora MCD(a, b) = MCD(a− b, b)se a < b allora MCD(a, b) = MCD(a, b − a)

Algoritmo1 se a = b allora poni MCD(a, b) = a e termina2 se a > b allora poni a = a− b3 se a < b allora poni b = b − a4 torna al punto 1




Determinazione del minimo

Definizione del problema: ricerca del minimo in un array:

min(A[1 . . . n]) = a sse a ≤ A[i ] per ogni i = 1, . . . , n

(stabilisce una relazione tra input e output)

Algoritmo (descrive una procedura computazionale per realizzaretale relazione):

min(A) min(A) //se A e ordinatoa← A[1] return A[1]for i ← 2 to length[A]

do if A[i ] < aa← A[i ]

return a




Algoritmo: una definizione piu formale

Definition

Un algoritmo e un insieme finito e ordinato di passisemplici, eseguibili e non ambigui, che definisconoun procedimento atto a risolvere un problema, ouna classe di problemi, utilizzando dei dati iniziali eottenendo dei risultati.




Le quattro proprieta fondamentali di un algoritmo

1 Finitezza: la sequenza di passi di cui si compone un algoritmo deveessere finita. Nonostante cio l’esecuzione dell’algoritmo potrebberichiedere un tempo non finito.

2 Risolutivita: la sequenza di passi di cui si compone un algoritmodeve portare ad un risultato che consista nella soluzione delproblema o nella diagnostica sulla mancata soluzione.

3 Effettuabilita: le istruzioni devono essere eseguibili materialmente,ossia deve esistere un agente di calcolo in grado di eseguire ogniistruzione in un tempo finito.

4 Definitezza: ogni passo deve essere non ambiguo. Questo implicanon solo che i passi devono essere espressi chiaramente, ma ancheche il passaggio da un passo al successivo deve avvenire in modoesplicitamente previsto dall’algoritmo.




Perche parliamo di algoritmi

La teoria degli algoritmi ha iniziato a stabilizzarsi agli inizi del XX secolo,mentre ...

Le tecniche di progettazione di algoritmi e di analisi di correttezza e diefficienza si sono evolute nella seconda meta del XX secolo grazie alladiffusione dei calcolatori elettronici

Ovunque si impieghi un calcolatore occorrono algoritmi corretti eefficienti che ne utilizzino al massimo le possibilita. Esempi:

controllo dei voli aerei

regolazione reattori nucleari

reperimento d’informazioni da archivi

smistamento di comunicazioni telefoniche

gioco degli scacchi

controllo della produzione di una catena di montaggio




Come valutiamo gli algoritmi

Risolve correttamente il problema?

un algoritmo si dice corretto se, per ogni istanza di input, siferma con l’output corretto

un algoritmo corretto risolve il problema computazionale dato

dimostrazione matematica, descrizione informale

Risolve il problema in maniera efficiente (analisi di algoritmi)?

definizione di efficienza (tempo o memoria)

alcuni problemi non possono essere risolti in maniera efficiente

esistono delle soluzioni ottime: non e possibile fare di meglio




Algoritmi e Programmi

Gli algoritmi vengono descritti tramite programmi, che si avvalgonodi istruzioni e costrutti dei linguaggi di programmazione per essereeseguiti da calcolatori elettronici

I programmi sono formulazioni concrete di algoritmi astratti che sibasano su particolari rappresentazioni dei dati, e utilizzanooperazioni di manipolazione dei dati, messe a disposizione da unospecifico linguaggio di programmazione

Le proprieta degli algoritmi sono talmente fondamentali, generali erobuste, da essere indipendenti dalle caratteristiche di specificilinguaggi di programmazione o di particolari calcolatori elettronici




Strutture Dati

Il concetto di algoritmo e inscindibile da quello di dato: perrisolvere un problema computazionale, occorre organizzare edelaborare dati in input per produrre dati in output.

Un algoritmo puo essere visto come un manipolatore di dati: afronte di dati in ingresso che descrivono il problema producedati in uscita come risultato del problema.

E fondamentale che i dati siano ben organizzati e strutturatiin modo che il calcolatore li possa elaborare efficientemente.

L’efficienza di un algoritmo dipende in maniera critica dalmodo in cui sono organizzati i dati su cui l’algoritmo stessodeve operare.




Strutture Dati

Tra i dati su cui un algoritmo opera possono sussistere dellerelazioni logiche che definiscono delle “strutturazioni” dei datistessi.

Per esempio, e possibile rappresentare dati eterogenei quali ilnome, cognome e data di nascita di una persona, definendoun “dato strutturato” (un record) costituito dall’ insieme deidue campi di testo (per il nome ed il cognome) ed unoalfa-numerico (per la data di nascita).

Una struttura dati e un insieme di valori logicamente correlatie opportunamente memorizzati, per i quali sono definiti deicostruttori, degli operatori di selezione e degli operatori dimanipolazione.




Strutture Dati

Le strutture dati possono essere classicate in base alla lorooccupazione di memoria

Strutture dati statiche: la quantita di memoria di cuinecessitano e determinabile a priori (esempi: array, record).

Strutture dati dinamiche: la quantita di memoria di cui essenecessitano varia a tempo desecuzione e puo essere diversa daesecuzione a esecuzione (esempi: liste, code, pile, alberi,grafi).

Analizzeremo le principali strutture dati (ed in particolare,pile, code, liste, alberi, grafi) per fornirvi gli strumentinecessari per scegliere di volta in volta la struttura dati chemegli si adatta all’algoritmo che state progettando.



Analisi di Algoritmi

Analizzare un algoritmo vuol dire determinare le risorse necessarieall’algoritmo in termini di

spazio di memoria(quantita di memoria utilizzata durante l’esecuzione)

etempo computazionale

(tempo di esecuzione)



Analisi di Algoritmi

L’analisi della complessita di un algoritmo in termini di tempo diesecuzione consente di:

stimare il tempo impiegato

stimare il piu grande input gestibile in termini ragionevoli

confrontare l’efficienza di due algoritmi diversi

ottimizzare le parti “critiche”

La complessita di un algoritmo viene descritta tramite una funzione

T : dimensione→ tempo impiegato



Dimensione dell’input

Per molti problemi (ex. l’ordinamento) la misura piu naturale e ilnumero di elementi (criteri di costo uniforme)

Per altri (ex. moltiplicazione di numeri interi) la misura migliore eil numero totale di bit necessari per la rappresentazione dell’input(criteri di costo logaritmico)

In realta ciascun elemento e rappresentato da un numero costantedi bit, quindi le due misure coincidono a meno di una costantemoltiplicativa

In altri casi ancora, e piu appropriato descrivere la dimensione condue numeri; ex: se l’input e una matrice bidimensionale ladimensione dell’input e #righe ×#colonne



Rappresentazione del “Tempo”

Abbiamo bisogno di stabilire quale sara la tecnologia di riferimentoutilizzata per eseguire gli algoritmi quando saranno realizzati comeprogrammi

Assumiamo di utilizzare

Mono-Processore + RAM (Random Access Memory)

assenza di concorrenza e parallelismo



Definizione di tempo

Tempo = “wall-clock time”, il tempo effettivamente impiegato pereseguire l’algoritmo

Dipende da troppi fattori (non sempre prevedibili)

1 bravura del programmatore

2 linguaggio di programmazione utilizzato

3 processore, memoria (cache, primaria, secondaria)

4 sistema operativo, processi attualmente in esecuzione

Dobbiamo usare un modello astratto: introduciamo un concetto ditempo legato al numero di operazioni elementari o di passieseguiti per il calcolo dell’output corrispondente



Tempo di esecuzione

Numero di operazioni elementari o “passi” eseguitiper il calcolo dell’output

passo ∼= una linea di pseudocodice

Hp: ogni passo riferito ad una linea i , e eseguito inun tempo costante ci


Definizione del problema dell’ordinamentoInsertion-Sort

Parte I

Il problema dell’ordinamento



Il problema dell’ordinamento

Definition

Dato un insieme di n numeri 〈a1, a2, . . . , an〉, trovare un’opportunapermutazione 〈a′

1, a′2, . . . , a

′n〉 tale che a′

1 ≤ a′2 ≤ . . . ≤ a′

n

Input: 〈a1, a2, . . . , an〉

Output: 〈a′1, a

′2, . . . , a

′n〉 oppure

〈aπ(1), aπ(2), . . . , aπ(n)〉dove π e una permutazione degli indici 1, . . . , nπ : {1, ..., n} −→ {1, ..., n} tale che se π(i) = jallora j e la corretta posizione dell’elementooriginariamente in posizione i



Istanza del problema

Input: (31, 41, 59, 26, 43, 58)

Output: (26, 31, 41, 43, 58, 59)

La scelta del migliore algoritmo dipende:

dal numero di elementi da ordinare

da quanto gli elementi siano gia ordinati

dispositivo di memoria (metodo d’accesso)



Idea per ordinare



Idea per ordinare

Ad ogni passo si ha una sottosequenza ordinata in cui inserisco unnuovo elemento dell’input:

ordinatiA[j] = key

non necessariamente ordinati

ordinati

non necessariamente ordinati

≥ key



Insertion Sort

L’algoritmo di ordinamento Insertion Sort risulta efficiente nelcaso in cui il numero n degli elementi da ordinare e piccolo

for j ← 2 to lenght[A]

do key ← A[j]

. key viene inserito nella sequenza ordinata

. A[1 ... j-1]

i ← j-1

while i > 0 e A[i] > key

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

i ← i-1A[i+1] ← key



Istanza A = {5, 2, 4, 6, 1, 3}

1 2 3 4 5 6j = 2 5 2 4 6 1 3j = 3 2 5 4 6 1 3j = 4 2 4 5 6 1 3j = 5 2 4 5 6 1 3j = 6 1 2 4 5 6 3j = 7 1 2 3 4 5 6



Insertion Sort

Il tempo computazionale impiegato dalla procedura Insertion Sortdipende

dalla dimensione input, il numero degli elementi

dallo ordinamento implicito nella sequenza

Il tempo di esecuzione e espresso in funzione della dimensione delproblema, cioe dell’input



Insertion Sort

Insertion-sort(A,n)

statement costo1. for j = 2 to n { c1

2. key ← A[j] c2

3. i ← j-1 c3

4. while (i > 0) and (A[i ] > key) { c4

5. A[i + 1]← A[i ] c5

6. i ← i − 1 c6

7. }8. A[i + 1]← key c8

9. }



Insertion Sort

Indichiamo con ni il numero di volte che un passo iviene eseguito:

T (n) = n1c1 + n2c2 + . . . nkck =k∑

i=1

nici



Insertion-sort

statement costo volte1. for j = 2 to n { c1 n2. key = A[j] c2 n − 13. i = j-1 c3 n − 14. while (i > 0) and (A[i ] > key) { c4 n4???5. A[i + 1] = A[i ] c5 n5???6. i = i − 1 c6 n6???7. }8. A[i + 1] = key c8 n − 19. }

Sia tj= numero di volte che la guardia del ciclo while di riga 4viene valutata, per j = 2, . . . , n, i.etj = (elementi in A[1, . . . , j − 1] > key) + 1

n4 =n∑

j=2

tj n5 = n6 =n∑

j=2

(tj − 1)



Insertion Sort

Il che ci porta ad un costo

T (n) = c1n+(c2+c3+c8)(n−1)+c4

n∑j=2

tj+(c5+c6)n∑

j=2

(tj−1)



Insertion Sort: analisi del costo computazionale

tj A[j]

Il valore di tj = (elementi in A[1, . . . , j − 1] > key) + 1 dipende dalvettore in input:

Caso ottimo (vettore gia ordinato) tj = 1

Caso peggiore (ordinato in maniera decrescente) tj = j

Caso medio tj = j/2



Analisi del costo computazionale nel caso ottimo

Costo “generico”

T (n) = c1n+(c2+c3+c8)(n−1)+c4

n∑j=2

tj+(c5+c6)n∑

j=2

(tj−1)

nel caso ottimo — tj = 1 e tj − 1 = 0

T (n) = c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 1

= c1n + (c2 + c3 + c8)(n − 1) + c4(n − 1)= (c1 + c2 + c3 + c4 + c8)n − (c2 + c3 + c4 + c8)

T (n) = an + bdove a e b sono delle opportune costanti

T (n) e una funzione lineare in n



Analisi del costo computazionale nel caso peggiore

Nel caso peggiore tj = j , quindi

T (n) = c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 tj + (c5 + c6)

∑nj=2(tj − 1)

= c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 j + (c5 + c6)

∑nj=2(j − 1)

Fact

n∑j=2

j =( n∑

j=1

j)− 1 =

n(n + 1)

2− 1 =

n2

2+

n

2− 1

n∑j=2

(j − 1) =n−1∑j=1

j =(n − 1)n

2=

n2

2− n

2



Analisi del costo computazionale nel caso peggiore

T (n) = c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 j + (c5 + c6)

∑nj=2(j − 1)

= c1n + (c2 + c3 + c8)(n − 1) + c4(n2

2 + n2 − 1) + (c5 + c6)(

n2

2 −n2 )

= c4+c5+c6

2 n2 + (c1 + c2 + c3 + c4−c5−c6

2 + c8)n − (c2 + c3 + c4 + c8)

T (n) = an2 + bn + cdove a, b e c sono delle costanti

T (n) e una funzione quadratica in n



Analisi nel caso medio

L’analisi del tempo di esecuzione nel caso medio analizza come sicomporta l’algoritmo in “media”

E legato al fatto che in alcune circostanze non e necessario che unalgoritmo operi con una quantita limitata di risorsa per ognipossibile input, ma e sufficiente che sia “generalmente efficiente”

Per ogni n, il costo dell’algoritmo viene calcolato come la sommadei costi per ogni possibile input di dimensione n tenendo contodella probabilita che ciascun singolo caso si verifichi

Tmedio(n) =∑

{I :|I |=n}

T (I )Pr(I )



Analisi nel caso medio

Bisogna determinare la distribuzione di probabilita di ciascun input

Problema: non sempre si dispone delle informazioni necessarie perdeterminare la distribuzione Pr

Una possibile soluzione: fare delle assunzioni plausibili sullecaratteristiche del problema

Ad esempio, nel caso del Insersion sort e plausibile assumere che,mediamente, solo la meta degli elementi della porzione di vettoreA[1...j − 1] sia maggiore di key , e quindi che tj = j/2



Analisi del costo computazionale nel caso medio

Nel caso medio tj = j/2, quindi

T (n) = c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 tj + (c5 + c6)

∑nj=2(tj − 1)

= c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 j/2

+(c5 + c6)∑n

j=2(j/2− 1)

n∑j=2

j/2 =1

2

n∑j=2

j =1

2(

n∑j=1

j − 1) =1

2(n2

2+

n

2− 1) =

n2

4+

n

4− 1

2

n∑j=2

(j/2− 1) =n∑

j=2

j − 2

2=

1

2

n∑j=2

j − 2 =1

2

n−2∑j=0

j =1

2

n−2∑j=1

j =

1

2

(n − 2)(n − 1)

2=

1

2

n2 − 3n + 2

2=

n2

4− 3n

4+

1

2



Analisi del costo computazionale nel caso medio

T (n) = c1n + (c2 + c3 + c8)(n − 1) + c4

∑nj=2 j/2

+(c5 + c6)∑n

j=2(j/2− 1)

= c1n + (c2 + c3 + c8)(n − 1) + c4(n2

4 + n4 −

12 )+

(c5 + c6)(n2

4 −3n4 + 1

2 )

= c4+c5+c6

4 n2 + (c1 + c2 + c3 + c4−3c5−3c6

2 + c8)n+( c5+c6

2 − (c2 + c3 + c4

2 + c8))

T (n) = an2 + bn + cdove a, b e c sono delle costanti

T (n) e una funzione quadratica in n



Analisi del caso peggiore vs. analisi del caso medio

Il tempo di esecuzione nel caso ottimo non e molto significativo

Di solito prenderemo in considerazione il tempo di esecuzione nelcaso peggiore. Perche??

il tempo di esecuzione nel caso peggiore rappresenta unalimitazione superiore sui tempi di esecuzione per qualsiasiinput, non possiamo fare di peggio

per alcuni algoritmi il caso peggiore si verifica abbastanzaspesso (ex. ricerca di un elemento in una base di dati)

il caso medio e in generale altrettanto cattivo quanto il casopeggiore (vedi Insertion Sort)


Corso di Perfezionamento - Modelli di calcolo e analisi di algoritmi01]Modelli.pdf ·...

Documents

Transcript of Corso di Perfezionamento - Modelli di calcolo e analisi di algoritmi01]Modelli.pdf ·...