Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

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

2

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 log n tentativi.

2

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 log n tentativi è dovuta al fatto che la minima quantità di

2

informazione necessaria per individuare un numero dato tra 1 ed n - 1 è costituita da un

 

numero di bit pari a log n che, come si può facilmente verificare, è il numero di bit

2

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 log n non può essere comunque sufficiente per risolvere, in generale, il nostro

2

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 log n tentativi.

2

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

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

Dimensione del problema

1 x10 x20 x30 x40 X50

n 0.000001 0.00001 0.00002 0.00003 0.00004 0.00005

2

n 0.000001 0.0001 0.0004 0.0009 0.0016 0.0025

3

n 0.000001 0.001 0.008 0.027 0.064 0.125

n 0.000001 0.001 1.0 17.9 min 12.7 giorni 35.7 anni

2 8

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

3

Tabella 1.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: n , n , n , n . Per

1 2 3 4

individuare il numero più grande sono necessari almeno 3 confronti: ad esempio vanno prima

confrontati (i) n con n (e supponiamo che sia n più grande) e n con n (e supponiamo che

1 2 2 3 4

sia n più grande) e poi (ii) n con n (e supponiamo che sia n più grande). E’ facile

3 2 3 3

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 n “perdente” nel passo (ii) ma va fatto un ulteriore confronto tra n e n che nel passo

2 2 4

(i) era già risultato superato da n ma che tuttavia potrebbe essere maggiore di n . Si consideri

3 2

ad esempio il caso n = 4, n = 8, n = 20, n = 10.

1 2 3 4

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

P

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

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

P

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

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

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

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

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

sapere quante partite occorrono in funzione del numero di giocatori.

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

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

essi.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

dall'algoritmo.

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

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

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

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

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

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

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

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

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

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

registri. P

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

Figura 1.1 Rappresentazione fisica di una macchina a registri.

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

calcolatore reale.

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

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

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

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

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

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

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

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

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

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

registro nell'accumulatore e viceversa.

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

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

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

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

maggiore da un numero minore. P

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

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

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

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

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

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

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

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

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

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

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

registro sul nastro di uscita.

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

y

seguente programma dà in uscita il valore x .

READ 1

READ 2

LOAD =1

STORE 3

LOAD 2

LOOP JEQZ STOP

LOAD 1

MULT 3

STORE 3

LOAD 2

SUB =1

STORE 2

JUMP LOOP

STOP WRITE 3

HALT

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

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

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

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

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

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

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

grande.

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

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

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

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

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

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

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

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

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

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

P

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

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

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

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

termini di istruzioni eseguite?

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

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

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

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

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

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

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

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

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

complessità adottata è il numero di incontri effettuati.

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

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

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

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

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

quello utilizzato prevalentemente in tutto questo corso.

n

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

determina quanti confronti sono sufficienti

i) per individuare il massimo e il minimo,

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

3.3. Dimensione dell'input

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

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

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

determinazione del vincitore di un torneo, abbiamo fatto riferimento rispettivamente

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

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

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

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

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

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

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

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

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

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

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

P

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

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

= c n.

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

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

dell'input

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

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

2

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

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

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

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

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

2

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

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

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

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

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

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

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

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

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

   

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

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

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

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

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

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

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

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

n n

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

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

n

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

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

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

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

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

|n|/2

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

100

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

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

50

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

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

P

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

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

50

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

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

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

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

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

dell'algoritmo.

Domanda 1.4 Considera i seguenti problemi:

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

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

 moltiplicare due polinomi a coefficienti interi di valore compreso tra

-MAXINT e +MAXINT,

 calcolare il fattoriale di un numero intero.

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

esprimere la complessità di algoritmi per la loro soluzione?

3.4. Tipi di analisi

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

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

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

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

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

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

grandezza in questione.

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

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

|n|/2

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

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

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

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

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

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

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

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

|n|/2

piu' chiara 2 .

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

funzione che:

- delimiti superiormente il valore esatto

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

dimensione dell'input. P

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

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

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

peggiore.

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

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

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

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

2

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

2

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

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

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

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

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

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

dell'algoritmo è O (g).

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

|n|/2

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

2

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

corrette?

a) f(n) è O(n)

2

b) f(n) è O(n )

3

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

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

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

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

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

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

2

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

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

realtà, inferiore fino ad n=10000.

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

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

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

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

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

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

ignorati e l'analisi deve essere maggiormente raffinata.

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

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

P

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

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

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

n/2

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

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

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

2

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

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

"a bolle" esegue soltanto n confronti.

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

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

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

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

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

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

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

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

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

2

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

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

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

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

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

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

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

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

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

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

n

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

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

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

k

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

22 4 22 . 22 28 24 . 24.

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

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

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

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

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

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

. .

k 8 4

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

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

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

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

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

una qualunque base. Adesso possiamo calcolare quante moltiplicazioni richiede questo

P

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

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

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

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

2

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

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

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

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

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

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

richiedere un numero sensibilmente inferiore di confronti e di scambi.

P

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

4. ANALISI DI EFFICIENZA DI PROGRAMMI SCRITTI IN LINGUAGGIO AD

ALTO LIVELLO

4.1. Introduzione

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

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

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

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

eccessivamente gravoso

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

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

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

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

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

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

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

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

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

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

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

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

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

delle operazioni dominanti.

4.2. Analisi dettagliata di programmi in linguaggio ad alto livello

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

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

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

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

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

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

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

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

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

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

Esempio 1.6 Supponiamo di avere il seguente frammento di programma:

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

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

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

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

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

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

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

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

complessivo sarà 3m.

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

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

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

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

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

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

gestione di chiamate ricorsive di procedura

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

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

per lo stesso problema.

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

valore del fattoriale di n:

public static int fact1 (int n)

{ int fattoriale=1;

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

fattoriale*=i;

return fattoriale;

}

public static int fact2 (int n)

{ if (n = 0) return 1

else return n*fact2(n-1);

}

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

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

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

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

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

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

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

utilizzato asintoticamente è sensibilmente maggiore di quello utilizzato dal programma

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

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

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


PAGINE

38

PESO

280.25 KB

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

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


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

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

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

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

Recensioni
Ti è piaciuto questo appunto? Valutalo!