Algoritmi - analisi

Capitolo 1 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, 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.

PCapitolo 2 Strutture dati elementari (Bozza del % , ") ag. 2.3

1. Complessità di programmi e complessità 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 linguaggio 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 x1 2 tale che essa sia contemporaneamente la concatenazione di stringhe in S e la1 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, PCapitolo 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 possiamo 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 è PCapitolo 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 il2 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.

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

• 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;
• Considera il comportamento dei due algoritmi in presenza di un vettore di n elementi, già ordinato in senso decrescente; quanti confronti eseguiranno?
• 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 po' 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?

PCapitolo 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