COMPLESSITA' COMPUTAZIONALE

La complessità computazionale viene usata in ambito informatico per misurare le prestazioni di un algoritmo.I teorici dell’informatica hanno introdotto delle notazioni che permettono di sempliﬁcare la rappresentazione della complessità computazionale di un algoritmo. Come primo passo il problema viene deﬁnito come funzione della grandezza dell’input, che di solito viene indicato con la lettera n. Quindi la complessità di un algoritmo viene deﬁnita come T(n) dove n è la dimensione dell’input. T(n) , la n era il valore di un numero intero, ma spesso n non rappresenta la dimensione di un singolo numero ma la cardinalità di un insieme: ad esempio nei problemi di ordinamento in cui si tratta di ordinare un insieme di oggetti secondo una certa relazione di ordinamento, la dimensione del problema è determinata dal numero di oggetti da ordinare. Per fare un esempio: supponiamo di aver analizzato un algoritmo e aver trovato che la sua complessità computazionale vele T(n) = n2 +7n+20, se dovessimo ordinare 10 oggetti l’algoritmo compierebbe 100+70+20 = 190 istruzioni, se ne dovessimo ordinare 20 allora avremmo 400 + 140 + 20 = 560 istruzioni e così via. Quindi la formula T(n) ci permette di capire il numero di istruzioni che dovranno essere compiute per risolvere un problema avendo un input di dimensione n: pur non essendo questo direttamente traducibile in un tempo ﬁsico , ci permette comunque di avere un’indicazione di massima sulla possibilità o meno di arrivare a termine di un algoritmo e ci permette di confrontare algoritmi diversi tra loro. Rispetto a quest’ultima possibilità proviamo a prendere in considerazione un algoritmo A1 con complessità T1(n) = n2 + 7n + 20 e un altro A2 con complessità T2(n) = 100n + 400 che siano in grado di risolvere lo stesso problema: quale dei due risulta preferibile? Se ad esempio consideriamo un input di dimensione n = 10 è evidente che il primo algoritmo è più veloce in quanto ha bisogno di 190 operazioni contro le 1400 del secondo. Se però la dimensione del problema diventasse n = 100 allora il primo algoritmo avrebbe bisogno di 10720 mentre il secondo di 10400 e diventando a questo punto il secondo il più veloce. Inoltre con n > 100 il secondo diventerebbe via via sempre più veloce del primo.CASI DI COMPLESSITA' COMPUTAZIONALEPuò essere utile a questo punto deﬁnire delle classi di complessità che si trovano nell’analisi degli algoritmi più usati :Costante: gli algoritmi che appartengono a questa classe compiono sempre lo stesso numero di istruzioni indipendentemente da quanto è grande l’input e la classe viene denotata come O(k).Logaritmica: il numero delle operazioni è solitamente il logaritmo in base 2 della dimensione dell’input, poichè sono algoritmi che dividono il problema in due parti e ne risolvono solo la parte che interessa. La classe viene denotata come O(ln). Nella pratica non è molto diversa dalla classe costante.Lineare: il numero delle operazioni dipende linearmente dalla grandezza dell’input, se l’input raddoppia anche il numero delle operazioni raddoppia. La classe è O(n).

L'ALGORITMO RISOLUTORE

