FONDAMENTI DI INFORMATICA I - CNRstaff.icar.cnr.it/.../upload/lezioni/complessita2010.pdf · 2010....

FONDAMENTI DI INFORMATICA I

INTRODUZIONE ALL’ANALISI DI ALGORITMI

1. INTRODUZIONE

Quando realizziamo un programma per risolvere un determinato problema mediante il calcolatore, dobbiamo tenere presente che, per essere realmente utilizzabile, il nostro programma deve soddisfare diverse proprietà; in particolare deve essere, innanzitutto, corretto ed efficiente. In questo corso la nostra attenzione sarà principalmente rivolta ai metodi di analisi dell'efficienza degli algoritmi e alle tecniche di progettazione di algoritmi efficienti.

Per iniziare a trattare tali argomenti, introdurremo i concetti di efficienza di algoritmi e programmi e i metodi con cui tale efficienza può essere analizzata; infine chiariremo anche che relazione c'è tra l'efficienza degli algoritmi (o dei programmi) e la complessità dei problemi che con tali algoritmi intendiamo risolvere.

Obiettivo di questo parte del corso è l'acquisizione della capacità di valutare il costo di esecuzione di un algoritmo o di un programma in modo da poter confrontare vari algoritmi per la risoluzione di un problema e scegliere quello le cui caratteristiche di efficienza corrispondono alle esigenze dell'utente.

Per la risoluzione di un problema sono in genere disponibili più algoritmi dotati di diverse caratteristiche di efficienza. Nella Sezione 2 vedremo un semplice esempio che chiarisce questo fatto.

I diversi algoritmi per la risoluzione di un problema, in genere, utilizzano, durante l'esecuzione, quantità di tempo e quantità di memoria diverse. Per poter scegliere l'algoritmo o il programma più adatto alle esigenze dell'utente è necessario imparare a valutarne il costo di esecuzione in modo formale. Innanzitutto è necessario esprimere l'algoritmo facendo riferimento ad un modello di calcolo astratto (come la macchina a registri) o un linguaggio di programmazione reale (come il Pascal o il C++ o Java). Poi dobbiamo individuare quale misura di complessità considerare (tempo, memoria, numero di operazioni di tipo particolare

Fondamenti di Informatica I Introduzione all’Analisi di Algoritmi Pag. 2

ecc.) e quale parametro scegliere per esprimere la variabilità dell'input, in funzione della quale misuriamo il costo di esecuzione (ad esempio possiamo assumere il numero di caratteri di cui è composto l'input o, secondo i problemi trattati, altri tipi di grandezze). Infine dobbiamo decidere se ci interessa valutare il comportamento dell'algoritmo nel caso peggiore o nel caso medio . Questi concetti sono introdotti nella Sezione 3.

Nella Sezione 4 vedremo come i concetti introdotti si applicano al caso dell'analisi di un algoritmo scritto in linguaggio ad alto livello e poi, più in particolare, come si può semplificare l'analisi limitandosi a valutare il numero di volte in cui una particolare operazione del nostro programma, detta operazione dominante, viene eseguita.

Nella Sezione 5, introdurremo i concetti di limite superiore (upper bound ) e limite inferiore (lower bound ) alla complessità di un problema.

Nella Sezione 6, applicheremo le tecniche di analisi di complessità per alcuni semplici algoritmi per due problemi classici: l’ordinamento di un vettore e la ricerca di un elemento in un vettore.

Nella Sezione 7, infine, introdurremo due strutture dati classiche, pile e code, e valuteremo la complessità dei metodi per la loro manipolazione.


1. COMPLESSITA' DI PROGRAMMI E COMPLESSITA' DI PROBLEMI

1.1. Introduzione

In questa prima sezione cercheremo di chiarire, innanzitutto in modo intuitivo, cosa si intende per complessità di un programma e per complessità di un problema ma prima di fornire esempi e definizioni più formali, facciamo alcune premesse.

Iniziamo dal concetto di problema. In termini molto generali possiamo definire un problema come segue. Dato un alfabeto Σ e l’insieme Σ* delle stringhe su di esso, un problema P è una funzione da Σ* a 2Σ* tale che per ogni stringa x (istanza del problema), P(x) è un insieme di stringhe (soluzioni dell’istanza del problema), eventualmente vuoto (se l’istanza del problema non ha soluzioni). Il dominio del problema P, indicato come dom(P), è l’insieme delle stringhe x, per le quali P(x) non è vuoto. Il problema P può essere definito in maniera analoga come una funzione parziale a multi-valori da Σ* a Σ*, cioè una relazione su Σ×Σ; la funzione è definita solo su dom(P).

Un problema P è detto: − di ricerca se per ogni x in dom(P), P(x) è finito; − deterministico se per ogni x in dom(P), P(x) è un singoletto; − di decisione se per ogni x in dom(P), P(x) vale {si} oppure {no}.

Dato un problema di ricerca P, un problema O di ottimizzazione associato a P è un problema tale che dom(P) = dom(O) e per ogni x in dom(P), O(x) ⊆ P(x), cioè le soluzioni di O sono alcune delle soluzioni di P che soddisfano particolari condizioni di ottimizzazione (di minimo o massimo).

Un algoritmo A di risoluzione di un problema P è una sequenza finita di istruzioni che calcola P tale che ogni istruzione sia eseguibile da un particolare esecutore (essere umano o automa) in un tempo finito, anche se può accadere che la esecuzione complessiva non termini poiché potrebbe essere richiesto di ripetere le stesse istruzioni un numero illimitato di volte. Un programma in un linguaggo qualsiasi di programmazione è un algoritmo; in tal caso l’esecutore è il calcolatore.

