Appunti per orale di Algoritmi e strutture dati

B A A A

− · } ∀(i,

(v v ) n{v , v > 0 j) (1.4)

j i i i+1

La prima parentesi indica i vertici del polinomio ”di fronte” a quello testato, la seconda sono i

vertici che sto testando.

TUNNELING: è quando un oggetto in rapido movimento attraversa o buca un altro collider senza

rilevare collisione.

SAMPLING: il campionamento, permette di raccogliere i dati per intervalli discreti in una sim-

ulazione continua.

1.6 Collision Resolution

Risolvere le collisioni equivale ad imporre dei vincoli (detti costraints) che rispettino la fisica dell’oggetto.

Esistono vari metodi:

1.6.1 Separazione

Si usa con:

• Coppie di oggetti (A,B) con centri di massa (r , r ) in collisione.

a b

• Asse di collisione a (A = B)

c

• Profondità di penetrazione (d).

e si implementa in tre soluzioni: d

d | ·

− · r (t + 1) = r (t) + a

1. Dinamico vs Dinamico: r (t + 1) = r (t) a B B c

a a c 2 2

− ·

2. Dinamico vs Statico: r (t + 1) = r (t) a d

a a c

·

3. Statico vs Statico: r (t + 1) = r (t) + a d

B B c

1.6.2 Sliding

Si occupa dello scivolamento orizzontale e laterale, salto e trattenuta del personaggio su una parete.

3

La soluzione di questo collider è basato su Swept AABB . In pratica, bisogna occuparsi del verso

del vettore velocità di un oggetto quando urta un altro. L’idea iniziale è di correggere la velocità v,

eliminando la parte che causa compenetrazione.:

− − ·

ṽ = v (v(1 t )) = v t (1.5)

c c

Però ho un problema; sto modificando solo il modulo della velocità e se poi t = 0, la velocità si

c

annulla!

Soluzione: correggo la velocità v, eliminando la parte che causa compenetrazione lungo la normale

di collisione. − − ·

ṽ = v n̂ (v(1 t ) n̂ ) (1.6)

c c c

dove tutto quello compreso nella parentesi è la porzione di v che causa compenetrazione. Si nota poi

che l’oggetto scivolerà su un lato dell’oggetto.

E’ importante l’ordine delle collisioni poiché esse vanno risolte in base al blocco su cui si posiziona

l’oggetto in un istante t c

1.6.3 Bouncing

Rimbalzo con cambio di direzione, attraverso la conservazione della quantità di moto e θ = θ

i r

− ·

ṽ = v 2(v n̂ )

n̂ (1.7)

c c

3 Swept shapes: forme generate dal moto dell’oggetto da t a t1.

Algoritmi dei Videogiochi

2.1 Complessità Asintotica

Nella programmazione molti problemi vengono risolti attraverso diversi algoritmi. La loro carat-

teristica è l’efficienza, a livello di tempo di calcolo delle operazioni elementari e la gestione dello

spazio in memoria.

Verrebbe da pensare che sia facile poter misurare un algoritmo in secondi, però non è cosı̀. Il tempo (in

secondi) dipende dal calcolatore, dal codice inserito, dai dati in input; perciò, si preferisce una misura

che si basi solo sulla dimensione dell’input: la complessità temporale (o computazionale).

Complessità Temporale

Si dice complessità temporale, la funzione T (p(n)), dove:

• T tempo di calcolo

• p(n) passi di calcolo

• n dimensione dati in ingresso

I passi di calcolo sono istruzioni elementari nel codice, come assegnazioni (=), operazioni aritmetiche

(+,-,...), accesso agli elementi di un array.

La più efficace semplificazione che si può adottare è ipotizzare il costo temporale unitario (T = 1)

per ogni passo di calcolo (T (n) = p(n)). Se invece di un’istruzione semplice si ha una istruzione

composta, il costo è limitato da una costante K volte il costo di un’istruzione semplice, proporzionale

ad essa.

Viene riportato un esempio:

for(i = 0; i < n; i++) Ciclo temporale (riga 1):

for(j = 0; j < n; j++) [i = 0] = 1

if(i == j) [i < n] = n + 1,

matrice[i][j] = 1; [i + +] = n

else Ciclo temporale (riga 2)

matrice[i][j] = 0; ·

[j = 0] = 1 n ·

[j < n] = (n + 1) n

·

[j + +] = n n

Confronto

if (i == j) = n

matrice[i][j] = 1

else = n

matrice[i][j] = 1

Ulteriore esempio: Ricerca Lineare

Si ha un vettore A di 14 elementi, voglio trovare elem con un algoritmo di ricerca lineare

for each(i appartenente A) do

if(i == elem) return true;

return false;

Tenendo a mente l’array con posizioni [0, 1, 2, 3, 4, 5, 6, 7, 8, ..., 13], si ha:

• Elem non presente nell’array, scorro tutto il vettore T (n) = n

• Elem = 6, in posizione 7, ho T (n) = n + 1

Si ottengono diversi casi per cui la complessità temporale assume valore minimo (1, caso migliore) o

valore massimo (n, caso peggiore). Si ottiene anche un caso medio (average) nonché media statistica

n−1 1

P · i).

