Algorithm Analysis

02

03

04

Computabilità

Analisi

Complessità

Sviluppi

1

1

Calcolare il minimo di un insieme di interi

positivi.

Input: < a0; a1; a2; … ; an-1 >

Output:

1

2

3

2

Problema

Memorizzo in una variabile min il

primo elemento dell’insieme.

Eseguo una scansione (ciclo)

dell’insieme A a partire dal secondo

elemento e confronto ogni elemento

di A con il valore memorizzato nella

variabile min

Se l’elemento corrente è < min,

aggiorno la variabile min (cioè

assegno a min l’elemento corrente).

Al termine del ciclo stampo il

minimo.

1

2

3

3

Analisi

4 Pseudocodice

5 Analisi L’algoritmo della ricerca del minimo risolve il

problema (correttezza).

Quante risorse utilizza e quali sono i tempi di esecuzione? (complessità computazionale)

Un algoritmo è corretto se, per ogni istanza di input, termina con l’output corretto

É fondamentale analizzare il tempo di calcolo impiegato per risolvere un problema e lo spazio occupato durante la

computazione (memoria RAM o disco) per poter progettare algoritmi efficienti

6 Complessità T(n) = tempo di esecuzione = numero di operazioni elementari eseguite

S(n) = spazio di memoria = numero di celle di memoria utilizzate durante l’esecuzione

n = dimensione (taglia) dei dati di ingresso

Il tempo di accesso alle risorse può essere calcolato da una funzione costo. La funzione T(n) esprime il tempo necessario affinché l’algoritmo produca la soluzione.

7 T(n) Caso peggiore: (spesso)

T(n) = tempo massimo dell’algoritmo su qualsiasi input di dimensione n

Caso medio: (talvolta) T(n) = tempo atteso su tutti gli input di dimensione n =

tempo di ogni input x la probabilità che ci sia quell’input (media pesata)

È necessaria un’assunzione sulla distribuzione statistica degli input (spesso distribuzione uniforme)

Caso migliore: (fittizio = prob. non si verificherà mai) Ingannevole per algoritmi lenti che sono veloci su qualche

input

8 T(n) Generalmente si cerca un limite superiore perché:

Fornisce una garanzia all’utente L’algoritmo non potrà impiegare più di così

Per alcuni algoritmi si verifica molto spesso Es. ricerca in un DB di informazione non presente

Il caso medio spesso è cattivo quasi quanto quello peggiore Non sempre è evidente cosa costituisce un input medio

9

Costo computazionale: Indichiamo con f(n) la quantità di risorse (tempo di esecuzione e occupazione di memoria) richiesta da un algoritmo su input di dimensione n, operante su una macchina a registri (MT). Si calcola l’ordine di grandezza di f(n) studiando l’analisi asintotica (limite superiore).

10 Esempio T(n)

11 T(n) Qual è il tempo di calcolo di un algoritmo nel caso

peggiore? Dipende dal computer usato

velocità relativa (confronto sulla stessa macchina)

velocità assoluta (su macchine diverse)

“Analisi asintotica” Ignorare le costanti dipendenti dalla macchina

Studiare il tasso di crescita di T(n) con n→∞

12 T(n) Limite superiore del tasso di crescita del tempo di

esecuzione di un algoritmo «O grande»

Definizione: Sia g(n) una funzione non negativa. g(n) è in O(f(n)) se esistono due costanti positive c e n0 tali che g(n) <= cf(n) per

tutti gli n > n0

O(f(n)) = {g(n) : ∃c > 0, n0 ≥ 0 tali che ∀n ≥ n0 : g(n) ≤ cf(n)}

Significato: Per input abbastanza grandi (n>n0) l’algoritmo viene eseguito in un numero di passi inferiore a cf(n)

Limite asintotico superiore

g(n) = O(f(n))

13 T(n) Attenzione!

A causa dei fattori costanti e dei termini di ordine inferiore che vengono ignorati

Se T1(n) > T2(n) [asintoticamente]: Per input piccoli algoritmo1 può richiedere meno

tempo di algoritmo2, ma…

Per input sufficientemente grandi algoritmo2 sarà eseguito più velocemente di algoritmo1

Classi di complessità 1

LINEARE O(n):

Posseduta da algoritmi che

eseguono operazioni

proporzionale ad n o ripetute n

volte. Variante polinomiale se

cicli doppi, ecc…

2

3

COSTANTE O(1):

Posseduta da algoritmi che

eseguono lo sempre lo stesso

numero di operazioni indipendete

dalla dimensione dei dati.

4

14

LOGARITMICA O(n log n):

Posseduta da algoritmi di

ordinamento ottimi.

ESPONENZIALE O(n^k):

Posseduta dal Bubblesort e da

moltiplicazioni tra matrici o

similari.

15 Esempio1 Dato un problema P e due algoritmi A1 e A2 che lo risolvono siamo interessati a determinare quale ha

