Un Problema de Conjuntos en Computación		Esteban Meneses,  Francisco J. Torres-Rojas.

Inicio  1  2  3  4  5  6	Versión PDF

 

El Problema de los Conjuntos Imposibles

 

El problema de los Conjuntos Imposibles establece que:

Dado un conjunto con n etiquetas vectoriales de k entradas cada una, decidir si es posible o no

 

De esta forma, dado un conjunto de vectores se quiere determinar si este conjunto cumple la propiedad de ser el reflejo de una historia distribuida. Un punto importante de mencionar es que la historia distribuida que justifica un conjunto puede tener más etiquetas que las que están en el conjunto. El asunto es que todos los vectores que están en el conjunto sean etiquetas de algún evento en la historia distribuida.

Este problema claramente tiene solución, dado que existe una cantidad finita de historias distribuidas que podrían servir de testigo para declarar a un conjunto como posible.

Los conjuntos posibles son aquellos resultantes de aplicar las reglas V0, V1 y V2 a una historia distribuida particular. Los imposibles aparecen porque al aplicar las reglas V0, V1 y V2 a cualquier historia distribuida no se pueden generar todos los elementos del conjunto.

Para ilustrar, considérense los siguientes dos conjuntos:

$\mathcal{A}=\{<2,3,1>,<3,0,0>\}$
$\mathcal{B}=\{<1,1,1>\}$

En el primer caso, el conjunto $\mathcal{A}$ contiene dos elementos (o sea, $n=2$) y $k=3$ (el número de sitios). Para determinar si $\mathcal{A}$ es posible o no, basta con aplicar las reglas V0, V1 y V2 a todas las combinaciones posibles de mensajes entre eventos. Ahora, nótese que si se maximiza, entrada por entrada, los vectores de $\mathcal{A}$ se obtiene el número máximo de eventos en cada sitio ([11]). En este caso, $<3,3,1>$ es ese máximo y entonces la historia distribuida tendrá 3 eventos en el sitio 1, 3 en el sitio 2 y 1 en el sitio 3.

Entonces, cada uno de esos 7 eventos debe tener alguno de los tipos: INTERNO, ENVIO o RECEPCION. Analizando las posibles combinaciones que se pueden genererar al hacer que cada uno de estos eventos tenga uno de los tipos anteriores y aplicando las reglas V0, V1 y V2 se puede determinar si el conjunto es posible o no.

 

Figura 4: Varios candidatos para la historia testigo

 

En la figura 4 se presentan varias historias que podrían ser la historia testigo que se anda buscando. Particularmente, al aplicar las reglas V0, V1 y V2 se descubre que las historias en a) y b) no son testigos del conjunto $\mathcal{A}$, mientras que la historia c) sí lo es. Como se tiene una historia testigo, entonces el conjunto $\mathcal{A}$ es posible.

En el otro extremo, se puede aplicar esta misma estrategia para el conjunto $\mathcal{B}$, pero rápidamente se topa con la limitante de que es imposible lograr el objetivo de construir una historia testigo para este conjunto ([9]).

Esta estrategia funciona, pero a un costo muy elevado: probar todas las posibles alternativas de mensajes entre los eventos de una historia. Este algoritmo exhaustivo agota posibilidad por posibilidad hasta dar con una historia testigo o bien, darse por vencido.

Sería muy provechoso encontrar un algoritmo más eficiente, que no tuviera que lidiar con todas las alternativas.

Revista digital Matemática, Educación e Internet.
Derechos Reservados