Algoritmi & Principi dell'informatica

P’.

In generale: se trovo un algoritmo che, data un’istanza di P’ ne costruisce la

soluzione ricavandone un’istanza di P per il quale a sua volta so ricavarne la soluzione,

ho ridotto P’ a P.

Esempio: se so risolvere il problema della ricerca di un elemento in un insieme posso

costruire un algoritmo per risolvere il problema dell’intersezione tra due insiemi.

Ricondurre quindi a problemi noti risolvibili.

Funziona anche il viceversa: se so di non poter risolvere un y∈S’ se trovo una funzione

t calcolabile e totale tale che y∈S’ <=> t(y)∈S concludo che un ipotetico x∈S non è

decidibile.

Questa tecnica si può usare per dimostrare l’indecidibilità di molte proprietà tipiche

dei programmi durante la loro esecuzione: indici di array fuori dai limiti, compatibilità

dinamica dei tipi..

NB: Molti errori a run-time come la divisione per 0 sono problemi semidecidibili e non

non decidibili perché prima o poi scopro l’errore PERO’ è semidecidibile la PRESENZA

dell’errore (se c’è lo trovo) non l’assenza!

L’assenza di errori in un programma non è ne decidibile né semidecidibile.

Complessità

Il costo di un algoritmo è basato sulle risorse: memoria e tempo di esecuzione.

Complessità temporale: sia c |- c |- c |- … |- c T (x)=r se la computazione termina

0 1 2 r m

in c altrimenti ∞.

r k

∑ | |

+1 }

