UNIVERSITA' DEGLI STUDI DI PISA

CORSO DI INGEGNERIA INFORMATICA (NUOVO ORDINAMENTO)

APPUNTI DI INFORMATICA TEORICA

Parte prima

Complessità computazionale, funzioni ricorsive, liste, alberi

Il corso di informatica teorica si divide in due parti fondamentali: I- Complessità computazionale; II- Teoria della calcolabilità.

Partiamo ora dal primo troncone , la complessità computazionale.

Complessità di un algoritmo

Prendiamo una funzione e ne associamo un certo costo che indicheremo d'ora in poi con il simbolo T(n) con [T:N → N]. La dimensione (in un algoritmo è data dal peso degli elementi compresi in esso) implica un costo nell'algoritmo, in pratica a una dimensione maggiore occorre un tempo di esecuzione alto, ad una minore un tempo relativamente basso.

Quindi Dimensione => Costo, un algoritmo che richiede molti passaggi tra altrettanti elementi avrà bisogno di un tempo maggiore per la sua risoluzione.

Esempio 1: T(n)=n² => il costo di questa di questo algoritmo è dato dalla dimensione, che in questo caso è data da n che rappresenta il numero degli elementi, che a sua volta apporta a d un costo pari alla dimensione '2'.

Tratteremo il costo in questo corso come 'tempo' soprattutto, ma può anche voler dire spazio di memoria occupato nello svolgimento del programma.

Da ogni programma si tirerà fuori una funzione simile del tipo T(n):N → N.

Esempio 2: Abbiamo tre algoritmi che chiameremo p, q ed r, i quali calcolano la stessa funzione; studiamo i loro contenuti e ricaviamo queste tre funzioni di complessità: Tp(n)=n², Tq(n)=2n², Tr(n)=n³/2; ora facciamo l'analisi di queste funzioni e da un primo confronto possiamo scartare l'algoritmo r, poiché è di ordine maggiore e nel grafico la curva caratteristica va prima all'infinito rispetto alle altre due; p e q, invece, sono molto simili, poiché la loro curva caratteristica differisce solo per il coefficiente '2', quindi all'infinito non ci sono in pratica differenze.

Possiamo quindi dare una prima definizione (errata): Tp(n)≤ Tq(n) per ogni n, quindi p è meglio di q; ma la definizione giusta è un'altra ed è la seguente.

Def.1: una funzione g(n) è o(f(n)) [con 'o' rappresenta la classe migliore, ovvero letteralmente 'meglio'] se esistono n, c costanti tali che per ogni n ≥n', g(n)≤c*f(n).

Quindi continuiamo la nostra analisi: Tp(n) è o(Tr(n)) per n'=2 e c=1, cioè il programma p è migliore o uguale a quello r, dimostrando che per ogni valore di n≥2 Tp(n)<Tr(n); dopodiché analizziamo Tp(n)che è o(Tq(n)) per n'=1 e c=1, ma anche Tq(n) che è o(Tp(n)) per n'=1 e c=2.

Poniamoci ora questo quesito: per n'=1 e c=50 000, Tr(n) è o(Tp(n))? NO, perché non per tutte le n>n' vale la legge Tr(n)<Tp(n), quindi Tr(n) non può essere o(Tp(n)). Se abbiamo un altro algoritmo h(n) che è o(Tp(n)), allora sarà anche vera che h(n) è o(Tq(n)).

Elenchiamo ora le classi di complessità più diffuse:

• o(n²) tutte le funzioni, o classi di funzioni, che crescono come n²
• o(n) programmi che crescono di costo linearmente rispetto alla dimensione
• o(1) programmi che hanno un tempo costante (programmi più semplici)
• o(log n) programmi di complessità logaritmica, intermedia tra o(1) e o(n)
• o(n log n) programmi di complessità logaritmica, intermedia tra o(n) e o(n²).

Esistono poi altre classi meno diffuse, ma ugualmente importanti, e che sono le classi polinomiali o(nS), le classi logaritmiche o(nS log n), e infine le classi esponenziali o(aⁿ) , le più difficili, molte delle quali ancora insolute.

Data la def. 1 analizziamo la presenza dei fattori costanti: o(f(n))~ o(k*f(n)) [con '~' 'simile'] → o(n)~ o(3n), cioè le costanti non hanno grande rilievo nel calcolo della complessità di una funzione.

Ora passiamo alla regola della somma: o(n² + n)~ o(n²), cioè hanno maggiore rilevanza le classi di più alto grado poiché influiscono molto di più sulla curva caratteristica all'infinito, quindi passiamo al seguente