I problemi risolvibili (o calcolabili) sono quelli per i quali esiste un programma di risoluzione. Non tutti i problemi sono risolvibili. Ad esempio, il seguente problema delle corrispondenze non è risolvibile: dati due insiemi di stringhe S1 e S2, trovare una stringa x tale che essa sia contemporaneamente la concatenazione di stringhe in S1 e la concatenazione di stringhe in S2. Una istanza del problema è S1 = {01, 00, 110} e S2 = {001, 1}; una soluzione è 0011001, ottenibile sia come 00 ⋅ 110 ⋅ 01 sia come 001 ⋅ 1 ⋅ 001,

Introduciamo ora il concetto di complessità di un programma. Con questo termine intendiamo riferirci ad una valutazione quantitativa dell'efficienza del programma, cioè, intuitivamente, del tempo che il programma impiega per risolvere il problema che dobbiamo affrontare e per il quale esso è stato realizzato.


A questo proposito, facciamo un'ulteriore osservazione. Nel trattare il problema dell'efficienza parleremo in generale indifferentemente sia di algoritmi sia di programmi poiché il fatto che un algoritmo sia espresso mediante un vero e proprio linguaggio di programmazione, pur essendo utile all'analisi formale dell'efficienza stessa, non influenza sostanzialmente il risultato. L'efficienza di un programma, infatti, dipende fondamentalmente dai passi previsti dall'algoritmo, dalle operazioni che esso esegue, dai cicli che devono essere percorsi e non dal modo in cui passi di calcolo elementari, operazioni, cicli si esprimono nel particolare linguaggio di programmazione usato.

Un secondo aspetto della complessità che prenderemo in esame in questa sezione (e poi, più approfonditamente, nella Sezione 4) è quello relativo alla complessità di problemi . In questo caso il termine complessità viene utilizzato per dare una valutazione quantitativa della effettiva difficoltà di risoluzione del problema, cioè di quelle intrinseche caratteristiche che rendono la soluzione di un problema più costosa della soluzione di un altro.

2.2 Complessità di algoritmi

Per comprendere, con un semplice esempio, come le stesse operazioni possono essere svolte da due algoritmi in modo molto diverso dal punto di vista dell'efficienza consideriamo il seguente gioco.

Esempio 1 Supponiamo di dover indovinare un numero tra 1 e 99 e supponiamo che ad ogni tentativo ci venga semplicemente detto se il numero che abbiamo proposto è "troppo grande", "troppo piccolo", "corretto". Come possiamo procedere per individuare il numero facendo il minimo numero di errori?

Il modo più ingenuo consiste nel tentare di indovinare il numero senza una precisa strategia. In questo caso, se siamo molto fortunati possiamo anche indovinare il numero al primo o secondo tentativo ma se siamo molto sfortunati rischiamo di dover fare un numero molto alto di tentativi, anche 50 o, al limite, 99!

Una scelta preferibile è certamente quella di procedere in modo più razionale, secondo una ben determinata strategia. Ad esempio posssiamo effettuare i seguenti tentativi:10, 20, 30, ..., 90. Se,ad esempio a 70, la risposta è " troppo grande" vuol dire che abbiamo superato il numero. A questo punto possiamo variare il numero di uno in uno: 61, 62, 63 ecc. Prima di arrivare a 70 avremo certamente terminato. In definitiva , in questo modo , anche se siamo molto sfortunati (il numero da indovinare è 99) non serviranno mai più di 18 tentativi.

Esiste però un metodo ancora più efficiente, che richiede ancora meno tentativi. Proponiamo il numero 50 come primo tentativo. Se esso è "troppo grande" proponiamo la metà di 50, cioè 25; se è "troppo piccolo" proponiamo 75, cioè il numero che sta a metà tra 50 e 100, e così via, ogni volta dimezzando l'intervallo di ricerca. Chiaramente questo non è altro che il metodo di ricerca binaria che si è appreso in corsi precedenti per effettuare efficientemente la ricerca di una informazione in una tabella. Se il numero da indovinare è ad esempio 34 la sequenza di tentativi che dovremo fare è: 50, 25, 37, 31, 34. Con questo metodo, si può facilmente verificare che per indovinare un numero nell'intervallo 1,.., n - 1 sono sempre sufficienti al più ⎡log2 n⎤ tentativi (dove con il simbolo ⎡log2 n⎤ intendiamo il minimo intero maggiore o uguale a log2 n), e quindi, nel nostro gioco, anche nel caso più sfortunato, non serviranno mai più di ⎡log2 100⎤ =7 tentativi.


Domanda 1. Utilizzando il metodo basato sulla ricerca binaria per indovinare un numero tra 1 e 99, conta quanti tentativi sono necessari per indovinare i numeri 6, 18, 20, 24. Quanti tentativi servono, in generale se dobbiamo indovinare un numero tra 0 ed n-1?

Come abbiamo visto nell'esempio lo stesso problema può essere risolto in diversi modi, con caratteristiche di efficienza molto diverse.

Essenzialmente l'efficienza di un algoritmo è legata al suo costo di esecuzione, cioè alla quantità di risorsa che esso impiega durante l'esecuzione. Nell'esempio precedente tale costo è stato misurato in termini di "numero di tentativi" fatti per indovinare. Nei casi più frequenti il costo corrisponderà (o sarà direttamente proporzionale) alla quantità di tempo o alla quantità di memoria utilizzata per l'esecuzione del programma.