max ⁡{ a i=1 … r

Complessità spaziale: sia c |- c |- c |- … |- c T (x)= (a

0 1 2 r m ij

ij

j=1

contenuto del nastro j alla mossa i-esima).

Per le complessità verrà sempre considerato il caso pessimo.

NB: Complessità in f(x) -> complessità in f(n) con n=”dimensione dei dati ingresso”

cioè n=|x|.

Il valore esatto di Tm(n) non è rilevante, è di interesse il tasso di crescita per esempio,

2 2

avendo Tm(n)=3n +12n+35, è noto che si comporterà come n . Interessa il

comportamento asintotico.

Notazione O-grande (O(n)): indica un limite asintotico superiore cioè che

 2 2

3n +12n+35 ∈ O(n )

3 4

ma ∈ anche a O(n ), O(n ) etc..

Notazione Ω-grande (Ω(n)): indica un limite asintotico inferiore cioè che

 2 2

3n +12n+35 ∈ O(n )

ma ∈ anche a O(n) etc..

Notazione Θ-grande (Θ(n)): indica un limite asintotico che è sia inferiore che

 superiore cioè che

2 2

3n +12n+35=O(n ).

Le tre notazioni godono della proprietà transitiva, riflessiva, simmetrica, simmetrica

trasposta in più Θ è anche una relazione di equivalenza. L’uso dell’ordine di grandezza

permette di evidenziare con facilità la parte più importante di una funzione di

complessità.

NB: La complessità spaziale non potrà mai essere < Θ(n) perché i dati almeno una

volta vanno letti.

1° Teorema di accelerazione lineare: se L è un linguaggio accettato da una MT M a

k nastri con complessità S (n), per ogni c>0 (con c∈R) si può costruire una MT M’ (a k

M

nastri) con complessità S (n)<cS (n).

M’ M

2° Teorema di accelerazione lineare: se L è accettato da una MT M a ka nastri con

complessità S (n), si può costruire una MT M’ a 1 nastro (non nastro singolo) con

M

complessità S (n)= S (n) (si mettono le parti significative dei k nastri nell’unico

M’ M

nastro, una dietro l’altra).

3° Teorema di accelerazione lineare: se L è un linguaggio accettato da una MT M a

k nastri con complessità S (n), per ogni c>0 (con c∈R) si può costruire una MT M’ a 1

M

nastro con complessità S (n)<cS (n) (si mettono le parti significative dei k nastri

M’ M

nell’unico nastro, una dietro l’altra + codifica).

4° Teorema di accelerazione lineare: se L è un linguaggio accettato da una MT M a

k nastri con complessità T (n), per ogni c>0 (c∈R) si può costruire una MT M’ (a k+1

M

nastri) con complessità T =max{n+1,cT (n)}.

M’ M

NB: I miglioramenti possono essere al massimo lineari (mantenendo lo stesso

algoritmo), miglioramenti di ordini di grandezza più grandi possono essere ottenuti

solo cambiando algoritmo.

Macchine RAM: modello astratto di calcolatore.

Utile per capire meglio la complessità all’interno di un calcolatore (in una MT per la

somma di due numeri serve una complessità di Θ(n), in un calcolatore è fornita come

elementare, questo perché le MT hanno un accesso sequenziale alla memoria, un

calcolatore ha accesso diretto).

Lista di instruction set e semantica per le macchine RAM:

Esempio di macchina RAM che calcola se un numero è primo: Nota bene:

M[1] contiene

sempre il valore di ingresso.

Nota bene2:

Assunzione: non si

conta l’input nella

complessità spaziale. (Scriverlo

sempre).

Il costo dell’esecuzione di un programma tramite RAM dipende dalle istruzioni.

Per ora viene assunto che ogni istruzione abbia costo costante, quindi:

Da 1 a 6 vengono eseguite una volta: c +c +c +c +c +c quindi costo costante k .

1 2 3 4 5 6 1

Da 7 a 18 vengono eseguite nel caso pessimo n volte: n*(c +c +…+c ) quindi costo

7 8 18

nk .

2

Da 18 a 22 eseguite una volta: c +c +c +c quindi costo costante k .

19 20 21 22 3

In definitiva: T (n) = k + nk + k quindi il costo T (n)=Θ(n) (NB: n non è la lunghezza

r 1 2 3 r

dell’input!).

Algoritmo di ricerca binaria: input sequenza ordinata di numeri interi e uno da

cercare, output 1 se l’elemento cercato esiste nella sequenza, 0 altrimenti.

La complessità di questo algoritmo di ricerca in una macchina RAM è T (n)= Θ(log(n)).

r

Con una MT, lo stesso algoritmo avrebbe avuto complessità Θ(nlog(n)) che è maggiore

di Θ(log(n)).

Il costo costante delle istruzioni è troppo astratto, viene quindi considerato un criterio

a costo logaritmico perché le istruzioni non possono avere tutte lo stesso costo. Si

ottengono quindi dei nuovi costi:

(Esempio per MUL scolastica):

Costo di algoritmi di ordinamento noti:

2

Insertion sort: temporale Θ(n ), spaziale O(1).

Merge sort: Θ(nlog(n)), spaziale Θ(n).

Quick sort: Θ(n2), spaziale O(log(n)).

Un algoritmo divide-et-impera è un algoritmo che prende un problema e lo divide in

sottoproblemi ognuno con dimensione 1/b rispetto a quello originale.

Se il sottoproblema ha dimensione n piccola a sufficienza (n<c costante arbitraria del

problema) esso può essere risolto in tempo Θ(1) altrimenti indichiamo con D(n) il

costo di divere il problema, C(n) il costo di ricombinare i sottoproblemi e T(n) il costo

per risolvere il problema totale, si ottiene che:

Per trovare la complessità di algoritmi ricorsivi ci sono tre tecniche principali:

Sostituzione: intuire una possibile soluzione, sostituirla alla soluzione nella

 ricorrenza e dimostrare

per induzione che la presunta soluzione è tale per l’equazione/disequazione alle

ricorrenze.

Esempio con complessità della ricerca binaria:

Albero di ricorsione: Si calcola la profondità massima delle chiamate e la si

 pone =1.

Si risolve isolando la n che rappresenta la complessità (NB: è noto che la

profondità massima

di un albero è posta sull’estrema destra del disegno dell’albero stesso).

Esempio:

If(N>1){ x

Return N+f(N/2); Parte ricorsiva: N/2 = 1 => x=log(n)

}else{return 1}

Master theorem: Trovare l’espressione T(n) della ricorsione.

 n ¿

Per essere applicabile la ricorsione deve avere forma T(n)=aT( +f(n) con

b

a≥1 e b>1. ( )−Ɛ

log a

Si confronta l’espressione di f(n) con ponendole uguali.

n b

Il più grande tra i due rappresenterà il costo della ricorsione.

Esempio: 2 2

T(n)=5T(n/2)+n log(n) quindi si ha a=5, b=2 e f(n)=n log(n).

( )−Ɛ

log 5

2 2 2,3-Ɛ

Si confronta n log(n)= da cui n log(n)=n (Nb: log (5)=2,3 circa)

n 2 2

2,3 2

dato che n è sempre > di n si ha che la ricorsione ha complessità Θ(n)=

( )

log 5 .

n 2

Strutture Dati – Pile, code, liste e tabelle hash

Una struttura dati è un costrutto usato per contenere oggetti, rappresentano

collezioni di oggetti.

Spesso gli oggetti di una struttura dati hanno una “chiave” che serve per indicizzare

l’oggetto e dei “dati satelliti” associati che sono i dati di interesse che porta con sé

l’oggetto.

Esempio: si ricerca una chiave per accedere ai dati satellite.

Possono esserci operazioni che modificano la collezione o che interrogano la

collezione.

Operazioni tipiche su una struttura dati:

Search(s,k): restituisce l’oggetto x nella collezione s con chiave k.

 Insert(s,x): inserisce l’oggetto x nella collezione s.

 Delete(s,x): cancella l’oggetto x dalla collezione s.

 Minimum(s): restituisce l’oggetto nella collezione con la chiave più piccola.

 Maximum(s): restituisce l’oggetto nella collezione con la chiave più grande.

 Successor(s,x): restituisce l’oggetto che segue x nella collezione in base ad un

 ordine.

Predecessor(s,x): restituisce l’oggetto che precede x nella collezione in base ad

 un ordine.

Pile(Stack): collezione di oggetti sulla quale si possono fare alcune operazioni

specifiche quali controllare se è vuota, inserire un elemento (PUSH), cancellare e

restituire un elemento (POP). Una pila è gestita in LIFO:

l’elemento che viene cancellato dalla POP è quello che è stato inserito per ultimo.

Se la pila può contenere al massimo n elementi può essere implementata come un

vettore di n elementi.

Per tenere traccia dell’indice dell’elemento che è stato inserito per ultimo si usa un

attributo chiamato “top” quindi S.top() è l’indice dell’ultimo elemento inserito.

Se S.top() = 0 allora la pila è vuota (non si possono cancellare elementi).

Se S.top()=S.length la pila è piena (non si possono aggiungere nuovi elementi).

Se la pila è implementata come array la si può gestire in pseudocodice come si

gestirebbe un array sfruttando la funzione “top”.

Code(Queue): simile ad una pila, su una coda si possono eseguire operazioni come

controllare se è vuota, inserire un elemento nella collezione (ENQUEUE) e

cancellare restituend