Analisi degli algoritmi - algoritmi e strutture dati

Esempio:

Abbiamo una sequenza di numeri interi e ci chiediamo se

ci sono delle triplette di numeri la cui somma è zero, le

triplette possono essere non contigue. Questo

programma utilizza un meccanismo brutale, infatti prova

tutte le triplette, fissiamo quindi il primo numero con il

ciclo più esterno a indice zero, il secondo numero

appena dopo e il terzo numero appena dopo, poi

cominciamo a muoverli, quindi con il primo e il secondo

numero fissati facciamo passare tutti i possibili numeri

sul terzo, poi spostiamo il secondo numero, mettiamo il

terzo numero più avanti e prendiamo tutti i numeri fino

alla fine etc…, quindi abbiamo 3 cicli nidificati che

generano tutte le possibili triplette a meno dell’ordine

che non ci interessa, su tutte le possibili triplette

calcoliamo la somma e se fa zero incrementiamo il

contatore.

Variabili di questo algoritmo è: prendo tutte le terne

pitagoriche tra 1 e 1 milione e vado a vedere quali di

queste soddisfano la somma pari a zero, potrei

modificare leggermente la cosa, è però un algoritmo che

enumera tutte le soluzioni e cerca di capire come

quando l’ha trovato. Gli algoritmi che enumerano tutte le

possibili soluzione e vedono se ce ne è una che va bene

vengono detti algoritmi di forza bruta o ricerca

esaustiva. Questo algoritmo visto è un algoritmo di forza

bruta, vogliamo chiederci quanto temo richiede, la

risposta è però complessa perché dovrebbe tenere conto

anche di come è fatto e implementato l’algoritmo,

possiamo disegnare il modello minimo di un computer:

Questo è un modello minimo perché la massa di dati che

utilizziamo oggi è tale da superare ampiamente la

capacità della memoria centrale del computer (RAM), se

così fosse, sapendo che la memoria del disco è molto più

grande, allora possiamo leggere il file dal disco per

poterlo elaborare, non è pensabile leggerlo tutto intero

ed elaborarlo. Esistono algoritmi ottimizzati per vari

scenari di lavoro, alcuni per lavorare sulla memoria

centrale e altri sulla memoria di massa. La maggior

parte degli algoritmi sono ottimizzati per lavorare in

RAM, questa è spesso una grossa fregatura questo

perché questi algoritmi sono spesso implementati in

librerie su cui non abbiamo controllo, le utilizziamo e poi

quando ci ritroviamo a lavorare con un insieme di dati

che è consistente scopriamo che il nostro programma

rallenta in modo anomalo, questo perché abbiamo

utilizzato un algoritmo ottimizzato per lavorare in RAM

mentre in realtà stiamo lavorando in memoria di massa.

Il tempo di accesso alla memoria di massa più lento

dell’accesso alla memoria centrale che è ordine di

grandezza più lento dell’accesso cache, questo però è un

impatto di natura tecnologica e tutti questi impatti li

vogliamo eliminare

Riproducendo questo codice si nota che guardando

queste curve il modello che ci dice qual è il tempo di

esecuzione richiesto rispetto alla dimensione del

problema, cioè al numero di interi presenti nel file che

stiamo elaborando, è dato da c+aN quindi è un

3

esponenziale, approssimativamente possiamo indicarlo

come aN perché per N grande c perde sempre più

3

valore. Questo perché ci sono 3 cicli innestati.

Negli anni 60 Knuth ha elaborato un principio secondo il

quale è possibile elaborare un modello matematico che

descrive il funzionamento nel tempo di un programma,

questo modello si basa su due fattori:

costo e tempo necessari per eseguire ogni singola

·6 istruzione, questa è una proprietà tecnologica del

computer

la frequenza di esecuzione di ogni istruzione

·7 contenuta nel programma, questa è invece una

proprietà del programma

La nostra sfida è quella di determinare la frequenza di

esecuzione delle istruzioni, quindi quello che dipende dal

programma perché quello che dipende dal computer

potremmo misurarlo una volta per tutte mediante

benchmark. L’analisi a questo punto diventa una analisi

matematica.

Il problema considerato è già risolto dal punto di vista

delle prestazioni, infatti generando le triplette di interi

non stiamo facendo altro che generare le combinazioni

semplici di 3 interi su n, cioè .

Dai risultati sperimentali avevamo visto che il nostro

tempo di esecuzione, a meno delle costanti a e c è di

tipo cubico, ivnfatti avevamo trovato che T(N)=c+a

(per N>>0). Nel primo caso è una costante alfa e

nel secondo caso è una costante a. Non abbiamo tenuto

conto del termine noto che è il tempo di avviamento

iniziale che è quello che tiene conto del fatto che il

programma, prima di partire farà qualcosa, ad esempio

prima del ciclo ci sono inizializzazioni di variabili, ci

potrebbero essere operazioni di inizializzazione più

complesse che portano via un po' di tempo che è un

tempo fisso e viene pagato a ogni esecuzione del ciclo.

Quindi con l’aumentare con il numero di esecuzioni del

ciclo, cioè della dimensione del vettore, il tempo di

inizializzazione del programma diventa sempre meno

importante.