A volte per indicare questo costo di esecuzione parliamo anche di complessità dell'algoritmo e chiamiamo misura di complessità la risorsa (tempo o memoria) di cui abbiamo valutato il consumo da parte dell'algoritmo.

La questione della valutazione dell'efficienza degli algoritmi e della scelta degli algoritmi più efficienti atti a risolvere un dato problema è al centro del nostro interesse in tutto questo corso. Tuttavia, prima di procedere a dare le basi e i metodi formali che consentono di analizzare l'efficienza di un algoritmo e di confrontarla con quella di algoritmi alternativi, vogliamo fare ancora qualche considerazione preliminare.

Prima di tutto osserviamo che la necessità di disporre di una soluzione efficiente dipende dalla natura del problema dato. Ad esempio se dobbiamo controllare se un impianto nucleare sta funzionando regolarmente il tempo di risposta che richiediamo è dell'ordine dei decimi di secondo, se dobbiamo effettuare una prenotazione per un volo internazionale abbiamo bisogno di ottenere una risposta nell'arco di qualche decina di secondi, ma se dobbiamo fornire un rapporto mensile per l'ufficio del personale di un'azienda il vincolo dell'efficienza è molto meno stringente.

Inoltre dobbiamo tenere presente che, a volte, la produzione di un programma molto efficiente può comportare una diminuzione della sua leggibilità e quindi un aumento dei costi di redazione e di manutenzione del programma stesso.

Infine esistono problemi intrinsecamente difficili per i quali è impossibile trovare algoritmi molto efficienti e, se si vuole ottenere una risposta in tempi rapidi, ci si deve accontentare di una risposta approssimata.

La questione della intrinseca difficoltà dei problemi sarà discussa nel prossimo paragrafo e poi, più diffusamente, nella Sezione 4. Prima di procedere, tuttavia, per fissare le idee sul confronto di efficienza tra diversi algoritmi, risolvi il seguente esercizio.


Esercizio 1. Facendo riferimento a quanto appreso nei corsi di base di informatica, esamina due diversi algoritmi per l'ordinamento di un vettore, l'algoritmo di ordinamento per selezione e l'algoritmo di ordinamento a bolle. e: i) considera il seguente vettore: e

determina quanti confronti tra singoli elementi sono richiesti dai due algoritmi esaminati per ordinare il vettore in senso decrescente;

ii) considera il comportamento dei due algoritmi in presenza di un vettore di n elementi, già ordinato in senso decrescente; quanti confronti eseguiranno?

iii) Cosa accade se i due vettori sono ordinati in senso crescente?

2.3. Complessità di problemi

La possibilità di ottenere algoritmi efficienti per i problemi che si devono risolvere con l'elaboratore è legata certamente alla conoscenza, da parte del progettista software, delle tecniche di programmazione più avanzate e delle strutture di dati più idonee, ma, come abbiamo già detto, essa dipende soprattutto dalla effettiva complessità intrinseca del problema dato.

La questione dell'esistenza di un algoritmo efficiente per la risoluzione di un dato problema è una questione estremamente importante. In molti casi, infatti, l'esistenza di un algoritmo efficiente è una condizione indispensabile perché un problema sia realmente risolubile. Problemi che richiedono, ad esempio, un numero esponenziale di operazioni per essere risolti possono essere considerati non risolubili a tutti i fini pratici, anche se si presentano semplici ed innocui.