complessità minore (qual è "il migliore" dal punto di vista dell'efficienza computazionale).

T1(n) = 3n² + n

T2(n) = n² + 10n

Per n>=4.5, T2(n) < T1(n). La complessità di A2 è minore per ingressi con dimensione maggiore di 4.5.

Soluzione: studio la disequazione T1>T2

16 Esempio2 Ricerca se un elemento è presente in un vettore:

Le istruzioni (1) e (2) sono quelle dominanti, e vengono eseguite rispettivamente N+1 volte (per i=0..N) e N volte (per i=0..N-1): dunque il costo è lineare. T(n) = 2*(c1+c2) + (n+1)*c3 + n*c4 + n*c2 + n*(c2+c5) + c6

17 Esempio2

Analisi Asintotica

T(n) = 2*(c1+c2) + (n+1)*c3 + n*c4 + n*c2 + n*(c2+c5) + c6

T(n) = (n+1)*c3 + n*(2*c2+c4+c5)

T(n) = a*(n+1)+b*n = a*n + b*n + a

T(n) = (a+b)*n funzione lineare

18 Esempio3 Data la funzione T(x) è importante studiare il grafico

trovando il massimo e il minimo nel primo quadrante dell’asse cartesiano per capire quando si ottengono

tempi di esecuzione ridotti o tempi di esecuzione alti in modo da predire il comportamento del calcolatore e

comprendere:

- l’efficienza

- l’atteggiamento a regime

- possibili sovraccarichi

19 Esempio3 T(n) = n⁴*log(n)

Dominio = n>0

Intersezione assi = A(0,0);B(1,0)

T(n)’= 4n³*log(n)+n⁴/n= 4n³*log(n)+n³= n³*(4log(x)+1)

T(n)’>= 0 ----> n>0; n>2.15

Min(2.15;21.70)

20 Esempio4 Se T fosse una funzione a due variabili?

T(x,y)= x2 + y2 –2x

In questo caso è importante studiare i massimi e minimi (se esistono). Studiare il limite è più complicato.

Quindi l’unica cosa a cui cambiare significato in R 2 è il modulo, che andrà naturalmente sostituito con la distanza; per cui se (x0,

y0) è un punto di accumulazione per un insieme A dove è definita una funzione f(x, y) diremo che

21 Esempio4

Esercizi per casa ? 1)

2)

22

Dati due algoritmi con T1(n) = 4n² + 10n T2(n) = 3n² + 5n – 6, indicare l’efficienza computazionale.

Creare una funzione che calcola il valore minimo in un vettore e fare l’analisi asintotica.

3) Data T(n) = n*(n-3)² studiare i valori di massimo e minimo se presenti.

4) Data T(x,y) = 4x-x²-y² studiare i valori di massimo e minimo se presenti.

22 Classificazione Problemi

Possiamo classificare i problemi in base alla quantità di risorse necessarie per ottenere la soluzione

Per certi gruppi di problemi, le difficoltà incontrate per trovare un algoritmo efficiente sono sostanzialmente le stesse

Possiamo raggruppare i problemi in tre categorie: 1. I problemi che ammettono algoritmi di soluzione efficienti;

2. I problemi che per loro natura non possono essere risolti mediante algoritmi efficienti e che quindi sono intrattabili;

3. I problemi per i quali algoritmi efficienti non sono stati trovati ma per i quali nessuno ha finora provato che tali algoritmi non esistano

23 Classi di complessità

Classi di problemi risolubili utilizzando una certa quantità di risorse (per esempio di tempo)

Problemi decidibili

hanno una soluzione algoritmica

Problemi indecidibili

non hanno una soluzione algoritmica

24 Problemi dedicibili

Problemi polinomiali (P)

problemi per i quali esistono soluzioni praticabili, cioè di complessità in O(f(n)) dove f(n) è un

polinomio oppure è limitato superiormente da un polinomio

Problemi polinomiali non deterministici (NP)

problemi risolvibili in tempo polinomiale o esponenziale da un algoritmo non deterministico

(non si sa a priori quale decisione prenderà: esperienza, decisione, probabilità, reazioni

chimiche, prova tutte le strade…)

25 Problemi NP

Un commesso viaggiatore deve visitare alcuni suoi clienti in città diverse senza superare il

budget per le spese di viaggio: il suo problema è trovare un percorso (che parta dalla sua

abitazione, arrivi nelle varie città da visitare e poi lo riconduca a casa) la cui lunghezza totale

non superi i chilometri consentiti.

27 Problemi NP

Algoritmo non deterministico Se esiste un percorso accettabile e lo selezioniamo per primo, l’algoritmo

termina velocemente

altrimenti … Seleziona uno dei possibili percorsi e calcola la sua distanza.

if(questa distanza non è

maggiore del chilometraggio consentito)

then (dichiara un successo)

else (non dichiarare nulla)

26 Problemi NP

Soluzione tipica: Si considerano i potenziali percorsi in modo sistematico confrontando la lunghezza di ogni percorso con il limite

chilometrico finché si trova un percorso accettabile oppure sono state considerate tutte le possibilità

Non è una soluzione in tempo polinomiale Il numero dei tragitti da considerare aumenta più velocemente di

qualsiasi polinomio al crescere del numero delle città (n!)

La Clay Institute ha istituito nel 2000 un premio di un milione di dollari per chi riuscisse a risolvere uno dei sette problemi

matematici definiti i problemi del millennio. Uno di questi è quello di rendere i problemi NP = P.

Fine Seconda Parte

27