Teorema 1: abbiamo una funzione f(n) che è o(g(n)), quindi f(n) + g(n) appartiene alla classe o(g(n)), cioè la somma di due funzioni mantengono la  complessità di quella più grande. I gradi di complessità contengono al loro interno anche le classi successive, cioè le più grosse.

Dimostrazione: prendiamo la def. 1 per cui esistono n' e c tali che per ogni n≥n' f(n) ≤c*g(n), quindi se abbiamo f(n) + g(n) ≤ c*g(n) + g(n), quindi f(n) + g(n)≤ (c+1)*g(n); in conclusione possiamo affermare che f(n) + g(n) è o(g(n)).

Esempio: f(n)=n³+3n²+n+4, quindi la funzione f(n) appartiene alla classe di complessità o(n³) per l'applicazione incondizionata delle due regole precedenti.

Prodotto: abbiamo f(n) є o(g(n)) e h(n) є o(k(n)), quindi f(n)*h(n) є o(g(n)*k(n)).

Regola della transitività: abbiamo f(n) є o(g(n)) e g(n) є o(k(n)), quindi si può definire f(n)є o(k(n)). Perciò una funzione generica nS (con a costante e reale) є o(2ⁿ), di conseguenza il tempo da prendere in considerazione nel programma sarà la n all'esponente (la base può essere qualsiasi).

Abbiamo ora altre due funzioni f(n) e g(n), passiamo alla loro analisi e notiamo che non possiamo dare una relazione di complessità in tutti i casi tra le due funzioni; in questi episodi siamo di fronte a funzioni incommensurabili.

Esempio: f(n)=n²[per n pari] | n[per n dispari]; g(n)=n[per n pari] | n²[per n dispari]; f(n) è o(g(n))? si sovrappongono n ed n², quindi non si può confrontare né in un modo né nell'altro, tutt'al più la loro somma è o(n²); in questo caso siamo in presenza di funzioni incommensurabili.

Calcolo della complessità dei programmi

Espressioni [assegnamenti, operazioni aritmetiche, etc.]: complessità costante. Quale sarà il tempo per calcolare le nostre espressioni?

C[k]← costante = o(1) non ci si mette tempo a calcolarla.

C[x]← variabile = o(1) il tempo rimane comunque costante.

