revista ciencias basicas ujat v7n2 dic-2008

Revista deCiencias Básicas

UJAT

CunduacánTabascoMéxico

Contenido

Grandes Matemáticos: Leonardo Bonaccio (Fibonacci)

Rodolfo Conde del Águila 3

Simulación Numérica de Nitruración PostdescargaJorge López López 8

Modelo Depredador-PresaJosé Manuel López Cruz y Gamaliel Blé González 25

La métrica de LevenshteinAbdiel Emilio Cáceres González 35

Volumen 7Número 2

Diciembre 2008

REVISTA DE CIENCIAS BASICAS UJATes editada por la

División Académica de Ciencias Básicasde la Universidad Juárez Autónoma de Tabasco

EditoresDr. Abdiel E. Cáceres González ([email protected])Dr. José Leonardo Sáenz Cetina ([email protected])

Comité editorialFísicaM.C. Esteban Andrés Zárate

QuímicaDr. Isaías Magaña MenaM.C. Ma. Teresa Gamboa Rodríguez

MatemáticasM.C. Robert Jeffrey Flowers

ComputaciónL.S.C.A. Diana G. Chuc Durán

DescripciónLa Revista de Ciencias Básicas UJAT es una publicación semestral, dedicada a la difusión de las

ciencias básicas. Se dirige a profesores y estudiantes universitarios, y en general a todos los interesados en las ciencias. Su propósito es ofrecer un espacio que permita informar sobre las investigaciones en el área correspondiente y difundir temas generales de las ciencias básicas.

Información para autoresLos autores deben enviar por correo electrónico a [email protected], un paquete que

contenga los archivos fuente, tanto del texto en LaTeX2e; las imágenes en formato JPG y una copia en formato PDF del artículo propuesto. El artículo será distribuido a los revisores, quienes darán su aprobación para que sea publicado. El autor es libre de utilizar el molde para conservar el estilo tipográfico de la revista. Este molde se puede obtener desde la página WEB de la revista en http://www.dacb.ujat.mx/revistas_enlinea.html, en la sección de Información para autores. También es posible solicitarlo por correo electrónico directamente a los editores.

El contenido de los artículos debe ser de interés científico en las áreas de física, matemáticas, computación y química; pudiendo ser de divulgación de temas de investigación o de reportes de investigación. La extensión deseable de los artículos oscila entre las 5 y 15 páginas, pudiendo extenderse tanto como sea necesario de acuerdo a los criterios de los editores.

Todos los artículos deberán ser escritos en español o inglés, con un resumen de no más de 150 palabras tanto en español como en inglés.

Para encontrar revisores adecuados, agregue el siguiente cuestionario resuelto en el correo electrónico que nos envíe:

1) ¿Cuál es la contribución importante de este trabajo?2) ¿Cuáles son las áreas de conocimiento más relacionadas con este trabajo?

Suscripción a la Revista Ciencias Básicas UJATLa suscripción es absolutamente gratuita, solamente envíe un correo electrónico a cualquiera de los

editores, proporcionando la siguiente información:a) Nombre del representante institucional, o de la persona.b) Dirección postalc) Dirección electrónicad) Número de ejemplares que desea.

AdvertenciaEl contenido de los artículos es responsabilidad única del autor. Toda aclaración en cuanto al

contenido de los artículos, debe ser enviada por correo electrónico al autor que corresponde.ISSN: [En trámite]Página WEB:http://www.dacb.ujat.mx/revistas_enlinea.htmlCorreo electrónico:[email protected]

Revista de Ciencias Básicas UJAT, volúmen 7 número 1, junio 2008.Se terminó de imprimir en junio de 2008 en los talleres de Gráficos Cánovas.

El tiraje consta de 300 ejemplares.

Revista deCiencias Básicas

UJAT

CunduacánTabascoMéxico

Volumen 7Número 2

Diciembre 2008

Contenido

3

Grandes Matemáticos: Leonardo Bonaccio (Fibonacci)Rodolfo Conde del Águila

8Simulación Numérica de Nitruración PostdescargaJorge López López

25Modelo Depredador-PresaJosé Manuel López Cruz y Gamaliel Blé González

35La métrica de LevenshteinAbdiel Emilio Cáceres González

Grandes Matematicos:

Leonardo Bonaccio (Fibonacci) ∗

Rodolfo Conde del Aguila†

Universidad Juarez Autonoma de Tabasco, DACB

En este trabajo hacemos una descripcion somera de la vida del mas grande matematicode la Edad Media: Leonardo Bonaccio (Fibonacci). La importancia de su trabajo enla traduccion de los textos arabes al latın abrio el camino al desarrollo en Europa delas Matematicas.

In this paper, we make a brief review about the life of the greatest mathematicianin the Middle Age: Lenardo Bonaccio (Fibonacci). We will see how his translationsof the arabic text to latin language were a fundamental part for the development ofmathematics in Europe.

Palabras clave: Leonardo Bonaccio, Fibonacci, Biografıa.Keywords: Leonardo Bonaccio, Fibonacci, Biography.

Galileo Galilei, uno de los grandes hombres de Ciencia que ha dado la humanidaddecıa:

El gran libro de la naturaleza siempre esta abierto ante nuestro ojos y la verdaderafilosofa esta escrita en el, pero no la podemos leer a menos que hayamos aprendidoprimero el lenguaje y los caracteres con los cuales esta escrito. El gran libro estaescrito en lenguaje matematica y los caracteres son triangulos, cırculos y otras figurasgeometricas.

La matematica es el alfabeto con que Dios escribio al Universo.

Como podemos apreciar en el contenido de lo expresado por Galileo, la matematicacomo quehacer del ser humano ha sido actividad primordial desde la aparicion delhombre en la faz de la tierra y ha estado revestida de misticismo religioso. Las grandesculturas antiguas como la Egipcia desarrollaron algunos conocimientos matematicosque aplicaron en problemas practicos, sin embargo fueron los griegos quienes primer-amente empezaron a estudiarla de manera abstracta, ya que recordemos que paralos pitagoricos la matematica era una religion y que sus resultados eran guardadoscelosamente entre ellos.

En la antiguedad hubieron muchos matematicos notables, los logros y teoremasencontrados por ellos nos llenan todavıa de asombro y los nombres de Pitagoras,Euclides, Tales de Mileto, Heron de Alejandrıa, Hipatia, Arquımedes, Eudoxio yotros mas, son conocidos por toda persona dedicada al estudio de la matematica. Sin

∗Recibido el 26 de septiembre de 2008 y aceptado el 17 de noviembre de 2008†Direccion postal: Carr. Cunduacan-Jalpa Km 1, Cunduacan Tabasco, Mexico. A.P. 24 C.P.

86690. Tel.(+52)914 336-0928. Correo electronico: [email protected]

Revista de Ciencias Basicas UJAT, volumen 7 numero 2 (Diciembre 2008) p 3–7

4 Rodolfo Conde del Aguila

embargo, durante el periodo conocido como la Edad Media, la matematica no tuvo undesarrollo considerable, ya que pocos son los matematicos que podemos citar en dichaepoca. La ciencia matematica se desarrollo con mucha lentitud y en consecuenciacomo mencionabamos con anterioridad fueron muy escasos los matematicos.

Uno de los grandes matematicos que durante la Edad Media realizo un trabajorelevante en la matematica fue Leonardo de Pisa, conocido como Fibonacci. Suaportacion a la matematica fue fundamentalmente la traduccion de los textos Arabesde matematicas al Latın y su obra conocida como LIBER ABACCI, escrita en el ano1202, resume todo el conocimiento aritmetico y algebraico de esa epoca. Durantevarios siglos tuvo gran influencia en el desarrollo de la matematica en Europa ygracias a el se conocio el sistema de enumeracion Indo Arabiga.

A finales del siglo XII la ciudad de Pisa es una gran potencia comercial, conDelegaciones en el Norte de Africa. Una de estas delegaciones se encontraba en laciudad Argelina de Bugıa y de la cual era responsable Guillermo Bonaccio, padrede Leonardo. En consecuencia Leonardo es educado por maestros Arabes y de ellosaprende el calculo posicional Hindu, teniendo su primer contacto con lo que acabarıaconvirtiendose, gracias a el, en uno de los magnıficos regalos del mundo Arabe a lacultura Occidental y que es el Sistema de Numeracion Posicional.

Leonardo de Pisa, conocido como Fibonacci (contraccion de las palabras FiloBonaccio que significa hijo de Bonaccio) aprovecho sus viajes comerciales por todoel Mediterraneo, Egipto, Sicilia, Grecia, para entablar contacto y discutir con losmatematicos mas notables de esos tiempos y para descubrir y estudiar la geometrıade Euclides que tomo como modelo de estilo y de rigor.

En el ano de 1202 escribe su obra mas relevante que titula Liber Abacci, en elaparece por vez primera en Occidente, las nueve cifras Hindues y el sımbolo del Cero,es decir el sistema de numeracion posicional de base diez. Fibonacci proporciona en suobra reglas precisas para realizar operaciones con estas cifras tanto para numeros en-teros como para fracciones, brindando a sus colegas comerciantes un potente sistemade calculo cuyas ventajas el ya habıa experimentado.

Su obra Liber Abacci fue fundamentalmente un amplio tratado del sistema de nu-meracion indoarabigo, en el que presenta los signos hindues y el cero. Con el tiemposu libro llego a ser la obra de maxima influencia entre todas las que contribuyeron aintroducir en Occidente el sistema de numeracion indoarabiga . Consideramos impor-tante senalar que no deja de ser ironico que Leonardo de Pisa, cuyas aportaciones a lamatematica fueron de tanta relevancia, sea hoy conocido a causa de un matematicofrances, del siglo XIX, de nombre Eduardo Lucas, quien encadeno el nombre de Fi-bonacci a una sucesion numerica que forma parte de un problema trivial del LiberAbacci.

