正规树文法的产生式相交判定

在针对产生式不相交的正规树文法的XML类型检查中,需要对正规树文法的产生式进行相交判定。基于正规树文法的产生式的构成特点,提出了基于自动机的相交判定算法。根据产生式的内容模型即正则表达式,构建相应自动机,判定两个自动机的交是否为空,该算法的时间复杂度为O(‖E1‖.‖E2‖.|∑E1∪∑E2|)。实验结果表明,该算法运行正确且高效,可以应用到针对产生式不相交的正规树文法的XML类型检查中。

基于规则推导的正规式相交判定算法

正规式相交判定问题在扩展标记语言(extensible markup language,XML)类型检查中起着十分重要的作用。传统方法是将其转化为自动机的相交问题,在转化过程中会产生大量计算。基于XML模式语言的特点,提出了一种基于规则推导的正规式相交判定算法。该算法直接根据输入的正规式进行推导而无需进行任何转化计算。对于一般的正规式,尽管其仍然是指数级算法,但无需进行复杂的构造自动机的计算;而对于一些特殊的正规式,特别是在XML类型检查中广泛使用的One-Unambiguous正规式,该算法的时间复杂度降为多项式级。最后证明了该算法所使用的推导规则的正确性和完备性。

隐私保护的四方判定线段是否相交协议

鉴于目前已有的隐私保护的线段相交判定协议的参与方都是两方,不能解决多方之间判定线段是否相交的问题,因此提出了一个隐私保护的四方相互合作判定线段是否相交的协议。4个参与方各自拥有线段的一个端点,采用安全多方计算中的一些基础运算协议,通过两两计算,判定由这4个端点构成的两条线段是否相交,同时确保不会向其它的参与方泄漏线段以及端点的信息。最后给出了该协议在现实中的一个应用。

块体理论中结构面相交算法优化研究

针对传统块体理论中结构面无限延伸的假定和部分有限结构面理论的不足,提出了一种新的结构面相交关系的判定方法。在结构面有限延伸的前提下,选择结构面圆盘模型进行分析。在判定两结构面是否相交的计算中,回避了线段与圆形直接求交的困难,选择投影法,即求得两结构面交线矢量的法平面,根据法线在法平面投影为一点、圆形域在对应法平面投影为线段的特点,分别计算垂足和两圆心投影点的距离并与圆形域半径进行比较,分析交线和圆形结构面域的包含关系,进而对结构面相交与否进行判断。并利用此原理提出了块体分析工作中野外实测结构面的筛选方法,经由判别矩阵的筛选,剔除原无限块体理论不能分辨的、实际延伸很短、并不与其他结构面相交,或虽与其他结构面相交,但对形成块体没有贡献的结构面。新算法简化了块体计算的工作量,大大提高了效率,对结构面数据量大的块体分析工作尤为明显。

基于傅里叶逆变换的土石混合体模型生成研究

针对土石混合体结构模型内部块石形态过于简单且无法对模型本身参数进行敏感性分析的现状,提出了一种新的土石混合体结构模型生成方法。首先,采用回归分析法建立傅里叶描述因子和块石形状参数之间的函数关系式,并通过傅里叶逆变换法生成具有特定形状的块石轮廓。接着,基于各粒径块石组面积相等的原则,推导出了指定面积级配曲线下各粒径组块石的个数,并利用拟采样法得到各块石对应的面积。再次,根据包围盒相交判定原理等,提出了块石相交判定算法,实现了块石的随机投放。最后,改变土石混合体模型结构参数,如含石量、粒径级配曲线和块石空间方向角等,生成具有特定块石形状的土石混合体随机结构模型并进行可行性验证。验证表明:该法可以重构出具有特定形状特征的块石轮廓,能生成满足计算精度要求的土石混合体随机结构模型,这为后续进行含石量、粒径级配曲线和块石形状等参数对土石混合体材料性能影响规律研究奠定了基础。