Riassunto esame Algoritmica, prof. Romani, libro consigliato Elementi di Algoritmica di Francesco Romani

RAM.

Seconda parte: Analisi e sintesi di algoritmi

5. Introduzione alla complessità computazionale concreta

Dato un qualunque problema esistono infiniti algoritmi per risolverlo. Il problema sta nell’individuare il

migliore fra essi: la complessità computazionale concreta studia appunto la questione dell’efficienza degli

algoritmi e del costo della risoluzione dei problemi. La difficoltà nel risolvere un problema dipende dalla

sua natura e dalla sua dimensione, la quale è comunemente legata al numero dei dati in input. Un problema

di riconoscimento di una stringa ha come dimensione la lunghezza della stringa, operazioni su alberi e grafi

hanno come dimensione il numero dei nodi e degli archi, i calcoli di una RAM hanno come dimensione la

lunghezza della stringa di input, e così via. Dato un modello di calcolo si possono scegliere varie misure di

costo che tengono conto della qualità della risorsa utilizzata per risolvere un problema. Un computer reale

può avere come misure di costo il tempo di elaborazione in secondi (misura di tempo) o il numero massimo

di byte di memoria utilizzati (misura di spazio).

Si definisce complessità o costo di un algoritmo una funzione non negativa, non decrescente e a valori

interi, che associa alla dimensione del problema il costo della sua risoluzione in base alla misura scelta. Uno

stesso algoritmo, con dati diversi della stessa dimensione, può presentare diversa complessità. In questo

caso si parla di complessità nel caso peggiore se si prende in considerazione il caso più sfavorevole e di

complessità media se si prende in considerazione la media dei casi.

Si definisce complessità del problema una funzione che associa alla dimensione del problema il minimo

costo della risoluzione in base alla misura scelta. Anche in questo caso, se la funzione dipende anche dal

dato di ingresso e non solo dalla sua dimensione, si parla di complessità nel caso peggiore o di complessità

media. Per determinare la complessità di un problema bisognerebbe individuare e valutare tutti gli algoritmi

che lo risolvono, ma questo studio è chiaramente impossibile. Si ricorre quindi a funzioni che limitino la

complessità dal basso all’alto: se per il problema P si trova un algoritmo A di complessità f(n) che lo

risolve, si dice che f(n) è una limitazione superiore alla complessità di P; se si dimostra che non esiste alcun

algoritmo di complessità minore o uguale a g(n) che risolve il problema, allora si dice che g(n) è una

limitazione inferiore alla complessità di P. Se per uno stesso problema P vale che f(n)=g(n), allora si afferma

che la complessità di P è f(n).

In generale una funzione di complessità risulta essere complicata e poco intuitiva, poiché deve tener conto di

molti dettagli (fasi della risoluzione, misura di complessità, ecc.) Per ovviare a questo inconveniente

comunemente si introduce il concetto di ordine di grandezza di una funzione, ovvero ci si concentra sulla

velocità di crescita della funzione di complessità al tendere di n all’infinito.

Con la notazione O(f(n)) si indica l’insieme delle funzioni g(n) per cui esistono due costanti c e n tali che

0

g(n) ≤ c f(n) per ogni n > n . Si dice quindi che g(n)=O(f(n)), ovvero che g(n) è di ordine f(n).

0

Con la notazione Ω(f(n)) si indica l’insieme delle funzioni g(n) per cui esistono due costanti c e n tali che

0

g(n) ≥ c f(n) per ogni n > n . Si dice quindi che g(n)=Ω(f(n)), ovvero che g(n) è di ordine omega f(n).

0

In base alla loro complessità gli algoritmi sono suddivisi in classi di funzioni:

Complessità costante: tutte le costanti reali sono dell’ordine di 1, a=O(1)

• Crescita lineare: tutte le funzioni del tipo an + b (2n, 3n + 2, ecc.) sono dell’ordine di n, an + b=O(n)

• 2 2

Crescita quadratica: tutte le funzioni del tipo an + bn + p(log n) + c sono dell’ordine di n

• 3 2 3

Crescita cubica: tutte le funzioni del tipo an + bn + cn + p(log n) + d sono dell’ordine di n

• k k

Crescita logaritmica: tutte le funzioni del tipo a log n + (termini di ordine inferiore) sono dell’ordine di log n

• n m

Crescita esponenziale: tutte le funzioni del tipo a + b + p(n) + q(log n), con n>m, p e q polinomi di

• n

qualsiasi grado e a>b>1, sono dell’ordine di a

Si parla di limitazioni inferiori e superiori anche interini di ordine di grandezza; quando la limitazione inferiore

è dello stesso ordine di quella superiore, si è determinato l’ordine di grandezza della complessità del

problema. E’ possibile limitare superiormente l’ordine di grandezza di funzioni limitate da relazioni ricorrenti

β

del tipo: f(n) ≤ u f ([n/v]) + c n , per ogni n>n . Poiché una simile relazione compare spesso nell’analisi di

0

algoritmi definiti per ricorrenza, vediamo in dettaglio il seguente lemma:

6. Tecniche di programmazione ricorsiva

La ricorsione è un potente strumento per la descrizione degli algoritmi e agevola la determinazione di

limitazioni superiori alla loro complessità.

La funzione fattoriale n! è definita ricorsivamente come 0!=1, n!=n(n-1)!, con n>0:

>>>

def fattoriale(n): 12! 479001600

if n==0: 13! 6227020800

return 1 14! 87178291200

return n* fattoriale(n-1) >>>

print ("12!", fattoriale(12))

print ("13!", fattoriale(13))

print ("14!", fattoriale(14))

Un programma che stampi la rappresentazione binaria di un numero intero positivo si basa

sull’osservazione che, dato un numero n, se la sua rappresentazione binaria R(n) ha k cifre, questa consiste

