Algoritmi e strutture dati - Appunti 2022/2023

1 di 32

Algoritmi e Strutture Dati

1- Istanze e soluzioni

Π f : D ↦ S

Ad ogni problema possiamo associare una funzione Π Π Π

Dove:

D Π

= insieme delle istanze di

• Π

S Π

= insieme delle risposte di

• Π

∀x ∈ D f (x) Π x

= soluzione del problema relativa a

• Π Π

2- Correttezza e algoritmi Φ : In ↦ Out ∪ { ⊥ }

Ad ogni algoritmo ALG associalo una funzione (parziale) ALG ALG ALG

Dove:

In = insieme degli ingressi di ALG

• ALG

Out = insieme delle uscite di ALG

• ALG

DEFINIZIONE

Π

risolve

ALG se e solo se :

In D

=

• ALG Π

Out S

=

• ALG Π

∀x ∈ D f (x) = Φ (x)

• Π Π ALG Π Π

Un algoritmo A che risolve un problema si dice corretto per

3- Le Risorse : Tempo e Spazio

L’e cienza di un algoritmo riguarda la quantità di risorse che vengono impiegate per la soluzione

di un problema. Occorre ssare:

• modello dell’esecutore

• tipo delle istruzioni elementari

Tempo: numero complessivo di istruzioni eseguite

Spazio: memoria occupata (programma + dati)

Il concetto di e cienza viene formalizzato tramite la nozione di Complessità (in tempo/spazio)

4- Complessità Φ : In ↦ Out ∪ { ⊥ }

Per ogni algoritmo ALG con funzione associata , introduciamo

ALG ALG ALG

W : In ↦ N

una funzione che esprime la dimensione dei dati in ingresso

ALG ALG T : N ↦ N

Esprimiamo la complessità di un algoritmo ALG attraverso una funzione che

ALG

indica per ogni intero n la quantità di tempo/spazio impiegata dall’algoritmo per elaborare dati di

dimensione n

FATTO

Un algoritmo può comportarsi in modo sensibilmente di erente anche per istanze del problema

aventi ugual dimensione

ffi ffi fi ff 2 di 32

w

[ T (n) ]

DEFINIZIONE ALG w

T (n)

complessità nel caso peggiore

La di un algoritmo ALG è una funzione che fornisce il

ALG

comportamento dell’algoritmo considerando per ogni dimensione l’istanza più sfavorevole.

b

[ T (n) ]

DEFINIZIONE ALG b

T (n)

complessità nel caso migliore

La di un algoritmo ALG è una funzione che fornisce il

ALG

comportamento dell’algoritmo considerando per ogni dimensione l’istanza più favorevole.

a

[ T (n) ]

DEFINIZIONE ALG a

T (n)

La complessità in media di un algoritmo ALG è una funzione che fornisce il

ALG

comportamento medio dell’algoritmo, calcolato eseguendo la media dei comportamenti sulle

a ∑

T (n) = p c

istanze aventi ugual dimensione dove:

i i

ALG |i|=n

p = probabilità dell’istanza i

• i

c = quantità di risorse impiegate per elaborare l’istanza i

• i In

Indicando con l’insieme dei dati in ingresso di dimensione n, si ha:

n

a ∑ ∑ ∑

T (n) = p c = P k P = p

dove

i i k k i

ALG i ∈ In

i∈In k≥0 n

n c = k

i

|

σ = #{i ∈ In c = k} In

Ponendo e ipotizzando che tutte le istanze siano equiprobabili ,

n,k n i n

σ 1

n,k

a ∑ ∑

T (n) = k = k σ

otteniamo : n,k

ALG #In #In

n n

k k

5- Notazioni Asintotiche

• DEFINIZIONE [ O GRANDE ]

f : N ↦ N g : N ↦ N f (n) = O(g(n))

Una funzione è detta O-grande di una funzione , , se

n c > 0 ∀n > n , f (n) ≤ cg(n)

esistono un intero e una costante per cui: , informalmente

0 0

f g

f (n) = O(g(n)) è “dominata” da

