Posterior: Cálculo proposicional Arriba: Estructuras algebraicas básicas Anterior: Ejercicios

Programas

1. Escriba un ensayo sobre la artimética de punto flotante. Indique criterios para decidir cuándo un número real está o no dentro de esa aritmética. Consulte el ANSI/IEEE 754-1985 IEEE Standard for Binary Floating-Point Arithmetic, The Institute of Electrical and Electronics Engineers, Inc., New York, 1985, http://www.wikipedia.com/wiki/IEEE_Floating_Point_Standard

2. Escriba un programa que dados $n,k\in{\mathbb{N}}$, $0\leq k\leq n$, encuentre todos los subconjuntos de $k$ elementos en el conjunto de índices entre 0, y $n-1$, $[\![0,n-1]\!]$.

3. Escriba un programa que dado $n\in{\mathbb{N}}$, encuentre todos los subconjuntos del conjunto $[\![0,n-1]\!]$.

4. Sea $n$ un entero mayor que 1 y sea ${\mathbb{Z}}_n$ el conjunto de residuos módulo $n$. ${\mathbb{Z}}_n=\{0,1,\ldots,n-1\}$. Considere las operaciones suma y producto que coinciden con las usuales de los enteros ${\mathbb{Z}}$ pero tomando residuos módulo $n$:

$$\begin{eqnarray*} x+y &=& (x+y)\mbox{\rm mod }n \\ x\cdot y &=& (x\cdot y)\mbox{\rm mod }n %%\\ \end{eqnarray*}$$

Escriba un programa que dado $n$ escriba las tablas de operaciones $+$ y $\cdot$ de ${\mathbb{Z}}_n$. Observación: El reloj de carátula en su cocina seguramente le puede dar una idea de la suma en ${\mathbb{Z}}_{12}$ (ahí 12=0 pues la medianoche es lo mismo que las cero horas, ¿verdad?).

5. Sea $n$ un entero mayor que 1. Un ideal en ${\mathbb{Z}}_n$ es un subconjunto $A\subset{\mathbb{Z}}_n$ que es cerrado bajo la suma y que ``absorbe productos'':

$$\begin{eqnarray*} \forall x,y\in A &:& x+y\in A \\ \forall x\in A\ \forall y\in{\mathbb{Z}}_n &:& x\cdot y\in A %%\\ \end{eqnarray*}$$

Por ejemplo, el conjunto $\{0\}$ siempre es un ideal, y el conjunto $\{0,6\}$ es un ideal en ${\mathbb{Z}}_{12}$. Escriba un programa que dado $n$ encuentre todos los ideales de ${\mathbb{Z}}_n$.

6. Si $A=\left\{a_i\right\}_{i=1}^n$ es un conjunto de $n$ elementos y $R$ es una relación en $A$, $R\subset A\times A$, la matriz de incidencia de $R$ es $M_R=\left[m_{ij}\right]_{i=1,\ldots,n}^{j=1,\ldots,n}\in\{0,1\}^{n\times n}$ tal que

$$\forall i,j\leq n:\ (m_{ij}=1\Leftrightarrow a_iRa_j)\&(m_{ij}=0\Leftrightarrow \neg (a_iRa_j)).$$

Dadas dos relaciones $R,S\subset A\times A$, la composición $S\circ R\subset A\times A$ se define como sigue:

$$\forall x,y\in A: \ x(S\circ R)y\ \Leftrightarrow\ \exists z\in A: xRz\; \& zSy.$$

Por ejemplo, piense que $A$ es el conjunto de alumnos, $R$ es la relación ``está en el mismo grado que'' y $S$ es la relación ``es amigo de''. Entonces se tendrá que $x(S\circ R)y$ si es que un amigo de $y$ está en el mismo grado que $x$. Escriba un programa que reciba las matrices de incidencia de $R$ y de $S$ y calcule la matriz de incidencia de $S\circ R$.

7. Escriba un programa que lea la matriz de incidencia de una relación y decida si la relación que representa es de orden.

8. Escriba un programa que lea un número entero $n$ y genere de manera aleatoria una relación de orden en el conjunto $[\![0,n-1]\!]$. La salida de este programa ha de ser la matriz de incidencia de la relación generada.