Domanda 2 Supponi che un ladro un pò ingenuo, volendo scassinare una cassaforte di cui non conosce la combinazione, decida di provare tutte le possibili combinazioni; supponi che ogni tentativo gli costi dieci secondi; tenendo conto del fatto che la combinazione della cassaforte è costituita da una sequenza di cinque caratteri alfabetici (tratti dall'alfabeto inglese), quanto tempo impiegherà il ladro per il suo tentativo? Supponi che un potente calcolatore sia collegato alla cassaforte e possa provare ogni combinazione in un milionesimo di secondo quanto tempo impiegherebbe per provare tutte le combinazioni? E cosa accadrebbe se la combinazione fosse costituita da dieci caratteri?

D'altra parte, come abbiamo già osservato in precedenza, la possibilità di individuare algoritmi sempre più efficienti dipende dalla complessità del problema considerato. Può infatti accadere che, data la intrinseca difficoltà del problema, non possa esistere alcun algoritmo sostanzialmente più efficiente di quelli già noti.

Aiutiamoci ancora con il gioco visto nell'Esempio 1. Supponiamo che per migliorare le possibilità di vittoria si cerchi un metodo di formulazione di tentativi ancora più efficiente, un metodo, cioè, che consenta di indovinare un numero da 1 a 99 con ancora meno tentativi di quelli richiesti dal metodo basato sulla ricerca binaria. Ebbene, purtroppo ci dobbiamo convincere che a questo punto non è più solo questione di astuzia nel fare i tentativi; a questo punto siamo giunti a un limite legato alla intrinseca difficoltà del problema. Infatti si può


dimostrare che non è possibile individuare un numero da 1 a n - 1 con meno di ⎡log2 n⎤ tentativi. Nota bene: se siamo fortunati possiamo anche indovinare il numero con uno o due tentativi; quanto detto significa però che nessun metodo sistematico consente di individuare sempre il numero con meno di ⎡log2 n⎤ tentativi.

Una dimostrazione formale di questo risultato è alquanto complessa, possiamo tuttavia cercare di spiegarlo con un ragionamento intuitivo, rinviando ad un momento successivo un approfondimento di questa problematica (vedi Sezione 5). L'impossibilità di trovare un metodo che richieda meno di ⎡log2 n⎤ tentativi è dovuta al fatto che la minima quantità di informazione necessaria per individuare un numero dato tra 1 ed n - 1 è costituita da un numero di bit pari a ⎡log2 n⎤ che, come si può facilmente verificare, è il numero di bit necessario per rappresentare in binario ogni numero dell'intervallo dato Poiché ogni tentativo può fornirci al più una quantità di informazione pari ad un bit un numero di confronti inferiore a ⎡log2 n⎤ non può essere comunque sufficiente per risolvere, in generale, il nostro problema.

In tutti i problemi che vogliamo risolvere c'è un limite oltre il quale non si può andare nel tentativo di realizzare algoritmi di sempre maggiore efficienza. Con il termine di complessità di un problema intendiamo proprio tale soglia. Ad esempio, la complessità del problema di indovinare un numero tra 0 ed n-1 è data da ⎡log2 n⎤ tentativi.

Sfortunatamente una grande quantità di problemi di rilevante interesse pratico hanno un'intrinseca complessità che li rende molto difficili da risolvere anche con un potente elaboratore. Per molti problemi di ottimizzazione, ad esempio, come problemi di gestione ottima di risorse, di distribuzione ottima di prodotti in una rete di magazzini, di sequenziamento ottimo di attività in un sistema di calcolo distribuito ecc. la complessità intrinseca è tale che questi problemi sono stati definiti "intrattabili" e se ne può ottenere soltanto una soluzione approssimata.

Per avere un'idea del tempo richiesto dalla soluzione di problemi di diverso grado di complessita' riportiamo nella Tabella 1 i tempi necessari per risolvere problemi di varia taglia, quando la funzione di costo è quella indicata nella prima colonna. Per fissare le idee possiamo immaginare che il primo dei problemi di ogni riga sia risolubile in un microsecondo. Le diverse colonne mostrano come cresce il tempo di risoluzione se la taglia diviene 10 volte, 20 volte, 50 volte più grande. Come si vede il concetto di intrattabilità per problemi di costo esponenziale è quanto mai giustificato.

Dimensione del problema

1 x10 x20 x30 x40 X50

n 0.000001 0.00001 0.00002 0.00003 0.00004 0.00005

n2 0.000001 0.0001 0.0004 0.0009 0.0016 0.0025

n3 0.000001 0.001 0.008 0.027 0.064 0.125

2n 0.000001 0.001 1.0 17.9 min 12.7 giorni 35.7 anni


3n 0.000001 0.059 58 min 6.5 anni 3855 secoli 2x10 8secoli

Tabella 1. Tempi di risoluzione (in secondi, se non diversamente indicato) di vari problemi per diverse funzioni di costo, al crescere della taglia dei problemi.

Prima di concludere consideriamo ancora un esempio per fissare le idee sul concetto di complessità intrinseca di un problema. Siano dati quattro numeri: n1, n2, n3, n4. Per individuare il numero più grande sono necessari almeno 3 confronti: ad esempio vanno prima confrontati (i) n1 con n2 (e supponiamo che sia n2 più grande) e n3 con n4 (e supponiamo che sia n3 più grande) e poi (ii) n2 con n3 (e supponiamo che sia n3 più grande). E’ facile convincersi che due soli confronti non sono sufficienti in quanto qualsiasi numero escluso dal confronto potrebbe inficiare il risultato. Per trovare il secondo maggiore, non basta prendere il numero n2 “perdente” nel passo (ii) ma va fatto un ulteriore confronto tra n2 e n4 che nel passo (i) era già risultato superato da n3 ma che tuttavia potrebbe essere maggiore di n2. Si consideri ad esempio il caso n1 = 4, n2 = 8, n3 = 20, n4 = 10.

Domanda 3 Consideriamo un torneo di tennis a eliminatorie con 16 giocatori; perchè se vogliamo determinare il vincitore servono 15 incontri? Perché se vogliamo determinare oltre al primo anche il secondo miglior giocatore 15 incontri non sono sufficienti e ne servono 18?


3. METODI DI ANALISI DI COMPLESSITA' DEGLI ALGORITMI

3.1. Introduzione

Nella sezione precedente abbiamo visto che uno stesso problema può essere affrontato con metodi di risoluzione diversi che possono presentare un diverso grado di efficienza. Abbiamo anche visto che l'efficienza di un algoritmo può essere decisiva rispetto alla possibilità di risolvere il problema dato nei limiti di tempo richiesti dall'applicazione. Infine abbiamo osservato che nella ricerca di algoritmi sempre più efficienti per la risoluzione di un problema ci dobbiamo confrontare con un limite determinato dalla intrinseca complessità del problema stesso. In questa Sezione inizieremo a porre questa problematica in termini più formali.

Come abbiamo già detto, con il termine complessità di un algoritmo intendiamo riferirci ad una valutazione quantitativa del costo di esecuzione dell'algoritmo stesso espresso con una opportuna unità di misura (nell'Esempio 1 della sezione precedente l'unità di misura era costituita dal numero di tentativi che effettuavamo per indovinare il numero dato) in funzione di qualche parametro caratteristico del problema (sempre nell'esempio citato questo parametro era dato dall'ampiezza dell'intervallo dei possibili valori del numero da indovinare). Spesso anziché di complessità parliamo di efficienza di un algoritmo o, più esplicitamente e più propriamente, di costo di esecuzione. La relazione tra questi termini è abbastanza chiara: un algoritmo è tanto più complesso e tanto meno efficiente quanto più elevato è il suo costo di esecuzione.