nelle prime k-1 cifre di R(n), ovvero R(n/2), seguite dall’ultima cifra n%2:

>>>

def binario(n): 100011

if n==0: >>>

return''

return binario(n//2)+str(n%2)

print(binario(35))

La Torre di Hanoi è un noto rompicapo che consiste in tre pioli e un numero qualsiasi di ciambelle di

dimensione decrescente. I pioli sono numerati da 1 a 3 e all’inizio le ciambelle sono impilate in ordine sul

piolo 1. L’obiettivo è spostarle tutte dal piolo1 al piolo2 senza che mai una ciambella più piccola stia sotto ad

una più grande. Il terzo piolo è usato come ausilio per i trasferimenti. Qualunque algoritmo di risoluzione

deve potersi suddividere in tre passi: a) sposta le prime n-1 ciambelle da piolo1 al piolo3, b) sposta l’ultima

ciambella dal piolo1 al piolo2, c) sposta le prime n-1 ciambelle dal piolo3 al piolo2.

def muovi (sorgente, destinazione): >>>

print("muovi da ", sorgente, " a ", destinazione) mosse per 4 dischi

muovi da 0 a 2

muovi da 0 a 1

def hanoi (n, sorgente, destinazione, ausiliario): muovi da 2 a 1

if n==1: muovi da 0 a 2

muovi(sorgente, destinazione) muovi da 1 a 0

else: muovi da 1 a 2

hanoi(n-1, sorgente, ausiliario, destinazione) muovi da 0 a 2

muovi(sorgente, destinazione) muovi da 0 a 1

hanoi(n-1, ausiliario, destinazione, sorgente) muovi da 2 a 1

muovi da 2 a 0

muovi da 1 a 0

print ("mosse per ", 4, " dischi") muovi da 2 a 1

hanoi(4, 0, 1, 2) muovi da 0 a 2

muovi da 0 a 1

muovi da 2 a 1

>>>

La complessità di questo algoritmo si calcola con la relazione di ricorrenza H(1)=1; H(n) ≤ 2H(n-1) + 1, e per

n

induzione si dimostra H(n)=2 - 1.

L’algoritmo della Torre è il primo esempio di applicazione della tecnica del divide et impera, che consiste nel

dividere il problema in più sottoproblemi della stessa natura ma di dimensioni inferiori, i cui risultati vengono

ricombinanti per ottenere la soluzione del problema originario. Il problema P viene diviso in sottoproblemi k

che vengono risolti ricorsivamente con lo stesso algoritmo. Il costo dell’algoritmo di risoluzione si calcola in

base alla relazione di ricorrenza C(n) ≤ C(n1) + C(n2) + … + C(nk) + costo del lavoro di combinazione.

Un caso particolare si ha quando ni ≤ [n/h] con i=1, 2, …, k e il costo di combinazione si può limitare con

β β

c n , allora vale che C(n) ≤ k C([n/h]) + c n .

Prendiamo come esempio problema della somma di un array di n numeri: a) se l’array ha lunghezza 1 il

problema è risolto, b) si divide l’array in due parti e se ne calcolano le somme parziali, poi si sommano. La

relazione di ricorrenza che da il numero di addizioni è S(n) ≤ 2S([n/2]) + 1, ovvero S(n)=O(n).

def somma1(v, i, j): >>>

if i==j: 45

return v[i] >>>

else: return somma1(v,i,(i+j)//2)+somma1(v,(i+j)//2+1, j)

A=[1,2,3,4,5,6,7,8,9]

print (somma1(A,0,len(A)-1))

I parametri della funzione sono v (vettore), i (posizione di partenza) e j (posizione finale), per cui il risultato

finale sarà dato ricorsivamente dalla somma dei sottovettori che vanno da i a j:

def somma1(v, i, j):

if i==j:

return v[i]

else: return somma1(v,i,(i+j)//2)+somma1(v,(i+j)//2+1, j)

A=[1,2,3,4]

print (somma1(A,0,len(A)-1))

somma1(A,0,3)

• somma1(A,0,1)+somma1(A,2,3)

• [somma1(A,0,0)+somma1(A,1,1)]+[somma1(A,2,2)+somma1(A,3,3)]

•

In questo caso non c’è nessun guadagno rispetto al banale algoritmo di addizione di vettori, perché in ogni

caso il numero di operazioni dipende dal numero di elementi da sommare. Però in generale, la partizione del

problema in due sottoproblemi il più possibile bilanciati porta a una notevole riduzione della profondità

dell’albero di computazione.

7. Algoritmi di ricerca

Un’operazione che ricorre frequentemente è la ricerca di un elemento detto chiave in un insieme di dati

omogenei detto tabella. Spesso alla chiave è associata l’informazione alla quale si vuol accedere con la

ricerca, mentre a volte lo scopo è sapere se una chiave è presente in una tabella o meno. Si distinguono più

casi:

Ricerca in insiemi di chiavi già prestabiliti, ovvero la tabella è stata precedentemente organizzata per

• effettuare le ricerche (elenchi, rubriche personali, dizionari, ecc.); in questo caso la ricerca può essere

ottimizzata in funzione delle chiavi

Si permette l’uso di algoritmi di ricerca e inserzioni

• Si prevede di effettuare ricerche, inserzioni e cancellazioni

•

La ricerca lineare è il più semplice algoritmo di ricerca in una lista, poiché gli elementi sono scanditi in

sequenza fino a trovare ciò che ci interessa o fino alla fine della lista:

def ricercaLineare (v, x): >>>

for i in range(len(v)): True

if v[i]==x: False

return True >>>

return False

A=[1,3,5,7,9]

print(ricercaLineare(A,3))

print(ricercaLineare(A,2))

La com