Quindi se vogliamo analizzare un algoritmo dobbiamo

cercare di capire quante operazioni vengono fatte nelle

sue varie parti, se ho delle operazioni innestate ina

nell’altra, le operazioni della parte più interna vengono

moltiplicate per il numero di volte del ciclo più esterno,

quindi la presenza di più cicli innestati ci porta a

calcolare il numero delle operazioni dell’operazione più

interna sulla base di quante volte vengono effettuate le

altre operazioni ma moltiplicando i vari risultati.

Tilde notation

Per semplificare le cose si introduce la tilde notation,

consideriamo la formula , sviluppando tutti i

calcoli scopriamo che il risultato è: , se

prendiamo in cosiderazione , se N è molto grande

scopriamo che questo termine diventa rapidamente

predominante sugli altri, quindi possiamo scrivere

cioè cresce come . Come tutti i

polinomi, questo ha la caratteristica che per N piccoli

potrebbe avere un andamento oscillante

Definizione: se e solo se

Abbiamo anche una classificazione degli ordini di

crescita, sono in ordine dal più al meno desiderabile:

costante

·8 ordine: 1

esempio: operazioni aritmetiche, ad esempio

c=a+b, anche gli statemant, ad esempio

aggiungere 2 al numero

logaritmico

·9 ordine: log N

si ha nei problemi di bisezione, cioè la divisione in

metà, come nella ricerca binaria.

Ogni volta in cui possiamo buttare via metà dello

spazio di ricerca abbiamo un tempo di crescita di

tipo logaritmico

lineare

·10

ordine: N

Esempio: trovare il massimo elemento in un vettore,

ovviamente devo leggerli tutti se il vettore non è

ordinato

Se lo spazio di ricerca raddoppia allora il tempo di

ricerca raddoppia

linearithmic

·11

ordine: NlogN

Esempio: algoritmi di ordinamento, come il migliore

che è il mergesort

Il problema viene diviso in sottoproblemi e poi

riunificato

quadratico

·12

ordine: N^2

esso è tipizzato da un’operazione che avviene

all’interno di due cicli innestati

a un raddoppiamento delle dimensioni del problema

corrisponde una quadruplicazione dei tempi di

calcolo

cubico

·13

ordine: N^3

esponenziale

·14

ordine: 2^k (potrebbe essere diverso da 2)

devo effettuare un numero di operazioni dove la

dimensione N del problema sta all’esponente

dell’ordine di crescita, questo è tipico della ricerca

esaustiva su sottoinsiemi

I problemi di ottimizzazione combinatoria seguono

l’esponenziale, ad esempio mi serve quando devo a

posto varie tessere di un mosaico di dimensioni

diverse all’interno di un contenitore di dimensioni

fisse, ad esempio per caricare i pacchetti di amazon

sul camion, immaginiamo di poter caratterizzare

ogni pacchetto con un numero e immaginiamo di

avere più di un pacchetto con numeri diversi o

uguali, il camion può portare 1000 numeri, quindi la

somma dei numeri di quei pacchetti deve fare 1000

ma i singoli pacchetti hanno un peso differente, io

devo capire come posso caricare i camion e devo

capire quanti pacchetti posso mettere sul camion in

modo da non superare 1000 come somma e

cercherò di mettere il maggior numero possibile

rispettando anche altri vincoli

Viene usato per i problemi di backpacking

Notiamo che se noi aumentiamo la dimensione del

problema, quello che diventa dominante sono le

istruzioni eseguite all’interno del ciclo più interno, queste

istruzioni vengono indicate come inner loop o in certi

casi come computational kernel.

Molti programmi hanno un comportamento che dipende

da un piccolo sottoinsieme delle istruzioni, in particolare

dalle istruzioni dell’inner loop.

Modello di costo

Se noi lavoriamo con gli ordini di grandezza possiamo

ottenere l’obiettivo che si era posto Knuth, usando

l’ordine di grandezza noi separiamo il fattore

tecnologico, quindi la particolare implementazione su un

particolare computer, dal fattore algoritmico, quindi il

comportamento dell’algoritmo che sarà uguale su tutti i

computer, arrivando alla conclusione che è l’algoritmo

che usiamo e qualche volta il modello dell’input a

determinare l’ordine di crescita dei nostri algoritmi,

possiamo in questo modo arrivare a un modello di costo

focalizzandoci sulle operazioni che il programma effettua

ma molto grossolanamente, cioè andando a guardare il

ciclo più interno, quindi possiamo affermare che

l’algoritmo di somma di triplette di forza bruta utilizza

circa (N^3)/6 accessi all’array, che è la figura di merito

che usiamo, per calcolare le somme che desideriamo,

questo è il modello di costo del nostro programma

In realtà esistono 3 diversi modelli di costo per lo stesso

programma:

best case

·15

Il nostro algoritmo ha un comportamento che nel

caso migliore ha un certo modello di costo

average case

·16

caso medio

worst case

·17

caso peggiore

il worst case è quanto tempo impiego a trovare un

elemento se nella lista non c’è o è l’ultimo-------

Esempio: consideriamo la ricerca di un elemento in una

lista che deve essere visitata elemento per elemento,

nel caso migliore lo troviamo subito, quindi il best case

mi d&agra