La sucesion de Fibonacci: (cada termino a partir del tercero es igual a la suma delos dos anteriores) ha tenido intrigados a los matematicos durante siglos, en parte acausa de su tendencia a presentarse en los lugares mas inopinados, pero sobre todoporque cualquier aficionado a las matematicas (Teorıa de Numeros), puede aspirar ainvestigarla y descubrir curiosos teoremas de los que parece haber una variedad in-agotable. El interes por esta sucesion o por las sucesiones llamadas del tipo Fibonacciha sido avivado por desarrollos crecientes en programacion de ordenadores ya que alparecer tiene aplicacion en clasificacion de datos, recuperacion de informaciones, gen-

Revista de Ciencias Basicas UJAT, 7(2)Diciembre 2008 p 3–7

Grandes Matematicos: Leonardo Bonaccio (Fibonacci) 5

eracion de numeros aleatorios e inclusos en metodos rapidos de calculo aproximadode valores maximos o mınimos de funciones complicadas. Sin embargo la propiedadmas notable de la sucesion de Fibonacci sea que la razon entre cada par de numerosconsecutivos se acerca al valor de la razon aurea.

Existe demasiada literatura en relacion a la sucesion de Fibonacci y la razon aurea.En el Reino Vegetal la sucesion de Fibonacci tambien hace su aparicion en el numerode espirales de las semillas de ciertas variedades de girasol. En fin podemos seguirmencionando un gran numero de afinidades que tiene la sucesion de Fibonacci con laNaturaleza.

El Liber Abacci, la gran obra de matematicas de la Edad Media se divide en quincecapıtulos que son:

Capıtulo I: Lectura y escritura de los numeros en el sistema indoarabigo.

Capıtulo II: Multiplicacion de Numeros Enteros.

Capıtulo III: Suma de Numeros Enteros.

Capıtulo IV: Resta de Numeros Enteros.

Capıtulo V: Division de Numeros Enteros.

Capıtulo VI: Multiplicacion de Numeros Enteros por Fracciones.

Capıtulo VII: Fracciones.

Capıtulo VIII: Precio de las mercancıas mas comunes.

Capıtulo IX: Comercio.

Capıtulo X: Relaciones de parentesco.

Capıtulo XI: Conversion de monedas.

Capıtulo XII: Problemas y soluciones.

Capıtulo XIII: La regla de la falsa posesion.

Capıtulo XIV: Raıces cuadradas y raıces cubicas.

Capıtulo XV: Proporciones, Geometrıa y Algebra.

Algunos problemas propuestos en el Liber Abacci son los siguientes:

Siete mujeres mayores van viajando a Roma y cada una de ellas lleva siete mulas.Cada mula lleva siete sacos y en cada saco hay siete piezas de pan. En cada pieza depan hay siete cuchillos y cada cuchillo tiene siete dientes. Cuantos dientes de cuchilloviajan a Roma?

Un hombre entro a una huerta que tenıa siete puertas y tomo un cierto numero demanzanas. Al abandonar la huerta le dio al primer guardia la mitad de las manzanasque llevaba mas una. Al segundo guardia la mitad de las manzanas que le quedabanmas una. Hizo lo mismo con los guardias de cada una de las cinco puertas que lefaltaban. Cuando se fue de la huerta le quedaba una manzana. Cuantas manzanashabıa tomado en un principio?

Un Rey mando treinta hombres a su huerta a plantar arboles. Si pudieron plantar1,000 arboles en nueve dıas, en cuantos dıas podran treinta y seis hombres plantar4,400 arboles?


6 Rodolfo Conde del Aguila

El problema que aparece en el Liber Abacci y que da origen a la sucesion deFibonacci podemos escribirlo de la manera siguiente:

En una granja hay, al principio del ano, (1 de Enero), una pareja de conejos,macho y hembra. Supongamos que la pareja de conejos empiezan a procreara los dos meses de vida,(1 de Marzo), engendrando un unico par, macho yhembra, y ası sucesivamente cada mes. Si en cada una de las nuevas parejasacontece lo mismo, es decir empiezan tambien a procrear a los dos meses devida, engendrando tambien un unico par macho y hembra. ¿Cuantos pares deconejos tendremos al cabo de un ano?

La solucion queda de la manera siguiente:

Supongamos que a partir del 1 de Enero tenemos la pareja original, la cualllamaremos P1 , obviamente durante los meses de Enero y Febrero tenemosunicamente a la pareja, ya que una condicion del problema es que comienzan aprocrear despues de dos meses de vida y en consecuencia en el mes de Marzotendremos dos parejas, una que es P1 y la otra es una nueva pareja que engendraP1 y que llamaremos P2 .

De acuerdo a las condiciones ideales del problema la pareja P1 da origen a unanueva pareja durante los meses de Marzo, Abril, Mayo, Junio, Julio, Agosto,Septiembre, Octubre, Noviembre y Diciembre. La pareja P2 empezara a pro-crear a partir del primero de Mayo y tambien procreara pareja nueva en losmeses de Mayo, Junio, Julio, Agosto, Septiembre, Octubre, Noviembre y Di-ciembre. En conclusion podemos elaborar el siguiente esquema:

Mes Pareja Numero de Pareja

Enero P1 1

Febrero P1 1

Marzo P1,P2 2

Abril P1, P2, P3 3

Mayo P1, P2, P3, P4, P5 5

Junio P1, P2, P3, P4, P5, P6, P7, P8 8...

......

Como podemos observar cada termino de la sucesion de pareja a partir deltercero es igual a la suma de los dos anteriores, es decir, en consecuencia duranteel mes de Julio tendremos 13 parejas, en Agosto 21 parejas, en Septiembre 34parejas, en Octubre 55 parejas, en Noviembre 89 parejas y en Diciembre 144parejas.

No olvidemos que el problema esta planteado en condiciones ideales, ya quesuponemos que la pareja original nace el primero de Enero y que comienza aprocrear a partir del primero de Marzo, y que las nuevas parejas siguen la mismasecuencia de la pareja original. Tambien suponemos que no se muere ningunade las parejas.

El trabajo realizado por el gran matematico italiano Leonardo Bonaccio ha sido degran trascendencia, es imposible concebir el desarrollo moderno de la matematica sinlas contribuciones de Fionacci, en cierta medida fue el eslabon que unio la matematicahindu y arabe con los pueblos de Europa antigua. Es inadmisible pensar en el


Grandes Matematicos: Leonardo Bonaccio (Fibonacci) 7

avance de las matematicas en Europa sin la traduccion de los Textos arabes quehizo Leonardo al Latin. Por ello Leonardo Bonaccio ha sido calificado como el masgrande matematico de la edad media.

Referencias

[1] Richard Mankirwics, Historia de las Matematicas, Ediciones Paydos Iberica, S.A.

[2] Hofmann, Historia de la Matematica, Limusa.

[3] Newmann, Sigma (El Mundo de la Matematicas), Grijalvo.

[4] N. N. Vorobyov, Los numeros de Fibonacci, Limusa.

[5] Dickson L. E., History of the Theory of Numbers. Vol. I, II, Carnegie Institute .


Simulacion Numerica de Nitruracion

Postdescarga ∗

Jorge Lopez Lopez †

En este trabajo se hace una simulacion del fenomeno de nitruracion postdescarga queinvolucra la formacion de capas y el consecuente movimiento de interfaces, dando lugara fenomenos de tipo Stefan. Se utiliza para la discretizacion del modelo, diferenciasfinitas en mallas moviles.

The matter of this work is the computational simulation of post-discharge nitriding.This phenomena involves layer formation and interfaces movemement of Stefan type.To discretice the model we use finite diferences with moving mesh.

Palabras clave: Nitruracion, Diferencias Finitas, Interfaces, Problemas tipo Stefan,Cuasiestabilizacion.Keywords: Nitriding, Finite diference, Interfaces, Stefan Problems, Cuasi-stabilization.

1. Introduccion

El tratamiento termoquımico de nitruracion produce importantes mejoras en laspropiedades mecanicas, tribologicas y quımicas del acero, mejorandose por ejemplola resistencia a la fatiga, la corrosion y el desgaste.

Los procesos de nitruracion involucran varios aspectos delicados como la evolucionde la concentracion de nitrogeno en la superficie y la evolucion de la concentracion denitrogeno en el interior del metal. En algunos estudios, sobre todo en simulacionesnumericas, se considera que la concentracion de nitrogeno en la superfice es constantedesde el inicio del proceso, lo cual no se da en general.

Un fin inmediato del estudio de los fenomenos de nitruracion es la automatizaciony control de estos. Para tal fin son necesarios modelos matematicos del fenomeno. Eigual de necesario es contar con la solucion, exacta o aproximada de estos modelos.En este sentido, este trabajo esta basado en [1] donde se propone un modelo para lanitruracion postdescarga y un metodo para calcular los coeficientes de difusion delproceso. El metodo consiste en minimizar un funcional que depende de medicionestomadas en la etapa final de cuasiestabilizacion y de suponer una solucion analıtica decomportamiento parabolico en esta ultima etapa. El comportamiento que se planteano se satisface en el inicio y las primeras etapas del evento, ası que es importanteanalizar al menos numericamente si la solucion del modelo con los coeficientes en-contrados en [1], refleja las propiedades cualitativas y cuantitativas del evento desdelas primeras etapas. Este es el fin del presente articulo: resolver numericamente elmodelo planteado en [1] usando los coeficientes de difusion encontrados en ese mismo




Simulacion Numerica de Nitruracion Postdescarga 9

Figura 1. Esquema de nitruracion.

trabajo.

2. El modelo

Se consideran condiciones de tal manera que el proceso sea unidimensional; es deciruna muestra de metal se pone en contacto con nitrogeno y se desea estudiar como varıala concentracion de nitrogeno en el interior del metal en funcion de la profundidad.Ver la figura 1.

