Want to make creations as awesome as this one?

Transcript

Complesssità computazionale

La complessità computazionale è una branca dell'informatica teorica che si occupa di studiare la quantità di risorse computazionali necessarie per risolvere un determinato problema. Queste risorse possono essere il tempo (numero di operazioni elementari eseguite) o lo spazio (quantità di memoria utilizzata) richiesti da un algoritmo per produrre un output corretto.

START

L'algoritmo

Qualità e costo di un algoritmo

Complessità computazionale

Cos'è un algoritmo

Cos'è un algoritmo

Per algoritmo si intende una successione di istruzioni o passi che definiscono le operazioni da eseguire sui dati per ottenere i risultati. Lo schema esecutivo di un algoritmo specifica che i passi devono essere eseguiti in sequenza, salvo diversa indicazione. Gli algoritmi sono ampiamente utilizzati in tutte le aree dell’IT (Information Technologies). Volendo fare un esempio di algoritmo in informatica, i motori di ricerca come Google sono basati proprio su questo concetto per poter rispondere quanto più coerentemente alla richiesta di un utente.

Caratteristiche di un algoritmo

Esistono diverse tipologie di algoritmo, ma possiamo individuare alcune proprietà comuni, senza le quali un algoritmo non potrebbe essere definito come tale:

-I passi che costituiscono lo schema devono essere “elementari”, ovvero non ulteriormente scomponibili (atomicità); -I passi che costituiscono lo schema devono essere interpretabili in modo diretto e univoco dall’esecutore, sia esso umano o artificiale (non ambiguità); -L’algoritmo deve essere finito, ossia composto da un numero definito di passi legati ad una quantità definita di dati in ingresso (finitezza); -L’esecuzione dello schema deve avvenire entro un tempo finito (terminazione); -L’esecuzione dello schema algoritmico deve condurre ad un unico risultato (effettività).

Algoritmi che "imparano"

· Oggi in genere si parla di algoritmi con riferimento al settore dell’intelligenza artificiale, quel ramo dell’informatica che progetta software software per i robot, o per i computer, che sembrano capaci di pensare e ragionare come un uomo (ecco... quasi!). Soprattutto, gli algoritmi sono legati al tema del machine learning, cioè l’apprendimento automatico delle macchine: anziché ripetere i set di istruzioni fornite “senza imparare nulla”, i sistemi che si basano sul machine learning li riscrivono e li migliorano mentre li eseguono, mentre lavorano. In questo modo gli algoritmi diventano sempre più sofisticati, e a volte non del tutto comprensibili nemmeno a chi li ha inizialmente programmati! Sono gli algoritmi a trovare la strada più veloce e meno trafficata su Google Maps, o a suggerirvi un film su Netflix in base a ciò che più vi piace (come fanno a capirlo? Vedono quello che avete scelto finora…). Una serie di algoritmi mette in ordine i risultati sui motori di ricerca, facendo “salire” quelli con più link, più parole chiave o spiegazioni migliori. Sono gli algoritmi che decidono che cosa far comparire sulla bacheca di Facebook, o quali annunci pubblicitari proporci mentre siamo online, e sono sempre loro a distorcere la voce dei trapper con l’autotune. Algoritmi specializzati ci permettono poi di interpretare le immagini rimandate dallo Spazio dando loro forme e colori “terrestri”; ma anche di mappare il complesso codice del DNA umano, o di fare previsioni su comportamenti o fenomeni futuri: semplicemente, perché questi set di istruzioni sono spesso in grado di individuare connessioni che all’occhio umano sfuggono.

Diversi tipi di algoritmo

-Algoritmo di forza bruta: Questo è il tipo più comune in cui si concepisce una soluzione esplorando tutti i possibili scenari. -Algoritmo greedy: In questo, prendiamo una decisione considerando l'opzione migliore locale (immediata) e la assumiamo come ottimale globale. -Algoritmo Divide et Impera: Questo tipo di algoritmo divide il problema principale in sottoproblemi e poi li risolve individualmente. -Algoritmo di backtracking: Questa è una forma modificata di Brute Force in cui si fa un backtracking alla decisione precedente per ottenere l'obiettivo desiderato. -Algoritmo randomizzato: Come suggerisce il nome, in questo algoritmo, facciamo scelte casuali o selezioniamo numeri generati casualmente. -Algoritmo di programmazione dinamica: Questo è un algoritmo avanzato in cui ricordiamo le scelte che abbiamo fatto in passato e le applichiamo negli scenari futuri. -Algoritmo ricorsivo: Questo segue un ciclo, in cui seguiamo un modello dei casi possibili per ottenere una soluzione.

Qualità di un algoritmo