indica che

Ω

• DEFINIZIONE [ GRANDE ]

f : N ↦ N ω g : N ↦ N f (n) = Ω(g(n))

Una funzione è detta -grande di una funzione , , se

n c > 0 ∀n > n , f (n) ≥ cg(n)

esistono un intero e una costante per cui: , informalmente

0 0

f (n) = Ω(g(n)) f g

è “domina”

indica che

Θ

• DEFINIZIONE [ ]

f : N ↦ N θ g : N ↦ N f (n) = Θ(g(n))

Una funzione è detta di una funzione , , se esistono un

n c, d > 0 ∀n > n , cg(n) ≤ f (n) ≤ dg(n)

intero e una costante per cui: , informalmente

0 0

f (n) = Θ(g(n)) f g

e hanno lo stesso ordine di grandezza.

indica che

∼

• DEFINIZIONE [ ] f (n)

lim =1

f (n) g(n) f (n) ∼ g(n)

è asintotica a , , se g(n)

n→+∞

• DEFINIZIONE [ o PICCOLO ] f (n)

f (n) g(n) f (n) = o(g(n)) lim =0

è un o-piccolo di , se g(n)

n→+∞ 3 di 32

6- Modelli di Calcolo

• Modello RAM ( Random Access Machine )

Caratteristiche:

1. Memoria ad accesso casuale formata da celle ( registri ) che possono contenere un intero

qualsiasi;

2. Istruzioni di un linguaggio macchina elementare;

- Input e output

- Operazioni aritmetiche

- Accesso e modi ca dei registri

- Salti e salti condizionati

Struttura:

• Programma : è ssato e composto da istruzioni indicizzate istr , istr , … che ricordano il

1 2

linguaggio Assembly

• Location Counter ( lc ) : contiene l’etichetta dell’ istruzione da eseguire

• Nastro di Lettura : è dotato di una testina di sola lettura che legge le in nite celle a partire dalla

prima. Ogni cella può contenere un intero

• Nastro di Scrittura : è dotato di una testina di sola scrittura che scrive a partire dalla prima

cella

• Registri : sono in niti e possono contenere interi di qualsiasi dimensione. Ognuno è identi cato

da un indirizzo intero k R

Accumulatore

• : il registro è l’unico sul quale si possono svolgere operazioni aritmetiche

0

Programma:

• E’ una sequenza nita di istruzioni

• Ogni istruzione ha un’ etichetta ( l’ indirizzo contenuto in lc )

• Ogni istruzione è una coppia ( OpCode , Indirizzo )

• Ogni indirizzo può essere un operando o un’ etichetta

TIPOLOGIA OpCode INDIRIZZO

Spostamento dati tra i registri LOAD , STORE

Operazioni aritmetiche ADD , SUB , MULT , DIV OPERANDO

Lettura e Scrittura READ , WRITE

Istruzioni di salto JUMP , JGTZ , JZERO , JBLANK ETICHETTA

Arresto HALT N/a

etichette

Le sono associate solo ai comandi di salto e indicano a quale istruzione viene passato il

controllo

operando

Un può assumere tre forme diverse :

• =i i ∈ Z

indica l’intero

i

• R i ∈ N

indica il contenuto di ( qui )

i

*i R R i, j ∈ N ↦

• indirizzamento indiretto

j

indica il contenuto di , dove è il contenuto di ( )

j i

Stato della Macchina:

È una funzione che associa ad ogni registro ( compreso lc ) il suo contenuto e alle testine la loro

S : {r, w, lc, 0 , 1 , . . . , k , . . . } → Z

posizione sul nastro. Formalmente , dove :

S(r)

• posizione della testina sul nastro di lettura

S(w)

• posizione della testina sul nastro di scrittura

S(lc)

• contenuto del location counter

S(k) R ∀k ∈ N

contenuto del registro ,

• k

S

Stato Iniziale :

0

S (r) = S (w) = S (lc) = 1

• 0 0 0

S (k) = 0 , ∀k ∈ N

• 0 fi

fi fi fi fi fi 4 di 32

