Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.10

risoluzione di una particolare istanza di un problema quanto vogliamo determinare con che

legge il costo di esecuzione che ci interessa (sia esso il tempo o la quantità di memoria o

qualche altra grandezza) varia al variare dell'istanza. Ad esempio, nel caso del problema della

determinazione del primo e secondo miglior giocatore di un torneo di tennis, ci interessa

sapere quante partite occorrono in funzione del numero di giocatori.

A tale scopo è necessario fare un passo di astrazione e considerare modelli di calcolo

concettualmente basati sugli stessi principi dei normali calcolatori ma molto più elementari di

essi.

Modelli di questo tipo ne sono stati introdotti diversi. Alcuni risalgono ai primi studi di logica

volti a determinare quale fosse la classe di problemi risolubili con metodi algoritmici. E' il

caso, ad esempio, delle macchine di Turing introdotte dal logico Alan Turing nel 1936 e

ancora oggi utilizzate in Informatica Teorica proprio per studi relativi alla complessità di

calcolo. Tali macchine sono dotate di un numero finito di stati interni ed operano leggendo e

scrivendo caratteri di un particolare alfabeto (ad esempio quello binario o quello

alfanumerico) mediante una testina di lettura e scrittura su un nastro potenzialmente

illimitato. Il carattere letto correntemente dalla testina e lo stato interno in cui la macchina si

trova determinano la transizione eseguita dalla macchina, cioè il nuovo stato interno, il

carattere eventualmente scritto sul nastro e lo spostamento della testina sul nastro.

Se come modello di macchina utilizziamo la macchina di Turing possiamo misurare il

numero di passi che la macchina compie (numero di transizioni) e assimilare questa

grandezza al tempo di calcolo. Oppure possiamo misurare il numero di celle del nastro di

lavoro utilizzate e considerarlo come indicativo della quantità di memoria richiesta

dall'algoritmo.

Un altro modello di macchina che può essere utilizzato sono le macchine a registri.

Una macchina a registri, detta anche RAM (Random Access Machine) è chiamata così perchè

la sua memoria consiste di un numero finito, ma arbitrario, di registri, ognuno dei quali può

contenere un intero grande a piacere. I registri sono accessibili direttamente, in base al loro

numero d'ordine. Un registro particolare, chiamato accumulatore, è destinato a contenere via

via, uno degli operandi su cui agiscono le istruzioni della macchina. La macchina scambia

informazioni con il mondo esterno mediante due nastri di ingresso e uscita consistenti di

sequenze di celle, ciascuna delle quali ancora capace di contenere un intero grande a piacere.

La macchina, infine, è dotata di una unità centrale capace di eseguire le istruzioni del

linguaggio di programmazione. La Figura 1 fornisce una rappresentazione di una macchina a

registri. P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.11

Figura 1.1 Rappresentazione fisica di una macchina a registri.

Il linguaggio di programmazione delle RAM è simile al linguaggio Assembler di un

calcolatore reale.

Un programma consiste in una sequenza di istruzioni di vario tipo (di trasferimento,

aritmetiche, di controllo, di I/O). Le istruzioni possono essere eventualmente dotate di

etichetta. In genere un'istruzione opera su operandi contenuti nei registri, che in tal caso

vengono indicati semplicemente con il numero d'ordine del registro (ad esempio 3 indica il

contenuto del registro 3). Quando un operando viene indirizzato in modo indiretto tramite il

contenuto di un altro registro esso viene indicato con il numero del registro preceduto da * (ad

esempio *3 indica il contenuto del registro indirizzato dal registro 3). Infine un operando può

essere direttamente costituito dal dato su cui si vuole operare. in tal caso il dato viene indicato

con = (ad esempio =3 indica che l'operando è l'intero 3).

Le istruzioni di trasferimento (LOAD e STORE) permettono di trasferire il contenuto di un

registro nell'accumulatore e viceversa.

Le istruzioni aritmetiche (ADD, somma, SUB, sottrazione, MULT, moltiplicazione, DIV,

parte intera della divisione, REM, resto della divisione) permettono di eseguire le quattro

operazioni tra il contenuto dell'accumulatore ed il contenuto di un registro. Il risultato rimane

nell'accumulatore. Nota che l'istruzione SUB dà risultato 0 se si tenta di sottrarre un numero

maggiore da un numero minore. P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.12

Le istruzioni vengono sempre eseguite sequenzialmente tranne nei casi in cui la sequenza di

esecuzione non venga alterata da una istruzione di controllo e cioè un'istruzione di HALT o

una istruzione di salto. Quando si incontra l'istruzione HALT l'esecuzione del programma si

arresta. Il programma termina anche se si tenta di eseguire un'istruzione inesistente. Le

istruzioni di salto sono salti incondizionati (JUMP) o condizionati in base al contenuto

dell'accumulatore (JGTZ, JEQZ cioè salta se l'accumulatore contiene un intero maggiore di

zero, o rispettivamente, uguale a zero); l'operando di un'istruzione di salto è l'etichetta (o il

numero d'ordine) dell'istruzione alla quale eventualmente si effettua il salto.

Infine due istruzioni di I/O (READ e WRITE) consentono di leggere un numero intero sul

nastro di ingresso e trasferirlo in un registro e, rispettivamente, di scrivere il contenuto di un

registro sul nastro di uscita.

Esempio 1.2 Supponiamo che gli interi x (> 0) e y siano forniti sul nastro di ingresso. Il

y

seguente programma dà in uscita il valore x .

READ 1

READ 2

LOAD =1

STORE 3

LOAD 2

LOOP JEQZ STOP

LOAD 1

MULT 3

STORE 3

LOAD 2

SUB =1

STORE 2

JUMP LOOP

STOP WRITE 3

HALT

Dal punto di vista del loro uso nell'analisi del costo di esecuzione di algoritmi si può dire

che le RAM sono un modello abbastanza realistico, sostanzialmente equivalente ad un

elaboratore reale programmato in Assembler, e per il quale il tempo è rappresentato dal

