Embed Size (px)
Citation preview
UNIVERSIDAD JUÁREZ AUTÓNOMA DE TABASCO
DIVISIÓN ACADÉMICA DE CIENCIAS BÁSICAS
“BIBLIOTECA DE FUNCIONES DE MINERIA DE DATOS INTERESANTES PARA APOYAR
LA TOMA DE DESICIONES RESPECTO A CUBRIMIENTOS R110”
T E S I S
QUE PARA OBTENER EL TITULO DE
LICENCIADO EN COMPUTACIÓN
P R E S E N T A
RAYMUNDO DOMÍNGUEZ COLÍN
ASESOR:
DR. ABDIEL EMILIO CÁCEREZ GONZÁLEZ
CUNDUACAN, TABASCO SEPTIEMBRE 2007
La tesis de Raymundo Domınguez Colın es aprobada.
LSCA. Diana Graciela Chuc Duran
Ing. Federico Suarez Domınguez
LC. Rafael Chable Candelero
Ing. Remigio Frıas Olan
LC. Tito Mundo Najera
Dr. Abdiel Emilio Caceres Gonzalez, Director de la tesis
Universidad Juarez Autonoma de Tabasco,
2007
ii
iii
Este trabajo de tesis lo dedico a mi padre,
Raymundo Domınguez Ceron
por todo su amor,
por ser uno de mis mejores amigos
y cuyo apoyo fue esencial
para terminarlo;
y para mi madre,
Marıa de la Luz Colın Mendoza,
a quien sigo extranando
cada dıa.
iv
v
Agradecimientos
Quiero agradecer sinceramente a las siguientes personas por haber contribuido
directa e indirectamente en mi formacion profesional, misma que se ve reflejada
en este trabajo: al Dr. Abdiel E. Cacerez Gonzalez por su asesoria y paciencia;
tambien agradezco a todos los profesores que contribuyeron para mi formacion
academica; a todos mis hermanos pero en especial a Bety por su gran carino,
ayuda y comprension; a mi primo Isaac por su insistencia, confianza y por esas
largas lecciones nocturnas de algebra (y tambien por dejarme quedar en su casa
en los primeros anos de mi carrera); al sr. Jose Elias por su apoyo moral y por las
facilidades que siempre me brindo para la adquisicion de hardware; a Guadalupe
Alor; Fabio Montoya; Noe; a la sra. Rosy por su trato amable y apoyo durante
mi estancia en el DF; a la sra.Luisa Bernal por soportarme en su casa durante
esos dıas (y noches) de trabajos finales, tareas y tambien de libre esparcimiento;
y a todos mis amigos y companeros a los que, por ser demasiado numerosos, es
imposible mencionar por su nombre.
Este trabajo de tesis forma parte del proyecto de investigacion 20060376 titulado
“Arquitectura, diseno e implementacion de un sistema computacional
de agregacion de mosaicos Regla 110”, con clave UJAT-2005-C01-08,
financiado por la Universidad Juarez Autonoma de Tabasco (UJAT).
vi
vii
Contenido
I Introduccion 1
1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 Automatas celulares . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Estudios formales de la regla 110 en Mexico . . . . . . . . 5
1.2 Los mosaicos como objetos de estudio . . . . . . . . . . . . . . . . 6
1.3 Problemas computacionales relacionados con los mosaicos R110 . . 6
1.4 Minerıa de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 La abundancia de datos . . . . . . . . . . . . . . . . . . . 10
1.5 Objetivo fundamental . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Descripcion del sistema . . . . . . . . . . . . . . . . . . . . 11
1.6 El porque de encontrar elementos interesantes . . . . . . . . . . . 12
1.7 Contenido general . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Automatas celulares y la regla R110 . . . . . . . . . . . . . . . . . 16
2.1 Automatas celulares lineales . . . . . . . . . . . . . . . . . . . . . 16
2.2 Diagrama espacio-temporal . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Descripcion de un triangulo R110 . . . . . . . . . . . . . . 22
2.2.2 Identificacion de los triangulos R110 incompletos en los DET 24
2.3 Mosaicos y cubrimientos R110 . . . . . . . . . . . . . . . . . . . . 25
2.4 Obtencion de los contornos R110 . . . . . . . . . . . . . . . . . . . 30
2.4.1 La secuencia < 10 > . . . . . . . . . . . . . . . . . . . . . 36
viii
2.5 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Definicion de lo interesante . . . . . . . . . . . . . . . . . . . . . . 45
3.1 El problema de la subsecuencia comun mas larga y los contornos
R110 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Distancia de Levenshtein . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 Definicion de los tipos de comparacion . . . . . . . . . . . . . . . 53
3.3.1 Primer tipo de comparacion: el de diferencias . . . . . . . 53
3.3.2 Segundo tipo de comparacion: el de semejanzas . . . . . . 54
3.4 Funcion de lo novedoso . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5 Funcion de la utilidad . . . . . . . . . . . . . . . . . . . . . . . . 56
3.6 Funcion de validez . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.7 Funcion de lo interesante . . . . . . . . . . . . . . . . . . . . . . . 62
3.8 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Descripcion del sistema . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1 Descripcion general del sistema . . . . . . . . . . . . . . . . . . . 68
4.2 Manejo de la base de datos . . . . . . . . . . . . . . . . . . . . . . 69
4.3 Generador de mosaicos R110 . . . . . . . . . . . . . . . . . . . . . 70
4.4 Biblioteca de funciones . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5 Conclusion final y trabajos futuros . . . . . . . . . . . . . . . . . 77
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
ix
Lista de Figuras
1.1 Evoluciones del aclr110 de 150 celulas a traves de 150 generaciones . . 5
1.2 Diagrama esquematico del sistema desarrollado. . . . . . . . . . . . . 11
2.1 La funcion global de un automata celular lineal determina la configuracion
global en el siguiente paso de tiempo. . . . . . . . . . . . . . . . . . . . 17
2.2 Izq: Representacion interna de una evolucion del aclr110. Der: Asignandole
un color obscuro a las celulas con valor 1 y un color claro a aquellas con valor 0. 20
2.3 Imagenes que representan las evoluciones de las reglas 110, 124, 137 y 193. . 22
2.4 (A) Triangulo R110 o t6. (B) Descomposicion en sus secciones principales: lacelula origen, las fronteras superior e izquierda y el cuerpo del triangulo. . . 23
2.5 Aquı se observan triangulos de diferentes tamanos contendidos en un DET . . 24
2.6 DETde tamano 50× 50. Pueden observarse muchos triangulos que estan fuera
de los lımites del DET. . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 Mosaico R110 formado por 18 triangulos incluyendo los t0 . . . . . . . . . 27
2.8 Contorno de un triangulo t3. . . . . . . . . . . . . . . . . . . . . . . . 29
2.9 Triangulo marcado. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.10 Diagrama de estados del BA . . . . . . . . . . . . . . . . . . . . . . . 37
2.11 (A). Secuencia de digitos obtenidos de un mosaico R110. (B). Caso imposible.Un mosaico como el que se muestra nunca ocurre en las evoluciones del aclr110. 37
2.12 Se observan las celulas que se van visitando a medida que se avanza sobre lasfronteras del triangulo y los valores que va devolviendo el automata. . . . . 39
2.13 Obtencion del contorno que involucra triangulos adyacentes de diferentes tamanos
que forman un mosaico R110 . . . . . . . . . . . . . . . . . . . . . . . 39
x
2.14 Izq: Evolucion del aclr110. Der: Contorno formado por todos los triangulos
contenidos completamente dentro de la evolucion. . . . . . . . . . . . . . 41
2.15 Esta imagen muestra como se reconstruye un contorno a partir de una cadena
de sımbolos con el formato [E,S,N,W]. . . . . . . . . . . . . . . . . . . . 42
2.16 Conjunto de contorno obtenidos de un mosaico R110. . . . . . . . . . . . . 43
3.1 Matriz binaria S donde calculamos que s(v, w)=8 en los contornos v y w. Estoscontornos tienen la subsecuencia EESSWWNN de longitud 8 en comun. . . . . . 50
3.2 Procedimiento para remover triangulos de un contorno. . . . . . . . . . . 59
3.3 Se muestran los pasos que se siguen al encontrar la secuencia NEEEEES paraeliminar el triangulo suelto t4. . . . . . . . . . . . . . . . . . . . . . . 61
3.4 Grafica de las funciones η y U , en la que el valor maximo devuelto por la
funcion I, se encuentra en el cruce de las dos lıneas. . . . . . . . . . . . . 64
3.5 Caso de estudio. Mosaico R110 que sera analizado por los procedimientos
hasta ahora explicados. . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1 Pantalla principal del sistema. . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Pantalla del procesamiento de los contornos en la base de datos . . . . . . . 75
5.1 Se observan dos mosaicos que a primera vista son muy parecidos. . . . . . . 77
5.2 Subcubrimiento. La zona punteada representa la seleccion realizada en la
evolucion. En el interior se observa el contorno del subcubrimiento que se
encuentra dentro del marco rectangular. . . . . . . . . . . . . . . . . . . 80
xi
Lista de Tablas
2.1 Tabla esquematica de las evoluciones de un Automata Celular . . . . . . . 21
2.2 Definicion de la funcion λ. El sımbolo que devuelve esta en funcion de los
parametros de entrada . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Las coordenadas de los puntos p1 y p2 que evalua la funcion ϕ estan en funciondel estado s ∈ S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Tabla de informacion que muestra la estructura que almacenara la posicion y
el tamano de cada uno de los triangulos del mosaico. . . . . . . . . . . . . 40
4.1 Se muestra la estructura de la tabla contornos que es la que almacenara la
informacion de los mosaicos R110. . . . . . . . . . . . . . . . . . . . . . 70
xii
xiii
Parte I
Introduccion
1
CAPITULO 1
Introduccion
El automata celular lineal regla 110 o aclr110, se ha tomado como objeto de estu-
dio desde mediados de 1980. Steven Wolfram propuso que en las evoluciones del
aclr110, se podrıa obtener un comportamiento global equivalente a hacer com-
putacion universal [2]; esto fue demostrado por Matthew Cook al realizar una
configuracion compleja de choques de gliders1 que simulan datos de entrada, in-
tercambio de informacion y resultados de los calculos hechos [12].
Por otra parte, las evoluciones del aclr110 pueden verse como mosaicos que cubren
el plano y se han relacionado con diversos problemas de computacion. Sin em-
bargo, los analisis de un gran numero de evoluciones requieren de una gran can-
tidad de paciencia y observacion para poder clasificarlas de acuerdo a un criterio
en particular. De aquı surge la idea de desarrollar un sistema de generacion de
mosaicos R110 y que al mismo tiempo realice analisis de las evoluciones de una
manera automatica, arrojando resultados que nos permitan destacar elementos
interesantes y descartar aquellos que no lo sean. Esta tesis es una contribucion a
los estudios del comportamiento complejo de este automata y de sus evoluciones;
a lo largo de los siguientes capıtulos se describen procedimientos disenados ex-
clusivamente para su analisis.
Este capıtulo es introductorio y hablamos de la historia de los automatas celulares
y de las investigaciones que se han hecho sobre el aclr110; abordamos de mane-
1Un glider es una estructura periodica que se desplaza en el tiempo.
2
ra general el concepto de Minerıa de Datos y de su aplicacion en este trabajo
como una manera de analizar una gran cantidad de datos en busca de elementos
interesantes que haya que destacar o que merezcan atencion especial. Algunos
terminos como contorno, triangulo, cubrimiento o mosaico R110, se explicaran en
el siguiente capıtulo.
1.1 Automatas celulares
Los estudios sobre automatas finitos, maquinas de Turing y otros modelos, con-
forman lo que se ha denominado Teorıa de Automatas, dentro de la Teorıa de
la Computacion. En 1940, el matematico Stanislaw Ulam [19] trabajo en la
evolucion de construcciones graficas basadas en reglas simples [9]. Estas cons-
trucciones eran espacios bidimensionales divididos en celulas como un tipo de
rejilla. Cada una de las celulas podıan tener dos estados: encendido o apa-
gado, y comenzando con un patron dado, las siguientes generaciones son deter-
minadas de acuerdo a unas reglas simples de vecindad. Ulam, quien uso una de
las primeras computadoras (sin monitor), noto rapidamente que este mecanis-
mo permitıa generar figuras esteticas y complejas y que esas figuras podıan, en
algunos casos, autoreproducirse.
De acuerdo a [1], diez anos despues, dos neurofisiologos, Warren S. McCulloch
y Walter Pitts [13] disenaron un modelo matematico para representar el fun-
cionamiento de las celulas cerebrales, que fue el principio de lo que hoy se conoce
como redes neuronales [23] y aunque el modelo era una aproximacion muy sencilla
al comportamiento real de las neuronas, se le encontraron grandes aplicaciones
en otros contextos; en el campo puramente matematico, Stephen Kleene [21]
redefinio ese modelo y dio lugar a los automatas finitos, especies de maquinas
ideales o modelos matematicos, similares a la maquina de Turing, con posibil-
3
idades bastante mas reducidas, pero muy adecuadas para ciertos procesos de
calculo.
Por otra parte el ingles Turing consiguio definir conceptualmente una maquina de
calculo que se considera universal, es decir, el mecanismo de procesar cualquier
algoritmo [1]. Turing diseno un modelo matematico de automata que, siguiendo
unas reglas simples conseguıa solucionar una amplia gama de problemas. En
principio, la maquina de Turing constituye el instrumento de calculo universal
mas general y aunque no es posible dar una demostracion rigurosa de esto, si se
tiene una gran cantidad de indicios agrupados en lo que se conoce como Tesis
de Church [24], que puede plantearse ası: No existen funciones que puedan ser
definidas por personas y cuyo calculo sea descrito por algun algoritmo, que no
puedan computarse con una maquina de Turing. Basandose en la maquina de
Turing, von Neumann trabajo en la concepcion de una maquina autoreproduc-
tiva que llamo kinematon. Esta maquina podıa, en teorıa, ser capaz de repro-
ducir cualquier maquina descrita en sus programas, incluyendo una copıa de si
misma [1].
De acuerdo a [4], los automatas celulares son herramientas utiles para construir
modelos aproximados de algunos sistemas complejos de naturaleza contınua, sin
pasar por modelos analogicos. Es posible, por ejemplo, lograr sencillos modelos
digitales que representen con suma fidelidad algunas leyes de la fsica; ademas son
una buena alternativa a las ecuaciones diferenciales y con ellos (dependiendo de la
naturaleza compleja de un sistema y de la posibilidad de identificar estados locales
y reglas generales de evolucion) se podrıan simular comportamientos tales como:
simulacion de trafico automotriz, virus, globulos, epidemias, bacterias, contami-
nacion, ecosistemas, evolucion galactica, flujo de electrones, medios granulares
entre otros.
4
Figura 1.1: Evoluciones del aclr110 de 150 celulas a traves de 150 generaciones
1.1.1 Estudios formales de la regla 110 en Mexico
El primer trabajo formal sobre la regla 110 en Mexico, fue el desarrollado por H.V.
McIntosh [14] a finales de la decada de 1990; en el, realizo un profundo estudio
sobre la evolucion de los automatas celulares y en particular en las evoluciones del
aclr110; dicho automata genera, a partir de una configuracion inicial, cubrimien-
tos formados por triangulos de diversos tamanos que muestran una regularidad
sorprendente (ver figura 1.1). El trabajo de McIntosh, se enfoca principalmente
al comportamiento y la clasificacion de ciertas estructuras periodicas llamadas
gliders encontrados en el espacio de evoluciones y que fueron catalogadas por
Matthew Cook [12] en 1999; ademas, desarrollo una profunda investigacion acerca
de la posibilidas de cubrir el plano con esas formas triangulares que ocurren en
las evoluciones del aclr110.
En 2005, se presento la tesis doctoral Maquina celular de computacion basada
en Mosaicos R110 [2], en donde se inicia un detallado estudio teorico basado en
5
los triangulos R110 que toman su nombre a causa de la aparente distribucion de
los estados de las celulas en el diagrama espacio-temporal de las evoluciones del
aclr110. En esa tesis, se crea un lenguaje regular de agregacion de mosaicos, es
decir, se crea una manera ordenada de cubrir el plano con las figuras definidas
como mosaicos unitarios, que corresponden a las figuras de forma triangular,
para cada tipo de triangulo, que son diferentes solo por su tamano, y ademas se
formaliza la nocion de mosaico R110 en base a la teorıa de mosaicos en Rd [18].
1.2 Los mosaicos como objetos de estudio
Esta tesis es una contribucion al estudio de las evoluciones generadas por el
aclr110; los mosaicos que genera este automata aportan elementos suficientes para
estudiar problemas tales como:
• El analisis de las porciones de las evoluciones de manera automatizada
• La seleccion de patrones interesantes
• La interpretacion del nuevo conocimiento
1.3 Problemas computacionales relacionados con los mo-
saicos R110
El estudio del aclr110ofrece una amplia variedad de analisis debido a que en sus
evoluciones ocurren cosas periodicas y aperiodicas juntas; su comportamiento
no trivial, se basa en las propiedades basicas del fondo periodico que muestran
una alineacion en el espacio de evoluciones y de la aparente regularidad de las
figuras que aparecen en ellas [11]. Las evoluciones del aclr110 se pueden ver como
6
piezas de rompecabezas que, de manera conjunta, forman mosaicos que pueden
cubrir el espacio plano; este punto de vista, el de cubrir el plano con los mosaicos
obtenidos a partir de las evoluciones del aclr110, ha causado que se le relacione
con problemas computacionales tales como:
• El problema del domino. A principios de la decada de 1960, H. Wang, quien
mostro que cualquier maquina de Turing se puede ver como un problema
de encontrar alguna secuencia de mosaicos, planteo en 1962 [5] el problema
del domino, que en pocas palabras dice: cualquier conjunto de mosaicos
(finito) que pueda cubrir el plano, es a causa de cubrimientos periodicos, es
decir, con copias de un subcubrimiento. Sin embargo, un artıculo publicado
en 1966 [17], demostro que la conjetura de Wang estaba equivocada.
• El numero de Heesch. El problema de Heesch consiste en averiguar cuantas
veces se puede rodear por completo una figura con copias de esa misma
figura de tal manera que si se puede cubrir con copias congruentes, entonces
se podra cubrir un numero infinito de veces, de otro modo el numero de
Heesch para esa figura debe ser finito [7].
• El problema de la palabra. Dado un conjunto A de palabras y un conjunto
de ecuaciones aplicables a esas palabras (elementos de A), el problema de la
palabra consiste en determinar, al iniciar con dos palabras {w1, w2} ∈ A, si
es posible aplicar una serie de transformaciones a w1 (de acuerdo al conjunto
de ecuaciones) para transformarla en w2.
A lo largo de esta tesis, se describe la forma de codificar los mosaicos R110, de tal
modo que, esa codificacion se almacene en diferentes bases de datos y posterior-
mente se analize de manera automatica por funciones especıficas, devolviendo al
final del analisis un valor (por encima de un umbral definido) que nos ayude a
7
tomar una desicion respecto a la informacion analizada. Los algoritmos que ha-
cen funcionar a estas funciones, estan basados en una herramienta que ha tomado
mucha fuerza en las ultimas decadas: la Minerıa de datos.
1.4 Minerıa de datos
Una de las areas de ciencias de la computacion implicadas en esta tesis es la
Minerıa de datos o MD para abreviar. De acuerdo a [22], la MD, tambien lla-
mada descubrimiento del conocimiento en bases de datos (Knowledge-Discovery
in Databases), se define como la extraccion no trivial de informacion implıcita,
desconocida y potencialmente util a partir de los datos. Para realizar esto, la MD
realiza procesos automaticos de busqueda de patrones en grandes volumenes de
datos, usando diversas herramientas de clasificacion, de asociacion entre otras.
Aunque usualmente la MD se aplica a los negocios, organizaciones de inteligen-
cia y analisis financiero, tambien se ha incrementado su uso en las ciencias para
extraer informacion desde enormes conjuntos de datos generados por metodos
experimentales modernos y de observacion. Si bien, el termino minerıa de datos
es relativamente nuevo, la tecnologıa en sı no lo es. A partir de la decada de
1960, las bases de datos (BD) y las tecnologıas de informacion han estado sis-
tematicamente involucradas tanto en sistemas simples de manejo de archivos,
como en sofisticados y poderosos sistemas de BD [6].
Las investigaciones y desarrollo de los sistemas de BD en la decada de 1970,
desarrollaron los primeros sistemas jerarquicos de BD en red, los sistemas de
BD relacionales (donde los los datos son almacenados en estructuras de tablas
relacionadas), las herramientas de modelacion de datos y las tecnicas de organi-
zacion indexada. Ademas, comenzaron a usarse lenguajes flexibles de acceso y
8
consulta de datos, mejoraron las interfaces de usuario y se optimizaron los pro-
cesos de consulta y manejo de transacciones [20]. Surgio el concepto de Proce-
samiento de transaccion en lınea (OLTP), donde una consulta es vista como
una transaccion de solo lectura (read-only), contribuyendo substancialmente a
la evolucion y aceptacion de la tecnologıa relacional como una herramienta de
almacenamiento eficiente, de recuperacion y manejo de grandes cantidades de
datos.
Los anos 80, se carecterizaron por la completa adopcion de la tecnologıa rela-
cional en BD, y esto acelero el desarrollo de sistemas mas potentes como los
modelos entidad-relacion extendido, objeto-relacional, objeto-orientado y mode-
los deductivos. Surgieron las BD heterogeneas y los sistemas de informacion
globales basados en Internet, jugando un papel vital en la industrıa de la infor-
macion. Sumado a lo anterior, el desarrollo de las computadoras aumento, eran
mas rapidas, tenıan mayor capacidad de almacenamiento y procesamiento, y los
resultados de los analisis eran mejores.
Actualmente, los datos pueden ser almacenados en diferentes tipos de BD y una
de ellas es la arquitectura llamada data warehouse, la cual es un deposito de
multiples fuentes de datos heterogeneos, organizados bajo un esquema unificado
en un unico sitio para facilitar la toma de desiciones. Esta arquitectura incluye
limpieza de datos, integracion de datos y el concepto de Procesos Analiticos en
Linea (OLAP), los cuales son tecnicas de analisis con diferentes funcionalidades
como resumen, consolidacion y agregacion, ası como tambien la habilidad de ver
la informacion desde diferentes angulos [6].
9
1.4.1 La abundancia de datos
La abundancia de datos, acoplado con la necesidad de poderosas herramientas
de analisis, ha sido descrita como una situacion de muchos datos pero poca infor-
macion.
Cuando se habla de muchos datos, estamos en un rango de millones de datos
almacenados dentro de una BD cualquiera; esta coleccion de datos por si misma
no dice mucho, y se necesita en muchas ocasiones de un analisis profundo, para
extraer el significado de los datos y que sirva a un proposito en particular, digamos
predecir el comportamiento de algun evento, aumentar la productividad entre
otros.
Las lineas de aplicacion mas importantes de la MD, son: las clasificaciones es-
tadısticas, la inteligencia artificial (IA) y la de las maquinas de aprendizaje,
aunque esta ultima se considera como la union de las dos anteriores [20]. La
MD es fundamentalmente, la adaptacion del aprendizaje de las maquinas a las
aplicaciones empresariales. De hecho puede describirse como la union de las in-
vestigaciones mas actuales en IA, el aprendizaje de las maquinas y la estadıstica.
La MD ayuda a los analistas a reconocer hechos, relaciones, detectar patrones
interesantes, excepciones y anomalıas que de otra manera serıa muy difıcil en-
contrar.
Dentro de este trabajo, al final del capıtulo 3, lograremos almacenar grandes
cantidades de informacion obtenida a partir de las evoluciones del aclr110, y es
ahı donde se utilizaran las tecnicas de MD para lograr obtener un valor que pueda
ser considerado util para tomar una desicion respecto a estas.
10
1.5 Objetivo fundamental
Desarrollar un sistema de analisis automatico de las evoluciones del
aclr110, con el fin de evaluar su grado de novedad, validez y utilidad, y
ayudar de esta manera, a decidir si las evoluciones pueden considerarse
interesantes o poco interesantes
1.5.1 Descripcion del sistema
Se ha desarrollado un sistema que genera y muestra graficamente las evoluciones
del aclr110, las codifica, almacena en una base de datos, analiza y muestra los re-
sultados del analisis. El esquema del diseno del sistema se muestra en la figura 1.2.
Figura 1.2: Diagrama esquematico del sistema desarrollado.
El sistema se compone de tres modulos principales que son:
1. Generador de mosaicos R110. Formado a su vez por submodulos de control,
aquı se define la configuracion inicial del espacio (tamano, nivel de densidad,
escala), se generan los mosaicos R110 y se muestra la imagen correspondien-
te; los submodulos permiten manejar esta imagen, almacenarla (en formato
JPEG), realizar nuevas configuraciones, entre otras. Los mosaicos obtenidos
11
son los datos de entrada del siguiente modulo
2. Biblioteca de funciones (BF). Formada por seis submodulos, la BF lleva a
cabo el analisis de los datos de entrada; estos pueden ser de dos tipos: un
mosaico o un contorno R110. El Generador de mosaicos analiza los mosaicos
para obtener todos los contornos posibles y enriquecer la base de datos; los
contornos introducidos por el usuario, se analizan para evaluar su validez
(que solo contengan triangulos R110). Posteriormente, el analizador toma
los elementos de la BD, y con los submodulos novedoso,valido y util, evalua
estos elementos y la respuesta es enviada como dato de entrada para el
submodulo interesante, que al final es el que evalua el grado de interes de
los contornos analizados
3. Desempeno de la BD. La BD esta programada en un lenguaje flexible, sen-
cillo y potente, que permite manejar cadenas de texto muy grandes, realizar
consultas agiles entre otras caracterısticas importantes.
1.6 El porque de encontrar elementos interesantes
Dado que existe una gran cantidad de informacion y se requiere analizarla para
extraer de ella hechos significantes, semejanzas, tendencias, patrones, relacional-
idad, etcetera, que de otra manera serıa muy difıcil de analizar.
Dentro de los estudios de las evoluciones del aclr110, se realizan muchos experi-
mentos, se prueban diferentes configuraciones iniciales, se estudian los patrones
graficos obtenidos, se vuelven a probar las mismas configuracion con alguna va-
riante, en fin, de una u otra manera, se termina, despues de algun tiempo, con
un gran numero de hojas de papel en las que estan impresos las evoluciones
del aclr110 generados por las pruebas realizadas, y llegan a ser tantos, que se
12
convierte en un problema de almacenamiento fısico, ademas de que resulta muy
difıcil clasificarlos o relacionarlos con otros resultados obtenidos. Trabajar ma-
nualmente con evoluciones del aclr110 de gran tamano (por ejemplo, evoluciones
de 500 celulas × 500 generaciones) es un proceso laborioso y tardado, y no es
inmediatamente sencillo realizar comparaciones entre las evoluciones.
El aplicar procesos automatizados de analisis sobre las evoluciones del aclr110, nos
permite realizar estudios mas detallados del comportamiento del automata. La
informacion que se obtenga de estos analisis, debe de tener ciertas caracterısticas
que se destaquen de cualquier otra y las definimos de esta manera:
• Novedosa. La evolucion debe ser nueva o muy diferente a algunas otras que
esten en la base de datos
• Valida. Debe de ser valida dentro de la descripcion del aclr110
• Util. La utilidad de la evolucion estara en funcion de la ocurrencia de esta
dentro de ella misma o en otras evoluciones
Estos tres puntos son los que consideraremos al decidir si una evolucion presento
cosas interesantes. Si la informacion obtenida de un conjunto de evoluciones
tiene valores que sobrepasan los umbrales de cada uno de esos puntos, entonces
podemos decir que hemos encontrado algo interesante dentro de esas evoluciones.
Estos puntos seran analizados y definidos mas adelante.
1.7 Contenido general
El contenido de esta tesis esta dividido en 4 capıtulos.
• El capıtulo 1, este mismo, es el introductorio y establecemos un panorama
13
general de la tesis; hablamos de la teorıa de mosaicos y explicamos breve-
mente de donde viene la idea de considerar las evoluciones del aclr110 como
un problema de mosaicos. Hablamos de los trabajos realizados sobre este
automata, de la Minerıa de Datos y un poco de la historıa del desarrollo
de esta herramienta. Explicaremos, de manera general, el funcionamiento
de los modulos y submodulos que conforman el sistema que hemos desa-
rrollado para alcanzar los objetivos de este trabajo y ademas, daremos un
panorama general de los aspectos interesantes que se esperan obtener de los
resultados de esta tesis.
• En el capıtulo 2 se definen algunos terminos que usaremos a traves de
esta tesis, principalmente de automata celular ; definiremos que es un dia-
grama espacio temporal, que es un triangulo R110, ası como la descripcion
de cubrimiento y mosaico R110; relacionaremos el concepto de celula como
la mınima subregion R110 que puede surgir dentro de un diagrama espacio
temporal. Explicaremos la manera de codificar una evolucion en una cadena
de sımbolos a la que llamaremos contorno, con la ayuda de una maquina de
Moore. Mostraremos ejemplos concretos de estos contornos y veremos que
es posible reconstruir la imagen a partir de estos sin perdida de informacion.
• En el capıtulo 3 analizaremos los contornos R110 con un algoritmo que mide
la semejanza entre dos cadenas, y nos permite definir dos niveles de com-
paracion, con los cuales definimos dos funciones muy importantes para el
desarrollo de este trabajo; una funcion determina si un contorno es parcial
o totalmente novedoso (si nunca ha ocurrido o ha sido registrado anterior-
mente dentro de la BD) y la otra funcion mide la utilidad del contorno (si
ocurre muchas veces dentro de la BD). Tambien describiremos la funcion
de validez de contornos, que consiste en comprobar si un contorno dado
14
puede llenarse solamente con triangulos R110. Finalmente, se define una
funcion que toma los valores de salida de las anteriores, de tal modo que,
si una evolucion es lo suficientemente novedosa, valida y util, entonces se
considerara interesante.
• En el capitulo 4 explicaremos el funcionamiento del sistema que desarro-
llamos para este fin. Describiremos todos los modulos que lo forman, las
interfaces de usuario, la conexion con la base de datos, la definicion de la
estrutura de las tablas donde se almacenan los datos y las especificaciones
del lenguaje de programacion en el que fue programado.
• El capıtulo 5 se plazman las conclusiones obtenidas del proyecto y se pro-
ponen trabajos futuros.
15
CAPITULO 2
Automatas celulares y la regla R110
Resumen
En este capıtulo definimos formalmente el aclr110; describimos que son los dia-
gramas espacio temporales y porque se les considera como imagenes digitales.
Formalizamos los conceptos de triangulo, mosaico y subcubrimiento R110. Ex-
plicamos como se obtienen, a partir de los mosaicos R110, cadenas de sımbolos
a las que llamamos contornos R110 o simplemente contornos y del porque los
utilizamos en este trabajo en lugar de trabajar directamente con las imagenes.
Desarrollamos un procedimiento que identifica y marca a los triangulos que se
encuentran en los diagramas espacio temporales, para que despues, un recorrido
hecho por una maquina de Moore [8] devuelva una secuencia de direcciones que
forman el contorno de estos triangulos. Ademas, encontramos que a partir de los
contornos, podemos reconstruir un subcubrimiento en su totalidad sin perdida de
informacion.
2.1 Automatas celulares lineales
Los automatas celulares lineales estan definidos por un arreglo de celulas de di-
mension d, llamado espacio celular; donde cada uno de los elementos del arreglo
se denomina celula, que es un termino tomado de las ciencias biologicas como
16
algunos otros tales como evolucion, vida, muerte; que son adecuados para com-
prender el comportamiento individual de los elementos [2].
El espacio celular, en principio y tal como fue definido originalmente, es infinito
en todas sus direcciones, pero debido principalmente a las limitaciones practicas
y tecnicas, el espacio celular puede acotarse. Para poder simular el espacio celular
infinito, se ha decidido tomar condiciones periodicas de frontera, esto es, que la
celula siguiente a la ultima es la primera, y la celula anterior a la primera es la
ultima como se ve en la figura 2.1. Cuando d = 1 el espacio celular es un anillo,
en d = 2 se forma un espacio toroidal.
Figura 2.1: La funcion global de un automata celular lineal determina la configuracion global
en el siguiente paso de tiempo.
De acuerdo a [2], los automatas celulares lineales (acl) son sistemas dinamicos
discretos que evolucionan a traves del tiempo en espacios tambien discretos. Un
acl basicamente se compone de:
Un espacio celular G. Un acl es un sistema compuesto por una secuencia
G = (si)0≤i≤n-1 de celulas que evolucionan a traves del tiempo T en pasos
17
discretos. Cada si, es la i-esima celula de G.
El conjunto de estados de las celulas. Es el conjunto de estados en el que
puede encontrarse la celula; el estado que tendra la celula en el siguiente
paso del tiempo, esta determinado por el estado actual de ella misma y de
las celulas vecinas en un radio de vecindad predeterminado.
La configuracion de las vecindades. Al entorno que rodea una celula central
sc que se encuentra en el espacio celular, se le llama vecindad. Una vecindad
esta formada por el conjunto V ={si|d(sc, si) ≤ r}∪{sc}. Siendo r el numero
de vecinos en todas las direcciones que se encuentran con respecto a la celula
central y d(sc, si), es la distancia que existe entre la celula central sc y si.
La regla de evolucion local. Cada celula del espacio celular toma su valor
en dependencia de la configuracion de su vecindad. Si K es el conjunto de
estados, con K 6= 0, la regla de evolucion ϕ esta definida como:
ϕ : K2r+1 → K
Donde, 2r+1 es el tamano de la vecindad definida para el automata celular.
Definicion 1. El automata celular R110 se representa como una cuadrupla:
{K, φ, r, c}
Donde K es el conjunto de estados, φ la funcion de transicion, r el radio de
vecindad y c es el estado que por primera vez toma cada una de las celulas
del espacio celular (la configuracion inicial). El aclr1101 es un automata celular
1El numero 110 aparece porque los dıgitos “01110110” del codominio de la funcion, se puedenleer como una palabra en binario cuyo valor correspondiente en decimal es 110.
18
unidimensional de orden k=2, r=1, K={0, 1} y φ la regla de evolucion local que
esta definida como:
φ =
000 001 010 011 100 101 110 111
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 1 1 1 0 1 1 0
La regla de evolucion local queda determinada cuando se han nombrado todas
las posibles combinaciones de su vecindad, es decir 22(1)+1=23=8, y su asignacion
de estados dentro del conjunto de estados K.
En la figura 2.2 se muestra un ejemplo de evolucion de la regla 110, tomado a
partir de una configuracion inicial aleatoria con distribucion pseudouniforme.
El espacio celular es de 25 celulas y se muestra la historia del automata a traves
de 25 generaciones. Por convencion, se le dara un color obscuro a las celulas con
valor 1, y un color claro a aquellas con estado 0.
Observe que en este espacio se aprecian figuras pseudo triangulares2 de diferentes
tamanos. Estas figuras triangulares son el objeto de estudio de esta tesis, y han
sido estudiadas desde finales de la decada de 1990 [2, 15]. El que los triangulos
conserven la misma orientacion y forma, es lo que hace al aclr110 objeto de analisis
con el fin de responder cuestionamientos como ¿cual es la causa de que estos
triangulos ocurran? y ¿tendran algun significado computacional?.
2En realidad no son triangulos, pues ocurren en un espacio 2D discreto, lo que hace que suhipotenusa se vea como escalera, ademas de que estan semi-bordeadas solo por el lado superiore izquierdo.
19
Figura 2.2: Izq: Representacion interna de una evolucion del aclr110. Der: Asignandole un
color obscuro a las celulas con valor 1 y un color claro a aquellas con valor 0.
2.2 Diagrama espacio-temporal
Un diagrama espacio temporal (en adelante DET para abreviar), es una repre-
sentacion visual de las evoluciones del aclr110. Un DET se puede ver como un
arreglo de configuraciones globales, donde el primer elemento de este arreglo es
la configuracion inicial del aclr110 en el primer momento del tiempo (que usual-
mente es t=0), y los siguientes elementos del arreglo se situan en orden creciente,
cada uno debajo del anterior como se ve en la tabla 2.1.
Cuando se apilan hacia abajo las configuraciones obtenidas de las evoluciones del
aclr110, se crea un subespacio de Z × Z. Cada punto de este subspacio celular
en cualquier momento de su evolucion es una celula, de manera que cada punto
grafico del subespacio tiene asociado un estado dentro del conjunto de estados
definido [2].
Teoricamente, todas las celulas de un automata evolucionan al mismo tiempo,
pero debido a la arquitectura secuencial, las celulas se actualizan secuencialmente
20
t = 0 Configuracion Inicial
t = 1 1a Evolucion
t = 2 2a Evolucion
. .
. .
. .
t ta Evolucion
Tabla 2.1: Tabla esquematica de las evoluciones de un Automata Celular
a una velocidad tal, que parece que la evolucion es en paralelo. Sin embargo,
cuando el numero de celulas y evoluciones aumenta, observamos claramente las
desventajas de lo secuencial, pues el tiempo de procesamiento aumenta. Ası que,
por necesidades tecnicas, consideraremos que tanto el espacio celular como el
numero de pasos en el tiempo deben ser finitos y estar acotados; debido a esto,
en el DET se forman regiones de frontera, de tal modo que definiremos el conjunto
frontera F={fup, fdw, flf , frw}, como el conjunto de puntos p ∈ DET tal que:
Frontera superior (fup) = {(x, y) | y=0}
Frontera inferior (fbt) = {(x, y) | y=maxy}
Frontera izquierda (flf ) = {(x, y) | x=0}
Frontera derecha (frw) = {(x, y) | x=maxx}
Si p=(x, y), entonces p ∈ F si, p ∈ fup ∪ fbt ∪ flf ∪ frw. Por ejemplo, si p ∈ fup,
las regiones de frontera establecen que no existen celulas en p=(x, y-1), ası como
tampoco hay celulas en p=(x, y+1) para un punto p ∈ fdw, y de igual manera para
cualquier otro punto que pertenezca a las otras regiones de F .
En este trabajo, el tamano del espacio celular va desde 50×50 hasta 500×500, y
21
es posible varıar su tamano en incrementos de 50 en 50 celulas; esto ultimo solo
por la comodidad de tener espacios fijos multiplos de 50. Un DET se representa
internamente con una estructura de datos (arreglo) bidimensional y cada posicion
(celula) de la estructura puede tener valores 1 o 0. Si cada celula se representa
como un cuadrado al que se le asigna un color obscuro para las celulas con valor
1 y un color claro para aquellas con valor 0, se forman imagenes (mapas de bits)
de diferentes tamanos, dando pie a que los DET se consideren imagenes digitales.
En adelante llamaremos D al conjunto de todos los DET generados por las evolu-
ciones del aclr110.
Figura 2.3: Imagenes que representan las evoluciones de las reglas 110, 124, 137 y 193.
2.2.1 Descripcion de un triangulo R110
En las evoluciones de la regla 110, se observan patrones triangulares de diferentes
tamanos pero conservando una orientacion hacia la derecha; otras reglas como
la 124, 137 y 193 tambien producen patrones triangulares pero en orientaciones
diferentes (vea la figura 2.3). Ademas de las zonas triangulares, aparece otra zona
que aparenta ser el contorno que rodea los triangulos.
22
Figura 2.4: (A) Triangulo R110 o t6. (B) Descomposicion en sus secciones principales: lacelula origen, las fronteras superior e izquierda y el cuerpo del triangulo.
De manera informal, un triangulo R110 de tamano n denotado como tn, es una
sub-region del diagrama espacio temporal del aclr110, que se extiende n+1 pasos
en el tiempo y abarca n+1 puntos en el espacio [2] (vea la figura 2.4), que se
distribuyen de la siguiente manera:
• Una celula de estado 1 llamada el origen del triangulo.
• Una secuencia de n celulas de estado 1 extendidas horizontalmente, llamada
la frontera superior del triangulo.
• Una secuencia de n celulas de estado 1 extendidas verticalmente, llamada
la frontera izquierda del triangulo.
• Un conjunto triangular de celulas de estado 0 de tamano n contados de
abajo hacia arriba, llamado el cuerpo del triangulo. Esta seccion da pie a lla-
mar frontera diagonal a las celulas que forman la hipotenusa del triangulo.
A partir de aquı, denotaremos por tk a un triangulo R110 de tamano k ≥ 0. Un
criterio de identificacion se muestra en la figura 2.5. Observe que hemos desta-
cado con una lınea mas obscura a tres triangulos que cumplen con la definicion.
23
Podemos ver un t7, un t1 y un t0; un caso particular es el triangulo t0, que es
la mınima region dibujada de un triangulo R110 y se compone unicamente de
una celula, la del origen, no tiene cuerpo y ademas tanto sus fronteras superior
e izquierda son de tamano 0. Una celula es un cuadrado de longitud unitaria;
en estado 1 se le llama celula viva mientras que en estado 0 se le llama celula
muerta.
Figura 2.5: Aquı se observan triangulos de diferentes tamanos contendidos en un DET
2.2.2 Identificacion de los triangulos R110 incompletos en los DET
Graficamente, un DET esta formado de triangulos de diferentes tamanos adya-
centes uno del otro, y tambien por algunos a los que llamaremos triangulos incom-
pletos. Estamos interesados particularmente en los primeros. Los triangulos in-
completos se encuentran siempre en las fronteras de un DET de cualquier evolucion
del automata; en la figura 2.6 se muestra un DET y los triangulos incompletos
estan delineados con una lınea mas obscura (no todos) para poder visualizarlos
mejor; estos triangulos no cumplen con la definicion y tampoco estan contenidos
completamente dentro del DET, por lo tanto no se consideran triangulos R110. La
importancia de identificarlos radica, en que estos triangulos no seran considerados
en los procedimientos de manipulacion que describiremos mas adelante.
24
Figura 2.6: DET de tamano 50× 50. Pueden observarse muchos triangulos que estan fuera delos lımites del DET.
2.3 Mosaicos y cubrimientos R110
Las evoluciones de los espacios celulares gobernados por la regla de evolucion 110,
cubren un semiplano bidimensional discreto con triangulos de diferentes tamanos.
Pero cuando consideramos los triangulos como elementos constructivos, se forman
nuevos elementos a los que llameremos cubrimientos con los cuales podemos
cubrir regiones del plano; estos cubrimientos definen un semigrupo aditivo, lo
que nos permite agregar nuevos triangulos (bajo ciertas condiciones) y seguir
teniendo un cubrimiento valido, como se define a continuacion.
Cubrimientos completos y subcubrimientos
Consideremos primero los triangulos y un alfabeto de triangulos T = {t0, t1, . . . , tk}.
Un T-cubrimiento completo es la region infinita Q2 = (Z× Z), que esta cubierto
completamente por un conjunto infinito de triangulos R110 definido como:
25
Q2={tk1 , . . . , tk′m| tkj∈ T, k ≥ 0, si m > 1, ∃ i 6= j : tki
‖ tk′j}
El sımbolo ‖ quiere decir que los triangulos son adyacentes.
Nota: Decimos que dos triangulos son adyacentes si estan uno junto al otro por
cualquiera de sus fronteras y no se traslapan. Para una definicion mas precisa de
adyacencia de triangulos R110, refierase al punto Definiciones relacionadas con
los cubrimientos en [2].
De modo que un cubrimiento T, es una subregion del DET (que puede no cubrirlo
todo), y esta compuesto por mas de un triangulo R110 de cualquier tamano.
Aunque no pueda cubrir todo el DET, no existen celulas medio cubiertas debido
a la discretud del espacio. Ası que en un DET ⊂ Q2, un subcubrimiento esta
contenido dentro del DET. Siguiendo esta lınea de pensamiento, un triangulo R110
de tamano k, es un subcubrimiento del DET formado por un solo triangulo. De tal
manera que a estos subcubrimientos los llamaremos por el tamano del triangulo
correspondiente, es decir, t0, t1 o tn; mientras que a una extension natural de los
DET que involucren a mas de un triangulo R110, los llamaremos por lo general
mosaicos R110 como el que se muestra en la figura 2.7.
Estamos especialmente interesados en los subcubrimientos que cumplan con la
definicion dada en el punto 2.2.1, que esten contenidos completamente dentro del
DET y en aquellos que en conjunto, formen mosaicos R110. De estos subcubrim-
ientos, se obtendra mucha informacion que sera extraida por procedimientos au-
tomaticos que describiremos en las siguientes secciones.
26
Figura 2.7: Mosaico R110 formado por 18 triangulos incluyendo los t0
Cerradura de Kleene en el espacio de direcciones
Es posible recorrer un trianguloR110 de tamano 0 (una celula), visitando cada uno
de sus lados; esto se hace evidentemente en 4 pasos. Definimos entonces el espacio
de direcciones Σ={N, S, E, W}, como el conjunto de sımbolos que representan
direcciones de longitud unitaria en Z2. Si p0=(x, y) es un punto en el plano
discreto, el sımbolo ‘E’ representa la accion de visitar el punto p1=(x+1, y) y lo
representamos graficamente como un segmento de linea con una flecha que apunta
hacia la derecha, similarmente, los sımbolos ‘N’, ‘S’, ‘W’, aplicados a un punto
p0=(x, y) representan la accion de visitar los puntos p1=(x, y-1), p2=(x, y+1) y
p3=(x-1, y) respectivamente.
Definicion 1. Trayectoria: Una trayectoria es una secuencia (di)0≤i<k-1 de
longitud k, con cada di ∈ Σ.
Notamos entonces que Σ es un conjunto de funciones, todas con dominio y codo-
minio en Z2. Aplicando cada una de las funciones de Σ sobre un punto p ∈ Z2,
podemos definir una funcion N con estructura N : Z2 → Z2 de tal modo que:
27
N(x, y) = (x, y-1)
S(x, y) = (x, y+1)
E(x, y) = (x+1, y)
W(x, y) = (x-1, y)
Ası, una trayectoria es una secuencia de sımbolos de Σ que representa al recorrido
de un punto p ∈ Z2 que se mueve por la accion de aplicar las funciones de
la secuencia, lo que se entiende como la composicion de funciones de Σ. Si
d∗ = d0d1d2 · · · dk ∈ Σ∗, entonces definimos una funcion recorrer con estructura
recorrer : Z2 → Z2 que se define ası:
recorrer(x1, y1) = dndn-1 · · · d1d0(x1, y1)
= d∗(x1, y1)
Entonces, el resultado de aplicar d∗ a un punto p ∈ Z2, es un nuevo punto p′ ∈ Z2
(posiblemente el mismo), es decir:
d∗(p) = dn
(dn−1
(· · ·(d0
(p))· · ·))
= p′
Si p = p′, entonces d∗ es una trayectoria cerrada, y si ademas d∗ delinea un espacio
que puede llenarse con triangulosR110, entonces d∗ es un contorno R110. Entonces,
aplicando la Cerradura de Kleene [21], obtenemos palabras de longitud finita
formada de sımbolos de Σ que representan contornos R110; ası que de acuerdo a
lo anterior, podemos dar la siguiente:
28
Figura 2.8: Contorno de un triangulo t3.
Definicion 2. Contorno R110: Un contorno R110 es una trayectoria cerrada
c = c1, c2, . . . , ck donde cada ci ∈ Σ y normalmente k < ∞ tal, que recorre
un mosaico R110.
Los contornos R110 tienen las siguientes propiedades:
1. Son curvas cerradas. Esto se puede verificar comprobando el numero de
N’s, S’s, E’s y W’s que tiene la trayectoria. Si hacemos que num(N) sea el
numero de N’s que ocurren, y del mismo modo num(S) la cantidad de S’s;
num(E) la cantidad de E’s y num(W) el numero de W’s, entonces
num(S) + num(E) = num(W) + num(N) (2.1)
2. Se pueden distinguir tres partes de la secuencia, una de ellas poblada de
E’s, que indican la extencion del triangulo R110; la parte central compuesta
por SW’s que forman la diagonal; y finalmente una serie de N’s que forman
la frontera izquierda. Hay que mencionar que este punto es valido solo en
triangulos unitarios, no ası para los mosaicos R110.
Para ilustrar propiedades, el contorno del t3 de la figura 2.8, esta codificado como
29
ct6= EEEESSWSWSWWNNNN. En las siguientes secciones se describen los procedimien-
tos que se desarrollaron para que la codificacion de los DET, sea automatica.
2.4 Obtencion de los contornos R110
Para obtener el contorno de un triangulo R110, debemos realizar un recorrido por
cada una de sus fronteras dibujando una trayectoria cerrada, de tal modo que
rodeemos al triangulo. Sin embargo, cuando tenemos un mosaico compuesto por
mas de un triangulo, ya no es tan simple obtener el contorno. Obtener manual-
mente el recorrido de un mosaico T = {t1, t2, . . . , tn} formado por n triangulos, es
una tarea laboriosa que incrementa su dificultad a medida que crece el numero
de triangulos. A continuacion se describen los procedimientos para obtener los
contornos tanto de un triangulo unitario, como de un mosaico compuesto por
cualquier numero de estos. Los procedimientos actuan en el arreglo bidimen-
sional que tiene almacenados en sus casillas los valores de cada una de las celulas
del mosaico.
Para obtener el contorno de un tn con cualquier valor de n, intervienen tres
procesos diferentes:
1. Identificacion de un triangulo
2. Marcacion de las fronteras
3. La obtencion del contorno
Identificacion del triangulo
Para identificar a los triangulos que estan dentro de un DET, se hara un barrido
de izquierda a derecha y de arriba a abajo, comenzando en el punto p=(0, 0).
30
Cuando se encuentre una celula viva, se hace una llamada a un procedimiento
que evaluara si esa celula es la del origen de un triangulo.
Algoritmo 1 : Algoritmo que identıfica un Tk
Requiere: {x, y} ∈ DET
while((ν(x+1, y)=1 & ν(x+1, y+1)=0
)&(ν(x, y+1)=1 & ν(x+1, y+1)=0
))do
contX ← contX + 1, contY ← contY + 1x← x + 1, y ← y + 1
end whileif contX = contY then
Si es trianguloend if
El algoritmo 1, muestra la manera en que se identifica un tk de cualquier tamano.
Recibe como parametros un punto p ∈ DET, donde se localiza una celula viva
(suponiendose que se trata de la celula origen del triangulo), a partir de ese
punto, realiza dos recorridos, uno hacia la derecha (−→) y otro hacia abajo (↓)
verificando el valor de las celulas vecinas con la ayuda de una funcion auxiliar
ν : DET→ {1, 0} que se comporta ası:
ν(x, y) =
1 Si la celula esta viva
0 e.o.c
(2.2)
A partir del punto p=(x, y), en cada llamada, la funcion ν verifica dos puntos
diferentes para cada una de las direcciones: uno de ellos es un punto guıa que
se desplaza hacia la derecha y hacia abajo (siguiendo celulas vivas), e indica
que estamos en la frontera ya sea superior o izquierda del triangulo, y el otro
funciona como un punto de referencia que se desplaza por el cuerpo del triangulo
(siguiendo celulas muertas); ademas se actualizan los valores de dos contadores
contX y contY que indicaran el tamano del triangulo. El recorrido termina
cuando el valor del punto de referencia es diferente de 0, lo que indica que ya no
31
estamos en el cuerpo del triangulo. De acuerdo a la direccion, los puntos que se
verifican son:
• −→: (Frontera superior) Se verifican los puntos (x+1, y) y (x+1, y+1)
• ↓: (Frontera izquierda) Se verifican los puntos (x, y+1) y (x+1, y+1)
Cuando el recorrido termina, si el valor de los dos contadores contX y contY, es
el mismo, entonces se encontro un triangulo R110, por lo que pasamos al siguiente
paso; en caso de que contX 6= contY, se sigue avanzando hacia la derecha en busca
de otra celula viva para repetir el procedimiento y de esa manera identificar (y
marcar) a todos los triangulos completos que existan dentro del DET.
Marcacion de las fronteras
Al llegar a este paso, se tiene la seguridad de que se ha encontrado al menos
un triangulo R110 y por lo tanto se marca realizando algunas substituciones en
el arreglo: se coloca un sımbolo ‘*’ en las celulas que tengan valor 1 (frontera
superior e izquierda del triangulo) incluyendo desde luego a la celula origen, y
un sımbolo ‘+’ a las celulas de la frontera diagonal como se ve en la figura 2.9.
Este proceso de substitucion sirve para identificar las fronteras del triangulo y
posteriormente tomar esos sımbolos como referencia.
Figura 2.9: Triangulo marcado.
32
La obtencion del contorno
Este procedimiento realiza un recorrido por los triangulos que ya han sido mar-
cados (con los sımbolos ‘*’ y ‘+’) en sus fronteras y nos devuelve una cadena
(di)0≤i<k-1 de longitud k, con cada di ∈ Σ que representa el contorno de los
triangulos contenidos dentro del DET. Para dicho recorrido, utilizaremos un au-
tomata finito determinıstico, al que hemos llamado el automata ciego.
El automata ciego (BA)
El BA recorre las fronteras de los triangulos marcados, y en cada llamada de-
vuelve un sımbolo que se concatena formando una palabra tal que, al terminar
el recorrido, es una secuencia de sımbolos que representan un cubrimiento R110.
Para explicar el funcionamiento basico del BA, imagine a un invidente que in-
tenta rodear algun objeto a tientas. La mano derecha del invidente siente el
objeto y la mano izquierda funciona como guıa para que cambie de direccion. El
invidente avanza en una direccion fija mientras sienta el objeto con la derecha
y con la izquierda no sienta nada (no hay objeto), y cambia la direccion de su
desplazamiento cuando ocurre cualquiera de los dos casos siguientes:
• Deja de sentir el objeto con la mano derecha (giro a la derecha) o
• Cuando sienta el objeto con ambas manos (giro a la izquierda)
Con esta lınea de pensamiento, substituimos la funcion de la mano izquierda por
una variable α1, la de la mano derecha por α2, el objeto por un DET formado
de triangulos R110 marcados y el termino sentir con el valor devuelto por una
funcion ϕ que actua sobre un punto p ∈ DET; la estructura de esta funcion es
ϕ : DET→ {0, 1} y esta definida como:
33
ϕ(x, y) =
1 Si la celula esta marcada (ya sea con ‘*’ o con ‘+’)
0 e.o.c(2.3)
Donde se entiende que con ϕ(x, y)=1, se siente el triangulo, mientras que con
ϕ(x, y)=0 no se siente.
Formalmente, el BA es una 6-tupla (S, S0, Σin, Σout, Min, Mout) donde:
• S = {e, f, s, g, h, i, j, CI, k, x, n, y, w}
• S0 = e ∈ S. El estado inicial
• Σin = {0, 1}
• Σout = {N,S,E,W, ci, b}. b = NULL
• Min= {M1,M0}, la funcion de transicion para las entradas
• Mout : S × Σin → Σout
La funcion Min con estructura Min : S × Σin → Σout, se define para M1 ∈ Min
de la siguiente manera:
M1 =
e f s g h i j CI k x n y w
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
i e g e n n s ci s w x w j
De igual manera para M0 ∈Min, definida como la funcion anterior:
M0 =
e f s g h i j CI k x n y w
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
f s k ci e ci ci ci w ci h n y
34
Finalmente, la funcion de salida Mout, con estructura Mout : S × Σin → Σout, se
define como:
Mout =
e f s g h i j CI k x n y w
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
E b S b b b b b b b N b W
Definimos un subconjunto Ψ ⊂ S = {e, s, n, w} de estados que devuelven un valor
de Σout distinto de b y de ci. El funcionamiento del BA, es una funcion λ con
estructura λ : {0, 1} × {0, 1} → Σ∗ que se define en la tabla 2.2:
ψ ϕ(p1) & ϕ(p2) −→ {E,S,W,N}
0 & 0 −→ S
e 0 & 1 −→ E
1 & 0 −→ CI∗
1 & 1 −→ N
0 & 0 −→ W
s 0 & 1 −→ S
1 & 0 −→ CI∗
1 & 1 −→ E
0 & 0 −→ N
w 0 & 1 −→ W
1 & 0 −→ CI∗
1 & 1 −→ S
0 & 0 −→ E
n 0 & 1 −→ N
1 & 0 −→ CI∗
1 & 1 −→ W∗Caso Imposible
Tabla 2.2: Definicion de la funcion λ. El sımbolo que devuelve esta en funcion de los
parametros de entrada
35
Donde ψ ∈ Ψ, los valores {0,1} son el resultado de aplicar la funcion ϕ a dos
puntos {p1, p2} ∈ DET, y c ∈ Σ∗ es el sımbolo devuelto por la funcion y esta en
funcion del estado ψ ∈ Ψ en el que se encuentra el BA. Las coordenadas de los
dos puntos p1 y p2, tambien estan en funcion del valor de ψ como puede verse en
la tabla 2.3:
ψ ∈ Ψ p1 p2
E (x+1,y-1) (x+1,y)
N (x-1,y-1) (x,y-1)
S (x+1,y+1) (x,y+1)
W (x-1,y+1) (x-1,y)
Tabla 2.3: Las coordenadas de los puntos p1 y p2 que evalua la funcion ϕ estan en funciondel estado s ∈ S.
Por convencion, el valor inicial de d=E. Se hacen dos llamadas a la funcion ϕ sobre
dos puntos p1 y p2, de acuerdo a la tabla 2.3, con lo que obtenemos una secuencia
de dos dıgitos {α1, α2} ∈ {0, 1}; estos dos valores se envıan a la funcion λ que
es la que hace funcionar a el BA de acuerdo a el diagrama de estados que puede
verse en la figura 2.10. Observe que comenzando en el estado inicial e, para cada
secuencia par de digitos {0,1}, siempre se llega a un estado ψ∗ ∈ Ψ despues de
visitar uno de los estados auxiliares, y que la secuencia < 10 > termina siempre
en el estado CI (caso imposible) desde cualquier estado ψ∗ ∈ Ψ.
2.4.1 La secuencia < 10 >
En la figura 2.11 (A), vemos algunos de los casos en los que obtenemos las se-
cuencias de dıgitos que hacen funcionar a el BA. El inciso (a), con d=E, obtiene
la secuencia < 01 > y devuelve E; en (b), d=E, obtiene la secuencia < 11 > y
36
Figura 2.10: Diagrama de estados del BA
devuelve N y para el caso (c), d= S, obtiene la secuencia < 00 > y devuelve W.
Un caso especial es la secuencia < 10 >.
Esta secuencia de dıgitos es imposible de obtener por las llamadas a la funcion ϕ,
pues para esto se necesita que en el DET, haya mosaicos como el que se muestra
en la figura 2.11 (B); mosaicos como ese, nunca ocurren en las evoluciones del
aclr110, pues las alineaciones por la frontera superior entre los triangulos no estan
permitidas por las reglas de evolucion de este automata [2].
Figura 2.11: (A). Secuencia de digitos obtenidos de un mosaico R110. (B). Caso imposible.Un mosaico como el que se muestra nunca ocurre en las evoluciones del aclr110.
37
A manera de ejemplo, vamos a obtener el contorno del triangulo de la figura 2.12.
El punto inicial es la celula origen del triangulo, y el recorrido es hacia a la
derecha. El algoritmo 2 muestra como funciona la funcion recorre triangulo en
el ciclo que recorre el triangulo y que termina al llegar al mismo punto en el que
comenzamos.
De la concatenacion de los sımbolos devueltos por λ, resulta el contorno de un t6
que se codifica como ct6 = EEEEEEESSWSWSWSWSWSWWNNNNNNN.
Algoritmo 2 : Algoritmo de la funcion recorre triangulo
Requiere: d ∈ Σ∗, α1, α2
Devuelve: ck ∈ Σwhile (condicion final) do
if (d = E) thenα1 ← v1 ∈ {0, 1} //donde vi = ϕ(p); x, y son las coordenadasα2 ← v2 ∈ {0, 1} //de un punto p ∈ DET y estan en funcion del valor de d
end ifif (d = N) thenα1 ← v1 ∈ {0, 1}α2 ← v2 ∈ {0, 1}
end ifif (d = S) thenα1 ← v1 ∈ {0, 1}α2 ← v2 ∈ {0, 1}
end ifif (d = W) thenα1 ← v1 ∈ {0, 1}α2 ← v2 ∈ {0, 1}
end ifc← c.σ ∈ Σ //donde σ= λ(d, α1, α2)end while
Obtencion de los contornos de los mosaicos R110
El procedimiento anterior funciona tanto para obtener el contorno de un triangulo,
como para el de un mosaico que contenga mas de un triangulo como se ve en la
figura 2.13. Sin embargo, al aplicar los procedimientos de identificacion y mar-
38
Figura 2.12: Se observan las celulas que se van visitando a medida que se avanza sobre lasfronteras del triangulo y los valores que va devolviendo el automata.
cacion de triangulos a una evolucion R110, agregaremos una funcion que va al-
macenando datos de cada uno de los triangulos, tal como las coordenadas en las
que se localiza y su tamano; estos datos se almacenaran en listas cuya estructura
puede verse en la tabla 2.4, y que podran ser consultadas posteriormente por
otros modulos del sistema.
Figura 2.13: Obtencion del contorno que involucra triangulos adyacentes de diferentes
tamanos que forman un mosaico R110
Graficamente, la informacion de la posicion 0 de la tabla 2.4, corresponde al
triangulo tm que se encuentra mas arriba y mas a la izquierda del mosaico, y lo
identificamos como el t(0)m , mientras que el n-esimo triangulo es el que se encuentra
mas a la derecha y mas abajo del mosaico, y esta denotado como t(n)k .
39
x y Tamano (tm)
x0 y0 t(0)m
x1 y1 t(1)m′
......
...
xn yn t(n)k
Tabla 2.4: Tabla de informacion que muestra la estructura que almacenara la posicion y el
tamano de cada uno de los triangulos del mosaico.
Definimos una operacion QuitaTriangulo, que substituye los sımbolos ‘+’ y
‘*’ de un triangulo por los valores 0 y 1 respectivamente, de esta manera este
triangulo ya no es seguido por el BA. Ahora, aplicando el BA a un mosaico R110
como el de la imagen (A) de la figura 2.14, obtendremos un contorno que con-
tiene a todos los triangulos R110 que existen dentro de el, tal y como se ve en
la imagen (B); el contorno de este mosaico (delineado con una lınea mas obs-
cura), se compone de 78 triangulos incluyendo los t0’s, y es codificado como:
c =EEEESEENEEEESEEEESSSEENESSSSSSSSSSSSSSSSSSSSSWWSWWNWWWNENNWWWWW
SWWWWSWWWSWSWWWWNNENENENENENENENNWWWWWWWNNNENNWNENENENENENENNWNEN.
El contorno c es el contorno de mayor longitud que podemos obtener de este DET.
Es posible reconstruirlo graficamente usando los sımbolos del contorno dibujando
lıneas de longitud unitaria en direccion del valor de cada uno de los sımbolos del
contorno3. Por ejemplo, si el primer caracter del contorno es E, dibujamos una
lınea en la direccion Este, una lınea en direccion Sur para S y ası con las otras
direcciones hasta terminar con todos los sımbolos del contorno.
El resultado de dibujar esa serie de lıneas, forma una trayectoria cerrada que
graficamente es el contorno del mosaico de la imagen (B), y se ve en la figura 2.15;
3Formado por los sımbolos E,S,W,N
40
Figura 2.14: Izq: Evolucion del aclr110. Der: Contorno formado por todos los triangulos
contenidos completamente dentro de la evolucion.
sin embargo, aunque reconstruimos el contorno del mosaico, hemos perdido infor-
macion valiosa que no es posible determinar facilmente pues no sabemos cuantos
triangulos (ni de que tamano) estan contenidos dentro del contorno.
Desde luego, es posible recuperar los triangulos del interior. En el siguiente
capıtulo definiremos un procedimiento que evalua la validez de cualquier contorno
R110, es decir, si el contorno puede ser llenado completamente con triangulos R110.
Por el momento nos ocuparemos de obtener toda la informacion que podamos
extraer de un mosaico; ası que dado un mosaico R110, aplicamos el procedimiento
para obtener el contorno que contiene a todos los triangulos contenidos den-
tro de el, y de esta manera llenamos nuestra tabla con la informacion de los
triangulos encontrados, para posteriormente aplicar un nuevo procedimiento que
basicamente es eliminar los triangulos uno por uno y al mismo tiempo realizar
un nuevo recorrido para obtener un nuevo contorno. Este procedimiento recorre
la tabla de abajo hacia arriba comenzando en el n-esimo triangulo, hasta llegar
al triangulo t(0). El algoritmo trabaja basicamente de esta manera:
41
Figura 2.15: Esta imagen muestra como se reconstruye un contorno a partir de una cadena
de sımbolos con el formato [E,S,N,W].
1. Comienza en la n-esima posicion de la tabla.
2. Retira el triangulo de esa posicion del mosaico.
3. Aplica el BA para buscar un nuevo contorno.
4. Se ubica en la siguiente posicion de abajo hacia arriba (n-1).
5. Repite los pasos 2, 3 y 4 hasta llegar a la posicion 0 de la tabla.
El procedimiento termina cuando se han retirado todos los triangulos de la tabla
y se han obtenido los contornos, pues en cada llamada al BA, se obtiene un
contorno diferente, ası que, al terminar el analisis de este mosaico formado por
78 triangulos (imagen (B) figura 2.14), tendremos 78 contornos diferentes mas el
contorno vacıo (φ) como puede verse en la figura 2.16. Al encontrar todos los con-
tornos que involucran triangulos R110 contenidos dentro de un mosaico, se obtiene
suficiente informacion de los triangulos que lo forman; de este modo, esa infor-
macion es almacenada en una base de datos y puede consultarse posteriormente
por otros modulos del sistema para diversos propositos como la reconstruccion de
los mosaicos a partir de su contorno, o realizar comparaciones entre contornos.
42
Figura 2.16: Conjunto de contorno obtenidos de un mosaico R110.
43
2.5 Conclusiones
Como se demostro, los mosaicos pueden ser factiblemente manipulados como
cadenas de texto. La codificacion de los mosaicos nos permite almacenar la
informacion necesaria de ellos de tal modo que es posible volver a reconstruirlo
sin perdida de informacion. Ademas es mas facil manipularlos de esta manera,
dejando a un lado el aspecto grafico y la dificultad que representa la comparacion
de imagenes de mapas de bits. Encontramos que el automata ciego es eficaz para
obtener los contornos de cualquier evolucion, sin embargo, el tiempo de ejecucion
del sistema aumenta cuando el tamano de los DET es muy grande y esto se debe
a la gran cantidad de triangulos que hay en la evolucion.
44
CAPITULO 3
Definicion de lo interesante
Resumen
En este capıtulo analizamos muchos contornos R110 que representan evoluciones
graficas del aclr110. Explicamos el funcionamiento del algoritmo de la subsecuen-
cia comun mas larga o LCS por sus siglas en ingles (Longest Common Subse-
quence), y su aplicacion en el analisis de los contornos R110, para obtener la
distancia de Levinshtein entre dos contornos, y definir dos tipos de comparacion:
el de diferencias y el de semejanzas. Con estos dos tipos, definimos dos funciones
de semejanza, una evalua si un contorno ocurre por primera vez dentro de una
BD (funcion de lo novedoso), y la otra mide el numero de veces que aparece el
contorno dentro de la misma BD (funcion de utilidad). Ademas, debido a que los
contornos se manejan tambien como datos de entrada, se definio una funcion que
evalua si el contorno rodea solamente triangulos R110 (funcion de validez ). Final-
mente, la funcion de lo interesante, recibe los valores devueltos por las funciones
anteriores y devuelve un resultado que nos ayudara a decidir si los contornos
analizados son interesantes o no.
45
3.1 El problema de la subsecuencia comun mas larga y
los contornos R110
De acuerdo con [10], la forma no trivial mas simple de analizar secuencias de
caracteres similares es utilizar el algoritmo de la Subsecuencia Comun mas Larga.
El algoritmo consiste en obtener la longitud maxima que puede tener una palabra
d que sea subsecuencia de las palabras v y w [10]. De acuerdo con [3], una de
las principales aplicaciones para este algoritmo entre otras, se da en la biologıa
molecular. Como las cadenas de ADN pueden ser representadas como secuencias
de las letras ACGT (adenina, citocina, guanina y timina)1, cuando los biologos
encuentran una nueva secuencia, normalmente quieren saber si hay alguna otra
que sea lo suficientemente similar a esta. Una manera computacional de hacerlo
es encontrar la longitud de la LCS entre secuencias de letras que representen
cadenas de ADN.
Aquı es donde existe una relacion del problema de la LCS con uno de los obje-
tivos de esta tesis. Si tenemos dos secuencias de sımbolos NSEW que representan
mosaicos R110, es posible compararlos para determinar que tan similares o que
tan diferentes son entre ellos. Para explicar el funcionamiento del algoritmo que
resuelve el problema de la LCS, definiremos algunos terminos necesarios:
Definicion 3. Una subsecuencia s de una cadena v, denotada como s ⊂ v, es
simplemente una secuencia ordenada de caracteres no necesariamente consecu-
tivos de v [10].
Por ejemplo, si v ∈ Σ∗ es un contornoR110 y v = EEEEEEESSSEESSWSWSWWWWWWWNNN
NNNN, entonces EEEESSSWSWSWWNNN y EESEWSNN son subsecuencias de v, mientras
que EESEWWEEN y SSSSEEWWNN no lo son. La diferencia entre una subsecuencia
1Que corresponden a las cuatro submoleculas que forman las cadenas de ADN
46
y una subcadena, es que una subcadena consiste solo de caracteres consecutivos
de v, mientras que una subsecuencia puede ir escogiendo diversos caracteres a lo
largo de v, preservando solamente el orden en el que estan. Si s es una subse-
cuencia de v, lo denotaremos como s ⊂ v.
Definicion 4. Una subsecuencia comun s de dos cadenas v y w, es una
subsecuencia de ambas cadenas, denotada por s ⊂ (v, w), si s ⊂ v y tambien
s ⊂ w.
No siempre hay una unica subsecuencia comun entre dos cadenas v y w, cuando
hay mas de una, algunas llegan a ser mas largas que otras, y no es inmediatamente
obvio encontrar precisamente la mas larga de ellas.
Definicion 5. Una palabra s es la subsecuencia comun mas larga de las palabras
v y w, denotada como S(v, w), si:
S(v, w) = max{|s| : s ⊂ (v, w)} (3.1)
Donde |s| es la longitud maxima de todas las subsecuencias entre v y w. Por ejem-
plo, si v= EESSEENEEEESSSWWSSSWSWSWWNWWNNNNNNNN y w= EESSSEESSSSWWWWSWW
NNNWWNNNN son dos contornos, entonces S(v, w)=23 es la longitud de la LCS entre
v y w, y es z= EESSEESSSWWWWSWWNWWNNNN. Obtener la longitud de la subsecuen-
cia comun mas larga entre dos contornos v y w, nos servira para determinar la
distancia de Levinshtein [25], que puede verse como el mınimo numero de opera-
ciones de edicion necesarias para transformar una cadena en otra, o contornos en
nuestro caso. Mas adelante, en 3.2 volveremos con la distancia de Levinshtein.
47
El algoritmo de la LCS
El algoritmo 3 calcula la longitud de la LCS entre dos contornos R110, vn y wm,
donde n ym son las longitudes de los contornos. Sea entonces v(12) = EEESSWSWWNNN
y w(8) = EESSWWNN dos contornos que graficamente corresponden a dos triangulos
t2 y t1 respectivamente. Este algoritmo va calculando progresivamente las LCS
de las porciones iniciales de ambos contornos, guardando los valores calculados en
una matriz bidimensional M[n+1, m+1]. Si llamamos vi al i-esimo sımbolo de v y
wj al j-esimo sımbolo de w, entonces, la componente M[i, j] | i=0, . . . , n, j=0, . . . ,m
se calcula para i, j > 0 de la siguiente manera:
M[i, j] =
φ Si i=0 o j=0
M[i-1, j-1] + 1 Si vi =wj
max(M[i, j-1], M[i-1, j]) e.o.c
Para entender mejor el funcionamiento del algoritmo, vease la tabla 3.1. Los
numeros indican los valores calculados de la matriz y las flechas indican desde
donde fue actualizado dicho valor.
Cada vez que los caracteres de las palabras coinciden se observa una flecha dia-
gonal (‘↖’), pues el valor fue actualizado desde la fila y columna anteriores,
mientras que cuando los caracteres no coinciden aparece una flecha vertical (‘↑’) u
horizontal (‘←’) de acuerdo al valor contenido en M [i, j-1] o M [i-1, j]. Notemos
que M [i, j] = 0 en caso de que i=0 o bien j=0 y tambien de que la LCS entre
cualquier contorno y un contorno vacıo (φ) es siempre cero. El valor de la LCS
queda guardado en M[n,m] y en este caso S(v, w) = 8.
48
Algoritmo 3 Longest-Common-SubsequenceRequiere: v, n, w,mDevuelve: M[n,m]
for i← -1 to m-1 doM [i, -1]← 0
end for
for j ← -1 to n-1 doM [-1, j]← 0
end for
for i← 0 to m-1 do
for j ← 0 to n-1 do
if vi=wj thenM [i, j]←M [i-1, j-1] + 1
elseM [i, j]← max(M [i, j-1],M [i-1, j])
end ifend for
end for
3.2 Distancia de Levenshtein
De acuerdo con [16], la distancia de Levenshtein (LD) se define como la medida
de similaridad entre dos cadenas v y w. La LD se aplico en este trabajo para
medir la distancia basada en la semejanza entre dos contornos v y w, que tambien
se conoce como la distancia de edicion. La distancia de edicion no es sino el
numero mınimo de operaciones que necesitamos para transformar una cadena en
otra bajo la suposicion de que solo se permiten inserciones y eliminaciones de los
sımbolos de cada una de ellas.
Si definimos S(v, w) como la longitud de la LCS entre dos contornos v y w,
entonces la LD es una funcion δ, con estructura δ : Σ∗ × Σ∗ → [0, |v| + |w|],
siendo Σ∗ el conjunto de todos los contornos, que esta definida como:
49
Figura 3.1: Matriz binaria S donde calculamos que s(v, w)=8 en los contornos v y w. Estoscontornos tienen la subsecuencia EESSWWNN de longitud 8 en comun.
δ(v, w) = |v| + |w| - 2S(v, w) (3.2)
Los valores devueltos por δ, en un rango de 0 ≤ δ(v, w) ≤ |v|+|w|, y se definen
como:
δ(v, w)=
0 Si coinciden todos los sımbolos entre v y w (v=w)
|v|+|w| Si no existe ninguna coincidencia entre v y w (v 6= w)
(3.3)
Siguiendo con el ejemplo anterior y aplicando el algoritmo 3 a v y w, vemos que
S(v, w) = 8 y usando la ecuacion 3.2, tenemos que:
δ(v, w) = 12 + 8 - 2(8) = 4
50
Donde δ = 4 es el mınimo numero de inserciones y eliminaciones necesarias para
transformar v en w, es decir, que v puede transformarse en w realizando cuatro
operaciones que en este caso es eliminando los sımbolos E,S,W y N como puede
verse en esta alineacion:
v → E E E S S S W W W W W W
w → − E E − S S − W W − N N
En adelante, la LD se referira a la idea intuitiva de similaridad. Dos contornos
son mas similares a medida que se requieren menos operaciones de insercion y
eliminacion para transformar un contorno en otro.
Propiedades de la distancia de Levenshtein
Las inserciones o eliminaciones de los sımbolos de los contornos ocurren o pueden
ocurrir en cualquiera de sus posiciones. Entonces, si tenemos dos contornos p y q,
simbolizaremos como pi ⇒ qj a la insercion del i-esimo sımbolo de p en la j-esima
posicion de q, y como {pi / qj} ⇐ NULL a la eliminacion de un caracter de p
o q. Para cualquier contorno R110 (o cualquier otra secuencia de sımbolos que
pertenezcan a algun alfabeto), la distancia de Levenshtein cumple las propiedades
de reflexibilidad, transitividad y desigualdad del triangulo. De modo que sean p,
q y r, contornos R110, tenemos que:
1. δ(p, p) = 0: Debido a que los contornos son iguales, los sımbolos de cada
uno coinciden en todas las posiciones y como la longitud de los contornos
es la misma, entonces δ(p, p) = 2n-2S(p, p), y debido a que p = p, la suma
de las longitudes de p menos el doble de la LCS (ecuacion 3.2), da como
resultado que
51
δ(p, p) = 2n-2n=0
2. δ(p, q) = δ(q, p): Las operaciones de insercion y eliminacion de caracteres
ocurren cuando los sımbolos tanto de p como de q son diferentes, es decir
que para alguna posicion pi y qj donde el sımbolo no coincida, tenemos
tanto una insercion para pi, como una eliminacion para qj. Luego entonces,
la operacion pi ⇒ qj, ocurre en el mismo sitio en que qj ⇐ NULL para
todo sımbolo de p y q.
3. δ(p, r) ≤ δ(p, q) + δ(q, r): Para demostrar este punto, consideremos el
caso en el que los tres cubrimientos sean completamente diferentes, lo que
implica que el valor de la LCS para cada pareja de contornos es igual a 0,
por lo tanto la distancia δ en cada caso es igual al maximo valor que esta
dado por la suma de las longitudes de los contornos, es decir:
δ(pi, rk)= i+k, de igual manera
δ(pi, qj)= i+j, y
δ(qj, rk)= j+k
Siendo i = |p|, j = |q|, y k = |r|; como los contornos son diferentes, se tiene
que:
δ(pi, qj) + δ(qj, rk) = (i+j) + (j+k) = i + 2j + k
De manera que:
δ(pi, rk) ≤ δ(pi, qj) + δ(qj, rk)
i + k ≤ i + 2j + k
52
Para cualquier valor de i, j, k ≥ 0. Por otro lado, si consideramos que los
tres contornos son iguales, entonces la LD es igual a 0 para cada pareja de
contornos de acuerdo a la demostracion 1 de esta subseccion, por lo que
tambien se cumple que:
δ(p, r) ≤ δ(p, q) + δ(q, r)
3.3 Definicion de los tipos de comparacion
A pesar de saber con presicion la longitud de la LCS entre dos contornos, este
dato no dice mucho acerca de lo parecido que son en terminos de se parecen mucho
o se parecen poco; de modo que podemos normalizar la nocion de similaridad y
definir dos tipos de comparacion: el de diferencia y el de semejanza, de tal manera
que podamos determinar las diferencias o semejanzas entre los contornos. Con
estos dos tipos de comparacion, se definen dos funciones mas, cuyos valores se
aplicaran a una tercera funcion que nos ayude a decidir el grado de lo interesante
en los contornos que sean analizados.
3.3.1 Primer tipo de comparacion: el de diferencias
Este tipo de comparacion se basa en la normalizacion de la LD, es decir, del
numero de operaciones que hay que hacer para transformar un contorno en otro.
El tipo de diferencia es una funcion δ∗ con estructura δ∗ : Σ∗ × Σ∗ → [0, 1], se
define como
δ∗(a, b) =δ(a, b)
|a| + |b|(3.4)
Donde Σ∗ es el conjunto de todos los contornos R110 y a y b son dos contornos que
son comparados por la funcion δ (ecuacion 3.2); el valor devuelto 0 ≤ δ∗(a, b) ≤ 1
53
se define como:
δ∗(a, b)=
1 Cuando a y b son completamente diferentes
0 Cuando a y b son completamente iguales
En este tipo, cuando el valor devuelto por δ∗(a, b) = 0, se interpreta como que
existen 0 diferencias o que a = b; por otro lado, cuando a 6= b, entonces S(a, b)=0
(la longitud de la LCS), por lo que δ(a, b)=|a|+|b|-0, y de acuerdo a la ecuacion 3.4,
tenemos que δ∗= |a|+|b||a|+|b|=1 y siendo este el valor maximo, tenemos que a y b son
completamente diferentes.
Contornos µ-diferentes. El parametro µ ∈ Z es el umbral mınimo permitido
para evaluar si dos contornos son diferentes entre si. Si la diferencia es menor o
igual que el umbral µ, podemos considerar que los contornos analizados no son
muy diferentes entre si. De modo que:
a =µ b si δ∗(a, b) ≤ µ, con 0 ≤ µ ≤ 1 (3.5)
El sımbolo =µ quiere decir “suficientemente igual a” bajo el umbral µ. Si la
diferencia entre dos contornos a y b supera el umbral, entonces decimos que a es
diferente a b sobre el umbral µ y se denota como a 6=µ b.
3.3.2 Segundo tipo de comparacion: el de semejanzas
Este tipo de semejanzas se define en terminos de los sımbolos que tengan en comun
dos contornos a y b, es decir, de la longitud de la LCS. El nivel de semejanza es
una funcion S∗ con estructura S∗ : Σ∗ × Σ∗ → [0, 1] y se define como:
S∗(a, b) = S(a, b)
max(|a|, |b|)(3.6)
54
Donde la estructura esta definida como la anterior, y el valor devuelto por la
funcion 0 ≤ S∗(a, b) ≤ 1 se define como:
S∗(a, b)=
1 Cuando a y b son completamente iguales
0 Cuando a y b son completamente diferentes
Contornos µ-semejantes. Al igual que el de diferencias, aquı tambien se define
un umbral (en este caso de semejanza) para evaluar si dos contornos son muy
semejantes o poco semejantes. Si la diferencia entre dos contornos a y b es mayor
o igual que el umbral, decimos que a es suficientemente similar a b sobre el umbral
µ de modo que:
a ≈µ b si S∗(a, b) ≥ µ, con 0 ≤ µ ≤ 1 (3.7)
3.4 Funcion de lo novedoso
Dentro del analisis de los contornos R110, decimos que un contorno es nuevo o
novedoso si la BD no ha registrado el mismo contorno anteriormente, ası que
vamos a definir una funcion que mide el nivel de lo novedoso de los contornos
analizados. Para establecer esta funcion, utilizaremos el primer tipo de com-
paracion, el de diferencias, con el que evaluaremos las diferencias que existen en-
tre los contornos. La funcion de lo novedoso η, con estructura η : Σ∗×F → [0, 1],
se describe como:
η(c,BD) = 1 -# de diferencias de c en BD
Total de contornos en BD
Donde el # de diferencias debe ser el mınimo para cada comparacion de c y
los contornos en BD, de tal modo que, si c es diferente de todos los contornos,
55
entonces c es completamente novedoso. Esta funcion se define como:
η(c,BD) = 1 -
∑di∈BD
δ∗µ≈0(c, di)
|BD|(3.8)
Donde, el tipo de diferencias δ∗ –ecuacion 3.4–, evalua un contorno c, contra
un contorno di ∈ BD, y realiza una sumatoria de los valores devueltos por δ∗,
que sean menores o iguales al valor del umbral µ, el cual debe ser cercano a 0
(µ ≈ 0); esto es porque si c es muy parecido a los contornos en BD (o igual),
entonces δ∗(c, di ∈ BD)=0 en cada comparacion; de modo que la funcion devuelve
un valor 0 ≤ η(c, BD) ≤ 1 de tal forma que:
η(c, BD)=
1 Cuando c es completamente novedoso
0 Cuando c no es novedoso
Si δ∗(c,BD)=1, entonces podemos asegurar que el contorno de entrada c, al final
del analisis, es completamente novedoso (el valor del umbral puede modificarse
para hacer el analisis menos estricto).
3.5 Funcion de la utilidad
La funcion de utilidad de los contornos, se evalua de acuerdo al parecido que tenga
un contorno de entrada contra los que se encuentren en la BD, es decir, que un
contorno v ∈ Σ∗ es util, si es muy parecido a un gran numero de contornos en BD.
La medida de la utilidad es una funcion U con estructura U : Σ∗ × F → [0, 1] y,
tomando como base el segundo tipo de comparacion, el de semejanza, se describe
como:
56
U(c,BD) =# de ocurrencias de c en BD
Un subconjunto de BD
Donde, a diferencia de la funcion de lo novedoso, el numero de ocurrencias ocurre
con un valor de µ ≈ 1. La funcion U se define como:
U(c,BD) =
∑di∈BD
S∗µ≈1(c, di)
|BD|(3.9)
Al igual que la funcion anterior, el tipo de semejanza S∗ –ecuacion 3.6–, evalua
un contorno c, contra un contorno di ∈ BD, y realiza una sumatoria de los valores
devueltos por S∗ que cumplan que µ ≥ S∗ ≤ 1; esto es porque buscamos que
c sea semejante a todos los contornos en BD (o al menos muy parecido). Esta
funcion devuelve un valor 0 ≤ U(c, BD) ≤ 1 de tal modo que:
U(c,BD) =
1 Si es completamente util
0 Si es completamente inutil
Donde es claro que el valor de utilidad aumenta a medida que el contorno c ocurre
muchas veces dentro de la BD
3.6 Funcion de validez
Aunque la mayorıa de los contornos con los que trabajamos, se obtienen direc-
tamente de las evoluciones del aclr110, tambien esta permitido obtener contornos
desde otros modulos, archivos e incluso que sean introducidos por el usuario. Sin
embargo, en estos contornos no es inmediatamente obvio saber si son contornos
R110 validos o a cuantos triangulos rodeo al momento de obtenerse. Por este
57
motivo desarrollamos una funcion que evalua la validez de los contornos que se
obtengan de manera externa.
Decimos que un contorno es valido, si despues de eliminar secuencias correspon-
dientes a triangulos R110 (ademas de otras operaciones), nos queda una cadena
vacıa, lo que quiere decir, que el contorno puede ser cubierto completamente con
uno o mas triangulos R110. Entonces, la validez es una funcion ϕ : Σ∗ → {0, 1}
que evalua si un contorno es valido o no, y devuelve uno de entre dos valores de
tal modo que:
ϕ(Σ∗)=
1 Si el contorno es valido
0 e.o.c
Donde Σ∗ es el contorno de entrada. Por convencion, los contornos deben comen-
zar en la direccion E, sin embargo, para esta funcion no es un requisito muy
necesario, de hecho el primer paso es encontrar la secuencia SWkN con k > 0, y se
toma la subsecuencia a partir de la primer W y la secuencia previa a esta direccion
se coloca al final del ultimo sımbolo del contorno.
Un procedimiento que ocuparemos constantemente, es el que elimina los triangulos
de tamano 0, debido a que son las mınimas cadenas que tienen significado y que
ademas nos permite despejar las fronteras superior e izquierda de los triangulos de
tamano ≥ 0. Los triangulos t0 que ocurren en las fronteras superior e izquierda,
son detectados por las secuencias NES y WNE, y seran substituidas directamente
por la direccion E y N respectivamente.
Cuando se han eliminado los t0, comienza un ciclo que va quitando los triangulos
sueltos que haya en la evolucion. Un triangulo suelto puede ser removido del
contorno realizando algunas substituciones y eliminaciones de sımbolos, las cuales
iremos explicando a lo largo de esta seccion.
58
Definicion 6. (Triangulo suelto) Un triangulo se considera “suelto” si se
puede determinar con precision la cadena de la forma N(E)kS, con k > 0.
Figura 3.2: Procedimiento para remover triangulos de un contorno.
El procedimiento quitaTriangulo, quita el triangulo suelto mas arriba y mas a la
59
izquierda de la cadena que representa el contorno. A manera de ejemplo, vamos a
analizar el contorno v = EEEEESSSWWSSSSSSSSWWSWWNNWWWNNNNEENNNNEENN, que
graficamente corresponde a la parte (A) de la figura 3.2. La parte D, muestra
como queda el mosaico original cuando se le quita un triangulo suelto y la manera
de quitarlo es la siguiente:
1. Se localiza la subsecuencia SWkN y se toma la primer W de esta subsecuencia
como el comienzo del contorno (un cırculo pequeno en la imagen (A)), y la
subsecuencia previa se envıa al final del contorno. En este ejemplo, quedarıa
ası: WWNNWWWNNNNEENNNNEENNEEEEESSSWWSSSSSSSSWWS
2. Se llama al procedimiento que elimina los triangulos t0.
3. De izquierda a derecha, se localiza la subsecuencia NEkS. El numero k-1
de E’s determina el tamano del triangulo, ası que una vez que se locali-
za la subsecuencia, se alinea respecto a la secuencia de E‘s de v, el con-
torno correspondiente a un triangulo de tamano k-1 comenzando por los
sımbolos N. En este ejemplo la primera ocurrencia NEEEEES, indica que
debemos alinear un contorno correspondiente a un triangulo t4, es decir
t4=NNNNNEEEEESSWSWSWSWW; de este modo tenemos:
4. Tomando como origen la primera E, se eliminan tanto hacia a la izquierda
como a la derecha los sımbolos que sean iguales en ambos contornos, sin
embargo, al aparecer dos sımbolos diferentes, se suspende la eliminacion en
esa direccion como se ve en la figura 3.3.
60
Figura 3.3: Se muestran los pasos que se siguen al encontrar la secuencia NEEEEES paraeliminar el triangulo suelto t4.
5. Los sımbolos restantes del contorno del t4 pasaran a formar parte del con-
torno original, pero antes se realiza lo siguiente:
• La subsecuencia de sımbolos de la derecha que no fueron eliminados, se
invierte. En este caso la subsecuencia restante fue WSWSWSWW e invertida
queda WWSWSWSW. Se concatena con los sımbolos de la izquierda que
no fueron eliminados, que en este caso fueron NNN, por lo que queda
NNNWWSWSWSW.
• Se invierte la direccion de los sımbolos de esta nueva secuencia, es
decir:
N→ S
W→ E
S→ N
E→ W
Por lo que la secuencia NNNWWSWSWSW se cambia a SSSEENENENE, y se
agrega al contorno v en el espacio donde se realizaron las eliminaciones
de sımbolos.
61
• Se resume el contorno. Se anulan las subsecuencias de la forma EW,
WE, NS y SN (en este caso no hay pero es parte del procedimiento),
hasta que no haya mas direcciones encontradas; por ejemplo, si tu-
viesemos una secuencia . . . EENEEWWSSSE . . ., se eliminarıa la secuencia
EEWW, quedando ahora la secuencia . . . EENSSSE . . ., ası que tambien
debe anularse la secuencia NS con lo que la secuencia se reduce en-
tonces a . . . EESSE.
6. Se repite el procedimiento desde el paso 2.
El proceso continua hasta que se logra obtener la cadena vacıa lo que significa
que el contorno es valido; cuando despues de un ciclo no se logro quitar ningun
otro triangulo y la cadena no es vacıa, entonces el contorno es incorrecto; cuando
la cadena no es vacıa y se ha logrado eliminar un triangulo, el proceso empieza
nuevamente con el contorno simplificado.
3.7 Funcion de lo interesante
Al decidir el grado de lo interesante que se ha encontrado en los contorno analizados,
lo haremos en terminos de que, si un contorno R110 es novedoso, es valido y es
util, entonces se considera interesante. Ası que se busca que el valor devuelto
por las tres funciones (que ya hemos definido) sea el maximo en cada caso, de
tal manera que el resultado supere un umbral previamente definido. Si se supera
este umbral, los contornos analizados pueden considerarse como interesantes.
La funcion de lo interesante esta en funcion de los valores devueltos por las
funciones anteriores, principalmente el valor de la funcion de validez (ϕ). Si el
contorno analizado por ϕ no es valido, se detienen los demas procedimientos,
porque no se puede continuar analizando un contorno que no sea un contorno
62
R110, pues no hay una razon logica para hacerlo. Ası que el resultado de la
funcion de validez, determina si el proceso continua o se detiene.
De esta manera, la funcion de lo interesante I, con estructura I : Σ∗×F ;→ [0, 1)
esta definida como:
I(c,BD) = ϕ(c) ∗(η(c,BD) + U(c,BD)
)(3.10)
Donde c es un contorno de entrada, y las funciones ϕ, η y U ya definidas, reciben
como parametros a c y actuan sobre una BD. El valor mınimo devuelto por I,
ocurre cuando ϕ(c)=0, que es cuando c no es un contorno R110 valido; sin embargo,
su valor maximo nunca llega a ser mucho mayor que 1, pues es claro que, si c es
un contorno completamente novedoso (η(c,BD)=1), entonces c nunca ocurre en
la BD (U(c,BD)=0); y si por el contrario, c no es novedoso (η(c,BD)=0), entonces
el valor de I podrıa a lo mas ser 1.
Por lo que, un contorno se considera interesante en la medida de que, ademas
de ser valido, sea lo suficientemente novedoso y suficientemente util. Esto puede
verse en la grafica de la figura 3.4. El cruce de las dos lıneas, representa graficamente
el valor maximo que puede obtenerse de la suma de las funciones η y U en una
hipotetica BD de 100 elementos.
Sin embargo, este no es el unico valor que debe tomarse en cuenta para la toma
de decisiones, porque un contorno puede considerarse interesante si es completa-
mente novedoso, aun cuando no sea muy util; y si no es novedoso, pero es muy
util, tambien se considera interesante. Ası que los valores que devuelve la funcion,
en el rango de 0 ≤ I(c,BD) ≥ 1, se definen como:
63
Figura 3.4: Grafica de las funciones η y U , en la que el valor maximo devuelto por la funcionI, se encuentra en el cruce de las dos lıneas.
I(c,BD)=
0 No es interesante
I(c,BD) ≥ 1 Sı es interesante
Caso de estudio
A manera de ejemplo de como actuan las funciones que hemos definido, mos-
traremos un caso de estudio en el que aplicamos todos los aspectos que hemos
mencionado hasta este punto.
Como primer paso, seleccionamos un mosaico R110 de 250 celulas y 250 gen-
eraciones, obtenido a partir de una configuracion inicial aleatoria, y le hemos
aplicado los procedimientos explicados en el capıtulo 2 para obtener todos los
contornos posibles. En la figura 3.5 podemos ver el mosaico que analizaremos.
De este mosaico, se obtienen cerca de 9500 contornos diferentes, que son al-
macenados en una BD. Cada uno de estos contornos sera comparado contra un
64
Figura 3.5: Caso de estudio. Mosaico R110 que sera analizado por los procedimientos hastaahora explicados.
contorno de entrada, por las funciones que hemos definido. Entonces, dado el con-
torno v = {EEESEEEESEENENEEEESSEENEEEENEESSEENENEESEENEEEESEENEEEEEEEEEEE
EESSEENESEENENEEEEEEEEEEEEEEESEEEENEEEEEEEEEESSSEENENEEEENEEEEEEESEENEEE
SSEENENEEESSEENENEESEENEEESEEEEENEEEESEEEENEEESEENEESEEESEENENEEEESEEEEE
NEEESEESSEENENEEEEEENEEEEESSEENEEENEEEEEESSSEENENEEEEEEEEEENEEESEENEEEES
EENEEESEENEEEEEEEESEENEESEEESSSEENENENEEEEEENEEEEESEEEEEEEESSWSSSSWWWWSS
SSSSSEENESSSEESSWSWWSSSSSSSSSSSSSSSWSSSSSSEESSSSSEESSSSWSWSSSSEESSWSWSSS
SSSSSSSSSSSSWSSSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSS
SSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESS
SWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSS
SEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSSSSEESSSWWSWWWWSWWN
WSWSWWNWSWSWWNNNWWWWSWWNWSWSWWNWSWSWWNNNWWWWSWWNWSWSWWNWSWSWWNNNWWWWSWWN
WSWSWWNWSWSWWNNNWWWWSWWNWSWSWSWSWWNNNNWWWSWWNWWWWSWSWWNWWNWWWWSWWNWWSWSW
SWWNNNWSWSWSWWNNNWWSWWNWSWSWWNWSWSWWNNNWWWWSWWNWSWSWWNWSWSWWNNNWWWWSWWNW
SWSWWNWSWSWWNNNWWWWSWWNWSWSWSWSWSWWNNNNNWWSWWSWSWSWWNNNWWWWSWWNWSWSWWNWS
65
WSWWNNNWWWWSWWNWSWSWWNWSWSWWNNNWWWWSWWNWSWSWWNWSWSWWNNNWWWWSWWNWSWSWWNWS
WSWWNNNWWWWSWWNWSWSWWNNWWSWWNWWWWSWWWSWWNNWSWSWSWWNNWWNNNNENENNWWNNNNENE
NNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNN
NNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENEN
NWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNNNENENNWWNNN
NENENNWWNNNNENENNWWNNNNENENNWWNNENENNWWNNENENNWWNNENENNWWNNENENNWWWNNNNE
NENNWWNNNNNNENENENENNWWWWNNENENNWWNNENENNWWNNENENNWWNNENENNWWNNNNENENNWW
NNENENNWNENENNWWWNNN}, cuya longitud es de 1522 sımbolos, se envıa como para-
metro a la funcion I, la cual, como primer paso, verifica su validez con ayuda de
la funcion ϕ; este contorno es valido, ası que ϕ(v)=1.
Posteriormente, se ejecuta la funcion de lo novedoso, que en este caso η(v)=0.684,
que nos indica que v, es novedoso al menos en un 50%; la funcion de utilidad
nos da un valor de utilidad de 0.438. Entonces, la funcion de lo interesante I, de
acuerdo a la ecuacion 3.10, queda ası:
I(v,BD) = ϕ(v) ∗(η(v,BD) + U(v,BD)
)= (1) ∗ (0.544 + 0.418)
= 0.962
Vemos que el valor de I es muy cercano a 1, a pesar de que v no es totalmente
novedoso y su valor de utilidad tampoco es muy alto; sin embargo se conside-
ra interesante porque el resultado es muy cercano al valor maximo que puede
obtenerse de las funciones η y U de acuerdo a la grafica de la figura 3.4.
66
3.8 Conclusiones
La LD es un algoritmo eficiente para la comparacion de cadenas de texto y una
herramienta fundamental para definir funciones muy importantes dentro de este
trabajo. Es posible modificar la funcion de validez para recuperar los triangulos
que se encuentran en un contorno dado, esto se lograrıa almacenando las coor-
denadas y el tamano de cada triangulo que es removido, en una tabla, y poste-
riormente reconstruir el mosaico. Las funciones de lo novedoso, la de utilidad y
la de validez son las mas importantes del sistema, nos dan la base para definir
una funcion que toma los valores devueltos por esta y nos proporciona un re-
sultado que puede interpretarse como interesante, es decir, el valor devuelto por
la funcion de lo interesante no es determinante, nos ayuda a decidir el que tan
interesante es un contorno R110 que haya sido analizado.
67
CAPITULO 4
Descripcion del sistema
Resumen
En este capıtulo realizamos una descripcion del sistema, de los modulos en los que
esta dividido, su funcionamiento y los resultados que arroja despues de analizar
las datos. En la descripcion del sistema hablamos del lenguaje en el que se desar-
rollo y la plataforma en la que este se ejecuta. En el modulo del funcionamiento
explicamos la estructura de la interfaz, la manera en como lo ve el usuario final;
mostramos algunas pantallas, explicamos un poco del funcionamiento de la BD,
y tambien el manejo de los archivos de entrada y los archivos de salida.
4.1 Descripcion general del sistema
El Sistema Automatizado de Analisis de Evoluciones y contornos R110, es un sis-
tema que fue programado en el lenguaje C++Builder 6. Se escogio este lenguaje
principalmente para aprovechar su potencia en la creacion y manejo de estruc-
turas dinamicas de datos muy grandes y en la velocidad de analisis de cadenas
de texto que este ofrece.
De manera general, el sistema se divide en tres modulos que son independientes
entre sı, hablando de que podemos acceder a cualquiera de los tres sin depender
de los otros dos, pero sin embargo, comparten informacion importante tal como
68
archivos de entrada o de salida, o ambos. Los modulos son:
1. Generador de mosaicos R110
2. Biblioteca de funciones
3. Desempeno de la BD
Cada uno de los modulos esta conformado por submodulos que cumplen diferentes
funciones cada uno.
4.2 Manejo de la base de datos
Para el almacenamiento y manejo de los datos, se utilizo el sistema de adminis-
tracion de bases de datos MySQL. Se escogio este sistema para manejar grandes
cantidades de informacion (volumenes de datos), es facil de usar, es rapido, con-
fiable y gratuito, ademas de que cuenta con algunos tipos de datos que permiten
almacenar cadenas de texto muy grandes, lo cual es una caracterıstica importante
para el desarrollo de este trabajo.
La estructura de la tabla que contiene a los contornos R110, esta compuesta por
un campo para el ındice o clave de identificacion y otro campo para el contenido
del contorno como puede verse en la tabla 4.1. Este segundo campo debe ser
un tipo de dato que permita el almacenamiento, manejo y consulta de datos
de gran longitud; afortunadamente MySQLcuenta con varios tipos que soportan
estos requerimientos y uno de ellos es el tipo de dato text.
El campo CveContorno de la tabla contornos es de tipo int unsigned, lo cual
nos da un rango de 0 a 4,294,967,295, mas que suficiente para almacenar una
considerable cantidad de contornos. El otro campo es contorno y es de tipo
69
Nombre del campo Tipo Nombre del campo Tipo
CveContorno int unsigned contorno text
Tabla 4.1: Se muestra la estructura de la tabla contornos, que es la que almacenara la
informacion de los mosaicos R110.
text. Este tipo de dato propio de MySQL, es exclusivo para el manejo de cadenas
y a diferencia de los tipos comunes char y varchar, que son muy limitadas en
cuanto a su capacidad (255 caracteres), este permite un rango de hasta 65,535
caracteres.
El submodulo Generador de contornos, que pertenece al modulo Biblioteca de
funciones, se encarga de almacenar la informacion obtenida de los mosaicos R110
en la BD. Desde luego que se procura que la BD tenga la mayor cantidad de reg-
istros posibles con el objetivo de contar con suficiente material para el desempeno
de las funciones que evaluan la semejanza entre los contornos.
4.3 Generador de mosaicos R110
Este modulo representa la interfaz principal que es manejada por el usuario. En
el, se generan los mosaicos R110 a partir de una configuracion inicial, es decir, se
definen los valores de la primer lınea de evolucion para t=0, se establece el tamano
de la evolucion, su nivel de densidad y la escala de visualizacion; esto se logra
manipulando las diferentes opciones de los submodulos de control los cuales son:
1. Tamano del espacio. Esta opcion permite seleccionar el tamano del DET
de acuerdo a los requerimientos del usuario. El tamano se determina modi-
ficando el numero de celulas con las que se desea que trabaje el automata y
va desde un mınimo que es de 50×50, hasta el maximo que es de 500×500.
70
Los lımites del espacio se deben a las limitantes propias de la arquitectura
secuencial sobre la que se ejecuta la aplicacion, tal y como se menciono en
la seccion 2.2 en la pagina 20.
2. Configuracion inicial. Dividido a su vez en dos:
- Configuracion aleatoria. En esta opcion, el usuario selecciona el tamano
del DET, y ademas de eso, puede cambiar a su criterio, el nivel de den-
sidad (los valores 0 y 1) que tendra la configuracion. El sistema genera
una variable aleatoria, que toma como umbral los valores de este por-
centaje para devolver un 1 o un 0.
- Configuracion arbitraria. En esta configuracion la aleatoriedad queda
descartada, ası que el usuario debe colocar a su criterio valores 1 sobre
la primer lınea de evolucion. Esto es debido a que, por default los
valores de esta lınea son 0.
3. Nivel de densidad. Por default, los umbrales de seleccion de los valores 0
y 1 esta en 50% para cada uno. Es posible modificar los valores de manera
que si el porcentaje de uno aumenta, el del otro disminuye con el objetivo
de modificar la cantidad de 1’s y 0’s que apareceran en el mosaico.
4. Escala. Este submodulo permite una mejor apreciacion de los mosaicos
reduciendo o aumentando la escala (el tamano de las celulas) de tal modo
que pueda observarse con claridad, incluso las evoluciones que sean del
tamano maximo permitido.
5. Generador de Mosaicos. Cuando la configuracion inicial ya esta deter-
minada, este modulo genera las evoluciones del automata trabajando de
manera interna con la estructura de datos, para que el submodulo de salida
genere una representacion grafica de la misma.
71
6. Salida. Es la pantalla en la cual es posible visualizar el resultado de la
evolucion, modificar la escala para apreciar detalles e incluso guardar la
imagen del mosaico en el formato de imagen JPEG 1.
En la figura 4.1 se muestra la pantalla principal del sistema. Pueden apre-
ciarse los modulos antes mencionados.
4.4 Biblioteca de funciones
Este modulo es la parte central y la mas importante del sistema. En el se generan
los mosaicos, se obtienen los contornos, se analizan, se permite la entrada y salida
de archivos, se visualizan los resultados, se muestran tablas con informacion, entre
otras cosas. Ademas los contornos obtenidos van enriqueciendo la BD para que
haya suficientes datos con los cuales trabajen las funciones de lo novedoso y
utilidad. Este modulo se divide en:
1. Generador de contornos. Este es uno de los pocos submodulos que
dependen de otro. El submodulo Generacion de contornos se activa solo
despues de que se ha activado el Generado de mosaicos. Su funcion es
analizar el mosaico generado y como su nombre lo indica, genera los con-
tornos que encuentre y estos pueden ser utilizados o almacenados en la BD.
Ademas de eso, genera una tabla con datos de cada uno de los triangulos
que encontro en el mosaico. Los contornos y los datos de los triangulos
pueden visualizarse en el submodulo:
- Visualizacion de tablas de informacion. Aquı se muestran en una tabla
todos los contornos que se hayan obtenido de la evolucion; ademas, se
1Siglas de un standar de compresion de imagenes Join Photographic Expert Group
72
Figura 4.1: Pantalla principal del sistema.
muestra la posicion (en coordenadas cartesianas) y el tamano de cada
uno de los triangulos que se encontraron en el mosaico. Se puede
guardar en un archivo de texto, los contornos obtenidos y estos mis-
mos archivos sirven como datos de entrada para el submodulo de
analisis. La informacion de la tabla es fundamental para que el ge-
73
nerador obtenga todos los contornos posibles de la imagen, tal como
se explico en la seccion 2.4.1 en la pagina 38.
2. Analisis de contornos. La parte medular del sistema. Este submodulo
trabaja con la BD, evalua la validez, lo novedoso de archivos de entrada
y nos muestra los valores de salida. Para la funcion de lo novedoso hay
dos casos, uno que compara dos contornos y el caso general, que compara
un dato de entrada contra todo lo contenido en la BD. Este submodulo se
divide en:
- Novedoso (2 contornos). Aquı se toman como parametros, dos archivos
de texto a y b que contengan un solo contorno R110 de cualquier
tamano, los analiza y muestra el valor de lo novedoso que hay entre
ellos. Con contornos pequenos es posible ver la tabla bidimensional
que se genera, sin embargo con contornos muy grandes ya no es posi-
ble (ni tampoco recomendable), debido a la cantidad de recursos de
computo que requiere el sistema para mostrar visualmente la tabla, lo
cual se traduce en un mayor tiempo de procesamiento
- Validez. El archivo de entrada contiene un solo contorno, el cual es
evaluado y se muestra un mensaje en pantalla indicando si el contorno
es valido o no; si el contorno no es valido, no se puede continuar con
el analisis.
- Novedoso (caso general). Aquı se establece la conexion con la BD. El
proceso de comparacion puede ser ya sea con un contorno de entrada,
uno que genere el sistema (en el modulo Generador de contornos), o
bien con uno que pertenezca a la BD; se le llamara simplemente dato de
entrada. La interfaz se muestra en la figura 4.2; pueden verse las tres
opciones de seleccion del dato; cuando este se ha definido, comienza el
74
Figura 4.2: Pantalla del procesamiento de los contornos en la base de datos
proceso interno de comparacion. Este proceso puede durar desde uno
a varios segundos, dependiendo de la cantidad de informacion que se
halle almacenada en la BD. De igual manera el resultado se muestra
en pantalla con un mensaje que indica si el contorno es completamente
nuevo o no.
- Utilidad. Esta parte esta ligado al anterior. Evalua el numero de
ocurrencias del dato de entrada en la base de datos y muestra el valor
devuelto por la funcion con un mensaje que indica el nivel de utilidad
del contorno.
- Interesante. Aquı se muestra el resultado final de los analisis realiza-
dos. Toma los valores devueltos por las funciones anteriores y muestra
un valor al usuario.
75
Si los valores devueltos por las funciones no son satisfactorios o se quiere
realizar una nueva configuracion, hay un submodulo que libera la memo-
ria utilizada por las variables y estructuras utilizadas en la ejecucion del
sistema.
Para este sistema, se ha desarrollado una interfaz amigable, que exige solamente
de conocimientos basicos en el manejo de hardware de computacion. Todos los
modulos y submodulos mencionados, realmente son botones de manejo de eventos,
ası que cuando se menciona que un modulo realiza un evento, quiere decir que el
usuario debe dar un click del raton en el boton para que el evento se ejecute.
4.5 Conclusiones
El lenguaje de programacion en el cual se desarrollo el sistema tiene muchas
ventajas: es un entorno visual, permite el manejo de estructuras de tamano
variable y es de facil manejo. Sin embargo, por ser una arquitectura secuencial,
al trabajar con arreglos muy grandes el sistema se ve afectado por la gran cantidad
de calculos y operaciones que se ejecutan antes de mostrar el resultado, lo cual se
traduce en tiempo de ejecucion (algunos casos en el orden de los segundos). Es
posible que haya que optimizar los algoritmos de tal modo que el sistema sea mas
eficiente, aunque una buena opcion serıa evaluar algun otro lenguaje que aporte
mas ventajas y un mejor desempeno.
76
CAPITULO 5
Conclusion final y trabajos futuros
Las principales conclusiones de esta tesis son:
• Los resultados que muestra el sistema son satisfactorios. Esta afirmacion
la basamos en el hecho de que, teniendo a la mano una serie de evoluciones,
emitimos a simple vista un veredicto en los terminos de se parecen mucho,
se parecen poco o definitivamente no se parecen, contra los que devolvio el
sistema al trabajar con los contornos correspondientes a dichas evoluciones.
Por ejemplo, para los mosaicos de la figura 5.1, podemos observar que son se-
mejantes ası que a simple vista decimos que ambos se parecen mucho. Pues
bien, sus respectivos contornos sonA=EESEESSSEENENENENEEEESSSSSSSSSWSWS
WWWWWWWWSWSWWNNNNENENNWWNNNNNN yB=EESEESSEEENNEENNEEEESSWSWSSEESSSS
WSWSWWWWWWWNNNWWNWWNNNNNN.
Figura 5.1: Se observan dos mosaicos que a primera vista son muy parecidos.
77
Siendo ambos datos de entrada, el sistema devuelve que:
- Nivel de diferencias = 0.1803
- Nivel de semejanzas = 0.7812
Lo cual coincide con nuestra apreciacion, pues el nivel de diferencias nos
dice que entre los contornos hay una diferencia de 0.1803, es decir que no
son tan diferentes, mientras que el nivel de semejanza =0.7812 quiere decir
que ambos contornos son muy semejantes. Pruebas como esta se hicieron
muchas veces y en todas, los resultados fueron bastante aceptables. Lo que
significa que el sistema cumple con la funcion para la que esta disenado.
De este modo, podemos confiar en que al trabajar plenamente con la BD,
el sistema devuelva resultados satisfactorios que nos apoyen en la toma de
desiciones sobre los elementos interesantes de los contornos.
• Los mosaicos R110 pueden ser mejor manipulados en forma de contornos.
Debido a que los algoritmos que utilizamos para el manejo de cadenas
son bastante eficientes, resulta muy apropiado trabajar con los contornos;
ademas de que el sistema procesa mas que si lo hiciera con imagenes
• Las funciones de comparacion pueden aplicarse para casos generales. En
efecto, los niveles de comparacion, el de diferencias y el de semejanzas
pueden aplicarse para la comparacion de cadenas de todo tipo (incluso
archivos completos). Podemos imaginar una herramienta que haga una
comparacion de dos archivos fuente (hechos por dos personas distintas) del
mismo programa en busca de que tan semejantes son ambos archivos. Desde
luego que el resultado que se espera es que el nivel de diferencias entre am-
bos archivos sea el maximo, mientras que el de semejanza sea el mınimo, es
decir, que los archivos sean muy diferentes.
78
Pese a que para evoluciones muy grandes el sistema se lleva su tiempo en mostrar
los resultados, es evidente que comparado con lo que tardariamos en hacerlo
manualmente, realmente no es tanto. Ademas como mencionamos, el sistema es
lo suficientemente confiable con sus resultados y permite una evaluacion global
muy precisa al realizar miles de comparaciones.
El analisis de los mosaicos R110 es un problema abierto y tiene muchos trabajos
futuros aun por realizar. Algunos trabajos futuros relacionados con esta tesis
son:
(1) Traducir el codigo fuente del sistema a un lenguaje libre. Uno de los pro-
blemas principales que ocurre en la mayorıa de las aplicaciones, es la de la
compatibilidad de las plataformas en las que se ejecuta un programa. Este
sistema por ahora unicament puede ejecutarse en ordenadores que cuenten
con Windows como sistema operativo. Una alternativa rapida serıa tra-
ducirlo a un lenguaje libre como Java, el cual es software libre e indepen-
diente de la plataforma en la cual se ejecute. Aunque tal vez lo mejor
serıa evaluar el desempeno de varios lenguajes para realizar una seleccion
adecuada del software.
(2) Buscar la frecuencia de repeticion de subregiones del DET. El analisis de
subregiones especıficas de un mosaico es posible si se desarrolla un proce-
dimiento que seleccione una parte de la evolucion donde haya un patron
de triangulos del cual queramos saber exactamente cuantas veces se repite.
Esto puede lograrse desarrollando un procedimiento con el que sea posible
seleccionar mediante una superficie rectangular o recuadro, una subregion
del mosaico y que se realize una busqueda de esta subregion a traves del
mosaico. El recuadro define nuevos lımites de frontera del cual se obtiene un
subcubrimiento como puede verse en la figura 5.2. Incluso pueden definirse
79
Figura 5.2: Subcubrimiento. La zona punteada representa la seleccion realizada en la
evolucion. En el interior se observa el contorno del subcubrimiento que se encuentra dentro del
marco rectangular.
dos metricas, de las cuales una sea muy estricta, es decir, que busque el
numero de veces que el subcubrimiento ocurre exactamente tal cual es en
el mosaico, y otra que sea mas basica y que realize una busqueda del sub-
cubrimiento sobre un umbral pre-establecido.
(3) Crear nuevas clasificaciones de gliders. Realizar busquedas con el objetivo
de encontrar patrones de triangulos similares que aparezcan a lo largo de
la evolucion, puede ayudarnos a crear nuevas clasificaciones acerca de lo
que se conoce como gliders. Si un patron ocurre muchas veces y no ha sido
clasificado aun, entonces podrıa considerarse como un nuevo glider.
80
Referencias
[1] Manuel de la Herran Gascon and Farid Fleifel Tapia, Ricardo Aranguren.Automatas celulares. En lınea en http://www.redcientifica.com/gaia/
ac/auto c.htm. Consultado el 21/09/2006.
[2] Caceres Gonzalez Abdiel Emilio. Maquina celular de computacion basada encubrimientos Regla 110. PhD thesis, Centro de Investigacion y de EstudiosAvanzados del Instituto Politecnico Nacional. Dpto de Ingenierıa Electrica,Seccion de computacion, 2005.
[3] David Eppstein. Design and Analysis of Algorithms: the Longest Com-mon Subsequence. En lınea en http://www.ics.uci.edu/∼eppstein/161/
960229.html. Consultada el 11/01/2007.
[4] Gonzalez V. Luis Fernando. Una introduccion a los Automatas Celulares. Enlınea en http://yupana.autonoma.edu.co/publicaciones/yupana/005/
autocelular/Automatas.html Consultado el 22/11/2006.
[5] Wang H. Proving theorems by pattern recognition-II. Bell Systems TechnicalJournal, 40:1–42, Enero 1961.
[6] Jiawei Han and Micheline Kamber. Data Mining: concepts and techniques.Morgan Kaufmann, 2001.
[7] H Heesch. Regulares parkettierungsproblem. Westdeutscher Verlag, 1968.Cited in Tiling and Patterns by B. Grunbaum and Geoffrey C. Shephard.1986.
[8] John E. Hopcroft and Jeffrey D. Ullman. Introduccion a la teorıa deautomatas, lenguajes y computacion. Ithaca New York. Princeton, NewYersey, Marzo 1979.
[9] Rennard Ph. D Jean-Philippe. Introduction to Cellular automata. Enlınea en http://www.rennard.org/alife/english/acintrogb01.html\#acHisto. Consultada el 23/11/2006.
[10] Neil C. Jones and Pavel A. Pevzner. An introduction to bioinformatic Algo-rithms (Computational molecular biology). MIT Press, Agosto 2004.
[11] Genaro Juarez Martınez. Un camino para construir configuraciones comple-jas en la regla 110, 2002. Centro de Investigacion y de Estudios Avanzadosdel Instituto Politecnico Nacional. Dpto de Ingenierıa Electrica, Seccion deComputacion 2002.
81
[12] Cook Matthew. Introduction to the activity of rule 110. In the World WideWeb, r1994-1998 Matthew Cook, 1999. En lınea en http://w3.datanet.
hu/∼cook/Workshop/CellAut/Elementary/Rule110/110pics.html.
[13] Warren Sturgis McCulloch and Walter Pitts. A Logical Calculus of the IdeasImmanent in Nervous Activity, 1943.
[14] Harold. V McIntosh. Rule110. Universidad Autonoma de Puebla, 1999. Enlınea en http://delta.cs.cinvestav.mx/∼mcintosh/oldweb/pautomata.
html.
[15] H.V McIntosh. Rule110 as it relates to the presence of gliders. Enlınea en http://delta.cs.cinvestav.mx/∼mcintosh/comun/RULE110W/
rule110.pdf. Consultado el 02/12/2006.
[16] Gilleland Michael. Levenshtein Distance, in Three Flavors. En lınea enhttp://www.merriampark.com/ld.htm. Consultada el 18/06/2007.
[17] Berger Robert. The undecibility of the domino problem, volume 66. Ameri-can Mathematical Society, 1966.
[18] E. A Robinson Jr. Symbolic dynamics and tilings of Rd. Joint Mathematicsmeetings, January 2002. Unpublished Lecture Notes for a Short Course inSymbolic Dinamics.
[19] Stanislaw Marcin Ulam. Stanislaw M. Ulam bibliography. En lınea en http:
//www-groups.dcs.st-and.ac.uk/∼history/Biographies/Ulam.html.Consultada el 23/11/2006.
[20] Wikipedia. Data mining — Wikipedia, The Free Encyclopedia. En lıneaen http://en.wikipedia.org/w/index.php?title=Data mining&oldid=
150396415. Consultado el 20/09/2006.
[21] Wikipedia. Clausura de Kleene — Wikipedia, La enciclopedia libre.En lınea en http://es.wikipedia.org/w/index.php?title=Clausura
de Kleene&oldid=9052165. Consultado el 23/11/2006.
[22] Wikipedia. Data Mining —Wikipedia, The Free Encyclopedia. En lıneaen http://en.wikipedia.org/w/index.php?title=Data mining&oldid=
133902894. Consultado el 20/09/2006.
[23] Wikipedia. Neural network — Wikipedia, The Free Encyclope-dia. En lınea en http://en.wikipedia.org/w/index.php?title=Neural
network&oldid=134789440. Consultado el 23/11/2006.
82
[24] Wikipedia. Tesis de Church-Turing — Wikipedia, La enciclopedia li-bre. En lınea en http://es.wikipedia.org/w/index.php?title=Tesis
de Church-Turing&oldid=8697124. Consultado el 23/11/2006.
[25] Wikipedia. Vladimir Levenshtein — Wikipedia La enciclopedia libre.En lınea en http://en.wikipedia.org/w/index.php?title=Vladimir
Levenshtein&oldid=92677101. Consultado el 21/06/2007.
83