del caso (T (n) =

avg i=0 n

Best-Worst Case (Concetto)

La complessità temporale T (n) di un’istanza I(n) del problema P , si dichiara:

• →

caso migliore T (n) = minT (I(n)), meno lavoro per l’algoritmo

best

• →

caso peggiore T (n) = maxT (I(n)), più lavoro per l’algoritmo

worst

• P

→

caso medio bisogna conoscere la distribuzione di probabilità, T (n) = P (I)T (I)

avg I∈Φ

Classi di complessità

Per piccole dimensioni dell’input, tutti gli algoritmi con diverse complessità temporali hanno tempi

√

di risposta simili. Per grandi dimensioni dell’input, si crea una scala gerarchica tale che: n frazioni

2 3 n

di secondo, n + 5, 2n secondi, n giorni, n secoli, 2 miliardi di secoli. Perciò per grandi dimensioni

di n input, è importante tener conto dell’algoritmo.

2.2 Notazione asintotica

Chiamata f(n) la funzione associata alla complessità temporale o spaziale su un input, utilizza questa

notazione per descriverne l’ordine di grandezza ignorando termini di ordine inferiore. Le notazioni

sono:

• → ↔ ∃ ≥ → ≤ ·

Big O f (n) = O(g(n)) c > 0, n 0 f (n) c g(n)

0

g(n) è più grande di f(n) nel punto n dove la eguaglia.

0

• → ↔ ∃ ≥ → ≥ ·

Big Ω f(n) = Ω(g(n)) c > 0, n 0 f (n) c g(n)

g(n) rimane più piccola di f(n) e sono uguali in n

0

• → ↔ ∃ ≥ · ≤ ≤ ·

Big Θ f (n) = Θ(g(n)) c , c > 0, n 0 : c g(n) f (n) c g(n)

1 2 0 1 2

f(n) è compreso tra le due g(n) ma in n si eguaglia a c .

0 1

2

Esempio: f (n) = 3n + 10

• 2 ⇒ → · → ≤

f(n) = O(n ) c = 4, n = 10 f (10) = 310, g(10) = 310 4 f (n) g(n)

0

• 2 ⇒ → · → ≥

f(n) = Ω(n ) c = 1, n = 0 f (10) = 10, g(10) = 10 0 f (n) g(n)

0

• 2

f(n) = Θ(n )

• 3

f(n) = O(n ) ̸

Si dice f(n) ordine inferiore a g(n) se f (n) = O(g(n)) ma g(n) = O(f (n)).

Si dice f(n) complessità asintotica di g(n) se f (n) = O(g(n)) e g(n) è la più piccola di tutte le

funzioni possibili.

Esistono blocchi in sequenza: f (n) = O(g (n) + ... + g (n)) = O(max{O(g (n)), ..., O(g (n))}

1 k 1 k

· · · · ·

oppure blocchi annidati: f (n) = O(g (n) g (n) g (n)) = O(O(g (n)) ...O(g (n))

1 2 k 1 k

2.3 Calcolo complessità asintotica per algoritmi ricorsivi

Tramite la ricerca binaria su array ordinato, si può elaborare un algoritmo ricorsivo dove

(

c + T (n/2) se n > 1

T (n) = 1 se n = 1

risolvibile attraverso i seguenti modi: iterazione, sostituzione, teorema master.

Iterazione: i 1

T(n) = c + T(n/2) = 2c + T(n/4) = 3c + T(n/8) = ... = ic + T(n/2 ) con complessità O(log n)

2

1 se i = log n

2

Sostituzione:

Trovare attraverso ipotesi induttiva, passo base e passo induttivo una soluzione e verificarla attraverso

l’induzione matematica. n ), T (1) = 1 (2.1)

T (n) = n + T ( 2

Teorema Master

Il teorema master applica il metodo divide et impera.

• Divide il problema in ”a” sottoproblemi(n/b) dove b è fattore di riduzione della dimensione

del problema

• Impera, risolvere i sottoproblemi ricorsivamente e ricombinare le soluzioni, dove f(n) è il costo

della divisone e combinazione dei risultati. n

· ) + f (n) (2.2)

T (n) = a T ( b

L’enunciato fornisce una formula che determina la complessità asintotica di T(n) dal confronto di

a

log

f(n) e n . I tre casi:

b log a−ϵ log a

→

1. f (n) = O(n ) per ϵ > 0 T (n) = Θ(n )

b b

log (a) log a

→ ·

2. f (n) = Θ(n ) T (n) = θ(n log n)

b b 2

log (a)−ϵ · ≤ · →

3. f (n) = Ω(n ) con ϵ > 0; a f (n) c f (n) T (n) = Θ(f (n))

b

Esempi: T (n) = n + 2T (n/2) : a = 2, b = 2

log (2)

g(n) = n 2 log (2)

· ⇒ ·

f (n) = n = c g(n) T (n) = Θ(n log n)

2 2

→

T (n) = c + 3T (n/9) a = 3, b = 9

log (3) 1/2

g(n) = n = n

9 √ √

≤ · →

f (n) c g(n) = n T (n) = Θ( n)

→

T (n) = n + 3T (n/9) a = 3, b = 9

· ≤ · · ≤ · → ≤ ·

a f (n/b) c f (n) = 3 n/9 c n n/3 c n

Condizione di regolarità 1 →

≤ soddisfatto! T (n) = Θ(f (n)) = Θ(n)

c 3

T (n) = 4T (n/2) + n : a = 4, b = 2

log (4) 2

g(n) = n = n

2 2 2

≤ · →

f (n) = n c n T (n) = Θ(n )

Se serve, aggiungere ulteriori esempi qui!

2.4 Algoritmi di Ordinamento

2.4.1 Insertion Sort {6,5,3,1,8,7,2,4}.

Immagina di avere un vettore A di sei elementi Si vuole ordinare in ordine crescente,

un algoritmo è il seguente:

algo insertionSort(array A, int n)

{

for(i = 1 to n-1) // Avvio il ciclo dal primo vettore fino a n-1

{

int key = A[i]; // Key assume valore nella cella i di A, tipo 2

int j = i-1; //j assume l'indice della cella prima dove A valeva 2

}

while(j >= 0 && A[j] > key)

{

A[j+1] = A[j]; //Il valore della casella dopo j passa a quella prima

j = j-1;

A[j+1] = key; //key assume il valore vecchio di j

}

} 2

La sua complessità temporale [Worst Case(tutto disordinato): O(n )] e [Best Case (già or-

dinato): O(n)]

2.4.2 MergeSort

Algoritmo ricorsivo basato, come il teorema master, sul divide et impera. Funzionamento:

1. step: dividere l’array a metà fino a sottosequenze di un elemento

2. step: ordinare quella metà dal valore più piccolo al più grande

3. step: ricombinare le metà ordinate

algo mergeSort(Array A, int i f)

if i >= f //i = inizio; f = fine

return //stoppa il programma;

m = (i+f)/2 //m è il centro dell'array

mergesort(A,i,m)

mergesort(A,m+1,f)

merge(A,i,m,f)

Vediamo meglio la funzione di merge:

algo merge(Array A, int i