Algoritmi e strutture dati - Appunti 2022/2023

Algoritmi e strutture dati

1 di 32

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’efficienza di un algoritmo riguarda la quantità di risorse che vengono impiegate per la soluzione di un problema. Occorre fissare:

• Modello dell’esecutore
• Tipo delle istruzioni elementari

Tempo: numero complessivo di istruzioni eseguite

Spazio: memoria occupata (programma + dati)

Il concetto di efficienza 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 differente anche per istanze del problema aventi ugual dimensione

2 di 32

w[ T (n) ]

DEFINIZIONE ALG wT (n)

La complessità nel caso peggiore 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 bT (n)

La complessità nel caso migliore 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 aT (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 iALG |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 nn c = ki

|σ = #{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 #Inn nk 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 modifica dei registri
• Salti e salti condizionati

Struttura:

• Programma: è fissato 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 infinite 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 infiniti e possono contenere interi di qualsiasi dimensione. Ognuno è identificato da un indirizzo intero k R
• Accumulatore: il registro è l’unico sul quale si possono svolgere operazioni aritmetiche 0

Programma:

• È una sequenza finita 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

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

Un operando 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, kS

Stato Iniziale: 0

• S (r) = S (w) = S (lc) = 1 0 0 0
• S (k) = 0 , ∀k ∈ N 0

4 di 32

Esecuzione di un programma:

S Poni la macchina in ed esegue il ciclo fetch - decode - execute finché lc non indica l’istruzione 0 HALT

Ciclo:

1. Fetch: individua l’istruzione da eseguire mediante lc
2. Decode: decodifica il comando tramite l’OpCode
3. Execute: 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 è = i , dove i ∈ Z S se op è i , dove i ∈ Ni V (op) = valore con S S(S(i)) se op è * i , dove i ∈ N e S(i) ≥ 0 ⊥ altrimenti

Computazione:

S , S , . . . , S , . . .

È una sequenza (finita o infinita) di stati nella quale: 0 1 i

• S è lo stato iniziale 0
• ∀i , S S (lc) SP si ottiene eseguendo l’istruzione di indice del programma nello stato i+1 i iS S (lc)

Se la sequenza è finita 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 modificate durante l’esecuzione.

Il modello RASP mantiene il programma in memoria e permette di modificare le istruzioni durante l’esecuzione.

Struttura Comprende le differenze 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 codifica 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 prefissata 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) Ψ Φ

5 di 32

7- Complessità computazionale

DEFINIZIONE

La complessità computazionale di un algoritmo è la quantità di risorse da esso utilizzata durante la computazione.

• Minori sono queste risorse maggiore è l’efficienza dell’algoritmo
• Tali risorse vengono definite 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:

In alcuni casi tale misura è poco significativa, 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
• La dimensione 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 k2

Costo degli Operandi nel modello RAM

t (a) a S = Costo di un operando nello stato S t (a)

Costo delle Istruzioni

- Istruzioni di spostamento

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

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

6 di 32

- Istruzioni Aritmetiche

- Istruzioni di Lettura/Scrittura

- Istruzione d’arresto

- Istruzioni di Salto

DEFINIZIONE lT ( 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:

• lT ( x) ≤ T ( x) ∀input x P P
• lT ( x) << T ( x) In alcuni casi P P

7 di 32

8- Grafi

DEFINIZIONE [Grafo non orientato]

⟨V, ⟩ G = E dove:

• V insieme finito (nodi)
• (2) E ⊆ V (lati)

DEFINIZIONE [Grafo orientato]

⟨V, ⟩ G = E dove:

• V insieme finito (nodi)
• 2 E ⊆ V (archi)

⟨V, ⟩ | | | | G = E n = V m = E

Siano, e. Vale:

• 0 ≤ m ≤ n² (G orientato)
• 0 ≤ m ≤ n(n − 1) / 2 (G non orientato)
• m = O(n) G è sparso se
• m = Θ(n²) G è denso 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) è detto cappio
• (v, w) ∈ E {v, w} ∈ E w è adiacente a v 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