numero di istruzioni eseguite, eventualmente pesate in modo da tenere conto del fatto che le

varie istruzioni elementari possono avere un costo diverso (ad esempio la moltiplicazione è

in genere più costosa del semplice trasferimento di dati) e che, a differenza che negli

elaboratori reali, in queste macchine i registri possono contenere un intero arbitrariamente

grande.

Un metodo semplice ma già sufficientemente dettagliato per analizzare il costo di un

programma per RAM è di attribuire un costo unitario a tutte le istruzioni e limitarsi a

contare quante volte ogni istruzione viene eseguita in funzione dell'input del programma.

Riprendiamo in esame l'esempio precedente; possiamo vederlo diviso in tre parti; lettura

dell'input e inizializzazione, esecuzione del ciclo, terminazione. La prima e l'ultima parte

hanno rispettivamente un costo pari a 4 e a 2, indipendentemente dal valore dell'input. Il

corpo del programma, cioè il ciclo, consta di 8 istruzioni che vengono eseguite y volte.

Inoltre le prime due istruzioni del ciclo vengono eseguite una volta in più, quando il valore

y diventa uguale a zero e si effettua il salto all'etichetta STOP. In definitiva il costo di

esecuzione del programma è pari a 4+8y+2+2 = 8y+8.

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.13

Esercizio 1.2 Realizza un programma per macchine a registri che leggendo in ingresso

l'intero n e, successivamente, n numeri interi, ne determina il massimo e lo

stampa sul nastro di uscita. Quale è il suo costo di esecuzione misurato in

termini di istruzioni eseguite?

Per quanto le macchine di Turing e, soprattutto, le RAM siano dei modelli di calcolo astratti,

sufficientemente elementari per determinare facilmente il costo di esecuzione di un algoritmo,

non dobbiamo pensare che sia sempre necessario fare riferimento a tali modelli. In molti casi

possiamo utilizzare dei modelli più semplici, di potenza limitata ma adatti a descrivere il

particolare tipo di algoritmi che vogliamo analizzare. Un esempio tipico sono gli alberi di

decisione, nei quali ogni nodo dell'albero rappresenta un'operazione di confronto tra interi.

Essi possono essere utilizzati per analizzare e confrontare algoritmi di ricerca (come quello

dell' Esempio 1). Lo stesso concetto di torneo, utilizzato nella sezione precedente, può essere

visto come un modello di esecuzione di algoritmi di ordinamento parziale, in cui la misura di

complessità adottata è il numero di incontri effettuati.

Infine possiamo considerare un algoritmo scritto in un linguaggio ad alto livello (Java, Pascal,

C++ ecc.), o anche in uno pseudo-linguaggio (più simile al linguaggio naturale che ad un vero

e proprio linguaggio di programmazione) e limitarci a valutare il numero di operazioni

fondamentali che vengono compiute dall'algoritmo stesso (cioè le cosiddette operazioni

dominanti), adottando questo valore come misura del tempo di calcolo. Questo approccio sarà

quello utilizzato prevalentemente in tutto questo corso.

n

Esercizio 1.3 Dato un insieme di 2 interi, utilizzando il modello di calcolo del torneo,

determina quanti confronti sono sufficienti

i) per individuare il massimo e il minimo,

ii) per individuare il massimo e il secondo elemento più grande.

3.3. Dimensione dell'input

Quando vogliamo esprimere il costo di esecuzione di un algoritmo dobbiamo precisare in

funzione di quale parametro del problema forniamo questa rappresentazione. Ad esempio nei

casi visti precedentemente, l'individuazione di un numero in un dato intervallo o la

determinazione del vincitore di un torneo, abbiamo fatto riferimento rispettivamente

all'ampiezza dell'intervallo e al numero di giocatori impegnati nel torneo.

Al fine di standardizzare il concetto di "dimensione" o "taglia" dell'input rispetto alla quale

esprimere la valutazione dell'efficienza di un algoritmo, è stato convenzionalmente adottato il

concetto di lunghezza dell'input, corrispondente al numero di bit (o, più in generale, di

caratteri) che costituiscono l'input di un algoritmo. Ricordando che data una stringa w si

esprime con |w| la sua lunghezza, in generale con |I| indicheremo la lunghezza dell'input I.

Più in generale, in modo meno rigoroso, si tende a fare riferimento a caratteristiche dell'input

più informali ma più intuitive. Ad esempio se si analizzano algoritmi di ordinamento di un

vettore A si fa riferimento al numero n di elementi che lo costituiscono e così pure se si

considerano algoritmi di ricerca su una tabella T di n elementi. Ciò non deve stupire perchè,

se si assume che gli elementi del vettore o della tabella abbiano una lunghezza massima

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.14

prefissata c, il valore n è direttamente proporzionale ai valori |A| e |T| poichè abbiamo |A| = |T|

= c n.

A volte per ottenere una rappresentazione efficace del costo di esecuzione di un algoritmo si

sacrifica il rigore e si fa ricorso a parametri non direttamente proporzionali alla lunghezza

dell'input

Esempio 1.3 Consideriamo il caso di algoritmi che operano su matrici. Quando diciamo

che un algoritmo che opera su matrici di dimensione nn richiede un numero di operazioni

2

quadratico, ovvero dell'ordine di n , vuol dire che esprimiamo la complessità dell'algoritmo

in funzione della dimensione della matrice (cioè del numero delle sue righe o delle sue

colonne). In generale la scelta del parametro di riferimento può incidere sulla valutazione

dell'efficienza di un algoritmo. Se avessimo adottato come parametro di riferimento il

numero di elementi della matrice, la valutazione avrebbe dato un esito diverso. Chiamiamo

2

e tale numero; poiché abbiamo e = n una valutazione dell'efficienza dell'algoritmo in

funzione di questo nuovo parametro ci porterebbe a dire che l'algoritmo è lineare nella

dimensione dell'input, cioè richiede un numero di operazioni dell'ordine di e. Naturalmente

entrambe le valutazioni sono corrette, tuttavia la prima formulazione è indubbiamente più

suggestiva e, in effetti, è la più usata.

