Problema 2 · Álgebra UDL 2015

Problema 2 (2 punts). Indexació d'una matriu a vector

Les dades d'entrada d'un algorisme ens venen donades mitjançant una taula de 2 dimensions amb $m$ files i $n$ columnes. Les dades que es troben en la fila $i$ i la columna $j$ les indiquem mitjançant $(i, j)$. Volem emmagatzemar aquestes dades en una llista de mida $m \cdot n$. Per a fer-ho, les dades de cada casella de la taula s'assignen a una posició de la llista seguint l'aplicació $f$ següent:

$$\begin{aligned} f: M \times N &\longrightarrow T \\ (i, j) &\longmapsto n(i - 1) + j \end{aligned}$$

on $M = \{1, \dots, m\}$, $N = \{1, \dots, n\}$ i $T = \{1, \dots, m \cdot n\}$.

a.

En el cas que $m = 5$ i $n = 8$, determineu en quin lloc de la llista es guardarà la informació de la casella $(4, 3)$. I a quina casella li correspondrà el lloc $34$ de la llista?

b.

Determineu en quin ordre es van assignant les caselles a la llista.

c.

En el cas de $m = 4$ i $n = 10$, determineu $f^{-1}(\{20, 30\})$.

d.

Des de un punt de vista de l'enginyer informàtic que ho ha de programar, quin avantatge tindria el fet que $f$ fos injectiva? I que fos exhaustiva?

e.

Justifiqueu si $f$ és o no bijectiva.