Para los detalles tecnicos de los experimentos ver la seccion 2 de [1]. A partir deuna concentracion inicial que normalmente es cero, la concentracion de nitrogeno alo largo de la barra comienza a variar, incluso en la superficie, hasta un tiempo t0 enel que la concentracion en la superficie alcanza un valor estable Cs. A partir de aquıcomenzaran a formarse capas de nitrogeno. Las siguientes etapas estaran caracteri-zadas por la formacion de estas capas, hasta llegar a una etapa de cuasiestabilizaciondel fenomeno. Se formaran dos capas y una zona de difusion en lo mas profundo.

El modelo que se propone considera 4 etapas. La primera esta modelada por:

∂C

∂t= D

∂2C

∂x2, 0 < x < +∞, t > 0

C(x, 0) = C0, 0 < x < +∞∂C

∂x(0, t) =

λ

D(C − Ceq)

∣∣∣∣x=o

, t > 0

limC(x, t) = C0, t > 0

siendo λ el coeficiente de reaccion cinetica, D el coeficiente de difusion, Ceq es laconcentracion en equilibrio de nitrogeno en la atmosfera remota y C(x, t) representala concentracion de nitrogeno para el tiempo t y la profundidad x. La solucion paraeste modelo en t0 se da en [1], denotandose por f(x) y representa la concentracion


10 Jorge Lopez Lopez

Figura 2. Concentracion contra la profundidad.

al momento de iniciar la formacion de las capas. A partir de la concentracion f(x)al tiempo t0 dos capas de nitrogeno y una zona de difusion comenzaran a formarse ylentamente se desplazaran al interior del metal. En cada capa y zona de difusion, elcoeficiente de difusion toma un valor constante Di, i = 1, 2, 3. Entre capas adyacentesy zona de difusion hay un salto en la concentracion. En cada una de las primeras doscapas un valor constante mınimo Ci

min, i = 1, 2 es alcanzado. Para cada t > t0 sedefine ξi(t), i = 1, 2 como la profundidad de la capa correspondiente. Dado que loscoeficientes de difusion son constantes, se sigue que la concentracion en cada capa esuna funcion decreciente de la profundidad y entonces ξi(t) es la profundidad en la cualla concentracion alcanza el mınimo valor Ci

min (ver figura 2). Como una consencuenciadel proceso hay un valor experimental de la concentracion Ci+1

max < Cimin y un tiempo

t = ti tales que f(ξi(ti)) = Ci+1max, i = 1, 2. En esta situacion se dice que las capas

estan completamente formadas en el tiempo ti (ver figura 3). Se asume tambien quet1 < t2. Para t ∈ [t0, t1] la concentracion tiene un salto de tamano Ci

min − f(ξi(t)),i = 1, 2. Mas aun, para t > ti el tamano del salto en la concentracion en ξi(ti) esconstante e igual a Ci

min − Ci+1max, i = 1, 2. Denotamos xi = ξi(ti), i = 1, 2.

Para modelar desde el inicio de la formacion de capas e interfaces se consideran3 perıodos: t ∈ [t0, t1), t ∈ [t1, t2), t ∈ [t2,+∞), y se denota la concentracion denitrogeno en la i-esima capa o zona de difusion para el tiempo t y la profundidadx, por Ci(x, t). Se define x0

i como el valor de la profundidad donde f(x0i ) = Ci

min,i = 1, 2, Fi(t) = max

{Ci+1

max, f(ξi(t))}

, i = 1, 2 y x00 ≡ 0, ξ0(t) ≡ 0. Entonces el



Figura 3. Formacion de capas.

modelo para estos perıodos tiene la forma

∂C

∂t= D

∂2C

∂x2, t > t0, ξi−1(t) < x < ξi(t), i = 1, 2 (1)

t > t0, ξ2(t) < x, i = 3.

Ci(x, t0) = f(x), x0i−1 < x0

i , i = 1, 2, x02 < x, i = 3.

Ci(ξi−0(t), t) = Cimin, , t > t0, i = 1, 2,

C1(0, t) = Cs, , t > t0,

Ci+1(ξi+0(t), t) = Ci+1max, , t > ti, i = 1, 2,

(Cimin − Fi(t))

dξi

dt= −Di

∂Ci

∂x(x, t)

∣∣∣∣x=ξi−0

+ (2)

Di+1∂Ci+1

∂x(x, t)

∣∣∣∣x=ξi+0

, cuando i vale 1, 2,

limx→+∞

C3(x, t) = C0, t > t0,

ξi(t0) = x0i , i = 1, 2.

Este modelo describe los tres diferentes estados del proceso, caracterizados por loshechos siguientes:

Cuando t ∈ [t0, t1), se tiene Fi(t) = f(ξi(t)), i = 1, 2. Para t ∈ [t1, t2) se tieneF1(t) = C2

max, F2(t) = f(ξ2(t)), y finalmente, para t ≥ t2 se tiene Fi(t) = Ci+1max,

i = 1, 2. Para ser consistentes con la notacion usada se define ξ3(t), t > t0 como laprofundidad a la cual

C3(ξ3(t), t) = 0.1C3max. (3)

En la tercera etapa mencionada las dos capas estan completamente formadas como



Figura 4. Formacion de todas las capas.

se muestra en la figura 4. A partir de este momento, el modelo corresponde alcrecimiento de capas y movimiento de interfaces, previo a la ”estabilizacion” delcrecimiento de capas, donde capas e interfaces siguen exactamente el comportamientode un fenomeno de fronteras moviles del tipo Stefan. Esto esta ilustrado en la figura5.

Como se puntualiza en [1], para tiempos muy grandes el crecimiento de capasllega a ser insignificante, lo cual es justificado por ensayos experimentales y tambienanalıticamente dado que las interfaces se mueven con velocidad proporcional a 1

2√t.

Ası que el proceso alcanza un estado cuasi estable, donde la variacion ∂C∂t es muy

pequena.

3. Simulacion Numerica del fenomeno

Como se ha descrito, el fenomeno de nitruracion contempla 4 etapas. La primera vadesde el tiempo t = 0 hasta el tiempo t0 en el que la concentracion en la superficiealcanza el valor Cs. En esta etapa el fenomeno es uno de difusion estandard, que sepuede simular muy bien utilizando metodos numericos clasicos como el metodo θ. Lasegunda etapa, y a partir de la cual el fenomeno se vuelve mas interesante, va desdeel tiempo t0, es decir, desde la formacion del perfil umbral f(x) = C(x, t0) hasta eltiempo t1 en el que

C2(ξ1(t1), t1) = C(ξ1(t1), t0) = C2max.

La tercera etapa va desde t1 hasta el tiempo t2 en el que

C3(ξ2(t2), t2) = C(ξ2(t2), t0) = C3max.



Figura 5. Cuasi-stabilizacion de la concentracion de nitrogeno.

De acuerdo a estas relaciones, la segunda etapa termina cuando se forma la primeracapa, mientras que la tercera etapa termina cuando se forma la segunda capa. Y paraser consistentes, la cuarta etapa termina cuando se cumple (3). Finalmente la quintaetapa esta asociada con la cuasiestabilizacion del fenomeno; va desde t3 hasta +∞.

Para resolver numericamente el modelo correspondiente a las etapas 2, 3, y 4 setiene en cuenta que las ecuaciones que gobiernan el movimiento de las interfaces y elcambio en las concentraciones en cada capa son las mismas, siendo caracterizada cadacapa y cada etapa por: el coeficiente de difusion y la concentracion en el extremoizquierdo de cada capa,

C1(0, t) = Cs, t > t0, (4)Ci+1(ξi+0(t), t) = C(ξi(t), t0), ti−1 < t < ti , i = 1, 2,

Ci+1(ξi+0(t), t) = Ci+1max, t > ti, i = 1, 2;

la concentracion en el extremo derecho de cada capa,:

Ci(ξi−0(t), t) = Cimin, t > t0 , i = 1, 2, (5)

limx→+∞

C3(x, t) = C0, t > t0;

y los valores para el movimiento de las interfaces,

Fi(t) = C(ξi(t), t0) , i = 1, 2, t ∈ [t0, t1),

F1(t) = C2max

F2(t) = C(ξ2(t), t0)

}, t ∈ [t1, t2),



Fi(t) = Ci+1max, i = 1, 2, t ≥ t2).

Estas caracterizaciones se tomaron en cuenta en la implementacion del algoritmonumerico que se utilizo para resolver el modelo. Este algoritmo es una adaptacion delos metodos en diferencias finitas con malla movil para problemas de frontera movil[4], los cuales se aplican en cada capa y en la zona de difusion. Para este fin eldominio se subdivide en tres subdominios (0, ξ1(t)), (ξ1(t), ξ2(t)) y (ξ2(t), lim2). Elvalor de lim2 debe ser tal que refleje limx→+∞ C3(x, t) = C0, t > t0, . Un valorrazonable para lim2 es 55µ. Se denota con K el tamano de paso en el tiempo y conh1, h2, h3 el tamano de paso espacial en la capa i = 1, 2, 3, correspondiendo la capa3 a la zona de difusion. N es el numero de nodos en todo el dominio. Con esto, sehace Ci(nij , t0) = Ci(ξi(t0) + jhi, t0); ası que dada la concentracion Ci(nij , t) en cadatiempo t se aproxima el nuevo valor de ξi en el tiempo t + K para luego mover lamalla en cada capa, pudiendo mantenerse constante o variable el numero de nodos encada capa y en el dominio completo; se interpola la concentracion Ci(nij , t) al nuevodominio y a la nueva malla para obtener C

1/2i (nij , t + K) y finalmente se aproxima

el efecto difusivo en cada capa, resolviendo numericamente la ecuacion de difusion(1) para obtener Ci(nij , t + K). El algoritmo programado para simular el fenomenohasta T segundos se muestra en el Apendice.

3.1 Calculo de las interfaces.

