によって serena silipigni 7年前.
314
もっと見る
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 :
OGGETTIVI: legati alla velocità e al tempo.
SOGGETTIVI: semplicità di comprensione, accessibilità, qualità di scrittura, bellezza grafica..
COMPLESSITA' TEMPORALE: indica il tempo impiegato
PASSI BASE
MICROSECONDI (10^-6)
ASSEGNAZIONE
SOMMA ALGEBRICA
I/O DA TASTIERA
OPERAZIONI BOOLEANE
ACCESSO AD ARRAY
COMPLESSITA' DI I/O: tiene conto del tempo impiegato per l'acquisizione o il trasferimento dei dati
COMPLESSITA' SPAZIALE: dimensione del programma, occupazione di memoria
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.
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.
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.
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
ISTRUZIONE DOMINANTE
PROPRIETA' ALGEBRICHE
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.
TEOREMA DELLA SOMMA
TEOREMA DELLA SOMMA :la complessità di un blocco costituito da più blocchi in sequenza è quella del blocco di complessità maggiore.
CLASSI DI COMPLESSITA'
n^k
ESPONENZIALE
LOGARITMICA
FATTORIALE
COSTANTE
PSEUDO LINEARE
LINEARE
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.
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 semplificare la rappresentazione della complessità computazionale di un algoritmo. Come primo passo il problema viene definito come funzione della grandezza dell’input, che di solito viene indicato con la lettera n. Quindi la complessità di un algoritmo viene definita 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 fisico , 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' COMPUTAZIONALE
Può essere utile a questo punto definire delle classi di complessità che si trovano nell’analisi degli algoritmi più usati :
