Base De Datos

Resumen:

En Matemática existen muchos problemas que involucran conjuntos. Generalmente, estos problemas están relacionados con un grupo de elementos que deben cumplir una cierta propiedad. Por ejemplo, los conjuntos pitagóricos son aquellos de la forma , con tales que conforman una terna pitagórica: . Sin embargo, el algoritmo para determinar si un conjunto de cardinalidad 3 es pitagórico o no, es muy eficiente. En Computación Distribuida existen también problemas de conjuntos. Uno de ellos es el problema de los conjuntos imposibles de relojes vectoriales ([9]), que no se ha determinado si posee un algoritmo eficiente que lo resuelva.

Palabras claves: conjuntos, algoritmo, elojes vectoriales, clases P y NP

Introducción

La historia de las matemáticas recuerda con respeto a muchos hombres, uno de ellos es Georg Ferdinand Ludwig Philipp Cantor, creador de la Teoría de Conjuntos. Alrededor de 1873, Cantor descubrió esta apasionante rama de estudio, formalizando de paso la noción de infinito, que hasta el momento había sido solamente una forma de hablar.

La Teoría de Conjuntos sirve como base para muchas otras ramas matemáticas, como Probabilidades, Álgebra, Análisis y Ecuaciones Diferenciales. Mas aún, junto con el Cálculo de Predicados, constituye el fundamento de las Matemáticas. En Ciencias de la Computación, la Teoría de Conjuntos también juega un papel preponderante en la Matemática Discreta, Teoría de Computabilidad, Algoritmos, Programación y Especificación Formal de Software.

La Teoría de Conjuntos es la responsable de teoremas elegantes y poderosos, como el Axioma de Elección. Empero, en Computación Distribuida existen también problemas interesantes de conjuntos. Tal es el caso de los Conjuntos Imposibles de Relojes Vectoriales ([9]). Este artículo ofrecerá un reto con respecto a este problema.

El objeto de estudio de la Teoría de Conjuntos son los conjuntos. Estas entidades matemáticas son objetos que ayudan a representar conceptos. Por ejemplo, si las longitudes de los lados de un triángulo rectángulo son enteras, entonces, esas longitudes se convierten en una terna pitagórica, una especie particular de conjunto.

Una vasta cantidad de problemas en Teoría de Conjuntos se fundamentan en determinar si el conjunto cumple o no con una propiedad. Tal es el problema de los conjuntos balanceados. Un conjunto de números enteros se dice balanceado si la suma de los elementos es igual a su producto. De esta forma, es balanceado, pero no lo es.

En Computación Distribuida, cualquier ejecución produce una historia distribuida de eventos. Si se coleccionan las etiquetas vectoriales de esos eventos, se obtiene un conjunto de vectores de enteros, al que se le denominará conjunto posible. Sin embargo, no cualquier conjunto de vectores de enteros es el producto de los eventos de una historia distribuida. A estos conjuntos

...