ALGORITMO RISOLUTORE: l'algoritmo risolutore viene impiegato per risolvere un problema.Per algoritmo si intende un insieme di istruzioni che definiscono una sequenza di operazioni mediante le quali si risolvono tutti i problemi di una certa classe.La cosa più importante è che in partenza il problema da risolvere sia ben posto e che sia chiaro l'obbiettivo da raggiungere, che idati di partenza siano noti e sufficienti e che il problema sia risolubile da parte di chi lo affronta.Se manca una di queste condizioni l'algoritmo non può essere individuato.Un'altra cosa importante è non confondere il risultato con la soluzione.L'individuazione dell'algoritmo risolutivo di un problema è solo il primo passo di un procedimento in più fasi che conduce alla soluzione del problema stesso in modo automatico.Il passo successivo all'algoritmo consiste nella trasformazione di quest'ultimo in un linguaggio di programmazione.L'algoritmo è solo la descrizione delle operazioni da svolgere, è quindi un'entità statica costituita da istruzioni anch'esse statiche.Quando l'algoritmo viene eseguito si ottiene un flusso di esecuzione che invece è ovviamente dinamico ed è costituito da passi.Un algoritmo deve avere delle proprietà specifiche :GENERALITA': il metodo che permette di decidere se un qualsiasi numero naturale è primo;FINITEZZA: l'algoritmo deve avere un numero finito di istruzioni;ESEGUIBILITA': l'algoritmo deve essere eseguibile dalla macchina e quindi non deve prevedere istruzioni sconosciute (l'insieme delle istruzioni eseguibili da un computer da al computer la cardinalità);RIPRODUCIBILITA': più esecuzioni successive dell'algoritmo sugli stessi dati di input devono dare lo stesso risultato;NON AMBIGUITA': non possono esserci istruzioni vaghe, il metodo di soluzione deve essere completo e deterministico;DISCRETEZZA: l'esecuzione deve avvenire per passi discreti, perchè i dati coinvolti nei calcoli assumono valori che cambiano tra un passo e l'altro ciò comporta che non assumono valori intermedi;NON LIMITATEZZA DELL'INPUT: non deve esserci un limite alla lunghezza dei dati di input;NON LIMITATEZZA DEI PASSI D'ESECUZIONE: devono essere possibili esecuzioni costituite da un numero infinito di passi.

ISTANZE

ISTANZA: nella programmazione ad oggetti l'istanza rappresenta l'oggetto di una classe. L'istanza non è altro che una variabile con degli attributi che possono essere diversi per ogni oggetto stanziato e dei metodi con i quali è possibile accedere e modificare tali attributi.Quindi, mentre la classe rappresenta una sorta di modello, l'oggetto è una entità ben definita del modello. L'istanza di un problema è una possibile formulazione del problema quando alle sue variabili sono stati assegnati valori particolari.

CASO PEGGIORE

Non è possibile esprimere la complessità temporale di un algoritmo utilizzando come unità di misura i secondi, in quanto dobbiamo effettuare una valutazione che non deve dipendere da una particolare macchina o da un particolare compilatore.Per confrontare gli algoritmi indipendentemente dai dati è più significativo considerare sempre il CASO PEGGIORE.

CARDINALITA' n

LA CARDINALITA' :è una proprietà delle istanze. Se indichiamo con n la dimensione di un'istanza, questa raggruppa tutti gli input che hanno la stessa dimensione: la indicheremo come cardinalità n dei dati in ingresso.Per ogni istanza del problema l'algoritmo deve fornire la soluzione, indipendentemente dai valori, dal tipo e dalla cardinalità delle variabili.

FUNZIONE T(n)

LA FUNZIONE T(n) :esprime il tempo necessario affinchè l'algoritmo A possa produrre la soluzione di un'istanza di dimensioni n.

COMPLESSITA' ASINTOTICA

COMPLESSITA' ASINTOTICA: La complessità asintotica si usa per misurare l'efficienza di un particolare algoritmo, a prescindere dalla macchina utilizzata, bisogna valutare l'utilizzo di memoria e di tempo da parte dell'algoritmo i funzione dell'input.Per vedere come aumenta il tempo e la memoria all'aumentare dell'input , dobbiamo rifarci alla complessità asintotica attraverso 1 nuova notazione: O( o grande) prende il nome di NOTAZIONE O-GRANDE che è un criterio matematico per partizionare gli algoritmi in classi di complessità.Nel caso di una funzione composta da diversi termini la complessità asintotica è definita dal TERMINE DI COMPLESSITA' MAGGIORE, conta solo l'ordine di grandezza del termine più significativo.

NOTAZIONE O GRANDE

CLASSI DI COMPLESSITA'

LINEARE

PSEUDO LINEARE

COSTANTE

FATTORIALE

LOGARITMICA

ESPONENZIALE

n^k

PROPRIETA' ALGEBRICHE

TEOREMA DELLA SOMMA

TEOREMA DELLA SOMMA :la complessità di un blocco costituito da più blocchi in sequenza è quella del blocco di complessità maggiore.

TEOREMA DEL PRODOTTO

TEOREMA DEL PRODOTTO :la complessità di un blocco costituito da più blocchi annidati è data dal prodotto della complessità dei blocchi componenti.Se due sono equivalenti per capire qual'è il migliore calcoliamo la notazione O-GRANDE.

ISTRUZIONE DOMINANTE

PARAMETRI

SOGGETTIVI

SOGGETTIVI: semplicità di comprensione, accessibilità, qualità di scrittura, bellezza grafica..

TRASMISSIONE

COMPLESSITA' DI TRASMISSIONE: tempo di trasmissione , efficienza di I/O di un slgoritmo rispetto a "stazioni remote".Non è possibile esprimere la complessità temporale di un algoritmo utilizzando come unità di misura i secondi, in quanto dobbiamo effettuare una valutazione che non deve dipendere da una particolare macchina o da un particolare compilatore.Per confrontare gli algoritmi indipendentemente dai dati è più significativo considerare sempre il caso peggiore.

SPAZIALE

COMPLESSITA' SPAZIALE: dimensione del programma, occupazione di memoria

INPUT E OUTPUT

COMPLESSITA' DI I/O: tiene conto del tempo impiegato per l'acquisizione o il trasferimento dei dati

TEMPORALE

COMPLESSITA' TEMPORALE: indica il tempo impiegato

PASSI BASE

ACCESSO AD ARRAY

OPERAZIONI BOOLEANE

I/O DA TASTIERA

SOMMA ALGEBRICA

ASSEGNAZIONE

MICROSECONDI (10^-6)

OGGETTIVI

OGGETTIVI: legati alla velocità e al tempo.

GRAFICA

SEMPLICITA' DEL CODICE