Algoritmi - analisi

Capitolo 1

INTRODUZIONE ALLA 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, in questa prima unità 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.

Una prima introduzione ai concetti di complessità di calcolo di algoritmi e programmi è stata

fornita nei corsi di informatica precedenti nei quali hai visto come si può valutare la quantità

di tempo richiesta da un programma per risolvere un determinato problema. In particolare i

concetti forniti sono stati applicati per confrontare la complessità di diversi programmi per

l'ordinamento di un vettore e di diversi metodi di gestione di tabelle.

In questo corso riprenderemo gli stessi concetti in modo più formale e li approfondiremo per

mostrare tutti gli aspetti di cui si deve tenere conto per effettuare un'accurata analisi di

complessità. Innanzitutto introdurremo i concetti di base e le motivazioni per lo studio delle

proprietà di efficienza dei programmi e della complessità dei problemi. Successivamente

tratteremo più in dettaglio i metodi con cui si analizza e si esprime l'efficienza di un

programma, principalmente con riferimento all'analisi di programmi scritti in linguaggio ad

P

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

alto livello. Infine affronteremo il concetto di complessità intrinseca di un problema e

illustreremo alcuni semplici metodi per la determinazione di tale complessità.

Obiettivo di questo capitolo è 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

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.

Infine, nella Sezione 5, introdurremo i concetti di limite superiore (upper bound ) e limite

inferiore (lower bound ) alla complessità di un problema e alcuni metodi per la

determinazione della complessità intrinseca di un problema. In particolare discuteremo più in

dettaglio l'utilizzazione degli alberi di decisione che, nel caso dei problemi di ricerca e

ordinamento assumono un ruolo particolarmente importante.

P

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

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 S e S , trovare una stringa x

1 2

tale che essa sia contemporaneamente la concatenazione di stringhe in S e la

1

concatenazione di stringhe in S . Una istanza del problema è S = {01, 00, 110} e S = {001,

2 1 2

   

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,

P

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

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

P

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

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ù log n tentativi (dove con il simbolo log n intendiamo il

2 2

minimo intero maggiore o uguale a log n), e quindi, nel nostro gioco, anche nel caso più

2

 

sfortunato, non serviranno mai più di log 100 =7 tentativi.

2

Domanda 1.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.

P

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

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.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: <5 , 34 , 22 , 42 , 9 , 8 , 6 , 3 , 7> 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 1.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?

P

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

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