C[E1 operator  E2]← operazione generica = C[E1] + C[E2] + o(1) [tempo dell'operazione].

C[f(E1,E2,.;En)]← chiamata di funzione = C[E1] + C[E2] +.+C[En] + + T[body]: il tempo non è costante e dipende da più parametri, T[body] sta a significare il tempo di esecuzione del corpo del programma. C sta per la complessità tipica dell'espressione in esame.

C[x[E]] = C[E]

C[x = E] = C[E]

C[c1, c2] = C[c1] + C[c2]

int massimo ( int a[N])

Analizziamo ora questo programma C++ che dato un vettore di interi ritorna il suo valore massimo.

Le prime due istruzioni danno un tempo costante, quindi C = o(1); l'ultima istruzione è del tipo C[return E] che risulta uguale alla complessità C[E] che a sua volta è o(1).

L'istruzione centrale, segnata come "istruzione composta", è formata da un for con innestato al suo interno un if , il quale è a sua volta formato da un'istruzione logica e un assegnamento, operazioni entrambi dalla complessità costante; ora rimane da valutare il tempo di esecuzione del for, cioè C[for] = o(n)[iterazione operata tante volte quanto è 'pesante' il vettore] + o(1)[tempo dell' if] che risulta pari a o(n). Infine si passa a sommare le complessità della funzione totale e il risultato finale è o(n).

Complessità del for: C[for(i=E1; i<E2; i=E3) ]= C[E1] + o(g(n))*(C[E2] + C[body] + +C[E3]; dobbiamo innanzitutto calcolare la complessità dell'espressione E1 che viene eseguita una e una sola volta dal for, dopodiché si passa al calcolo del numero di iterazioni che può compiere (si considera sempre la 'peggiore' delle ipotesi) che si moltiplicano a loro volta alla somma delle altre due espressioni e il corpo del for che saranno ripetute ad ogni iterazione.

Complessità dell'if C[if(E) else ] = C[E] + o(f(n) + g(n)), con C[body] = o(f(n)) e C[another] = o(g(n)).

Complessità del while: while e do sono un mix di if e for innestati. C[while (E) ] = C[E] + +o(g(n))*(C[body] + C[E]), con o(g(n)) la complessità data dal calcolo del numero di iterazioni del while stesso.

int g (int n)

In questo programma la complessità totale è o(n) e non o(n²) come si potrebbe erroneamente pensare, e questo perché n è limitata al caso sia minore di 500, mentre il calcolo della complessità computazionale si basa su casi generici che divergono all'infinito, quindi è più preciso parlare di complessità lineare (dire o(n²) non è sbagliato, poiché una funzione come abbiamo già detto appartiene anche alle classi di complessità maggiori, ma pecca di precisione).

Alcuni algoritmi

Vedremo ora qui di seguito alcuni algoritmi di ordinamento: il selectionSort e il bubbleSort, ma prima definiremo una funzione tanto semplice quanto fondamentale, la scambia:

void scambia (int A[ ], int i, int j)

void selectionSort (int A[ ], int n)                                      //fine del programma e complessità totale pari a o(n²)

void bubbleSort (int A[ ], int n) //fine del programma e complessità totale C=o(n²)

I vantaggi dell'algoritmo di ordinamento bubbleSort rispetto al selectionSort sono due, anche se dal punto di vista della complessità siamo alla pari: 1- con un booleano si può uscire immediatamente se l'array è già ordinato; 2- negli scambi di files conviene perché scambia elementi vicini. Ma c'è anche uno svantaggio che è dato dal fatto che gli scambi possono essere n², mentre nel selectionSort ne sono al massimo n.

Funzioni ricorsive

Per spiegare questa classe di funzioni partiamo con un semplice esempio: il calcolo del fattoriale. Il fattoriale è definito da una funzione puramente ricorsiva. Abbiamo un caso base, cioè lo '0!' che è uguale a 1, dopodiché possiamo definire n! come n*(n-1!). Passiamo ora al codice C++.

int fact (int n)                                                    //complessità finale o[n]

A questo punto possiamo dare una prima definizione operativa di funzione ricorsiva: questa maniera di programmare comporta innanzitutto l'individuazione di uno o più casi di base che terminano l'operazione e impediscono all'algoritmo di ciclare (loop), poiché si passa alla chiamata (o alle chiamate) ricorsiva che deve essere fatta su elementi più piccoli del primo,, in modo tale da ridursi sempre sui casi base. Altri esempi.

int pari (int n)                                                    //nel rispetto di queste tre regole siamo sicuri che il programma

//termina, ma non che funzioni

int mcd (int x, int y)

Liste

Passiamo ora a studiare una classe di elementi quale la lista, tipo ricorsivo perché considerata come un elemento seguito da una lista, contrapposto all'array, tipo iterativo. Questa è la struttura tipica della lista generalizzata su più tipi predefiniti o classi definite dall'utente.

struct Elem

int lung (Elem* l)

int presente (Elem l, Type x)

Calcoliamo ora la complessità dei due programmi. Iniziamo da 'lung' e prendiamo il caso in cui la lista sia vuota e troviamo che T(0)=a, con 'a' un tempo costante; adesso prendiamo una lista generica con n>0 e abbiamo che la relazione di ricorrenza è T(n)=b + T(n-1), quindi secondo il criterio dell'induzione possiamo concludere che la complessità è o(n), stessa cosa per l'algoritmo 'presente'.

Questo è il preludio alla teoria della complessità che si può sintetizzare con una tabella, la seguente, in cui data una certa relazione di ricorrenza T(n)= cT(n/b) + hnS, possiamo definire la complessità così:

T(n) є o(nS)             se c < bS

T(n) є o(nS log n)                           se c = bS

T(n) є o(n ^ log[base b] c)  se c > bS

Queste sono dette "relazioni del metodo del divide et impera". Il metodo del divide et impera è da far risalire a quella classe di algoritmi che operano su oggetti ordinati dividendo e scartando nella ricerca. Ne vediamo ora di seguito un esempio.

Int ricBin (int A[ ], int n, int x, int i = 0, int j = n-1)

Questo algoritmo ha una relazione di ricorsività pari a T(n)= b + T(n/2), quindi secondo la precedente tabella abbiamo una complessità pari a o(log n), dimostrabile dal fatto che l'algoritmo visita nella peggiore delle ipotesi non tutti gli elementi, ma una quantità pari al logaritmo in base due degli elementi.

Ora analizziamo un altro algoritmo di ordinamento. Il quickSort ha questo funzionamento: dato un array di n elementi, si seleziona quello centrale e lo si chiama 'perno', dopodiché si spostano in cima gli elementi minori del perno e in basso quelli più grandi. Infine si fa la chiamata ricorsiva alle due parti, superiore e inferiore all'elemento con etichetta uguale al perno, separatamente fino all'ordinamento dell'array.

void quickSort (int A[ ], int n, int inf = 0, int sup = n-1)

} while (s <=i); //la complessità totale di questo do - while è o(n), perché

//la visita all'array è singola

if (inf < i) //condizioni di stop

quickSort (A, n, inf, i); //prima chiamata

if (sup > s) //altra condizione di stop

quickSort (A, n, s, sup); //seconda chiamata

La relazione di ricorrenza è T(n)= b*n + 2*T(n/2), quindi la complessità totale dell'algoritmo risulta pari a o(n log n). In conclusione l'algoritmo quickSort ha una complessità migliore rispetto agli altri tipici dell'ordinamento di array.

Def. 2: (metodo del divide et impera) spezzando il problema in tanti sottoproblemi si arriva al quickSort, che l'algoritmo di ordinamento migliore e più efficiente tra quelli trovati.

si esamina il problema e lo si divide in b sottoinsiemi di uguale dimensione ed equilibrati;

si richiama la funzione in maniera ricorsiva su alcuni sottoinsiemi (non sempre è necessario per tutti);

al termine della ricorsione l'algoritmo ricombina i risultati.

Principio di induzione

Per passare allo studio della complessità dei programmi che operano su liste bisogna dare uno sguardo completo al principio di induzione, che è definito quanto segue.

Def. 3: (principio di induzione) base dell'induzione → vero per n = | lista | = 0.

Ipotesi: la funzione f è vera su liste di dimensioni di n elementi

Tesi: la funzione f è vera su una lista di dimensione n + 1 elementi

Per l'induzione si può dimostrare anche l'efficienza dei programmi.

int f (Elem* l, int x)

Analizziamo la complessità. T(0)=a costante, quindi vero per n=0; ora vediamo per n>0, e scriviamo la relazione di ricorrenza T(n + 0)= b + T(n - 1), conseguentemente la complessità non può essere che o(n).

Alcuni algoritmi su liste

void deletex (Elem*& l, int x)

//complessità pari a o[n]

void appende (Elem*& l1, Elem* l2)                                      //complessità o[n]

Elem* appende (Elem* l1, Elem*l2)                                      //complessità o[n]

void split (Elem*& l1, Elem*& l2)

for (int n = 0; n < (i/2); n++) //si posiziona lista 1 al centro

l4 = l4->next;

l2 = l4->next;

l4->next = NULL;

Elem* merge (Elem* l1, Elem* l2)

l2->next = merge (l1, l2->next);

return l2;

Elem* mergeSort (Elem* l1)

Alberi binari

Funzione ricorsiva formata da nodi seguiti da due alberi binari. Gli alberi binari possono essere composti anche da un insieme di nodi vuoto. Un nodo è chiamato radice dei due sottoalberi che partono da esso. Il nodo che segue la radice è detto figlio destro o sinistro della radice (che a sua volta è chiamata padre). Nodo antecedente di tutti i nodi che lo seguono nei sottoalberi da esse discendenti. Nodo discendente di tutti i nodi che gli sono antecedenti. I nodi che non hanno figli né destri né sinistri sono detti foglie. Il livello di un nodo è dato dal numero dei suoi antecedenti, partendo dal livello zero, per poi arrivare ad un generico livello 'x'. Il livello dell'albero è dato dal massimo livello raggiunto dai suoi nodi.

Il compilatore nel assegnare la priorità agli operatori di un'espressione, crea un albero binario che in esecuzione viene visitato nell'ordine in cui operandi e operatori devono essere posti.

Nel linearizzare un albero binario si rischia sempre di perdere informazioni.

Nella struttura del nodo ci sono tre campi: il primo è quello fondamentale ed è l'etichetta che può essere formata da un tipo predefinito o da una classe definita dall'utente, gli altri due sono i puntatori ai sottoalberi destro e sinistro.

struct Node

Adesso passiamo agli algoritmi di visita di alberi binari, tramite la visita anticipata (preordre), la visita posticipata (postordre)  e la visita ordinata (inordre).

void preordre (Node* tree)

void postordre (Node* tree)

void inordre (Node* tree)

In tutte e tre le visite i nodi degli alberi vengono visitati una e una sola volta tutti, quindi la complessità di questi algoritmi è o(n). E' importante il fatto che i figli negli alberi sono sempre disgiunti ed hanno uno e un solo padre.

Alberi generici

Per definizione un albero generico è formato da un nodo seguito da n sottoalberi. Non si può definire però l'albero binario come un sottoinsieme di albero generico, poiché ci sono alcune differenze sostanziali che rendono i due alberi profondamente diversi: gli alberi binari hanno figli destri e sinistri, mentre gli alberi generici non hanno un numero ben determinato di figli, i binari possono avere sottoalberi vuoti, mentre gli altri possono avere delle foglie che non sono seguite da nulla.

La memorizzazione dell'albero generico è legata al metodo dello schema del figlio-fratello. Nella struttura del nodo abbiamo il solito campo etichetta, seguito da due puntatori, uno che punta al primo figlio e l'altro al fratello più vicino, quindi ci si avvicina molto alla struttura classica dell'albero binario.

struct Node

Questo tipo di struttura si chiama astratta e la sua definizione si trova nella disciplina della programmazione orientata agli oggetti. La differenza tra questa struttura e quella concreta è tutta nelle visite. Mentre nella struttura astratta la visita posticipata non funziona (poiché non da alcun ordine effettivo), negli altri due casi la visita è molto più agevolata; infatti sfruttando la normale visita anticipata degli alberi binari abbiamo una corretta visita in preordre dell'albero, sfruttando poi la visita simmetrica (o definita ordinata), abbiamo una corretta visita posticipata.

Caratteristica degli alberi generici che li differisce da quelli binari è il fatto che la radice ha il puntatore destro (il puntatore al fratello) sempre nullo, se così non fosse avremo un albero binario.

Albero binario di ricerca

Gli alberi binari di ricerca sono quegli alberi che appartengono a date classi le quali hanno particolari algoritmi di ingresso e di uscita, ma che hanno grosse proprietà dal punto di vista delle applicazioni a programmi specifici. La caratteristica principale di questi alberi è data dal fatto che ogni nodo è seguito a sinistra da un sottoalbero formato da nodi di valore minore alla sua etichetta e a destra da un sottoalbero con elementi maggiori. La ricerca in questi alberi è particolarmente efficiente, poiché vengono visitati solo il logaritmo in base due del numero dei nodi, escludendo ad ogni ricorsione un intero sottoalbero. Un albero binario di ricerca si dice bilanciato quando tutti i nodi, tranne quelli all'ultimo livello, hanno sempre due figli e non ci sono foglie che all'ultimo livello.

void insertNode (Type x, Node* tree)

if (tree->label == x) //in un albero binario di ricerca non possono

return; //coesistere due nodi uguali

if (x < tree->label) //seleziona la zona di inserzione

insertNode (x, tree->left);

insertNode (tree->right);

Node* findNode (Type x, Node* tree)

Node* findNode (Type x, Node* tree)

Notiamo così che la ricerca di un nodo in un albero binario di ricerca è molto più veloce ed immediata rispetto a quella su un albero generico.

Altra proprietà dell'albero binario di ricerca è quello di avere, tramite una visita simmetrica, una lista ordinata crescente degli elementi.

Heap

Lo heap (mucchio) è un particolare albero binario 'quasi' bilanciato, cioè ha fino al penultimo livello ha tutti i nodi pieni, e all'ultimo livello le foglie si dispongono tutte a sinistra. Caratteristica principale dello heap è la sua gerarchia: ogni nodo ha etichetta maggiore di tutti i suoi eredi. La sua struttura è linearizzata su un array statico, con la radice all'indice '0' e i figli sinistro a (2i + 1) e destro a (2i + 2), con 'i' indice generico del nodo padre. Vediamo alcuni algoritmi tipici che operano su heap.

void insert (Type h[ ], Type x, int & last)

void up (Tipe h[ ], int i)

void down (Type h[ ], int i, int last)

}

int extract (Type h [ ], int & last)

Passiamo ora all'algoritmo di ordinamento heapSort, il quale prende un array generico e lo ordina trasformandolo prima in uno heap e poi facendo tanti extract quanti sono gli elementi dell'array. Questo metodo ordina dal più piccolo al più grande, e il processo non si può invertire se non tramite una seconda trasformazione che capovolge l'array. Vediamo ora il codice C++ del programma.

void buildHeap (int A[ ], int n)

void heapSort (int A[ ], int n)                                                                                  //grande dell' heap rimasto