Vettori

Vettori unidimensionali

• $U$ tipo base del vettore
• $k$ numero di byte occupati da un elemento di tipo $U$
• $n$ dimensione del vettore $V$ $(V \in U^n)$
• $\alpha$ indirizzo base di $V$

Supponiamo che il primo elemento di $V$ sia $V[0]$. Dato $i,0\leq i<n,$ l'indirizzo in memoria di $V[i]$ è $\alpha + k*i$

Si noti come l'indirizzo venga **calcolato in tempo $O(1)$ (**una somma e una moltiplicazione)

Fissato un tipo base $U$ e $n\in \N$, un vettore di lunghezza n è un elemento di $U^n$=$UU...*U$ (n volte)

• PROIEZIONE $\pi:U^n*\N \rarr U \cup\{\perp\}$
  • $\pi(A,i)=\begin{cases} a_i \text{ se } A=(a_i, ..., a_n),1\leq i \leq n \\ \perp, altrimenti \end{cases}$
• SOSTITUZIONE $\sigma : U^n * \N * U \rarr U^n \cup \{\perp\}$
  • $\sigma(A, i, a)=\begin{cases} (a_i, ..., a_{i-1}, a, a_{i+1},...,a_n) \text{ se } A=(a_i, ..., a_n), 1\leq i \leq n \\ \perp, altrimenti \end{cases}$

Sintassi: molti linguaggi di programmazione usano l'operatore []:

$PROIEZIONE \rarr x=A[i]$

$SOSTITUZIONE \rarr A[i] = z$

Implementazione:

Se un singolo oggetto di tipo $U$ richiede $k$ registri, allora $A \in U^n$ viene memorizzato in $k*n$ registri consecutivi.

Noti $\sigma$ (indirizzo base del vettore) e i (indice), l'indirizzo di $A[i]$ è calcolato (in esecuzione) in tempo $O(1)$