La actualizacion de las interfaces ξi(t) se hace resolviendo con Euler explıcito laecuacion (2), de la que se puede observar que aunque la posicion inicial x0

i de estas estabien definida, ese no es el caso para las velocidades iniciales de las interfaces, ya que ent0 se obtiene la indeterminacion 0/0. Ası que se debe experimentar para determinaresta velocidad inicial. De hecho esta serıa informacion adicional proporcionada porlas simulaciones numericas.

3.2 Interpolacion y extension de Ci(nij , t) a la nueva malla para obtener C1/2i (nij , t + K).

Como las interfaces se mueven hacia la derecha, en cada paso de tiempo existiranintervalos (ξi(t), ξi(t+K)), i = 1, 2, que siendo de las capas 2 y 3 pasaran a ser de lascapas 1 y 2 respectivamente, por lo que es necesario que en esos intervalos definamosde manera adecuada C1 y C2. Lo mas facil es definir Ci = Ci

min, i = 1, 2. Se haceentonces una interpolacion lineal de la concentracion a los nuevos nodos, verificandoque el valor en un nodo sea menor o igual que el valor en el nodo anterior. Si esteno fuera el caso se obliga a tomar un valor igual al del nodo anterior, puesto que laconcentracion es una funcion decreciente de la profundidad.

3.3 Aproximacion del movimiento difusivo en cada capa.

Tomando C1/2i (nij , t+K) como condicion inicial se aplica el metodo θ para aproximar

Ci(nij , t + K). Como Ci es la concentracion en cada una de las capas y en la zona dedifusion, deben resolverse tres problemas de difusion en cada tiempo, uno para cadacapa y otro para la zona de difusion. Los problemas de difusion son similares puestoque los gobierna la misma ecuacion, solo cambiando el coeficiente de difusion y lascondiciones de frontera (4) a (5). Entonces en cada caso se debe resolver un sistema



de la forma Ac = b donde c denota el vector, de dimension s, de concentracionesaproximada en los nodos de cada capa y zona de difusion, incluyendo los extremos.La matriz A esta definida por

1 0−R1θ 1 + 2R1θ −R1θ

−R1θ 1 + 2R1θ −R1θ· · ·

· · ·−R1θ 1 + 2R1θ −R1θ

0 1

y el vector b es

αi

Ri(1− θ)Ci1 + (1− 2Ri + 2Riθ)Ci2 + Ri(1− θ)Ci3

Ri(1− θ)Ci2 + (1− 2Ri + 2Riθ)Ci3 + Ri(1− θ)Ci4

··

Ri(1− θ)Ci(s−2) + (1− 2Ri + 2Riθ)Ci(s−1) + Ri(1− θ)Cis

Cimin

donde Ri = DiK/h2i , α1 = Cs , α2 =

