Examen de Álgebra UDL 2015 · Primer parcial novembre 2015

Problema 1 (2 punts). Relació d'ordre en tuples

Considereu el conjunt $A_n = \{(a_1, a_2, \dots, a_n): a_j \in \{0, 1, 2\}\}$, on definim la relació d'ordre $R$ de la següent manera:

$$(a_1, a_2, \dots, a_n) R (b_1, b_2, \dots, b_n) \iff \begin{cases} a_i \le b_i, & \forall i \text{ senar}, \\ a_i = b_i, & \forall i \text{ parell}. \end{cases}$$

a.

Demostreu que $R$ és antisimètrica.

b.

Determineu si es tracta d'una relació d'ordre total o d'ordre parcial. Estudieu què passa si $n = 1$ i si $n \ge 2$.

c.

Determineu el conjunt $B = \{(a_1, a_2, a_3) \in A_3: (a_1, a_2, a_3) R (1, 0, 2)\}$.

d.

Determineu els elements minimals de $A_3$.

e.

Considereu el conjunt $S = \{(0,0,1), (1,0,0), (2,0,0), (2,0,1)\} \subseteq A_3$. Doneu el diagrama de Hasse de $S$ i determineu, si existeixen, les cotes inferiors i superiors, el màxim i el mínim, i els elements minimals i maximals.

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.