Esecuzione di un programma:

S

Poni la macchina in ed esegue il ciclo fetch - decode - execute nché lc non indica l’istruzione

0

HALT

Ciclo: Fetch

1. : Individua l’istruzione da eseguire mediante lc

Decode

2. : Decodi ca il comando tramite l’ OpCode

Execute

3. : Esegui l’istruzione secondo la sua semantica aggiornando lo stato della

macchina

Valore degli operandi:

op

Un operando allo stato S assume un valore che dipende dalla sua forma. Indichiamo tale

i se op e′ = i , dove i ∈ Z

S se op e′ i , dove i ∈ N

i

V (op) =

valore con S S(S(i)) se op e′ * i , dove i ∈ N e S(i) ≥ 0

⊥ altrimenti

Computazione: S , S , . . . , S , . . .

È una sequenza ( nita o in nita ) di stati nella quale:

0 1 i

S è lo stato iniziale

• 0

∀i , S S (lc) S

P

si ottiene eseguendo l’istruzione di indice del programma nello stato

• i+1 i i

S S (lc)

Se la sequenza è nita e è l’ultimo stato, allora indica un’ istruzione di HALT o un’

m m

istruzione che non può essere eseguita

Semantica del linguaggio RAM: ∞ ∞

n n

⋃ ⋃

F : Z → Z ∪ { ⊥ }

Si ottiene associando ad ogni programma P la funzione parziale P n=0 n=0

n

∀n , ∀x ∈ Z

P.

calcolata da , F ( x)

Se la computazione si arresta, è il vettore di interi risultante sul nastro di uscita

• P

F ( x) = ⊥

Altrimenti

• P

• Modello RASP ( Random Access Stored Program )

Nel modello RAM, il programma non è memorizzato nella memoria dei registri e le istruzioni non

possono essere modi cate durante l’esecuzione.

Modello RASP

Il mantiene il programma in memoria e permette di modi care le istruzioni durante

l’esecuzione.

Struttura Comprende le di erenze tra RAM e RASP

( ) :

• ma manca l’indirizzamento indiretto ( *i )

Set di istruzioni identico al modello RAM,

• Il programma è caricato in memoria

• Ad ogni istruzione sono associati due registri:

• Il primo codi ca l’istruzione e il tipo di operando

• Il secondo contiene l’indirizzo

• lc

Il registro viene automaticamente incrementato di 2

• La memoria contiene inizialmente il programma in una sequenza pre ssata di registri

• Equivalenza tra RAM e RASP

Teorema n

∀Φ ∃Ψ ∀n ∈ N , ∀x ∈ Z

programma RAM , programma RASP , tale che ,

F ( x) = F ( x)

• Φ Ψ

T ( x) ≤ 6 * T ( x)

• Ψ Φ  



fi fi fi

fi fi fi ff fi fi fi 5 di 32

7- Complessità Computazionale

DEFINIZIONE

complessità computazionale

La di un algoritmo è la quantità di risorse da esso utilizzata

durante la computazione.

• Minori sono queste risorse maggiore è l’e cienza dell’algoritmo

• Tali risorse vengono de nite come costi in termini di tempo e spazio

• Esistono due criteri di costo: Uniforme e Logaritmico

Utilizziamo il modello RAM per avere un sistema formale generale per studiare la complessità di

un algoritmo

Criterio di costo Uniforme ( CCU ):

Assume che ogni operazione abbia costo unitario in tempo e spazio. Si assume quindi che:

• La dimensione di ogni operando sia unitaria

• Lo spazio utilizzato da ogni registro sia unitario

DEFINIZIONE x t s

Secondo il CCU, un programma RAM su input richiede tempo di calcolo e spazio di memoria

T ( x) = t S ( x) = s

P x t s

se la computazione di su esegue istruzioni e utilizza registri: P P

Limiti del CCU: poco signi cativa,

In alcuni casi tale misura è poiché non tiene conto delle dimensioni degli interi

utilizzati

• Nella realtà i registri possono contenere un numero limitato di bit, quindi le operazioni con