{C(ξ1(t), t0), t0 < t < t1 ,

C2max, t > t1,

y

α3 ={

C(ξ2(t), t0), t0 < t < t2 ,C3

max, t > t2,.

4. Resultados Numericos.

Ejemplo 1. Se hizo una simulacion del fenomeno con los siguientes parametros:

D1 = 3.02204e− 13,

D2 = 1.27401e− 14,

D3 = D = 1.83122e− 11,

que son uno de los juegos de coeficientes de difusion calculados en [1], lim2 =0.000055 = 55 micras; este valor se hace mover de acuerdo a la relacion

(100)d lim2

dt= −D3

∂C3

∂x(x, t)

∣∣∣∣x=ε3



Figura 6. Concentracion de Nitrogeno al tiempo t0 ejemplo 1.

N = 100; θ = 1.0; K = 1.0s; T = 10000 seg; λ = 58, 400D; Ceq = 32.05; C0 = 0.0;C1

min = 19.0; C2max = 9.625; C2

min = 6.5; C3max = 0.365; C3

min = 0.00.

Se tomo un valor constante de 7e − 8 para los 10 primeros incrementos en laprimera interface y un valor constante de 2e− 8 para los 10 primeros incrementos enla segunda interface. Esto con el fin de evitar la indeterminacion 0/0 y la fluctuacionen tales incrementos. Esto resulto de las experimentaciones y estarıa indicando elvalor para la velocidad inicial del movieento de las interfaces. Valores diferentes alos mencionados y menos incrementos constantes dan lugar a fluctuaciones que sinembargo, despues de un cierto tiempo se suavizan.

En la figura 6 se muestran en gris la simulacion de la concentracion hasta el tiempot0, y en negro la concentracion exacta en t0 = 20 s.

En la figura 7 se muestra en verde las concentraciones simuladas a los 12000 s.Como se puede observar, ya han pasado mas de 120 min y no se ha formado laprimera capa. En este tiempo, las referencias mencionan que ya se debe estar en laetapa de cuasiestabilizacion. En rojo aparece como referencia la concentracion a los20 s.

En la figura 8 se muestra a travez del tiempo, el comportamiento de los incrementosde las 2 interfaces, en gris lo correspondiente a la primera y en negro la segunda.

De acuerdo a [1], la primera interfaces debe estabilizarse en una profundidad de 7micras, mientras que la segunda lo debe hacer en 17 micras. La mayor profundidad dedifusion debe estabilizarse en 67 micras. De acuerdo a la figura 7, estos requerimientosson imposibles de satisfacer pues la primera apenas estarıa formada a una profundidadde 17 micras aproximadamente, y la segunda estarıa formada a una profundidad de65 micras.



Figura 7. Concentracion de Nitrogeno a los 12000 s ejemplo1.

Figura 8. Comportamiento del incremento de las interfaces ejemplo 1.



Figura 9. Concentracion de Nitrogeno al formarse la capa1 ejemplo2.

Ejemplo 2. En esta otra simulacion del fenomeno se tomo:

D1 = 1.0259e− 13,

D2 = 2.186e− 13,

D3 = D = 1.83122e− 11,

que son otro de los juegos de coeficientes de difusion calculados en [1] y dejando losdemas identicos al ejemplo 1. En la figura 9 se muestra la formacion de la primeracapa pero a un tiempo muy grande.

Ejemplo 3. Para esta simulacion del fenomeno se considero:

D1 = 1.26e− 14,

D2 = 1.02e− 15,

D3 = D = 6.68e− 12,

lim2 = 0.000055 = 55 micras; N = 100; θ = 1.0; K = 1.0s; T = 234 min; λ= 58, 400D; Ceq = 55.25; C0 = 0.0; C1

min = 23.59; C2max = 19.923; C2

min = 19.479;C3

max = 14.365; C3min = 0.00. Estos fueron sugeridos por uno de los autores de [1].

Resultado de experimentaciones se tomo un valor constante de 1e− 8 para los 10primeros incrementos en las interfaces. Indicando el valor para la velocidad inicial delmoviento de las interfaces. Valores diferentes a 1e−8 y menos incrementos constantesdan lugar a fluctuaciones que despues de un cierto tiempo se suavizan.



Figura 10. Concentracion de Nitrogeno al tiempo t0 ejemplo 3.

En la figura 10 se muestra en gris la simulacion de la concentracion hasta el tiempot0, y en negro la concentracion exacta en t0 = 20 s.

En la figura 11 se muestran en gris la concentracion simulada a los 820 s, antes deque se forme la primera capa. En negro aparece como referencia la concentracion alos 20 s.

En la figura 12 se muestra, en color claro, la concentracion a los 5020 s, cuandoya se ha formado la primera capa.

En la figura 13 se muestra, en color oscuro, la concentracion a los 5520 s, cuandoya se ha formado la segunda capa.

En la figura 14 se muestra la concentracion en la etapa de cuasiestabilizacion, entanto que en la figura 15 se muestra el comportamiento de los incrementos de las 2interfaces a travez del tiempo: en color claro lo correspondiente a la primera y ennegro a la segunda. Cabe mencionar aquı que alrededor del tiempo 6500 s se presentaun ligero incremento en las velocidades de la interface 2.

5. Conclusiones.

Los juegos de parametros usados son los sugeridos en las referencias. Y aunque en lasdos primeras simulaciones los resultados numericos son muy distantes de lo esperadode acuerdo a las referencias, en el ejemplo 3 los resultados numericos estarıan deacuerdo al reporte de que las dos interfaces se cuasiestabilizarıan en 5 y 7 micrasaproximadamente. sugiriendo tambien una velocidad inicial para el movimiento delas interfaces.



Figura 11. Concentracion de Nitrogeno a los 820 s ejemplo 3.

Figura 12. Concentracion de Nitrogeno a los 5020 s ejemplo 3.



Figura 13. Formacion de la segunda capa ejemplo 3.

Figura 14. Concentracion de Nitrogeno en cuasiestabilizacion ejemplo 3.



Figura 15. Comportamiento del incremento de las interfaces

La profundidad de la zona de difusion tambien estarıa de acuerdo con algunosreportes, sobre todo [1].

De acuerdo a los parametros de difusion usados y a la forma en que se mueven lasinterfaces, el comportamiento numerico de cada Ci es aceptablemente adecuado, asıque los resultados numericos pueden sugerir una revision de los coeficientes usados ode alguno de los parametros experimentales usados.

Las propiedades de precision, estabilidad y convergencia del metodo numerico estanasociadas con las propiedades de estabilidad y convergencia del metodo θ que se usoen la solucion de los problemas parabolicos y en el metodo de Euler que se usopara mover las interfaces, pero faltarıa trabajo teorico para ver como se comportancombinados.

De acuerdo a los experimentos, alrededor de los 120 min ya deberıan estar formadaslas dos capas y estar en la etapa de cuasiestabilizacion, lo cual no sucede en lassimulaciones 1 y 2. Esto puede estar asociado con la velocidad inicial de las interfacesy la velocidad con que hacemos mover el dominio, datos que no estan reportados en laliteratura, pero tambien con los parametros experimentales y la precision y estabilidadde los metodos numericos usados.

Apendice

A. Algoritmo 1:

Para aproximar la concentracion de Nitrogeno Postdescarga: Inicio:



1 Leer Cimin, Ci

max, i = 1, 2, 3, K, D1, D2, D3, t0, T, N

2 Aproximar ξi(t0) de la ecuacion C(ξi(t0), t0) = Cimin.

3 Discretizar la primera capa en LM1 = round(N / 6) nodos,.

Discretizar la segunda capa en LM2 = 2 ∗ LM1− 1 nodos.

Discretizar la zona de difusion en LM3 = N − 3 ∗ LM1 + 1.

4 Hacer C1(t) = C(t0) en cada nodo de la primera capa;

Hacer C2(t) = C(t0) en cada nodo de la segunda capa;

Hacer C3(t) = C(t0) en cada nodo de la tercera capa;

5 Para cada etapa desde 2 hasta 4 hacer

t = t0.

Asignar valores a los parametros que caracterizan la fase y que

dependen solamente de la etapa :

parametro\etapa 2 3 4ucompara = C2(ξ1(t)) C3(ξ2(t)) −trefer = C2

max C3max −8000

Mientras ucompara > refer hacer

Aumentar lim2 si se desea.

Asignar valores a los parametros que caracterizan la etapa

pero que dependen de las interfaces:

parametro\etapa 2 3 4F1(t) = C(ξ1(t), t0) C2

max C2max

F2(t) = C(ξ2(t), t0) C(ξ2(t), t0) C3max

Se calcula la velocidad de las interfaces ξ′

i (t) excepto

para t = t0.

Se calcula la nueva ξi(t + K).

Se actualiza la malla a los nuevos subdominios.

Se interpola Ci(t) a la nueva malla para obtener C1/2i (t+K).

Se aplica el metodo teta en diferencias finitas para

aproximar el movimiento difusivo en cada capa, teniendo

como condicion inicial C1/2i (t + K), obteniendo las nuevas

Ci(t + K).

Se grafica C(t + K) (las Ci(t + K) simultaneamente).



Se hace Ci(t) = Ci(t + K) en cada nodo.

Se hace t = t + K.

termina el mientras

termina etapa

fin de algoritmo.

Referencias

[1] J. Bernal-Ponce, A. Fraguela-Collar, J. A. Gomez, J. Oseguera-Pena, F. CastilloAranguren. (2005) Identification of diffusion coefficients during post-discharge nitriding,Proceedings of the 5th International conference on Inverse Problems in Engineering:Theory and Practice, Cambridge, UK, Vol. 1, B05.

[2] J. Crank, The Mathematics of Diffusion, 2nd ed. Oxford Science Publications, 1993.

[3] J. Crank, Free and Moving Boundary Problems, Clarendon Press Oxford. 1984.

[4] E. Javierre-Perez, Numerical methods for solving Stefan problems, Report 03-16, De-partment of Applied Mathematical Analysis, delft University of Technology, 2003.


Modelo Depredador-Presa *

Jose Manuel Lopez Cruz **


Gamaliel Ble Gonzalez ***


En este artıculo se presenta un analisis detallado de un modelo matematico basi-co, depredador-presa, para la interaccion entre dos poblaciones .

In this paper a basic mathematical model for the interaction among two populationsof the depredator-prey type is analyzed.

Palabras clave: Lotka-Volterra, atractor global.Keywords: Lotka-Volterra, global attractor.

1. Introduccion

Una de las caracterısticas mas notables de la vida en nuestro planeta es la grandiversidad de aspectos y habitos que tienen los organismos que la componen. Sinembargo, es bastante mas difıcil observar que esta manifestacion de diversidad no seda de una forma arbitraria, sino todo lo contrario [2]. Los organismos viven en comu-nidades, formando intricadas relaciones de interaccion, donde cada especie dependedirecta o indirectamente de la presencia de las otras. Una de las tareas de la Ecologıaes el desarrollo de una teorıa de la organizacion de las comunidades que permita en-tender las causas de la diversidad y los mecanismos de interaccion. En este artıculose considera la interaccion de dos especies cuyos tamanos de poblacion al tiempo tson x(t) y y(t). Ademas, suponemos que el cambio en el tamano de la poblacion sepuede escribir como:

dx

dt= F (x, y)

dy

dt= G(x, y).

(1)

Existen diferentes clases de interaccion biologicas que pueden ser representadasmatematicamente con este sistema de ecuaciones. Ya que F (x, y) y G(x, y) determinanla velocidad de crecimiento de cada una de las poblaciones; se tiene el caso cuandouna de estas especies se alimenta de la otra, entonces el sistema de sobrevivenciaesta dado por:

*Recibido el 10 de septiembre de 2008 y aceptado el 3 de noviembre de 2008**Direccion postal: Carr. Cunduacan-Jalpa Km 1, Cunduacan Tabasco, Mexico. A.P. 24 C.P.

86690. Tel.(+52)914 336-0928. Correo electronico: chema [email protected]***Direccion postal: Carr. Cunduacan-Jalpa Km 1, Cunduacan Tabasco, Mexico. A.P. 24 C.P.



26 Jose Manuel Lopez Cruz y Gamaliel Ble Gonzalez

Fy(x, y) < 0Gx(x, y) > 0.

(2)

Esto es, el cambio de la poblacion de la presa con respecto al depredador disminuyey el cambio de la poblacion del depredador con respecto a la presa aumenta. Estas,son unas de las condiciones que debe cumplir un sistema de ecuaciones depredador-presa. En este trabajo analizaremos dos sistemas que cumple con la ecuacion (2). Elprimero sera el modelo de Lotka-Volterra y posteriormente haremos una modificacionde este que considera la competencia entre los individuos de la poblacion.

2. Analisis del sistema de tipo Lotka-Volterra

Este modelo se basa en las siguientes hipotesis.

1. La poblacion crece proporcionalmente a su tamano, es decir, tiene espacio y alimentosuficiente. Si esto sucede y x(t) representa la poblacion presa (en ausencia del depre-dador), entonces el crecimiento de la poblacion esta dado por

dx

dt= ax, a > 0,

x(t) = x0eat.

(3)

El numero de presas en ausencia del depredador crece exponencialmente.

2. El depredador y(t) solo se alimenta de la presa x(t). Ası, si no hay presas, su tamanodecae con una velocidad proporcional a su poblacion esto es

dy

dt= −dy, d > 0,

y(t) = y0e−dt.

(4)

El numero de depredadores en ausencia de la presa, decrece exponencialmente hastaextinguirse.

3. El numero de encuentros entre el depredador y la presa es proporcional al produc-to de sus poblaciones. Ademas, cada uno de los encuentros favorece al numero dedepredadores y disminuye el numero de las presas.

Por lo tanto, la presencia de la presa beneficia el crecimiento del depredador como

cxy, c > 0.

Mientras que la interaccion entre ellas, disminuye el crecimiento de la presa por

−bxy, b > 0.

Bajo las hipotesis anteriores tenemos que un modelo de interaccion entre x(t) yy(t) esta dado por el siguiente sistema:


Modelo Depredador-Presa 27

dx

dt= ax− bxy

dy

dt= cxy − dy,

(5)

con x > 0, y > 0 y los parametros a, b, c, d, son numeros reales positivos.

Este sistema lo podemos ver de la siguiente forma,

dx

dt= x(a− by) = xL(y)

dy

dt= y(cx− d) = yM(x),

y tiene como puntos de equilibrio a P00 = (0, 0) y Pxy = (d

c,a

b).

Si calculamos el Jacobiano del sistema tenemos:

J(x, y)=(

a− by −bxcy cx− d

).

Al evaluar la matriz jacobiana en los puntos de equilibrio se obtiene que

J(P00) =(

a 00 −d

)y J(Pxy) =

0−bd

cca

b0

.

Como los valores propios de J(P00) son reales y diferentes de cero, del teorema deHartman-Grobman concluimos que el punto P00 es un punto silla, [1]. Por otro lado,los valores propios de J(Pxy) son

λ = ±i√

ad.

En este caso la parte real de los valores propios es cero y no podemos aplicar el teo-rema de Hartman-Grobman. Ası que la aproximacion lineal no da informacion sobrela dinamica local en el punto Pxy. Por esto es necesario recurrir a otra herramientaque permita determinar el comportamiento local en Pxy.

3. Funcion de Liapunov del sistema

Sea E ⊂ Rn abierto, f ∈ C1(E) y

x = f(x) x(0) = x0, (6)

Una solucion de la ecuacion (6), es una funcion φt(x0) : I ⊂ R → Rn definida enuna vecindad de cero, tal que φ0(x0) = x0 y

d

dt(φt(x0)) = f(φt(x0)).



Si V ∈ C1(E), definimos la derivada de V a lo largo de la soluciones φt(x) como,

d

dtV (φt(x))|t=0 = V (x) = DV (x) · f(x).

Definicion . Sea x0 un punto de equilibrio de (6) y V ∈ C1(E) tal que:

i) V (x0) = 0.

ii) V (x) > 0 si x 6= x0.

Cuando V (x) ≤ 0 para todo x ∈ E o V (x) > 0 para todo x ∈ E \ {x0}, decimosque V es una funcion de Liapunov para (6) en E.

Con la finalidad de construir una funcion de Liapunov para el sistema (5), propo-nemos una funcion H como una suma de dos funciones

H(x, y) = F (x) + G(y). (7)

Vamos a calcular como deben ser G y F de tal manera que H satisfaga las condi-ciones sobre la derivada para ser una funcion de Liapunov.

Si calculamos la derivada de H a lo largo de la solucion del sistema (5), se obtiene

d

dtH(x(t), y(t)) =

dF

dx

dx

dt+

dG

dx

dy

dt= x

dF

dx(a− by) + y

dG

dy(cx− d).

Para que las soluciones de (5) vivan en las curvas de nivel de H se debe cumplir

d

dtH(x(t), y(t)) = 0.