Per valutare la qualità di un algoritmo bisogna valutare due aspetti: -la sua organizzazione interna, ovvero la struttura data alle sue istruzioni e le strutture utilizzate -le risorse necessarie per eseguirlo, legate allo spazio e al tempo necessari per la sua esecuzione

Dato un problema e uno o più algoritmi che lo risolvono, ora l’obiettivo sarà confrontarli per individuare il migliore sulla base di un’analisi qualitativa. Tra le risorse, va posta particolare attenzione a spazio di memoria e tempo di esecuzione. Per risorsa spazio si intende l’area di memoria occupata da un processo durante la sua esecuzione, chiamata memoria di lavoro. Per risorsa tempo, invece, intendiamo il tempo di esecuzione del processo dell’algoritmo. Oggi però sono in circolazione computer con grandi di capacità di memoria a costi relativamente bassi, fattore che rende la risorsa spazio molto meno importante.

Il costo di un algoritmo

Per valutare il tempo di esecuzione di un algoritmo e esiste un metodo molto semplice: esprimerlo in unità solari. Per esempio potremmo utilazzare un orologio ed esprimerlo in secondi. Anche se a prima vista questo metodo può sembrare corretto, i suoi risultati non sono attendibili perchè dipendono dalle condizioni in cui viene eseguito il test, cioè: -dalla velocità di esecuzione dell’elaboratore sul quale viene effettuata la prova; -dalla velocità dell’interprete o del compilatore utilizzato per la codifica; -dalla dimensione e dalla disposizione dei dati forniti di input, cioè da quanti dati arrivano in input e come vengono proposti.

Il test può essere valido solo se condizioni di esecuzione sono le stesse in entrambi i casi: -i programmi sono tradotti usando lo stesso interprete o compilatore; -il test è svolto sullo stesso computer, dedicato esclusivamente alla sua esecuzione; -l’esecuzione del test avviene più volte con dati di input diversi per dimensione e disposizione. Queste osservazioni ci portano a capire che nel valutare algoritmo bisogna concentrarsi sull’algoritmo stesso, e non sulla sua implementazione. Per ottenere una valutazione affidabile, misureremo il tempo di esecuzione in numero di operazioni che l’algoritmo deve compiere per fornire dei risultati e chiameremo questo numero costo dell’algoritmo.

Riferendoci a un linguaggio strutturato, possiamo introdurre alcune regole di valutazione per il calcolo del costo delle istruzioni di un algoritmo

-Le istruzioni semplici quali lettura, scrittura, assegnamento hanno un costo pari a uno. -I costrutti iterativi quali MENTRE … FINEMENTRE, RIPETI … FINCHE’ hanno un costo pari alla somma dei costi del test e del corpo del ciclo: il test vale uno, il corpo del ciclo vale quanto la somma dei costi delle singole istruzioni. -I costrutti iterativi quali PER … ESEGUI hanno un costo ottenuto dalla somma dell’inizializzazione della variabile del ciclo, che viene ripetuta una sola volta (costo = 1 ); costo di condizione di fine ciclo, pari al numero di volte che il ciclo viene eseguito più uno per il test finale che permette di uscire dal corpo del ciclo; costo del corpo del ciclo, dato dalla somma dei costi delle istruzioni del corpo moltiplicate per le K volte che il corpo del ciclo viene eseguito; costo di incremento della variabile del ciclo, pari al numero delle volte che il ciclo viene eseguito.-Il costrutto di selezione SE … ALLORA ha costo pari alla somma dei costi del test più il costo della dell’istruzione di chiamata, pari a uno. -L’istruzione di chiamata di un sottoprogramma ha valore uno (per l’istruzione di chiamata) più il costo del sottoprogramma. -L’istruzione composta ha un costo pari alla somma dei costi delle singole istruzioni semplici che la compongono. Il tempo di esecuzione di un algoritmo è proporzionale al suo costo, infatti conoscendo il tempo di esecuzione di un istruzione di tipo unitario, in secondi, basterà moltiplicare il costo complessivo dell’algoritmo per esso, per ottenere il tempo totale di esecuzione dell’algoritmo

Complessità computazionale

Usiamo la notazione generica T(N) per indicare la funzione matematica che indica la relazione esistente tra il numero di operazioni di un programma e la dimensione N dei dati di input. La funzione T(N) viene chiamata complessità computazionale (in tempo) o complessità dell’algoritmo; la dimensione N è anche detta dimensione del problema.

La complessità è legata ai valori dei dati di input e a come i dati sono disposti, oltre che alla loro dimensione. Confrontando due algoritmi è possibile che il primo esegua meno operazioni dell’altro quando la dimensione del problema è bassa, ma che le cose si invertano quando tale dimensione cresce. In questi casi conviene fare riferimento all’ordine di grandezza della complessità, cioè valutare la complessità molto grandi delle dimensioni del problema; si parla di complessità asintotica.