Per renderci conto dell'importanza di adottare come dimensione dell'input una grandezza che

varia linearmente o al più polinomialmente con la sua lunghezza, riflettiamo un attimo sul

valore che assume |n| quando n è un numero intero espresso in base 2. Ebbene, in tal caso

abbiamo che tra il valore |n| e il valore n c'è un salto esponenziale; infatti abbiamo che |n| =

   

log n + 1, dove log n rappresenta il massimo intero minore o uguale di log n.

Vediamo un esempio che mette in evidenza in modo palese quali diverse valutazioni si

ottengono se si analizza il costo di esecuzione di un algoritmo numerico utilizzando due

diverse misure dell'input corrispondenti alla lunghezza o al valore dell'input stesso.

Esempio 1.4 Consideriamo il cosiddetto test di primalità di un numero, cioè il problema di

decidere se un dato numero è, o meno, un numero primo. Un banale algoritmo, basato sulla

proprietà che se un numero n non è primo esso deve avere un divisore minore o uguale di

, consiste nel provare tutti i numeri da 2 a e verificare se qualcuno di essi è un

n n

divisore di n. Quante operazioni di divisione richiede questo procedimento? Chiaramente

- 1. Se valutiamo questo numero in funzione dell'input n abbiamo l'impressione di

n

trovarci di fronte a un compito relativamente facile, visto che il suo costo di risoluzione

cresce addirittura meno rapidamente dell' input. Se però effettuiamo una analisi più

accurata, ricordandoci che il costo di risoluzione deve essere valutato in funzione della

lunghezza dell'input, ecco che la difficoltà del problema ci si rivela in modo molto più

chiaro. In tal caso, infatti, poiché abbiamo che, sostanzialmente, |n| = log n, otteniamo che

|n|/2

il numero di operazioni di divisione, valutato in funzione di |n| è 2 e quindi

100

esponenziale. Vediamo un caso concreto. Supponiamo di dover decidere se il numero 2 -

1 è un numero primo. Usando l'algoritmo introdotto precedentemente dobbiamo eseguire

50

circa 2 operazioni di divisione Questo numero è in realtà talmente grande da rendere

praticamente insolubile il problema; se anche utilizzassimo una macchina capace di

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.15 100

eseguire un milione di divisioni al secondo il tempo necessario per verificare se 2 - 1 è

50

un numero primo con questo metodo sarebbe di 2 microsecondi: circa 10 anni !

La differenza tra un algoritmo che, prendendo in ingresso un numero n richiede un numero

di operazioni lineare in n e uno che richiede un numero di operazioni lineare in funzione della

lunghezza di n può essere dunque abissale ed è pertanto necessario fare la massima attenzione

a definire esattamente in funzione di quale parametro stiamo esprimendo la complessità

dell'algoritmo.

Domanda 1.4 Considera i seguenti problemi:

 determinare il massimo di un insieme di interi di valore compreso tra O

e MAXINT, dove MAXINT è il massimo intero rapprsentabile con 4 byte

 moltiplicare due polinomi a coefficienti interi di valore compreso tra

-MAXINT e +MAXINT,

 calcolare il fattoriale di un numero intero.

In funzione di quali parametri dell'input ritieni efficace e corretto

esprimere la complessità di algoritmi per la loro soluzione?

3.4. Tipi di analisi

Per effettuare l'analisi della complessità di algoritmi e programmi dobbiamo individuare una

funzione che esprima il costo di esecuzione dell'algoritmo stesso, al variare della dimensione

dell'input. Naturalmente se volessimo esprimere con una funzione l'esatta quantità di risorsa

utilizzata per la risoluzione di un problema incontreremmo delle notevoli difficoltà dovute

alla grande quantità di dettagli implementativi di cui dovremmo tenere conto e difficilmente

riusciremmo ad esprimere in modo analitico, cioè con un'espressione matematica, la

grandezza in questione.

Pensiamo, a titolo di esempio, ancora al problema della primalità di un numero. Ricordiamo

quale è il valore dei numeri primi minori di 20: 2,3,5,7,11,13,17,19. Il metodo alquanto

|n|/2

banale che abbiamo supposto di utilizzare richiede, come abbiamo già visto, al più 2

operazioni, tuttavia nel caso che il numero fornito in input sia un numero pari è chiaro che

una sola divisione, la divisione per 2, sarà sufficiente per verificare che il numero non è

primo. Se il numero è multiplo di tre basteranno due divisioni, se è multiplo di cinque ne

basteranno tre e così via. Sfortunatamente un'espressione matematica che in forma esplicita

rappresenti esattamente il numero di divisioni necessarie per verificare se un dato numero n è

un numero primo o no non è nota e sarebbe comunque talmente complessa essa stessa da

risultare poco comprensibile. E' per tale motivo che si usa la limitazione meno stringente ma

|n|/2

piu' chiara 2 .

In generale, dunque, è preferibile esprimere la complessità di un algoritmo mediante una

funzione che:

- delimiti superiormente il valore esatto

- esprima in modo chiaro come il costo di soluzione del problema varia al crescere della

dimensione dell'input. P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.16

Questo tipo di analisi viene detto analisi asintotica del caso peggiore. Chiariamo

separatamente cosa intendiamo per analisi asintotica e cosa intendiamo per analisi del caso

peggiore.

Parliamo di analisi asintotica poichè la valutazione del costo di risoluzione mette

essenzialmente in evidenza come tale costo va all'infinito al tendere all'infinito della

dimensione dell'input. E' chiaro che, da tale punto di vista, eventuali fattori costanti o termini

di ordine inferiore vengono ignorati. Ad esempio, noi diciamo che un algoritmo ha una

2

complessità dell'ordine di n anche se una valutazione più precisa del costo di esecuzione

2

dell'algoritmo stesso darebbe il risultato c n + b n

Per esprimere una valutazione asintotica di complessità è stata introdotta una notazione

derivata essenzialmentente dall'analisi classica: la notazione O (detta anche "o grande").