Al separar las variables x y y se tiene

xdF

dxcx− d

=ydG

dy

by − a.

(8)

Como x y y son variables independientes, la ecuacion (8) se tiene, si y solo si

x dFdx

cx− d=

y dGdy

by − a= cte.

Ya que esta constante puede ser uno, tenemos que

dF

dx= c− d

x.



Por lo tanto, F (x) = cx− d lnx.

De igual manera,

dG

dy= b− a

y.

Por lo tanto, G(y) = by − a ln y.

Ası, H es de la forma H(x, y) = cx− d lnx + by− a ln y, y esta definida para x > 0y y > 0.

A partir de H buscamos proponer una funcion de Liapunov, por lo que es necesariodeterminar los puntos crıticos de H.

Como,

(∂H

∂x,∂H

∂y) = (c− d

x, b− a

y),

tenemos que el punto crıtico de H es Pxy.

Para mostrar que Pxy es un mınimo, es suficiente checar que la matriz hessiana deH en Pxy es definida positiva, [3]. Por definicion,

Hess(H) =

∂2f

∂x2

∂2f

∂x∂y∂2f

∂x∂y

∂2f

∂y2

=

d

x20

0a

y2

.

Ası

Hess(H(Pxy)) =

c2

d0

0b2

a

.

Comoc2

d> 0 y |Hess(H(Pxy))| > 0, tenemos en que H tiene un mınimo en Pxy.

Sim = H(Pxy) = cx− d lnx + by − a ln y,

entonces la funcion

V (x, y) = H(x, y)−m,

es una funcion de Liapunov en el primer cuadrante para el sistema (5). Por lotanto, el punto de equilibrio Pxy es estable, [1]. Ademas las soluciones viven en lacurvas de nivel de V y en consecuencia en las curvas de nivel de H, ya que V es solouna traslacion de H.



Por otro lado, el sistema (5) no tiene ciclos lımites, ya que no es constante en unabierto de R2, [4].

4. Orbitas cerradas en el primer cuadrante

En esta seccion mostraremos que las soluciones de (5) cerca de Pxy son periodicas.

Teorema 4.1. Cada trayectoria en el primer cuadrante del sistema Lotka-Volterra,es una orbita cerrada salvo el punto Pxy y los ejes coordenados.

Demostracion 1. Supongamos que no tenemos orbitas cerradas en el primer cua-drante.Consideremos un punto w = (x, y) ∈ R2, x > 0, y > 0 tal que w 6= Pxy. Existe unasucesion doblemente infinita ..., t−2, t−1, t0, t1, t2, ... tal que φtn(w) esta sobre la recta

x =d

c. De tal manera que cuando n tiende a infinito tn tiende a infinito y cuando n

tiende a menos infinito tn tiende a menos infinito.

Supongamos que w no pertenece a una orbita cerrada. Entonces los puntos φtn(w),

forman una sucesion monotona a lo largo de la recta x =d

c.

Si w no esta en una orbita cerrada entonces los puntos φtn(w) forman una sucesion

monotona a lo largo de la recta x =d

c.

Como el sistema (5) no tiene ciclos lımites, φtn(w) converge a Pxy cuando n tiendea infinito o φtn(w) converge a Pxy cuando n tiende a menos infinito.

Ya que H es constante sobre la trayectoria de w, concluimos que H(Pxy) = H(w).Pero esto contradice la hipotesis de que H tiene un mınimo en Pxy.

Por lo tanto, las soluciones de (5) en el primer cuadrante son trayectorias cerradas.

Ası, dada cualquier condicion inicial (x(0), y(0)), con x(0) 6= 0 y y(0) 6= 0 y diferen-te de Pxy, tenemos que las poblaciones de presas y depredadores oscilan ciclicamenteen el paso del tiempo (vease la figura 1).

5. Modelo de Volterra

Si el modelo de Lotka-Volterra lo modificamos considerando que la poblacion xcompite por espacio o alimento, entonces introducimos un nuevo termino a la primeraecuacion del sistema (5), quedando

dx

dt= x(a− by)− λx2.

De igual manera, si lo suponemos para la poblacion y, obtenemos el siguientesistema



Figura 1. orbitas cerradas

dx

dt= x(a− by)− λx2

dy

dt= y(cx− d)− µy2,

(9)

donde a, b, c, d, µ, λ, son numeros reales positivos. Aquı, λ y µ representan laproporcion de sobrepoblacion de presas y depredadores respectivamente.

Vista de otra manera se tiene:

dx

dt= x(a− by − λx) = xL(x, y)

dy

dt= y(cx− d− µy) = yM(x, y).

(10)

Para este nuevo sistema los puntos de equilibrio son:

P00 = (0, 0)

Px0 = (a

λ, 0)

P0y = (0,− d

µ)



Pxy = (x, y) = (db + µa

cb + λµ,ca− λd

cb + λµ).

Como el punto P0y no esta en el primer cuadrante, lo vamos a descartar en elanalisis.

La matriz Jacobiana de este sistema es:

J(x, y) =[

a− by − 2λx −bxcy cx− d− 2µy

].

Para determinar la dinamica local en los puntos de equilibrio observemos que

J(P00) =[

a 00 −d

].

Como los valores propios de J(P00) son a y −d, por el teorema de Hartman-Grobman tenemos que el punto de equilibrio P00 es un punto silla.

Ya que

J(Px0) =

−a −ab

λ0

ac

λ− d

los valores propios de J(Px0) son −a y

ac

λ− d.

Siac

λ− d < 0, esto es,

a

λ<

d

c, entonces el punto de equilibrio Px0 es un pozo y el

punto de equilibrio no trivial Pxy no esta en el primer cuadrante, (observe la figura2).

Siac

λ− d > 0, esto es

d

c>

a

λ, entonces el punto de equilibrio Pxo es un punto

silla y el punto de equilibrio Pxy esta en el primer cuadrante, por lo que es necesarioanalizar su comportamiento local.

Como

J(Pxy) =[−λx −bxcy −µy

]tenemos que

Tr(J(Pxy)) = −λx− µy < 0 y Det(J(Pxy)) = λµxy + bcxy < 0. Esto implica quePxy es un pozo, [1].

Para determinar el comportamiento global del sistema recurriremos al siguienteteorema para sistemas en el plano, cuya demostracion puede ser consultada en [1].



Figura 2. Atractor en Px0

Teorema 5.1. (Teorema de Dulac). Sea D ⊂ Rn, una region simplemente conexa β,

F , G ∈ C1(D). Si∂

∂x(β(x, y)F (x, y)) +

∂

∂y(β(x, y)G(x, y)) es estrictamente positiva

o estrictamente negativa en D, entonces el sistema x′ = F (x, y), y′ = G(x, y) no tieneorbitas periodicas en D.

Teorema 5.2. El sistema (10) no tiene orbitas periodicas en el primer cuadrante.

Demostracion 2. Notemos que el primer cuadrante es una region simplemente co-

nexa. Ademas, si tomamos β(x, y) =1xy

tenemos que

∂

∂x(βx′) +

∂

∂y(βy′) =

Lx(x, y)y

+My(x, y)

x= −λ

y− µ

x< 0.

Como esta ecuacion es estrictamente negativa y β ∈ C1 en el primer cuadrante D,concluimos por el teorema de Dulac que el sistema (10) no tiene orbitas periodicasen el primer cuadrante.

En resumen tenemos el siguiente resultado.

Teorema 5.3. El punto de equilibrio Pxy del sistema (10) es globalmente estable.

Demostracion 3. Del teorema 5.2 y del teorema de Poincare Bendixon, [1], conclui-mos que todas las orbitas con condicion inicial en D tienden asintoticamente al puntode equilibrio Pxy.



Figura 3. Atractor global en Pxy

6. Conclusiones

En el modelo de Lotka-Volterra todas las soluciones en el primer cuadrante son

curvas cerradas alrededor del punto de equilibrio (d

c,a

b). Esto implica que dos po-

blaciones que cumplan las hipotesis que establece el modelo (5) sus tamanos oscilanperiodicamente.

Mientras que el sistema (10) predice que si dos poblaciones cumplen con la hipotesisdel modelo, terminan coexistiendo con valores cerca del punto de equilibrio Pxy.

En ambos casos las poblaciones no se extinguen.

Referencias

[1] L. Perko, Diferential equations and dynamical systems, Springer-Verlag, 1991.

[2] F. Brauer y C. Castillo-Chavez, Mathematical Models in Population Biology and Epi-demiology, Springer-Verlag, 2000.

[3] A. J. Tromba y J. E. Marsden, Calculo vectorial, Pearson Educacion, 1998.

[4] M. W. Hirsch y S. Smale, Differential equations, dinamical systems and linear algebra,academic Press 1974.


La metrica de Levenshtein ∗

Abdiel E. Caceres Gonzalez †


La distancia de Levenshtein, tambien conocida como distancia de edicion, es unamedida frecuentemente utilizada en bioinformatica. A pesar de que fue creada a me-diados del siglo XX, y de que se han hecho implementaciones en muchos lenguajesde programacion, es difıcil encontrar referencias de una demostracion de que esta lassecuencias creadas con un alfabeto finito de sımbolos son un espacio metrico con ladistancia de Levenshtein. Determinar formalmente este espacio metrico, es util parafuturas formalizaciones en la teorıa de bioinformatica.

Levenshtein’s distance, also known as edit distance, it’s a frequently used measureon bioinformatics. Although it was created in the mid-twentieth century, and thatthere have been many implementations in many programming languages, there is nodemonstration that shown that sequences formed with some finite alphabet of symbolsforms a metric space with Levenshtein’s distance. Determine formally this metricspace, it is useful for future formalization of different works related with bioinformaticstheory.

Palabras clave: Distancia de edicion, Bioinformatica, Espacios metricos.Keywords: Edit distance, Bioinformatics, Metric spaces.

1. Introduccion