Siano f(N) e g(N) due funzioni. Si dice che f(N) è di ordine di grandezza g(N) e si scrive O(g(N)) se esiste una costante C > 0 tale che, per tutti i valori nel dominio di N, f(N) < C * g(N). f(N) è proporzionale a g(N) se f(N) è O(g(N)) e g(N) è O(f(N)). Si dice anche che f(N) e g(N) sono dello stesso ordine di grandezza. Potremo allora affermare che T(N) è proporzionale a N^2 ovvero all’ordine di N^2:O(N^2).

I problemi computazionali

Nel contesto della complessità computazionale, si distinguono due tipi principali di problemi: i problemi P e i problemi NP. I problemi P sono quelli che possono essere risolti in tempo polinomiale da un algoritmo deterministico, mentre i problemi NP sono quelli per i quali una soluzione può essere verificata in tempo polinomiale, ma non necessariamente trovata in tempo polinomiale. Un problema è considerato NP-completo se è in NP e ogni problema in NP può essere ridotto a esso in tempo polinomiale. Gli algoritmi per risolvere i problemi NP-completi non sono ancora stati trovati in tempo polinomiale, ma se uno di essi fosse scoperto, tutti i problemi NP sarebbero risolvibili in tempo polinomiale. La classe di complessità P rappresenta quindi i problemi per i quali esiste un algoritmo efficiente per la loro risoluzione, mentre la classe NP comprende i problemi per i quali è possibile verificare rapidamente una soluzione proposta. La relazione tra queste classi è uno dei problemi aperti più importanti nella teoria della complessità computazionale ed è oggetto di intensa ricerca da parte della comunità scientifica.

Possiamo individuare alcuni ordini di grandezza per le funzioni T(N) che individuano le classi di complessità (o computabilità):

Complessità costante O(1) o O(C ) —> Indica la complessità degli algoritmi che eseguono lo stesso numero di operazioni indipendentemente dalla dimensione dei dati di input.

Complessità logaritmica O(logN) —> Indica la complessità degli algoritmi che eseguono un numero di operazioni proporzionale a logN.

Complessità lineare O(N) —> Indica la complessità degli algoritmi che eseguono un numero di operazioni proporzionale a N.

Complessità NlogN O(NlogN) —> E’ la classe di molti algoritmi di ordinamento.

Complessità polinomiale O(N^K) —> Ha le dimensioni del problema come base da elevare a un esponente K.

Complessità esponenziale O(K^N) —> Ha le dimensioni del problema come base.

Due algoritmi appartenenti alla stessa classe di complessità posso essere confrontati relativamente al tempo di esecuzione. Siano f1(n) e f2(N) due funzioni con la stessa classe di complessità computazionale, relative agli algoritmi A1 e A2 che risolvono la stesso problema. Diremo che A1 e A2 appartengono alla stessa classe di complessità se il limite tendente a infinito di f1(N) diviso f2(N) è uguale a C con C > 0 costante. Nel caso C < 1 A1 è più efficiente di A2, mentre nel caso C > 1 A2 è più efficiente di A1.

il tempo di esecuzione può essere calcolato in caso:-pessimo – dati d’ingresso che massimizzano il tempo di esecuzione - ottimo – dati d’ingresso che minimizzano il tempo di esecuzione -medio – somma dei tempi pesata in base alla loro probabilità

Confronto fra algoritmi che risolvono lo stesso problema; si valuta il tempo di esecuzione (in numero di passi) in modo indipendente dalla tecnologia dell’esecutore. In molti casi la complessità è legata al tipo o al numero dei dati di input:-ad esempio la ricerca di un valore in un vettore ordinato dipende dalla dimensione del vettore-il tempo è espresso in funzione della dimensione dei dati in ingresso T(n) -per confrontare le funzioni tempo ottenute per i vari algoritmi si considerano le funzioni asintotiche

Complessità temporale

Esempio

data la funzione polinomiale f(n) che rappresenta il tempo di esecuzione dell’algoritmo al variare della dimensione n dei dati di input.La funzione asintotica ignora le costanti moltiplicative e i termini non dominanti al crescere di n es. f(x) = 3x4 +6x2 + 10 funzione asintotica = x4l’approssimazione di una funzione con una funzione asintotica è molto utile per semplificare i calcoli.La notazione asintotica di una funzione descrive il comportamento in modo semplificato, ignorando dettagli della formula; nell’esempio: per valori sufficientemente alti di x il comportamento della funzione f(x) = 3x4 +6x2 + 10 è approssimabile con la funzione f(x) = x4