Definizione 1.1 Una funzione f è O (g) (dell'ordine di g ) se esistono una costante c e un

valore n' tale che, per ogni n >n', f(n) cg(n) . La complessità di un algoritmo, misurata in

termini di una data risorsa, è O (g) se la quantità di risorsa richiesta per l'esecuzione

dell'algoritmo è O (g).

Utilizzando la notazione "o grande" possiamo dire, ad esempio, che l'algoritmo per il test di

|n|/2

primalità di un intero n, visto nell'Esempio 4, ha una complessità O(2 ).

2

Domanda 1.5 Data la funzione f(n) = c n + b n quali delle seguenti affermazioni sono

corrette?

a) f(n) è O(n)

2

b) f(n) è O(n )

3

c) f(n) è O(n ).

L'uso dell'analisi asintotica nella valutazione del costo degli algoritmi dà un'indicazione molto

utile dell'andamento di tale costo al crescere della dimensione del problema affrontato. Esso,

tuttavia, ha dei limiti dovuti al fatto che le costanti e i termini di ordine inferiore vengono

ignorati. Di conseguenza, due programmi di costo n log n, l'uno, e 1000 n log n, l'altro,

vengono considerati della stessa complessità O(n log n). Più grave ancora è che se un

2

programma ha costo 1000 n logn e un altro ha costo n il primo è considerato

(asintoticamente) migliore del secondo anche se il costo di esecuzione del secondo risulta, in

realtà, inferiore fino ad n=10000.

Nonostante questi inconvenienti l'analisi asintotica viene ritenuta utile per determinare una

prima informazione di carattere globale sul costo di esecuzione di un programma.

Naturalmente se si deve stabilire come si comporta il programma per particolari valori

dell'input (come quando si devono confrontare, a fini pratici, due programmi destinati ad

operare su valori di n relativamente "piccoli" oppure quando si devono rispettare vincoli

temporali molto stringenti) le costanti e i termini di ordine inferiore non possono più essere

ignorati e l'analisi deve essere maggiormente raffinata.

Veniamo ora al concetto di analisi del caso peggiore. Con questo termine intendiamo dire che

per valutare il costo dell'algoritmo teniamo conto, per ogni valore n della dimensione

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.17

dell'input, del costo richiesto dai casi più complessi tra quelli che hanno dimensione n.

Sempre con riferimento al problema dei numeri primi, ad esempio, teniamo conto del fatto

n/2

che, tra i numeri di lunghezza n, sono proprio i numeri primi che richiedono 2 operazioni

per essere riconosciuti. Analogamente, nel caso dell'ordinamento in senso crescente di un

vettore di n elementi con il metodo "a bolle" diciamo che il costo di esecuzione è dell'ordine

2

di n perchè questo è ciò che accade nel caso peggiore, cioè se il vettore è ordinato in senso

decrescente, mentre noi sappiamo che se il vettore è già ordinato in senso crescente il metodo

"a bolle" esegue soltanto n confronti.

Naturalmente, come abbiamo già messo in evidenza in precedenza, in alcune applicazioni,

anziché tenere conto del caso peggiore è più utile tenere conto di ciò che accade nella

generalità dei casi. Più precisamente, se abbiamo informazioni sufficienti, possiamo calcolare

il costo di esecuzione per i diversi possibili input e determinare la media dei costi ottenuti. In

questo caso parliamo di analisi del caso medio. Anche nell'analisi del caso medio in genere si

utilizza un approccio asintotico, cioè si mette in evidenza solo l'andamento all'infinito del

costo di esecuzione, al crescere della dimensione dell'input. Un esempio significativo di

algoritmo che risulta sensibilmente più efficiente nel caso medio di quanto non sia nel caso

peggiore è il metodo di ordinamento "quicksort" (ordinamento rapido). Infatti tale algoritmo

2

(che sarà studiato nel capitolo 3 di questo Corso) esegue un numero di confronti O(n ) nel

caso peggiore ma solo O(n log n) nel caso medio.

Vediamo ancora un semplice esempio di applicazione dei concetti esposti fin qui.

Esempio 1.5 Consideriamo il problema di calcolare la potenza k-esima di un intero a cioè

ak , e cerchiamo di individuare un algoritmo per il calcolo di questo valore. Il metodo più

banale cui possiamo pensare consiste nel moltiplicare a per se stesso k-1 volte. Come

possiamo valutare la complessità di questo metodo? Chiaramente la misura di complessità

che possiamo usare per questo semplice calcolo è proprio il numero di moltiplicazioni

utilizzate; questo numero dovrà essere espresso in funzione della dimensione dell'input,

cioè in funzione di |a| e |k|. Definiamo m = |a| ed n = |k|. Il costo di esecuzione dell'algoritmo

n

è dunque pari a k - 1, cioè O(2 ) moltiplicazioni. Come si vede il costo è indipendente dal

parametro m ma, asintoticamente, varia con n in modo addirittura esponenziale. Potremmo

trovare un metodo più efficiente?. Vediamo il seguente metodo. Quando dobbiamo

k

calcolare 2 se k è una potenza di 2 il problema è abbastanza semplice: ad esempio se k = 8

22 4 22 . 22 28 24 . 24.

possiamo calcolare prima = 4, poi 2 come e infine come Il tutto

richiede quindi non k - 1 moltiplicazioni (cioè 7), come nel caso dell'algoritmo visto

precedentemente, ma semplicemente 3. Supponiamo ora che k non sia una potenza di 2. In

tal caso possiamo determinare lo sviluppo di k in potenze di 2, ovvero la sua

rappresentazione binaria, calcolare i contributi delle varie potenze di due e poi ottenere il

risultato richiesto moltiplicando tra di loro i vari contributi. Sia ad esempio k = 13. La

. .

k 8 4

rappresentazione binaria è 1101. Ciò significa che 2 = 2 2 2 e che, quindi, dobbiamo

calcolare il contributo della potenza ottava, della quarta e della prima mentre la potenza

seconda non dà alcun contributo. Una volta calcolati i vari contributi dobbiamo

semplicemente moltiplicarli tra di loro. Naturalmente il metodo può essere applicato