Per poter utilizzare correttamente questi termini, tuttavia, è necessario tenere conto di tutta una serie di fattori che devono essere precisati perché il concetto di complessità di un algoritmo non rimanga un concetto ambiguo. Il primo fattore da considerare è il modello di macchina utilizzato e, in relazione ad esso, l'unità di misura della complessità che viene adottata; è poi necessario definire il tipo di analisi che vogliamo effettuare e, infine, il modo in cui esprimiamo la complessità emersa dalle nostre valutazioni. Esaminiamo uno ad uno questi diversi aspetti.

3.2. Modelli di macchina e misure di complessità.

Il primo fattore che dobbiamo tenere presente per analizzare in modo rigoroso il comportamento di un algoritmo è il tipo di macchina, di sistema di calcolo su cui si suppone che l'algoritmo venga eseguito. Come abbiamo osservato nella sezione precedente, l'efficienza di un programma dipende essenzialmente dalla struttura dell'algoritmo utilizzato e non dalle caratteristiche del linguaggio di programmazione in cui l'algoritmo è stato codificato. Tuttavia per effettuare un'analisi accurata del costo di esecuzione dobbiamo definire formalmente come il calcolo sarà eseguito e quali grandezze utilizzare come misura della complessità.

La prima possibilità che ci si offre è, chiaramente, quella di fare riferimento ad un elaboratore reale su cui il programma può essere eseguito e sul quale possiamo misurare il tempo richiesto per l'esecuzione. Questo procedimento, tuttavia, presenta molti inconvenienti. Il primo è che tale metodo è troppo influenzato dalle caratteristiche tecnologiche della macchina utilizzata e cambiando macchina si otterrebbero dei risultati diversi. Il secondo e più grave inconveniente è che, in genere, noi non siamo tanto interessati a stabilire il tempo di


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.


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.

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 2 Supponiamo che gli interi x (> 0) e y siano forniti sul nastro di ingresso. Il seguente programma dà in uscita il valore xy. 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.

Esercizio 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.

Esercizio 3 Dato un insieme di 2n 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 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 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 quadratico, ovvero dell'ordine di n2 , 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 e tale numero; poiché abbiamo e = n2 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 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 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 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 il numero di operazioni di divisione, valutato in funzione di |n| è 2|n|/2 e quindi esponenziale. Vediamo un caso concreto. Supponiamo di dover decidere se il numero 2100 - 1 è un numero primo. Usando l'algoritmo introdotto precedentemente dobbiamo eseguire circa 250 operazioni di divisione Questo numero è in realtà talmente grande da rendere praticamente insolubile il problema; se anche utilizzassimo una macchina capace di eseguire un milione di divisioni al secondo il tempo necessario per verificare se 2100 - 1 è un numero primo con questo metodo sarebbe di 250 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 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 banale che abbiamo supposto di utilizzare richiede, come abbiamo già visto, al più 2 |n|/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 piu' chiara 2

|n|/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.

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


complessità dell'ordine di n2 anche se una valutazione più precisa del costo di esecuzione dell'algoritmo stesso darebbe il risultato c n2 + b n

Per esprimere una valutazione asintotica di complessità è stata introdotta una notazione derivata essenzialmentente dall'analisi classica: la notazione Θ.

Definizione 1 Una funzione f(n) è Θ(g(n)) se limn→∞ g(n)/f(n) = c > 0 cioè converge verso un valore finito maggiore di zero La complessità di un algoritmo, misurata in termini di una data risorsa, è Θ (g) se la quantità di risorsa richiesta per l'esecuzione dell'algoritmo è Θ (g).

Utilizzando la notazione "teta" possiamo dire, ad esempio, che l'algoritmo per il test di primalità di un intero n, visto nell'Esempio 4, ha una complessità Θ(2|n|/2).

Domanda 5 Data la funzione f(n) = c n2 + b n quali delle seguenti affermazioni sono corrette? a) f(n) è Θ (n) b) f(n) è Θ(n2) c) f(n) è Θ(n3).

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à Θ(n log n). Più grave ancora è che se un programma ha costo 1000 n logn e un altro ha costo n2 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 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 che, tra i numeri di lunghezza n, sono proprio i numeri primi che richiedono 2n/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 di n2 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 (che sarà studiato nel capitolo 3 di questo Corso) esegue un numero di confronti O(n2) 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 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 è dunque pari a k - 1, cioè Θ(2n) 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 calcolare 2k se k è una potenza di 2 il problema è abbastanza semplice: ad esempio se k = 8 possiamo calcolare prima 22 = 4, poi 2 4 come 22 . 22 e infine 28 come 24 . 24. 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 rappresentazione binaria è 1101. Ciò significa che 2k = 28 . 24 . 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 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 moltiplicazioni perché il contributo 22 era assente). Assumendo che le moltiplicazioni comportino un costo unitario, abbiamo quindi un costo complessivo 2n-2 che, asintoticamente, corrisponde ad un costo Θ(n), cioè lineare nella lunghezza dell'input.