La distancia Levenshtein, conocida tambien como distancia de edicion, fue creada eimplementada por Vladimir Levenshtein a mediados del sigle XX [1], con el propositode medir la diferencia entre dos secuencias de sımbolos. Recientemente, en el campode la bioinformatica, se ha utilizado esta distancia para determinar la diferencia entresecuencias genomicas y proteomicas [3].

Desde su creacion a la fecha, se han hecho muchas implementaciones compu-tacionales de esta distancia, en diferentes lenguajes de programacion, como una im-plementacion en Perl [4]; en Java, C++ y VB [5], donde incluso, se ofrece una listade implementaciones en muchos otros lenguajes de programacion, hechas por otrosautores.

A pesar de que esta distancia ha sido estudiada, comparada, implementada y uti-lizada en muchas oportunidades, es muy difıcil encontrar referencias que demuestrenque la distancia de Levenshtein es una medida formal de distancia, de acuerdo a losparametros establecidos en topologıa. Contar con referencias tales, es importantepara crear redes de semejanza, o tambien conocidas como Latices, que determinen lasrelaciones entre diversas secuencias, considerando un criterio adecuado para manipu-lar la clase de informacion que proporcionan las secuencias de sımbolos.




36 Abdiel E. Caceres Gonzalez

En este artıculo se da una demostracion formal para determinar que la distanciade Levenshtein, denotada por D, determina un espacio metrico para el conjunto desecuencias de sımbolos creadas con un alfabeto predeterminado. Consideraremos elalfabeto C de las cadenas, que se forman de un conjunto finito de sımbolos, colocadosuno despues del otro, sin intercalar algun sımbolo que no pertenezca al alfabeto.

La distancia de Levenshtein D : C∗ × C∗ → [0, N0) como se propone en (3), esuna funcion que considera el conjunto C como generador de todas las secuenciaso subsecuencias1, el conjunto C∗ es el conjunto de secuencias finitas generadas consımbos de C; y la imagen de la funcion asocia un valor entero no negativo a cada parde secuencias.

2. Similitud entre secuencias

El concepto de similitud tiene su fundamento en la cantidad de operaciones de edicionque se requieren para transformar una secuencia en otra. Las operaciones de edicionque se consideran son insertar un sımbolo, y borrar un sımbolo2. La interpretacionde similitud debe entenderse de acuerdo a las siguientes definiciones:

Definicion 1. Sean x =< x1, x2, . . . , xn > y y =< y1, y2, . . . , ym > dos secuenciasfinitas de sımbolos en algun alfabeto finito C. y es una subsecuencia de x, denotadopor y ⊂ x, si existe un conjunto de ındices {i1, i2, . . . , im} en x, con cada 1 ≤ ik ≤ n,y 1 ≤ k ≤ m, tales que i1 < i2 < · · · < im y que y =< xi1 , xi2 , . . . , xim >.

Definicion 2. Una subsecuencia y es una subsecuencia comun para las secuenciasxa y xb, denotado por y ⊂ (xa,xb), si y ⊂ xa y y ⊂ xb.

Definicion 3. La similitud entre dos secuencias x,y ∈ C∗, denotada por S(x,y) estadada por:

S(x,y) = max{|z| : z ⊂ (x,y)}; con z ∈ C∗, (1)

donde |z| indica la longitud de la secuencia z, es decir, la cantidad de sımbolos quecontiene.

Notese que S(x,y) = 0 cuando x no tienen sımbolos comunes con y, esto es, noexiste alguna subsecuencia comun para x y y, de modo que la longitud de la secuenciavacıa es 0; en el otro extremo, S(x,y) = min{|x|, |y|} cuando o bien x esta contenidacompletamente en y, o y esta contenida completamente en x. De modo que

0 ≤ S(x,y) ≤ min{|x|, |y|}. (2)

El problema de determinar la similitud de dos secuencias, se convierte entonces,en encontrar el tamano de la subsecuencia comun mas larga entre las secuencias x yy.

1En el caso del genoma se considera el alfabeto de nucleotidos T,C,G,A; de modo similar, elproteoma tiene un alfabeto determinado de 20 sımbolos.

2Originalmente se consideraba la sustitucion como una operacion, sin embargo esta no es consi-derada porque puede crearse a partir de una insercion y un borrado


El espacio eetrico de la distancia de Levinshtein 37

El procedimiento para encontrar la subsecuencia comun mas larga, se describe conel siguiente algoritmo, que llena una matriz de orden n×m con numeros enteros queindican la similitud de cada subsecuencia. En este algoritmo se considera que |x| = ny |y| = m.

Algoritmo que encuentra la similitud de dos secuencias[2]:

S(x,y) : C∗ × C∗ → N0

1: for i = 0 to n do2: Si,0 = 03: end for4: for j = 0 to m do5: S0,j = 06: end for7: for i = 0 to m do8: for j = 0 to n do

9: Si,j =

max{Si−1,j ,Si,j−1} si xi 6= yj

Si−1,j−1 + 1 si xi = yj

10: end for11: end for12: return z = Sn,m.

3. Distancia de Levenshtein

La distancia de Levenshtein entre dos secuencias x,y ∈ C∗, con n = |x|, m = |y|,esta definida como:

D(x,y) = n + m− 2S(x,y), (3)

donde S(x,y) es la similitud entre las secuencias x y y. Los lımites de esta distanciase logran, por un lado cuando la similitud entre las secuencias comparadas es nula, yen el otro extremo, cuando la similitud entre las secuencias comparadas es maxima.Cuando la simlitud es nula (secuencias sin sımbolos comunes), la distancia es n + m.Cuando la similitud es maxima (se comparan secuencias iguales), la distancia es 0.

0 ≤ D(x,y) ≤ n + m (4)

La idea general de esta distancia es que dos secuencias distan entre sı tanto comosımbolos se deban borrar y sımbolos se deban agregar, para hacer iguales ambassecuencias. De modo que el lımite maximo de esta distancia se debe leer como: sedeben borrar todos los n sımbolos de x y agregar todos los m sımbolos de y.

Tanto las funciones de distancia como la de similitud se encuentran definidas en[2], donde se hace un estudio de la complejidad algorıtmica de este procedimiento,aunque las lıneas 7 - 11 del algoritmo sugieren que la complejidad es O(n2) paraencontrar la similitud, y Θ(1) para encontrar la distancia3.

3Recordemos que O(f(n)) dice que existe una funcion f(n) que acota superiormente el tiempode ejecucion del algoritmo, y Θ(1) dice que el tiempo de ejecucion del algoritmo (para encontrar ladistancia en este caso) es constante. Para un estudio mas profundo sobre funciones asintoticas paraacotar comportamientos algorıtmicos, consulte la referencia [2].



4. El espacio metrico de las secuencias

Sea C∗ el conjunto de todas las secuencias validas de longitud finita4; y sea tambienD como la definida en (3).

Teorema 1. El par (C∗,D) es un espacio metrico.

Prueba. Para probar que la distancia D sea una metrica sobre C∗, se debe cumplir:

1. D(x,y) ≥ 0 ∀x,y ∈ C∗.

2. D(x,y) = 0, si y solo si x = y ∀x,y ∈ C∗.

3. D(x,y) = D(y,x) ∀x,y ∈ C∗.

4. D(x,y) +D(x, z) ≥ D(y, z) ∀x,y, z ∈ C∗.

Es bueno recordar que el conjunto de puntos propuesto esta determinado porC∗ = {x|x = (xi)0≤i<∞, xi ∈ C}, es el conjunto de secuencias finitas en C, por ejemploC = {T, C, G, A}, para el caso del genoma.

4.1 D(x, y) ≥ 0 ∀x, y ∈ C

Si x =< x1, . . . , xn > y y =< y1, . . . , ym >, la distancia propuesta es |x| + |y| −2S(x,y), como 0 ≤ S(x,y) ≤ min{|x|, |y|},

si S(x,y) = |x|, entonces |y| > |x| y

D(x,y) = |x|+ |y| − 2|x|,= |y| − |x|,≥ 0.

si S(x,y) = |y|, entonces |x| > |y| y

D(x,y) = |x|+ |y| − 2|y|,= |x| − |y|,≥ 0.

si S(x,y) = |y| = |x|, entonces

D(x,y) = |x|+ |x| − 2|x|,= |y|+ |y| − 2|y|,= 0.

4.2 D(x, y) = 0 si y solo si x = y

1. Si D(x,y) = 0 entonces x = y.

Como D(x,y) = 0, entonces |x|+ |y| = 2S(x,y)

4Bien pueden ser genomas, proteomas, o partes de ellos.



Si x = λ (la palabra nula), entonces |x| = 0, de modo que |y| = 2S(λ,y) debe conser-varse. Esto hace que |y| = 0, puesto que la S(λ,y) es cuando mucho la cardinalidadde la secuencia de menor longitud, y esta es λ, con |λ| = 0. Si |y| = 0, entoncestambien y = λ y ası x = y.

Por otro lado, si ninguna de las secuencias es nula, aun debe conservarse la igualdad|x|+ |y| = 2S(x,y).

Supongamos ahora que x ⊂ (x,y), esto es, x es la subsecuencia comun mas grandede las secuencias x y y. Entonces, |x|+ |y| = 2|x|, y para que esto ocurra, |x| = |y|.Como x ⊂ y, todos los sımbolos de x ocurren en y en las mismas posiciones, estosignifica entonces que x = y.

2. Si x = y entonces D(x,y) = 0. Observese que, |x| = |y|. Como ambas secuencias soniguales, S(x,y) = n

|x|+ |y| − 2S(x,y) = n + n− 2n,D(x,y) = 0.

4.3 D(x, y) = D(y, x) ∀x, y ∈ C∗

