Posterior: Cálculo proposicional
Arriba: Estructuras algebraicas básicas
Anterior: Ejercicios
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
,
, encuentre todos los subconjuntos de
elementos en el conjunto de índices entre 0, y
,
.
3. Escriba un programa que dado
, encuentre todos los subconjuntos del conjunto
.
4. Sea
un entero mayor que 1 y sea
el conjunto de residuos módulo
.
. Considere las operaciones suma y producto que coinciden con las usuales de los enteros
pero tomando residuos módulo
:
Escriba un programa que dado
escriba las tablas de operaciones
y
de
.
Observación: El reloj de carátula en su cocina seguramente le puede dar una idea de la suma en
(ahí 12=0 pues la medianoche es lo mismo que las cero horas, ¿verdad?).
5. Sea
un entero mayor que 1. Un ideal en
es un subconjunto
que es cerrado bajo la suma y que ``absorbe productos'':
Por ejemplo, el conjunto
siempre es un ideal, y el conjunto
es un ideal en
.
Escriba un programa que dado
encuentre todos los ideales de
.
6. Si
es un conjunto de
elementos y
es una
relación en
,
, la matriz de incidencia de
es
tal que
Dadas dos relaciones
, la composición
se define como sigue:
Por ejemplo, piense que
es el conjunto de alumnos,
es la relación ``está en el mismo grado que'' y
es la relación ``es amigo de''. Entonces se tendrá que
si es que un amigo de
está en el mismo grado que
.
Escriba un programa que reciba las matrices de incidencia de
y de
y calcule la matriz de incidencia de
.
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
y genere de manera aleatoria una relación de orden en el conjunto
. 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
y
, y construya la matriz de incidencia de la relación producto. Recordamos que si
y
son dos relaciones de orden entonces el orden producto
está definido en el producto cartesiano
mediante la relación:
10. Sea
un entero positivo. A todo subconjunto
del conjunto
lo identificamos por la lista de valores de su función característica:
, donde
si
y
si
. Ahora bien, a cada vector
de 0's y 1's lo podemos leer como la representación en base 2 de un entero
en el intervalo
, donde el bit más significativo está más a la derecha (es decir, la representación en base 2 de
es el reverso de la palabra
). Por ejemplo, para
, si
entonces:
La correspondencia
,
, es una biyección. Sea
su función inversa.
Pues bien, definamos en
el orden siguiente:
Escriba un programa que dado
escriba la matriz de incidencia del orden
en
.
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
, escriba, para cada elemento
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
un conjunto con
elementos y sea
una operación de aridad 2. La tabla de operación de
es la matriz
con entradas en el conjunto
tales que
Escriba un programa que dada la matriz de incidencia de una relación de orden, digamos
, escriba las tablas de las operaciones
,
. 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
,
de un retículo, calcule la matriz de incidencia del orden inducido por el retículo.
14. Escriba un programa que lea la tabla
, con entradas en el conjunto
, de alguna operación
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
, 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
y escriba la tabla
, con entradas en el conjunto
, de alguna operación
generada aleatoriamente.
Corra este programa
veces y cuente el número
de tablas de operaciones asociativas. Muestre el cociente
como una proporción de las operaciones asociativas.
17. Escriba un programa que lea un número entero
y escriba la tabla
, con entradas en el conjunto
, de alguna operación
generada aleatoriamente que sea a la vez asociativa e idempotente.
Corra este programa
veces y cuente el número
de tablas de operaciones asociativas e idempotentes. Muestre el cociente
como una proporción de las operaciones asociativas e idempotentes.
18. Escriba un programa que reciba dos enteros positivos no-nulos
, calcule el mínimo común múltiplo
, enumere a los elementos en el cono inferior
de
, en el orden de divisibilidad, y escriba las tablas de las operaciones
y
en
.
19. Escriba un programa que lea una tabla de operación
y una permutación
del conjunto de índices
y escriba la tabla
.
20. Escriba un programa que dadas dos tablas de operaciones
,
decida si existe un retículo
tal que
,
. 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
un retículo. Para un elemento
la altura
de
es el número de aristas en el camino más corto que conecta 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
,
de un retículo, calcule para cada elemento
su altura
.
Posterior: Cálculo proposicional
Arriba: Estructuras algebraicas básicas
Anterior: Ejercicios
Guillermo Morales-Luna
2004-07-27