Esercizio 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 Θ e determina in quali situazioni vantaggiose l'algoritmo può richiedere un numero sensibilmente inferiore di confronti e di scambi.


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, utilizzando, 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 6 Supponiamo di avere il seguente frammento di programma: for (int n=1; n


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 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


Definizione 2 Dato un programma il cui costo di esecuzione è Θ(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) con d(n) = Θ(t(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 8 Consideriamo il frammento di programma già visto precedentemente: for (int n=1;n


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 Θ(log2 n). In tale occasione abbiamo anche osservato che il numero di ⎡log2 n⎤ tentativi rappresenta una soglia al di sotto della quale non è possibile scendere. Tale soglia è dovuta al fatto che il valore ⎡log2 n⎤ corrisponde alla quantità di informazione 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, ⎡log2 n⎤ bit e comporta quindi ⎡log2 n⎤ 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 quantità di risorsa (tempo, memoria) o di eseguire un certo numero di operazioni (ad esempio quadratico) almeno in una serie di casi particolarmente difficili.


Per rappresentare un upper bound e un lower bound di complessità di un problema si usano notazioni simili a quella adottata per la complessità di un algoritmo.

Sia data una qualunque misura di complessità per un dato modello di macchina (numero di operazioni dominanti, quantità di tempo, quantità di memoria ecc.); sia n la dimensione del problema dato e sia tA(n) il costo di esecuzione di un algoritmo A nel caso peggiore, cioè in corrispondenza della più difficile tra le istanze di dimensione n.

Definizione 3 Un algoritmo A ha un limite limite superiore (upper bound ) di complessità Ο(g(n)) se limn→∞ tA(n)/g(n) = c ≥ 0 cioè, asintoticamente, il costo tA(n) di esecuzione dell'algoritmo, nel caso peggiore, è sempre minore o uguale di c g(n). Un problema ha un limite superiore (upper bound ) di complessità O(g(n)) se esiste un algoritmo A per la sua risoluzione che ha un costo di esecuzione O(g(n)).

Definizione 4 Un algoritmo A ha un limite inferiore (lower bound ) di complessità Ω(g'(n)) se limn→∞ g(n)/tA(n) = c ≥ 0 esistono cioè, asintoticamente, il costo di esecuzione dell'algoritmo, nel caso peggiore, è sempre maggiore o uguale di c g'(n). Un problema ha un limite inferiore (lower bound ) di complessità Ω(g'(n)) se, dato un qualunque algoritmo per la sua risoluzione, esso ha una complessità Ω(g'(n)).

Chiaramente, tanto più vicine sono le funzioni g e g', tanto più precisa sarà la caratterizzazione della complesssità del problema dato. Ad esempio per il caso della moltiplicazione di matrici n⋅n è stato dimostrato che la complessità del problema (misurata in termini di moltiplicazioni tra elementi) è O(n2.34) ed Ω(n2). Se si vuole pervenire ad una più precisa caratterizzazione è necessario o individuare un algoritmo che richieda meno di n2.34 operazioni oppure dimostrare che la complessità intrinseca del prodotto di matrici è maggiore di quanto osservato finora e che ogni algoritmo per questo problema richiede necessariamente più di n2 operazioni (ne richiede ad esempio n2log n oppure n2.1).

Quando si riesce a mostrare che un problema ha una complessità O(g) e Ω(g') con g e g' asintoticamente uguali a meno di costanti moltiplicative (cioè lim g/g' = c > 0) possiamo dire che la complessità del problema è determinata con precisione. In questo caso usiamo la notazione “teta”.

Definizione 5 Dato un problema, se il suo upper bound è O(g(n)) e il suo lower bound è Ω(g(n)), diciamo che la sua complessità è Θ(g(n)).

Il problema dell'individuazione di un numero compreso tra 1 ed n è un esempio di problema la cui complessità può essere nettamente caratterizzata. Infatti, in base a quanto abbiamo visto, esso ha un upper bound O(log n) e un lower bound Ω(log n) e quindi possiamo dire che la sua complessità è Θ(log n).

Nel seguito di questa sezione prenderemo in esame diversi aspetti riguardanti la complessità intrinseca di problemi. In particolare dopo aver discusso il concetto di algoritmo ottimale presenteremo alcune tecniche elementari per la determinazione di lower bounds che ci consentono di mostrare algoritmi ottimali per semplici problemi come alcuni casi di ordinamento parziale e la fusione di due vettori ordinati. Infine tratteremo una tecnica più complessa che consente di caratterizzare la complessità di problemi come la ricerca di


un'informazione in un archivio e l'ordinamento di vettori mostrando che anche per essi disponiamo di algoritmi ottimali.

In realtà per un gran numero di problemi di interesse pratico una caratterizzazione precisa della complessità non è (ancora) stata determinata. Per tali problemi (ad esempio problemi di scheduling, di partizionamento di grafi, di soddisfacimento di formule logiche ecc.) i migliori algoritmi noti hanno comunque un costo esponenziale mentre le delimitazioni inferiori di complessità individuate sono di tipo polinomiale (in genere quadratico!). Il divario tra upper bound e lower bound in questi casi lascia dunque una grande incertezza sull'effettiva intrinseca difficoltà di questi problemi. In questi casi si può procedere a stabilire, almeno, valutazioni di complessità relativa mediante tecniche più sofisticate che permettono di arrivare comunque ad un'utile classificazione della complessità di questi problemi in base alla quale essi sono stati definiti "intrattabili".

5.2. Algoritmi ottimali

E' interessante osservare che quando abbiamo un problema per il quale upper bound e lower bound coincidono vuol dire che per tale problema disponiamo di un algoritmo ottimale. In questo caso, infatti, se l'algoritmo di cui disponiamo, e che ci ha consentito di determinare l'upper bound, ha un costo O(g(n)) e se il lower bound è Ω(g(n)) vuol dire che non sarà possibile trovare alcun algoritmo asintoticamente migliore; gli unici miglioramenti che si potranno apportare potranno incidere solo sulla costante moltiplicativa.

Definizione 6 Sia dato un problema P con un lower bound di complessità Ω(g) per una opportuna funzione g; se un algoritmo A per P ha un costo di esecuzione O(g) allora diciamo che A è un algoritmo ottimale per P.

Supponiamo di avere per un dato problema un algoritmo A che richiede tempo O(n2) e che il lower bound del problema sia proprio Ω(n2); potremo dire che A è un algoritmo ottimale per il problema dato. Ciò non significa che non ci siano algoritmi migliori; significa semplicemente che tali algoritmi potranno aver un migliore comportamento su alcune istanze particolari o, al massimo potranno richiedere un tempo di esecuzione che è minore di quello richiesto da A solo per un fattore costante. Se il costo di esecuzione di A è O(n2) vuol dire che il tempo che esso richiede (o il numero di operazioni che esso compie) è ad esempio tA(n) = c n2 + d n

Un algoritmo A' migliore di A potrà avere un costo di esecuzione tA'(n) = c/2 n2 + d n che asintoticamente è sempre O(n2). Comunque non sarà possibile trovare algoritmi che siano asintoticamente migliori, ad esempio nessun algoritmo per il problema dato potrà avere un costo di esecuzione O(n log n) e neanche O(n2-ε) per piccolo che sia ε.

5.3. Metodi elementari per determinare lower bounds

I primi esempi di lower bound che vogliamo mostrare possono essere ottenuti con tecniche abbastanza elementari.

Una prima considerazione, banale, è quella che ci dice che, se la soluzione di un problema di taglia n richiede che ogni dato in ingresso sia preso in esame, il costo di ogni algoritmo non può che essere lineare in n perchè totto l'input deve essere ispezionato almeno una volta e,


quindi, la complessità del problema è almeno Ω(n). Questo metodo di individuazione del lower bound di un problema è detto metodo di ispezione dell'input

Esempio 12 Un esempio in cui è applicabile il metodo suddetto è la determinazione del massimo di un vettore. In questo caso, infatti, poichè ogni elemento deve essere stato confrontato (direttamente o indirettamente) con il massimo possiamo asserire che il lower bound, in termini di confronti, è esattamente n-1. Poichè n-1 confronti sono anche sufficienti per determinare il massimo del vettore, in questo caso possiamo dire di avere una esatta caratterizzazione della complessità del problema.

Domanda 8 Perchè nel caso della ricerca di un'informazione in una tabella il metodo non è applicabile?

Una seconda tecnica elementare, ma che può essere utilizzata in generale per determinare il lower bound di un problema (detta tecnica dell'avversario) consiste nel supporre che, dato un ipotetico algoritmo che risolve il problema assegnato con un certo costo, un invisibile avversario possa alterare i dati in ingresso in modo da mettere in crisi l'algoritmo e mostrare che il costo deve necessariamente essere maggiore.

Esempio 13 Supponiamo che siano date due liste ordinate A=(a1, a2, ..., an) e B=(b1, b2, ..., bn). Per ottenere la loro fusione, cioè la lista C contenente in modo ordinato gli elementi di entrambe, si rendono necessari 2n-1 confronti. Per dimostrarlo procediamo come segue. Supponiamo che un algoritmo effettui soltanto n-2 confronti. In tal caso l'avversario può costruire due liste A e B tali che, mediante n-2 confronti si verifichi:

a1 ≤ b1 ≤ a2 ≤ ... ai-1 ≤bi-1≤ ai e bi ≤ ai+1 ≤ bi+1≤ ... ≤ an ≤ bn

A questo punto resta ancora da determinare, mediante un ulteriore confronto tra ai e bi, se il risultato corretto sia la lista

C=(a1, b1, a2, ... , ai-1, bi-1, ai, bi, ai+1, bi+1, ..., an, bn)

o la lista

C=(a1, b1, a2, ... , ai-1, bi-1, bi, ai, ai+1, bi+1, ..., an, bn).

Esercizio 7 Dimostrare, con il metodo dell'avversario che il lower bound del problema di determinare il primo e l'ultimo giocatore di un torneo è costituito da ⎡3/2 n⎤ - 2 incontri.

6. ORDINAMENTO E RICERCA IN UN VETTORE

6.1 Ordinamento in un Vettore

Un algoritmo di ordinamento di un vettore con n elementi abbastanza naturale e stremamente da realizzare è l'ordinamento a bolle (bubble sort). In esso il primo elemento è confrontato con il secondo ed eventualmente scambiato; il secondo con il terzo e così via. Durante questa prima iterazione gli elementi maggiori sono risaliti come bolle verso le posizioni di indice più


alto del vettore e in particolare l'elemento massimo si è portato nell'ultima posizione. Alla seconda iterazione sarà il secondo maggiore a portarsi nella penultima posizione. Dopo n-1 iterazioni, ogni elemento avrà raggiunto la sua posizione nell'ordinamento. In effetti, può accadere che durante una iterazione più elementi contemporaneamente raggiungano la posizione definitiva, in particolare quelli successivi all'indice in cui è avvenuto l'ultimo scambio; pertanto l'ordinamento può essere costruito in meno di n-1 iterazioni. Scriviamo di seguito l'algoritmo in un formato generico sia rispetto ai tipi degli elementi sia rispetto al tipo di ordinamento. Il metodo è definito all’interno della classe Vettore. public static boolean ordBolla( int [] V, int n ) { int limite = n-1; while ( limite > 0 ) { int indiceUltimoScambio = 0; for ( int i = 0; i < limite; i++ ) if ( V[i]> V[i+1] ) { int k = V[i]; V[i] = V[i+1]; V[i+1] = k; indiceUltimoScambio = i; } limite = indiceUltimoScambio; } }

La complessità è quadratica nel caso peggiore e medio mentre diventa lineare nel caso migliore quando il vettore è parzialmente ordinato. Volendo misurare le operazioni fondamentali di un algoritmo di ordinamento, cioè confronto tra due elementi e loro scambio, abbiamo che sia il numero di confronti che quello di scambi è Θ(n2) nel caso peggiore e medio mentre nel caso migliore il numero di confronti è Θ(n) e il numero di scambi è Θ(1).

Un altro noto algoritmo di ordinamento è quello per inserzione (insertion sort). Vengono effettuate n-1 iterazioni e a ogni iterazione i abbiamo che i primi i elementi sono ordinati per cui, allo scopo di estendere l'ordinamento anche all'elemento i+1, è sufficiente determinare la posizione in cui inserire tale elemento e effettuare tale inserimento attraverso opportuni spostamenti. public static boolean ordInserzione ( int [] V, int n ) { for ( int i = 1; i < n; i++ ) { int tmp = V[i]; int iPos=i; for ( int j = i-1; j >= 0 && iPos==i; j-- ) if ( tmp < V[j] ) V[j+1] = V[j]; else iPos=j; if ( iPos != i ) V[iPos] = tmp; } }

Come per l'ordinamento a bolle la complessità è quadratica nel caso peggiore e medio mentre diventa lineare nel caso migliore quando il vettore è parzialmente ordinato. Sia il numero di scambi che quello di confronti è Θ(n2) nel caso peggiore e medio mentre nel caso migliore il numero di confronti è Θ(n) e il numero di scambi è Θ(1).

L'algoritmo di selezione (selection sort) effettua l'ordinamento selezionando alla prima iterazione il primo minore che finisce in prima posizione, alla seconda il secondo minore


viene spostato alla seconda posizione, e così via; alla iterazione n-1 il vettore risulterà ordinato. public static void ordSelezione (int [] V, int n ) { for ( int i = 0; i < n-1; i++ ) { int iMinimo = i; for ( int j = i+1; j < n; j++ ) if ( V[j]> V[iMinimo] ) iMinimo = j; if ( i != iMinimo ) { int k = V[iMinimo]; V[iMinimo] = V[i]; V[i] = k; } } }

Questa volta la complessità è quadratica non solo nel caso peggiore e medio ma anche nel caso migliore. Il numero di confronti è Θ(n2) in ogni caso; il numero di scambi è nel caso migliore è Θ(n) nei casi peggiori e medio mentrefor_each_node 0) nel caso migliore.

Ricapitoliamo in Tabella 2 i numeri di confronti e scambi per i tre algoritmi di ordinamento. Più avanti nel libro avremo modo di studiare algoritmi di ordinamento più efficienti con complessità Θ(n logn).

Confronti Scambi MIN MEDIO MAX MIN MEDIO MAX Bolla Θ(n) Θ(n2) Θ(n2) Θ(1) Θ(n2) Θ(n2) Inserzione Θ(n) Θ(n2) Θ(n2) Θ(1) Θ(n2) Θ(n2) Selezione Θ(n2) Θ(n2) Θ(n2) Θ(1) Θ(n) Θ(n)

Tabella 2. Numero di confronti e scambi in vari tipi di ordinamento

Esercizio 9 L’ordinamento a contatore (counting sort) si applica a un vettore V di interi e consiste nell’allocare un vettore T di indici (Vmin,Vmax), dove Vmin e Vmax sono rispettivamente il minimo e il massimo valore in V, inizializzare tutti gli elementi di T a 0, scandire ciascun elemento i di V incrementando ogni volta T[V[i]] di 1 e, infine, ricopiare in V gli indici j da Vmin a Vmax tante volte quanto vale il contatore T[j]. Scrivere l’algoritmo e valutarne la complessità.

6.2 Ricerca in un Vettore

Affrontiamo ora il problema di ricerca di un elemento in un vettore di n elementi. Scriviamo un semplice algoritmo di scansione del vettore che restituisce l’indice dell’elemento cercato oppure -1 se l’elemento non è presente: public static int ricerca( int [] V, int n, int o ) { bool trovato = false; int io = 0; while ( io < n && !trovato ) if ( V[i] == 0 ) trovato = true; else io++;


return (io


2. Infatti, detto p = ⎡logn⎤, abbiamo che 2p < log n < 2p+1 per cui il numero di iterazione k vale: p < k < p+1. Pertanto k = Ω(p) e k = Ο(p+1) = Ο(p); quindi k = Θ(p) = Θ(⎡logn⎤) e, poichè ⎡logn⎤ < logn+1, k = Θ(⎡logn⎤). Notiamo che nel caso di ricerca con insuccesso la complessità Θ(log n) vale anche per il caso migliore. Ricapitoliamo in Tabella 3 le complessità delle tre ricerche nei vari casi. Con Successo Senza Successo MIN MEDIO MAX MIN MEDIO MAX Ricerca Θ(1) Θ(n) Θ(n) Θ(n) Θ(n) Θ(n) Ricerca Ordinata Θ(1) Θ(n) Θ(n) Θ(1) Θ(n) Θ(n) Ricerca Binaria Θ(1) Θ(logn) Θ(logn) Θ(logn) Θ(logn) Θ(logn)

Tabella 3. Complessità temporale per vari tipi di ricerca


7

FONDAMENTI DI INFORMATICA I - CNRstaff.icar.cnr.it/.../upload/lezioni/complessita2010.pdf · 2010....

Documents

Transcript of FONDAMENTI DI INFORMATICA I - CNRstaff.icar.cnr.it/.../upload/lezioni/complessita2010.pdf · 2010....