9. Escriba un programa que lea las matrices de incidencia de dos relaciones de orden $\leq_1$ y $\leq_2$, y construya la matriz de incidencia de la relación producto. Recordamos que si $(A_1,\leq_1)$ y $(A_2,\leq_2)$ son dos relaciones de orden entonces el orden producto $\leq_{12}$ está definido en el producto cartesiano $A_1\times A_2$ mediante la relación:

$$\forall (x_1,y_1),(x_2,y_2)\in A_1\times A_2:\ (x_1,y_1)\leq_... ...(x_2,y_2)\ \Leftrightarrow\ (x_1\leq_{1}x_2)\&(y_1\leq_{2}y_2).$$

10. Sea $n$ un entero positivo. A todo subconjunto $J$ del conjunto $[\![0,n-1]\!]$ lo identificamos por la lista de valores de su función característica: $\mbox{\boldmath$\epsilon$}_J=\left[\epsilon_j\right]_{j=0}^{n-1}$, donde $\epsilon_j=1$ si $j\in J$ y $\epsilon_j=0$ si $j\not\in J$. Ahora bien, a cada vector $\mbox{\boldmath$\epsilon$}$ de 0's y 1's lo podemos leer como la representación en base 2 de un entero $N(\mbox{\boldmath$\epsilon$})$ en el intervalo $[\![0,2^n-1]\!]$, donde el bit más significativo está más a la derecha (es decir, la representación en base 2 de $N(\mbox{\boldmath$\epsilon$})$ es el reverso de la palabra $\mbox{\boldmath$\epsilon$}$). Por ejemplo, para $n=10$, si $J=\{0,3,6,7,8\}$ entonces:

$$J\ \leftrightarrow\ \mbox{\boldmath $\epsilon$}_J=[1, 0, 0, 1... ...tarrow\ N(\mbox{\boldmath $\epsilon$}_J)= 457 = [0111001001]_2.$$

La correspondencia $\phi:{\cal P}([\![0,n-1]\!])\to [\![0,2^n-1]\!]$, $\phi:J\mapsto N(\mbox{\boldmath$\epsilon$}_J)$, es una biyección. Sea $\psi:[\![0,2^n-1]\!]\to {\cal P}([\![0,n-1]\!])$ su función inversa. Pues bien, definamos en $[\![0,2^n-1]\!]$ el orden siguiente:

$$\forall u,v\in[\![0,2^n-1]\!]:\ u\leq_Bv\ \Leftrightarrow\ \psi(u)\subset \psi(v).$$

Escriba un programa que dado $n$ escriba la matriz de incidencia del orden $\leq_B$ en $[\![0,2^n-1]\!]$. Sugerencia: Podría utilizar, para simplificar todo, funciones primitivas de C del tipo de datos unsigned integer, por ejemplo.

11. Escriba un programa que dada la matriz de incidencia de una relación de orden, digamos $M=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$, escriba, para cada elemento $j\in [\![0,n-1]\!]$ la lista de sus sucesores y la lista de sus antecesores y que señale cuáles elementos son el mínimo y el máximo, si los hubiera. Recordamos que los sucesores de un elemento son los elementos minimales de su cono superior en tanto que los antecesores de un elemento son los elementos maximales de su cono inferior, privados ambos conos del elemento que los define.

12. Sea $A=\left\{a_{i}\right\}_{i\in [\![0,n-1]\!]}$ un conjunto con $n$ elementos y sea $*:A\times A\to A$ una operación de aridad 2. La tabla de operación de $A$ es la matriz $M_*=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$ con entradas en el conjunto $[\![0,n-1]\!]$ tales que

$$\forall i,j\in [\![0,n-1]\!]\ \left(m_{ij}=k\ \Leftrightarrow\ a_i*a_j=a_k\right).$$

Escriba un programa que dada la matriz de incidencia de una relación de orden, digamos $M=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$, escriba las tablas de las operaciones $\land:(x,y)\mapsto \mbox{\rm Inf}\{x,y\}$, $\lor:(x,y)\mapsto \mbox{\rm Sup}\{x,y\}$. Si para alguna pareja de elementos una de estas operaciones no estuviera definida, se ha de indicar este hecho poniendo un símbolo especial en la correspondiente entrada de esa operación.

13. Escriba un programa que dadas las dos tablas de operaciones $M_{\land}=\left[m_{1ij}\right]_{i,j\in [\![0,n-1]\!]}$, $M_{\lor}=\left[m_{2ij}\right]_{i,j\in [\![0,n-1]\!]}$ de un retículo, calcule la matriz de incidencia del orden inducido por el retículo.

14. Escriba un programa que lea la tabla $M_*=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$, con entradas en el conjunto $[\![0,n-1]\!]$, de alguna operación $*:A\times A\to A$ y que decida cuáles de las siguientes propiedades posee $*$: Conmutatividad, asociatividad, idempotencia, existencia de unidades, existencia de inversos (en caso de que existan unidades).

15. Escriba un programa que dada la matriz de incidencia de una relación de orden, digamos $M=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$, encuentre una cadena que se inicie en un elemento minimal y termine en un elemento maximal.

16. Escriba un programa que lea un número entero $n$ y escriba la tabla $M_*=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$, con entradas en el conjunto $[\![0,n-1]\!]$, de alguna operación $*:A\times A\to A$ generada aleatoriamente. Corra este programa $m$ veces y cuente el número $k$ de tablas de operaciones asociativas. Muestre el cociente $k/m$ como una proporción de las operaciones asociativas.

17. Escriba un programa que lea un número entero $n$ y escriba la tabla $M_*=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$, con entradas en el conjunto $[\![0,n-1]\!]$, de alguna operación $*:A\times A\to A$ generada aleatoriamente que sea a la vez asociativa e idempotente. Corra este programa $m$ veces y cuente el número $k$ de tablas de operaciones asociativas e idempotentes. Muestre el cociente $k/n$ como una proporción de las operaciones asociativas e idempotentes.

18. Escriba un programa que reciba dos enteros positivos no-nulos $n,m$, calcule el mínimo común múltiplo $k=m\lor n$, enumere a los elementos en el cono inferior $C_k^-$ de $k$, en el orden de divisibilidad, y escriba las tablas de las operaciones $\land$ y $\lor$ en $C_k^-$.

19. Escriba un programa que lea una tabla de operación $M=\left[m_{ij}\right]_{i,j\in [\![0,n-1]\!]}$ y una permutación $\sigma$ del conjunto de índices $[\![0,n-1]\!]$ y escriba la tabla $\sigma(M)=\left[m_{\sigma(i),\sigma(j)}\right]_{i,j\in [\![0,n-1]\!]}$.

20. Escriba un programa que dadas dos tablas de operaciones $M_1=\left[m_{1ij}\right]_{i,j\in [\![0,n-1]\!]}$, $M_2=\left[m_{2ij}\right]_{i,j\in [\![0,n-1]\!]}$ decida si existe un retículo $(A,\land,\lor)$ tal que $M_1=M_{\land}$, $M_2=M_{\lor}$. En caso de que no exista tal retículo, explicar cuál es la causa.

21. Escriba un programa que mediante un procedimiento de backtracking localice todas las cadenas de una relación de orden.

22. Sea $(A,\land,\lor)$ un retículo. Para un elemento $a\in A$ la altura $h(a)$ de $a$ es el número de aristas en el camino más corto que conecta a $a$ con el elemento mínimo del retículo. La altura del mínimo es 0, la de los sucesores del mínimo es 1, la de los sucesores de los sucesores del mínimo es 2, etc. Escriba un programa que dadas las dos tablas de operaciones $M_{\land}=\left[m_{1ij}\right]_{i,j\in [\![0,n-1]\!]}$, $M_{\lor}=\left[m_{2ij}\right]_{i,j\in [\![0,n-1]\!]}$ de un retículo, calcule para cada elemento $a\in A$ su altura $h(a)$.
Posterior: Cálculo proposicional Arriba: Estructuras algebraicas básicas Anterior: Ejercicios