Archivos y etiquetas

Apuntes para MATEMATICAS DISCRETAS 1. Desaf´ Archivos y Etiquetas ıo:
Andreas Polym´ris, DIICC, Universidad de Concepci´n, Chile e o Entrega: 19.04.2010
En este primer Desaf´o, antes de realmente entrar en materia, consideraremos un objeto ı matem´tico que nos interesar´ en varias ocasiones durante este semestre. Porque articula un a a modelo matem´tico de un asunto inform´tico que tiene, a mijuicio, una renovada relevancia. a a Contribuye a entender y manejar mejor grandes repositorios de archivos que esencialmente — s´lo— est´n estructurados —o indexados— en base a etiquetas; una modalidad que vuelve a o a interesar a muchos desarrolladores, sobre todo en la medida en que permite capitalizar contribuciones y anotaciones de los usuarios del repositorio; en particular, en base a lo quese ha llamado social tagging; es decir, un proceso, masivo y continuo, de agregaci´n —y tambi´n elimo e inaci´n— de archivos y etiquetas. Interesa por lo tanto conocer mejor las propiedades de tales o objetos matem´ticos; para, por ejemplo, saber mejor c´mo especificar, sobre estos repositorios, a o procesos que permitan navegaciones satisfactorias y eficientes.

1.

Estructura

Convengamosen que tenemos un par de conjuntos finitos —pero t´ ıpicamente de cardinalidades muy grandes— A, B; de objetos, o archivos, y de etiquetas, o propiedades, respectivamente; y que ρ ⊆ A × B es una relaci´n dada, tal que para todo (a, b) ∈ A × B, vale (a, b) ∈ ρ, o si el objeto a ∈ A tiene, o corresponde, a la etiqueta b ∈ B. Para fijar las ideas podemos entender que la relaci´n ρ est´ especificada enbase a una matriz o a de incidencia A × B. Esto es lo que define el repositorio estructurado (A, ρ, B) que nos va interesar en lo que sigue. Es lo que estar´ estructuralmente dado —lo que no significa que no pueda cambiar; s´lo ıa o que es el dominio sobre el cual se dar´n los procesos que nos interesan. a

2.

Situaci´n o

Adem´s, situacionalmente, entenderemos que en todo momento del procesoque nos interea sa, la instancia que est´ dada, a la mano, expl´citamente, extensivamente, es un estado (X, Y ) a ı con X ⊆ A e Y ⊆ B; que para serlo —por definici´n— debe ser coherente; es decir, tal que o ∀(a, b) ∈ X × Y , (a, b) ∈ ρ. Podemos pensar, para fijar ideas, en estados que en la pantalla de nuestro PC plasman una 1

lista de (nombres de) archivos X, que son la respuesta de un buscadora una consulta gatillada por una lista de etiquetas (o palabras claves) Y ingresadas. Entonces ¿siempre tendremos coherencia? Ahora, un tal estado expl´cito (X, Y ) ∈ P(A) × P(B) —donde P(C) es el conjunto potencia ı de del conjunto C— puede, o no, tener otras propiedades interesantes: Entendemos que est´ A-clausurado, si ∀a ∈ A\X, ∃b ∈ Y con (a, b) ∈ ρ; y a que est´ B-clausurado, si ∀b ∈ B\Y , ∃a∈ X con (a, b) ∈ ρ. a O sea que (X, Y ) est´ A-clausurado, ssi Y bloquea, transversalmente, todos los elementos de a A\X. Por ejemplo, t´ ıpicamente entendemos que la uni´n de todos los archivos que podr´ aparecer o ıan en la pantalla de nuestro PC es un X ∈ P(A), tal que con el Y ∈ P(B) que orienta al buscador, forma un estado A-clausurado (X, Y ). ¿Por qu´? Sin embargo usualmente esos estado noest´n e a B-clausurados. ¿Por qu´? e

3.

Hacer

Por supuesto que debemos entender que para un par (a, b) ∈ A × B dado, siempre se puede decidir computacionalmente si vale (a, b) ∈ ρ o no. As´ que si tenemos un par (X, Y ) ∈ P(A) × P(B), a la mano, es decir, tal que se puedan recorı rer cada uno de esos dos conjuntos, entonces se puede decidir computacionalmente si (X, Y ) es un estado ono. Pero note que por lo mismo cabe suponer que para un estado dado (X, Y ), t´ ıpicamente X, Y tendr´n extensiones mucho menores a las de A, B, respectivamente. a M´s all´ de esto, etenderemos que todo lo que se puede hacer computacionalmente en a a el repositorio dado, se debe implementar mediante los dos operadores α : P(A) → P(B) y β : P(B) → P(A), que est´n definidos por: a ∀X ⊆ A, α(X) := {b...