esattamente nello stesso modo se anziché calcolare le potenze di 2 calcoliamo le potenze di

una qualunque base. Adesso possiamo calcolare quante moltiplicazioni richiede questo

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.18

metodo: se n = |k| ne occorrono semplicemente n - 1 per determinare le potenze di a e

successivamente altre n - 1 per moltiplicare i contributi necessari nel caso peggiore, cioè se

tutti i contributi sono presenti (nell'esempio visto questo secondo passo richiedeva meno

2

moltiplicazioni perché il contributo 2 era assente). Assumendo che le moltiplicazioni

comportino un costo unitario, abbiamo quindi un costo complessivo 2n-2 che,

asintoticamente, corrisponde ad un costo O(n), cioè lineare nella lunghezza dell'input.

Esercizio 1.4 Determina il numero di confronti ed il numero di scambi richiesti, nei casi

peggiori, dall'algoritmo di ordinamento "quicksort"; esprimi tali valori con

la notazione O e determina in quali situazioni vantaggiose l'algoritmo può

richiedere un numero sensibilmente inferiore di confronti e di scambi.

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.19

4. ANALISI DI EFFICIENZA DI PROGRAMMI SCRITTI IN LINGUAGGIO AD

ALTO LIVELLO

4.1. Introduzione

Per poter calare i concetti di analisi degli algoritmi visti fin qui nella pratica della

programmazione è necessario comprendere come si effettua l'analisi di complessità di

algoritmi formulati in linguaggi di programmazione ad alto livello. L'uso di modelli calcolo

formali, come le macchine di Turing e le RAM, infatti, come si è già detto, risulterebbe

eccessivamente gravoso

Nella sezione precedente abbiamo già valutato in vari casi il costo di esecuzione di algoritmi

descritti informalmente e, inoltre, abbiamo fatto riferimento a programmi scritti in Java

incontrati nei corsi di informatica del primo anno. In tali casi abbiamo adottato come misura

di complessità le operazioni più significative che venivano eseguite da tali programmi. Ad

esempio la complessità di algoritmi di ordinamento è stata misurata in termini del numero di

confronti e scambi eseguiti, algoritmi di elevamento a potenza sono stati valutati utilizzando

il numero di moltiplicazioni ecc. In realtà, anche se questo approccio rappresenta un modo

semplificato per misurare la complessità di un programma in linguaggio ad alto livello, se

esso viene applicato correttamente può dare risultati sufficientemente significativi. A tal fine

è necessario che sia ben chiaro quali sono tutte le ipotesi semplificative che vengono fatte.

In questa sezione vedremo come un programma in linguaggio ad alto livello possa nascondere

molti elementi che possono alterare la valutazione della complessità e vedremo quindi in

quali condizioni è possibile fare ricorso ad un'analisi basata semplicemente sul conteggio

delle operazioni dominanti.

4.2. Analisi dettagliata di programmi in linguaggio ad alto livello

Se vogliamo valutare in modo dettagliato il costo di un programma in linguaggio ad alto

livello possiamo procedere in modo molto simile a quanto abbiamo visto nel caso delle

macchine a registri, utlizzando, cioè un modello a costi uniformi. Assumendo che le

operazioni elementari abbiano tutte un costo unitario dobbiamo moltiplicare tale costo per il

numero di volte in cui l'operazione viene ripetuta (nel caso che essa si trovi ad esempio dentro

un ciclo). Un programma in linguaggio ad alto livello, però, può rendere difficile un'accurata

analisi della complessità. Quanto abbiamo visto nella Sezione 2 di questo Capitolo (e cioè il

modo di procedere formale che viene utilizzato nel caso di macchine a registri e che tiene

conto di tutti i costi in gioco) ci sarà utile per considerare tutti i dettagli implementativi che

possono essere nascosti dall'uso di un linguaggio ad alto livello.

Esempio 1.6 Supponiamo di avere il seguente frammento di programma:

for (int n=1; n<=m; i++) x=x+n;. P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.20

Se immaginiamo di implementare questo frammento di programma su una macchina a

registri (o su un reale elaboratore), ci rendiamo conto che il suo costo è dovuto non solo

alla ripetizione dell'istruzione x := x + n, che appare esplicitamente, ma anche alla

ripetizione di un'incremento della variabile n, il cui valore deve variare da 1 a m e di un

test sulla variabile stessa, che regola la ripetizione del ciclo fino a che n non ha assunto il

valore m. Poiché tali istruzioni vengono ripetute m volte, al variare di n da 1 a m, il costo

complessivo sarà 3m.

Ma in un programma scritto in linguaggio ad alto livello ci possono essere altri costi occulti.

Ad esempio dobbiamo tener conto della quantità di tempo necessaria per effettuare operazioni

che pur essendo primitive del linguaggio non possono realisticamente essere considerate di

costo unitario (come le funzioni matematiche standard sqrt , exp ecc. o come l'assegnazione

tra matrici). Inoltre, se analizziamo il consumo di memoria da parte di un programma

ricorsivo dovremo calcolare esplicitamente la quantità di memoria richiesta dalla pila per la

gestione di chiamate ricorsive di procedura

Per chiarire questi aspetti vediamo l'analisi dettagliata di due programmi scritti in linguaggio

ad alto livello, un programma iterativo per il calcolo del fattoriale e un programma ricorsivo

per lo stesso problema.

Esempio 1.7 Si considerino i seguenti metodi Java che, dato un intero n forniscono il

valore del fattoriale di n:

public static int fact1 (int n)

{ int fattoriale=1;

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

fattoriale*=i;

return fattoriale;

}

public static int fact2 (int n)

{ if (n = 0) return 1

else return n*fact2(n-1);

}

Come possiamo constatare, ad un'analisi sommaria i due programmi non appaiono molto

diversi dal punto di vista del costo di esecuzione. Entrambi i programmi devono eseguire n

moltiplicazioni per calcolare n! e, complessivamente, è facile verificare che per entrambi il

tempo di esecuzione è O(n) Se però passiamo ad un'analisi accurata dello spazio utilizzato ci