numeri grandi non hanno costo costante

• Tale metodo è considerato realistico solo per gli algoritmi che non incrementano troppo la

dimensione dei valori in ingresso

Criterio di costo Logaritmico ( CCL ):

È un criterio più preciso e realistico.

• Il costo dell’istruzione dipende dalla dimensione dell’operando

• dimensione

La di un intero è il numero di bit necessari alla sua memorizzazione

⌊ ⌋

| |

l(k) = log ( k ) + 1

Lunghezza NOTA BENE:

di un intero k , , Per k grande

• 2

| |

l(k) ≈ log k

2

Costo degli Operandi nel modello RAM

t (a) a S

= Costo di un operando nello stato

S t (a)

OPERANDO a COSTO S

l(i )

=i l(i ) + l(S(i ))

i l(i ) + l(S(i )) + l(S(S(i )))

*i

Costo delle Istruzioni

-Istruzioni di spostamento

ISTRUZIONI COSTO

T (a)

LOAD a S

l(S(0)) + l(i )

STORE i l(S(0)) + l(i ) + l(S(i ))

STORE *i

Esempio S(0) = 1024 , S(128) = 512 istr = STOR E * 128

S

Consideriamo tale che e l’istruzione

t (istr) = l(S(0)) + l(128) + l(S(128)) = l(1024) + l(128) + l(512) = 10 + 7 + 9 = 26

S fi fi ffi 6 di 32

-Istruzioni Aritmetiche

ISTRUZIONI COSTO

l(S(0)) + T (a)

ADD a S

l(S(0)) + T (a)

SUB a S

l(S(0)) + T (a)

MULT a S

l(S(0)) + T (a)

DIV a S

-Istruzioni di Lettura/Scrittura

ISTRUZIONI COSTO

l(X ) + l(k)

READ k S(r)

l(X ) + l(k) + l(S(k))

READ *k S(r)

T (a)

WRITE a S

-Istruzione d’arresto

ISTRUZIONI COSTO

HALT 1

-Istruzioni di Salto

ISTRUZIONI COSTO

JUMP b 1

l(S(0))

JGTZ b l(S(0))

JZERO b

JBLANK b 1

DEFINIZIONE l

T ( x)

tempo di calcolo logaritmico P x

Il richiesto dal programma su input è la somma dei costi

P P x

logaritmici delle istruzioni eseguite nella computazione di su input

Osservazioni:

l

T ( x) ≤ T ( x) ∀input x

• P P l

T ( x) << T ( x)

In alcuni casi

• P P 7 di 32

8- Grafi

DEFINIZIONE [ Grafo NON orientato ]

⟨V, ⟩

G = E dove:

• V insieme nito ( nodi )

(2)

E ⊆ V

• ( lati )

DEFINIZIONE [ Grafo orientato ]

⟨V, ⟩

G = E dove:

• V insieme nito ( nodi )

2

E ⊆ V

• ( archi )

⟨V, ⟩ | | | |

G = E n = V m = E

Siano , e . Vale:

2

0 ≤ m ≤ n

• ( G orientato )

n(n − 1)

0 ≤ m ≤ ( G non orientato )

• 2

m = O(n)

• sparso

G è se 2

m = Θ(n )

• denso

G è se

DEFINIZIONE [ Sottografo ]

⟨V′ ⟩ ⟨V, ⟩

G′ = , E′ G = E

è sottografo di se e solo se

V′ ⊆ V

• ′

(2)

E′ ⊆ E ∩ V′ × V′ E′ ⊆ E ∩ V

• ( o se G non orientato )

DEFINIZIONI

(x, x)

• cappio

è detto (v, w) ∈ E {v, w} ∈ E

• adiacente

w v

è a se ( )

| |

Adiac(v) = {w (v, w) ∈ E} Adiac(v) = {w {v, w} ∈ E}

• insieme di adiacenza v

L’ di è ( nel

caso non orientato ) ⟨V, ⟩ |

G = E x , x , . . . , x (x , x ) ∈ E , 1 &l