Tomese δ ⊂ (x,y) : |δ| = S(x,y), con δ =< δ1, . . . , δn >. Como δ es una subsecuenciade x, existe un conjunto {i1, . . . in} de ındices en x, con cada 1 ≤ ik ≤ |x| y 1 ≤ k ≤ n,tales que i1 < · · · < in y que δ =< xi1 , . . . , xin >.

Pero debido a que δ tambien es una subsecuencia de y, se puede dar un conjunto{j1, . . . , jn} de ındices en y, con cada 1 ≤ jk ≤ |y| y 1 ≤ k ≤ n, tales que j1 < · · · < jn

y que δ =< yj1 , . . . , yjn>. Ası que

n = |δ| = S(x,y) = S(y,x). (5)

De tal modo queD(x,y) = |x|+ |y| − 2S(x,y),

= |x|+ |y| − 2S(y,x),= |y|+ |x| − 2S(y,x),= D(y,x).

4.4 D(x, y) + D(y, z) ≥ D(x, z)

|x|+ |y| − 2S(x,y) + |y|+ |z| − 2S(y, z) ≥ |x|+ |z| − 2S(x, z)2|y| − 2S(y,x)− 2S(y, z) ≥ −2S(x, z)|y| − S(y,x)− S(y, z) + S(x, z) ≥ 0 (6)

Se probara (6). Sean:

α =< α1, α2, . . . , α|α| >: α ⊂ (x,y) y |α| = S(x,y).β =< β1, β2, . . . , β|β| >: β ⊂ (y, z) y |β| = S(y, z).

Como α ⊂ (x,y), entonces α se puede expresar con sımbolos de x y de y:

α =< xp1 , . . . , xp|α| >=< yq1 , . . . , yq|α| >, (7)



para algun conjunto de ındices {p1, . . . , p|α|} en x y algun conjunto de ındices{q1, . . . , q|α|} en y.

Del mismo modo

β =< yr1 , . . . , yr|β| >=< zs1 , . . . , zs|β| > (8)

para algun conjunto de ındices {r1, . . . , r|β|} en y y tambien algun conjunto de ındices{s1, . . . , s|β|} en z.

Se observa que |α| ≤ |y| y del mismo modo |β| ≤ |y|. Como ambas subsecuencias αy β tienen sımbolos de la secuencia y, entonces existe una subsecuencia δ ⊂ y dondeδ =< δ1, . . . , δ|δ| >: |δ| = S(α, β). Por (7) y (8), es posible escribir δ con sımbolos dex y de z.

δ =< xm1 , . . . , xm|δ| >=< zn1 , . . . , zn|δ| >, (9)

con |δ| ≤ min{|α|, |β|}. De modo que δ ⊂ (x,y), porque α ⊂ x y β ⊂ y; tambien esδ ⊂ (y, z), aunque no necesariamente la de mayor longitud, de modo que |δ| ≤ S(x, z).Entonces |α| representa la cantidad de sımbolos que comparten las secuencias x y y,|β| es la cantidad de sımbolos que comparten las secuencias y y z, y |δ| es la cantidadde sımbolos que pertenecen a y solamente.

Ası, |α| + |β| − |δ| es la cantidad de sımbolos de y que son compartidos con lassecuencias x y z, significa que |y| ≥ |α|+ |β| − |δ|, en consecuencia

|y| − |α| − |β|+ |δ| ≥ 0.

Como |δ| ≤ S(x, z), |α| = S(x,y) y |β| = S(y, z), se verifica (6):

|y| − S(x,y)− S(y, z) + S(x, z) ≥ 0.

5. Algoritmo k-means para agrupar secuencias genomicas

La distancia de Levenshtein es util en muchas aplicaciones, entre ellas, en el campo dela bioinformatica. En este apartado se describe un algoritmo que utiliza la distanciaLevenshtein para agrupar individuos que son caracterizados por su secuencia de ADN,mediante el clasico metodo de agrupamiento conocido como k-means.

El agrupamiento mediante el metodo k-means, fue desarrollado J. MacQueen(1967) [6] y posteriormente por J. A. Hartigan y M. A. Wong [7] al rededor de 1975.De manera simple, el algoritmo k-means sirve para clasificar objetos basados en susatributos en k grupos. k es un numero entero positivo. La agrupacion se realiza alminimizar la suma de los cuadrados de las distancias entre los datos y su centroidecorrespondiente, con el proposito de clasificar los datos.

En la figura 1 se muestra una secuencia de actividades que se desarrollan parallevar a cabo el algoritmo k-means.



Figura 1. Diagrama de flujo que muestra el desarrollo del algoritmo k-means.

1. En primer lugar se determina k, el numero de centroides, que a la postre conformarank grupos con los n indivıduos.

2. Se seleccionan los k individuos que serviran como centroides. En este ejemplo se hancoleccionado individuos que tienen un codigo genetico de 60 cromosomas5. La longitudde 60 para los cromosomas, se eligio arbitrariamente.

3. Cada individuo debe reconocer cual es el centroide mas cercano, para realizar estose determina D(x, c), para todos los individuos x y los centroides c, y eligiendo comocentroide mas cercano, aquel que hace

cnearest(x) = min{D(x, ci) : 1 ≤ i ≤ k}

4. Cada centroide forma de este modo una particion del conjunto de individuos. Todoslos elementos de cada parte tienen en comun que son mas cercanos al centroide elegidoque a cualquier otro.

5. Si los centroides elegidos fueron elegidos de tal modo que se requiere agrupar a otrosindividuos en torno a ellos, este algoritmo puede terminar. Sin embargo, en la versionoriginal del algoritmo, se desea agrupar individuos sin un conocimiento a priori dequienes deben ser los centroides. De modo que se toma la decision de seleccionar unnuevo centroide. Para cada grupo, se elige como nuevo centroide aquel individuo quehaya mostrado una diferencia menor entre la distancia a su centroide y el promediomuestral de las distancias. Esto hace que el nuevo centroide sea el que este mascercano al centro de masa del cumulo. Si no hubo cambios en la eleccion del nuevocentroide, el algoritmo termina; de otro modo, se vuelve al paso 2 para una nuevaiteracion.

5Teoricamente es posible con cualquier numero de cromosomas, sin embargo a medida que eltamano del genoma crezca, los recursos computacionales aumentan rapidamente.



Figura 2. Agrupacion de individuos considerando el parecido de su codigo genetico. Se han

establecido 10 centroides con 210 individuos.

Debido a que se utiliza la distancia Levenshtein, es irrelevante la posicion de losindividuos en el plano euclideano (figura 2: izquierda), de modo que se ha elegidodistribuir los centroides en la periferia de un cırculo, de modo que sean facilmentedistinguibles a la vista.

Los individuos son agrupados considerando la distancia Levenshtein (figura 2:derecha), y los grupos son visualmente representados utilizando el plano euclideano.

6. Discusion final

La metrica de Levenshtein es una herramienta que permite adquirir conocimientoacerca de las secuencias de sımbolos comparadas. Comparar secuencias extremada-mente largas como las secuencias genomicas, requiere tratamientos especiales a losalgoritmos utilizados. Esto ocurre por el crecimiento cuadratico del tiempo de eje-cucion asintotico del algoritmo para obtener la distancia de Levenshtein.

El problema que representan las secuencias sumamente grandes, implica un prob-lema de espacio (al guardarlas en la memoria de una computadora, o al escribirlasen un papel), de modo que se puede disenar modificaciones a esta metrica, con el finde para determinar la distancias parciales de una subsecuencia con otra, ambas delongitud manejable.

Alternativamente, es una oportunidad para utilizar clusters de computadoras paraque, con los recursos compartidos, sea posible manipular secuencias enormes.

7. Agradecimientos

Est artıculo ha sido apoyado financieramente por el PROgrama de Mejoramiento delProfesorado (PROMEP), bajo el proyecto numero PROMEP-20080798.



Referencias

[1] V. I., Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals.Soviet Physics Doklady 10 (1966):707710. Traduccion al ingles de la version original enruso publicada en 1965.

[2] T. H. Cormen, C. E. Leiserson, y R. L. Rivest. Introduction to Algorithms. MIT Press,Boston, MA., 1990.

[3] Neil C. Jones y Pavel A. Pevzner. An Introduction to Bioinformathics Algorithms. TheMIT Press, 2004.

[4] Yona, S. Edit Distance and string matching algorithms. Enconferencia dada en enero de 2004. Datos disponibles enhttp://mila.cs.technion.ac.il/∼yona/talks/edit distance/slides/index.html.Visitado en Octubre de 2008.

[5] Gilleland, M. Levenshtein Distance, in Three Flavors. Recurso de internet. URL enhttp://www.merriampark.com/ld.htm. Visitado en Octubre de 2008.

[6] MacQueen. J. B. Some Methods for classification and Analysis of Multivariate Observa-tions, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probabil-ity, Berkeley, University of California Press, 1:281-297 (1967).

[7] Hartigan, J. A. y Wong, M.A. Algorithm AS 136: A k-means clustering algorithm, Ap-plied Statistics 28 (1979), no.1, 100108.


La Revista de Ciencias Básicas UJATvolúmen 7 número 2, diciembre de 2008, se imprimió en

Impresiones en Gráficos Cánovas S.A. de C. V.Juan Álvarez 505 Centro. C.P. 86000.

Villahermosa, Tabasco, MÉXICOTerminó la edición de esta obra el 26 de noviembre de 2008

con un tiraje de 300 ejemplares

DIRECTORIO

M.A. Candita Victoria Gil JiménezRectora

M.P.E.S. María Isabel Zapata VásquezSecretaria de Servicios Académicos

Dr. José Manuel Piña GutiérrezSecretario de Servicios Administrativos

L.C.P. Marina Moreno TejeroSecretaria de Finanzas

Dr. Víctor Castellanos VargasDirector de Investigación y Posgrado

M. en C. Carlos Rogelio Beltrán MohaDirector de la División Académica de Ciencias Básicas

revista ciencias basicas ujat v7n2 dic-2008

Documents