accorgiamo che il costo di esecuzione dei due programmi è diverso. Infatti il programma

FACT1 utilizza solo quattro celle di memoria per contenere le variabili i, k, n, fattoriale. In

questo caso diciamo che lo spazio è O(1). Nel caso del programma FACT2, invece, lo spazio

utilizzato asintoticamente è sensibilmente maggiore di quello utilizzato dal programma

FACT1 poiché è necessario tenere conto dello spazio richiesto per allocare nella pila, durante

le chiamate ricorsive, i valori via via assunti dalla variabile FACT2. Poiché abbiamo n

chiamate ricorsive otteniamo che lo spazio richiesto è O(n).

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.21

4.3. Costo di un programma in termini di operazioni dominanti

Nonostante le cautele messe in evidenza nel paragrafo precedente l'analisi del tempo di

esecuzione di un programma può essere molto semplificata se si introduce il concetto di

istruzione dominante.

Definizione 1.2 Dato un programma il cui costo di esecuzione è O(t(n)) definiamo

un'istruzione istruzione dominante (e l'operazione da essa eseguita operazione dominante )

quando, per ogni intero n, il suo contributo al costo di esecuzione, nel caso peggiore di input

di dimensione n, è d(n) e soddisfa la relazione c d(n) ≥ t(n) per un'opportuna costante c, cioè

t(n) è O(d(n))

L' istruzione (o operazione) dominante è dunque quell'istruzione il cui costo di esecuzione è

tale, appunto, da dominare il costo di esecuzione dell'intero programma. E' chiaro che, per una

valutazione asintotica del costo di esecuzione di un programma, è del tutto sufficiente

determinare il costo dovuto all' operazione dominante. In tal modo si evita di quantificare

tutte le altre operazioni (trasferimenti, operazioni aritmetiche, salti condizionati e non) i cui

costi sono comunque dominati da essa.

Esempio 1.8 Consideriamo il frammento di programma già visto precedentemente:

for (int n=1;n<m;n++) x += n;

i costi di esecuzione di questo frammento valutati tenendo conto non solo della ripetizione

della istruzione x+ = n ma anche dell'aggiornamento della variabile n e del test sul suo

valore, in realtà sono dominati dal solo costo dell'operazione x += n.

Domanda 1.6 Quali sono le operazioni dominanti dei programmi FACT1 e FACT2?

Esercizio 1.5 Considera il seguente programma noto come "ordinamento mediante

inserimento" (insertion sort).

public static void insertionSort ( int[] A)

