Riassunto Algoritmi e strutture dati

Definizione di problema

Dato un problema P e un insieme X di possibili input di P e un insieme Y di possibili

output P, P è una funzione che associa ad ogni elemento x € X un elemento y € Y ->

y=P(x)

Definizione di algoritmo risolutore

Dato un algoritmo A e un problema P, con P: x->y. Si dice che A è un algoritmo

risolutore di P se per ogni x € X, l’esecuzione di A(x) restituisce un elemento y € Y tale

che y=P(x) dopo un numero finito di passi.

(2) Dato un problema P:I -> O {I= insieme dei possibili input , O= insieme dei possibili

∀

output} , un algoritmo è risolutore di P se i € I A(i)=P(i)

(3) Un algoritmo è un procedimento che risolve un determinato problema attraverso

un numero finito di passi, chiari e non ambigui.

Definizione di algoritmo ottimale Ω

Dato un problema P avente complessità intrinseca (g(n)), un algoritmo A

risolutore di P si dice ottimale per P se A ha complessità O(g(n)) nel caso peggiore.

Criteri di costo: Costo uniforme

Considero ciascuna operazione avente costo unitario, senza considerare la dimensione

dell’input.

Costo logaritmico

In questo modello per ciascuna operazione si paga un costo pari a log n, dove n è la

dimensione dell’input.

O-grande Ω

Omega

Theta

Caso peggiore, caso migliore e caso medio

Il concetto è quello di analizzare il tempo di esecuzione di un algoritmo a parità di

dimensione di input.

Sia T (x) il costo di esecuzione di A su x e con |x| la dimensione di X.

A

Ta worst(n) = max ({Ta(x) | x € I^|x| =n}) (caso peggiore)

Ta best (n)= min (Ta(x) | x € I^|x| =n}) (caso migliore)

Se si considera la distribuzione di probabilità che le istanze siano effettivamente date

in input all’algoritmo (Pr(x)) allora si può definire Ta avg(n)= somm Ta(x) x Pr(x) (caso

medio)

Definizione complessità intrinseca

Dato un problema P e una funzione g , si dice che P ha complessità intrinseca Ω(g) se

tutti gli algoritmi risolutori di P hanno complessità Ω(g). In altre parole, in qualsiasi

modo si risolva il problema, meno di Ω(g) non si può andare.

Tecnica dell’avversario

Questa tecnica consiste nel supporre che un dato algoritmo, che risolve un dato

problema a un certo costo, possa essere battuto, cioè dando in input dei dati

d’ingresso fatti appositamente per mettere in crisi l’algoritmo.

Analisi ammortizzata

L’analisi ammortizzata studia le prestazioni medie di una sequenza di operazioni su

una collezione di dati, piuttosto che su una singola esecuzione. Per caratterizzare le

prestazioni in media di un algoritmo, si parla di costo ammortizzato che è definito

❑

come: Ta(n)= ❑

T(n,k) = tempo totale richiesto dall’algoritmo nel caso peggiore per tutte le k

operazioni su un input di dimensione n.

k = numero di operazioni fatte da una sequenza di un algoritmo

Divide et Impera

Il principio su cui si basa la tecnica divide-et-impera consiste nel dividere i dati in

ingresso in due o più sottoinsiemi (DIVIDE) , risolvere ricorsivamente i sotto problemi e

poi ricombinare le soluzioni dei sotto problemi e ottenere la soluzione globale del

problema originario (IMPERA).

Tecnica golosa

Questa tecnica viene utilizzata per risolvere problemi di ottimizzazione, ovvero

problemi per cui è necessario trovare la migliore soluzione possibile.

Nella situazione generale avremo a che fare :

. un insieme c di candidati possibili (insieme di possibili algoritmi risolutori)

. insieme dei candidati che sono stati enunciati , tra cui si distinguono quali sono stati

scartati e quelli che sono stati selezionati per far parte di una soluzione parziale S

. una funzione ammissibile che verifica se un insieme di candidati fornisce una

soluzione anche non ottima al problema

. una funzione ottimo che verifica se c fornisce una soluzione ottima

. una funzione seleziona per estrarre un elemento dall’insieme dei candidati possibili

non ancora ------

. una funzione obiettivo che fornisce il valore di una soluzione

Per risolvere il problema è necessario trovare un insieme di candidati che: è soluzione,

ottimizza il valore della funzione obiettivo.

Algoritmi di ordinamento con divide et impera

Metodo principale che richiama il mergeSort

public static void mergeSort(int[] v){

if (v!= null)

mergeSort(v,0,v.length-1);

}

private static void mergeSort(int[] v, int in, int fin) {

if(fin<=in)

return;

int med = (in+fin)/2;

mergeSort(v, in, med);

mergeSort(v, med+1,fin);

merge(v,in,med,fin);

}//mergeSort

private static void merge(int[] v, int in, int med, int fin) {

int[] stage = new int[fin-in+1];

int i=in,j=med+1, st=0;

while((i<=med)&(j<=fin)){

if(v[i]<v[j])

stage[st++]=v[i++];

else stage[st++]=v[j++];

}//while

for(;i<=med;i++)

stage[st++]=v[i];

for(;j<=fin;j++)

stage[st++]=v[j];

for(int k=0; k<stage.length;k++)

v[in+k]=stage[k];

}//merge

Complessità spaziale

Ad ogni chiamata alloco una memoria pari allo spazio di allocazione di n/2 elementi.

S(n)= s(n/2) + b(merge)

S(1)= b

Quindi la complessità sarà O(log n +n)

Complessità temporale

O(n log n) in tutti i casi

Quick sort

private static void quickSortOriginale( int [] v , int in , int fin ) {

if(fin<=in)

return;

partiziona(v,in,fin);

int p=

quickSortOriginale(v,in,p-1);

quickSortOriginale(v,p+1,fin);

}

private static int partiziona(int[] v, int in, int fin) {

Math.floor(Math.random()*(fin-in+1));

int rnd = (int)

int tmp = v[in]; v[in]= v[rnd]; v[rnd]= tmp;

int p=in;

int inf=in+1, sup=fin;

while(inf<sup){

for(;(inf<=fin)&&(v[inf]<v[p]); inf++);

for(;(sup>=in)&&(v[p]<=v[sup]);sup--);

if(inf<sup){

int t = v[inf]; v[i