{ int b,j;

for (int i=1; i<A.length(); i++)

{ b=A[i]; j= i-1;

while ((j >= 1 ) && (b < A[j])

{ A[j+1]= A[j];j--;

}

A [j+1] = b;

}

}

Determina il costo di esecuzione nel caso peggiore, valutando

dettagliatamente il costo di tutte le istruzioni, e individua l'istruzione

dominante.

4.4. Un modello più preciso: il modello a costi logaritmici

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.22

Il metodo di analisi che abbiamo utilizzato finora è certamente il più semplice e più usato per

determinare il costo di esecuzione di un programma. Esso, come si è visto, è basato sul

modello di calcolo a costi uniformi, in cui tutte le istruzioni hanno un costo unitario e l'analisi

consiste semplicemente nel valutare quante volte (nel caso peggiore o nel caso medio) ogni

istruzione viene eseguita.

Un problema che può mettere in dubbio la validità dei risultati ottenuti applicando il metodo

dell'analisi asintotica a programmi valutati nel suddetto modo è però il seguente. Nel modello

considerato si ipotizza che ogni istruzione abbia un costo unitario indipendentemente dal

valore degli operandi; ad esempio, la moltiplicazione di due numeri costa sempre 1 sia che si

moltiplichino numeri di otto bit sia che si moltiplichino numeri di mille bit. Questa scelta è

legata, in modo implicito, al fatto che, sostanzialmente, facciamo riferimento, come modello

di macchina, alla macchina a registri in cui ogni registro contiene un numero arbitrariamente

grande.

Se vogliamo essere più realisti dobbiamo tener conto del fatto che nessun elaboratore reale

può operare con una sola istruzione di macchina su numeri arbitrariamente grandi e quindi se

dobbiamo effettuare la moltiplicazione tra numeri di mille bit dobbiamo realizzare una

procedura che via via opera su frammenti, ad esempio, di 16 o 32 bit. Ciò significa, in pratica,

che dobbiamo cambiare il modello di macchina e anche il modo di misurare il costo di

esecuzione di un programma.

Il modello che si usa in questi casi viene chiamato a costi logaritmici e si differenzia da

quello a costi uniformi usato precedentemente in quanto il costo temporale di ogni istruzione

è proporzionale alla dimensione (numero di bit) degli operandi. In tal modo se eseguiamo la

moltiplicazione tra due interi n ed m il costo non è più 1 ma log n + log m. Analogamente

dobbiamo tenere conto che l'accesso all'elemento i-esimo di un array non può avere un costo

unitario indipendente da i ma ha un costo proporzionale al logaritmo di i. Infine, se vogliamo

determinare la quantità di memoria utilizzata dobbiamo tenere presente che per memorizzare

la variabile n è necessario spazio |n|, cioè O(log n). Applichiamo il metodo dell'analisi a costi

logaritmici ad un esempio già visto in precedenza.

Esempio 1.9 Consideriamo il costo del programma FACT1 per il calcolo del fattoriale, già

considerato nell'Esempio 1.7. Il costo in termini di tempo del programma FACT1 istruzione

per istruzione può essere determinato come segue:

1. costo: 1 (costante)

2. costo: log n (per il confronto n > 0)

3. costo: n volte i costi seguenti:

log i (per l'incremento della variabile i) +

+ log n (per il test i=n, sul valore della variabile i)

+ (log k) + (log i) (per l'istruzione k := k i)

*

4. costo: log k 

Poiché k è la variabile in cui si costruisce il valore del fattoriale di n abbiamo k n! e quindi

  

log k n log n. Inoltre, poiché i n abbiamo che il costo dell'istruzione 3 è n(3log n + n

log n). In conclusione il tempo di esecuzione del programma FACT1 in funzione del valore

n è P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.23

2 2

t (n) 1 + log n + 4n log n + n log n = O (n log n)

FACT1

Per quanto riguarda lo spazio, tenendo conto del fatto che le variabili i, k e FACT1

contengono al massimo, rispettivamente, i valori n, n! ed n! abbiamo

s (n) |n| + 2 |n!| = log n + 2 n log n = O(n log n)

FACT1

Come si vede il risultato è sostanzialmente diverso da quello O(n) che abbiamo ottenuto con

l'analisi a costi uniformi.

Un secondo esempio ci potrà convincere ulteriormente che l'analisi a costi logaritmici è più

corretta di quella a costi uniformi. Prima di procedere, tuttavia, lo studente risponda alla

seguente domanda e confronti la risposta con la risposta alla Domanda 1.8.

Domanda 1.7 Nel caso che si applichi al programma FACT1 l'analisi a costi logaritmici quali

sono le operazioni che con il loro costo dominano il costo complessivo del

programma? n

2

Esempio 1.10 Consideriamo il seguente semplice programma per il calcolo di 2 (basato

su un'idea già applicata nell'Esempio 1.5):

public static int superexp (int n){

int s=2;

if (n > 0)

for(int i = 1; i<n; i++) s = s * s;

return s

}

Poichè il programma in effetti esegue semplicemente n moltiplicazioni e poichè la

moltiplicazione è l'operazione dominante, l'analisi a costi uniformi ci porterebbe a

determinare immediatamente un costo O(n). Cosa accade invece con l'analisi a costi

logaritmici? Poichè il valore della variabile superexp e, quindi i valori dei fattori della

n

2

moltiplicazione, aumentano, durante l'esecuzione del ciclo for, da 2 a 2 il costo

n

2 n

complessivo del programma è O(n log (2 )) e cioè O(n 2 ). Tale risultato è molto più

realistico soprattutto se si tiene conto che la lunghezza (in numero di bit) del risultato del

n

calcolo della funzione superexp(n) è 2 e non si può accettare che in tempo lineare O(n) si

n

possa produrre un risultato che richiede 2 bit per essere espresso.

Per tranquillizzare lo studente possiamo, tuttavia, anticipare subito che la situazione

presentata nell'Esempio 10 è molto particolare e che, nella maggioranza dei casi, sotto

opportune ipotesi, l'analisi a costi logaritmici può essere semplificata e ricondotta all'analisi a

costi uniformi vista nei paragrafi precedenti.

Un primo argomento che ci può consentire di semplificare l'analisi di un programma in

linguaggio ad alto livello e di giungere ad esprimere la complessità di un programma

semplicemente in base al numero di volte in cui viene eseguita l'operazione dominante è il

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.24

seguente. In molti problemi la variabilità dell'input riguarda principalmente il numero di

elementi che sono oggetto di elaborazione e non la dimensione di ciascuno di essi, che può,

anzi, senza difficoltà, essere considerata limitata.

Supponiamo, ad esempio, di dover effettuare l'ordinamento di un array di n elementi. In

questo caso è abbastanza naturale esprimere la complessità del programma di ordinamento

semplicemente mediante il numero di operazioni di confronto che vengono eseguite in

funzione di n senza tenere conto del fatto che ogni operazione di confronto, ad esempio tra gli

elementi A[i] e A[j], può avere un costo dell'ordine di log A[i] + log A[j]. E' chiaro, infatti, che

per valutare la complessità di un programma di ordinamento e per confrontarlo con altri si

può considerare, senza perdere di generalità, che gli elementi dell'array abbiano valori

variabili in un intervallo 0, … , A (dove A è una costante opportuna il cui valore è

MAX MAX

sufficiente a delimitare tutti i possibili valori degli elementi dell'array) e che, quindi, il costo

di esecuzione di ogni operazione di confronto sia limitato dalla costante log A .

MAX

Una seconda considerazione che ci può consentire di semplificare l'analisi riguarda la

valutazione dell'indirizzamento indiretto o, in altri termini, la valutazione del costo

dell'accesso agli elementi di un array. In molti casi è ragionevole supporre che le operazioni di

gestione degli indici di un array (come incremento e decremento dell'indice) e lo stesso costo

di accesso ai singoli elementi dell'array abbiano un costo unitario anziché logaritmico in

funzione del valore dell'indice. Una motivazione per questa scelta è che il numero di elementi

di un array indirizzabili, ad esempio, con una sola parola di 32 bit (e gestibili perciò con

32

operazioni di costo unitario) è 2 e quindi ampiamente sufficiente per tutte le applicazioni

reali, in cui si tratta di gestire array di un numero di elementi nettamente inferiore.

Vediamo ora attraverso un ulteriore esempio, come l'analisi a costi logaritmici possa essere

semplificata e come ci si possa ricondurre agli stessi risultati che si ottengono basandosi

sull'operazione dominante.

Esempio 1.11 Consideriamo nuovamente il programma di ordinamento chiamato insertion

sort presentato nell'Esercizio 1.5. Esaminiamo innanzitutto il costo di esecuzione di tale

programma istruzione per istruzione

1. log i ripetuta n - 1 volte

2. log i + log A[i] ripetuta n - 1 volte

3. log (i - 1) ripetuta n - 1 volte

4. 2 log j + log A [j] + log b ripetuta 1 +…+ (n-1) volte al più

5. log j + log A [j] ripetuta 1 +…+ (n-1) volte al più

6. log j ripetuta 1 +…+ (n-1) volte al più

7. log (j+1) + log b ripetuta n - 1 volte

Tenuto conto del fatto che i varia da 2 ad n, che nel caso peggiore j varia da i - 1 ad 1 e che,

 

per ogni i, abbiamo A[i] A e b A otteniamo complessivamente che il tempo di

MAX MAX

esecuzione del predetto programma è

 

t (n) (n - 1) ( 4 log n + 2 log A ) + j (4 log n + 3 log A )

MAX MAX

j=1,n-1

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.25

 2

Tenendo conto del fatto che j = n(n-1)/2 otteniamo l'espressione asintotica: O(n

j=1,n-1

(logn + log A ))

MAX

Se, come abbiamo detto precedentemente, facciamo l'ipotesi semplificativa che il valore

A sia considerato costante, otteniamo che il costo di esecuzione del programma

MAX 2

insertion sort è t(n) = O (n log n)

Se teniamo conto anche dell'ipotesi che il costo di gestione degli indici del vettore

(aggiornamento degli indici, accesso agli elementi ecc.) sia da considerarsi unitario abbiamo

un'ulteriore semplificazione. In tal caso infatti i costi delle istruzioni divengono

rispettivamente

1. 1 ripetuta n - 1 volte

2. 1 + log A[i] 1 + log A ripetuta n - 1 volte

MAX

3. 1 ripetuta n - 1 volte

4. 2+log A[j]+log b 2+2log A ripetuta 1 +…+ (n-1) volte al più

MAX

5. 1 + log A[j] 1 + log AMAX ripetuta 1 +…+ (n-1) volte al più

6. 1 ripetuta 1 +…+ (n-1) volte al più

7. 1 + log b ripetuta n - 1 volte

2

e quindi il costo complessivo diviene t(n) = O(n ) che coincide con il costo determinato con

l'analisi a costi uniformi.

Come si è potuto vedere negli esempi forniti, esistono dunque circostanze (come nel caso di

algoritmi numerici basati su operazioni aritmetiche) in cui si rende necessario utilizzare il

modello a costi logaritmici per evitare di fare un'analisi grossolana e imperfetta e altre

circostanze, più frequenti, in cui il modello a costi uniformi consente di ottenere una

valutazione sufficientemente accurata.

Nel resto di questo Corso si farà sempre uso dell'approccio più semplice basato sul conteggio,

a costi uniformi, delle istruzioni dominanti eseguite dal programma. Tuttavia non dobbiamo

sottovalutare il fatto che solo rendendoci conto del significato delle semplificazioni viste e

della loro applicabilità possiamo essere certi di non avere trascurato nessun elemento

importante ai fini di una corretta valutazione del programma.

Esercizio 6 Scrivi un programma in Java per determinare l'elemento massimo di un array;

analizzane la complessità sia in modo esatto con il modello a costi logaritmici,

sia tenendo conto delle ipotesi semplificative.

P

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.26

5. COMPLESSITA' INTRINSECA DI PROBLEMI

5.1. Limiti inferiori e superiori alla complessità di un problema.

Quando abbiamo mostrato i diversi modi di procedere per giungere ad indovinare un numero

compreso tra 1 ed n con il minimo numero di tentativi, abbiamo mostrato che un metodo

basato sulla ricerca binaria consente di risolvere tale problema sistematicamente con un

numero di tentativi O(log n). In tale occasione abbiamo anche osservato che il numero di

2

 

log n tentativi rappresenta una soglia al di sotto della quale non è possibile scendere. Tale

2  

soglia è dovuta al fatto che il valore log n corrisponde alla quantità di informazione

2

necessaria per individuare un oggetto in un insieme di n oggetti. Esso corrisponde infatti al

numero di bit necessari a rappresentare un qualunque numero compreso tra 0 ed n-1.

Qualunque metodo generale per determinare un oggetto tra n oggetti, e che sia basato non

sulla sorte ma su una sequenza sistematica di domande a risposta binaria, deve quindi

   

necessariamente produrre, almeno nel caso peggiore, log n bit e comporta quindi log n

2 2

tentativi.

La soglia di complessità che abbiamo individuato è, in un certo senso, una misura della

complessità intrinseca del problema dato. E' stato questo, dunque, il primo esempio di analisi

della complessità intrinseca di un problema che abbiamo incontrato. Per semplice che esso sia

possiamo utilizzarlo per fare alcune considerazioni.

Per caratterizzare la complessità di un problema abbiamo bisogno, fondamentalmente, di due

riferimenti.

Prima di tutto dobbiamo sapere quale è, nel caso peggiore, la quantità di tempo (o di

memoria) sufficiente per la risoluzione del problema dato. Questa quantità rappresenta un

limite superiore (un upper bound ) della complessità del problema. A tal fine è sufficiente

conoscere qualche algoritmo (non necessariamente il migliore) per la risoluzione del

problema dato e valutarne la complessità con uno dei metodi visti nelle sezioni precedenti.

La conoscenza di un upper bound, tuttavia, non ci dà un'informazione completa sulla

complessità del problema, infatti potrebbero esistere metodi di risoluzione del problema dato

diversi da quelli noti che ne consentono la soluzione in modo molto più rapido. Sapere che un

problema è risolubile con un algoritmo di costo esponenziale, ad esempio, non ci dice molto

sulla reale complessità del problema che, al limite, potrebbe essere anche lineare.

L'informazione data dall'upper bound deve dunque essere confrontata con una limitazione

inferiore (un lower bound ) cioè con un'indicazione della quantità di tempo (o di memoria)

che, sempre nel caso peggiore, è sicuramente necessaria (anche se non sufficiente) per la

risoluzione del problema.

E' qui che interviene il concetto di complessità intrinseca del problema. Per determinare un

lower bound di complessità di un problema è necessario, infatti, dimostrare che nessun

algoritmo per la risoluzione del problema stesso può fare a meno di utilizzare una certa


PAGINE

38

PESO

280.25 KB

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

Introduzione alla Analisi di Algoritmi. Nello specifico gli argomenti trattati sono i seguenti: complessità di algoritmi, complessità di problemi, modelli di macchina e misure di complessità, dimensione dell'input, tipi di analisi, analisi dettagliata di programmi in linguaggio ad alto livello.


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria informatica
SSD:
A.A.: 2009-2010

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Novadelia di informazioni apprese con la frequenza delle lezioni di Analisi Algoritmi e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Ingegneria Prof.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!