在MIMD—CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数。在该算法的基础构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ２（ｎ＋ｍ）ｌｏｇ２（ｎ＋ｍ）／ｌｏｇ２Ｓ），其中Ｓ为处理机个数。     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

寻找最小生成树的度优先算法

利用Ｋｒｕｓｋａｌ和Ｐｒｉｍ算法的优点，从图的每个顶点的度数入手，采取删除某些无用边的思想方法，给出了一个寻找最小生成树的算法。算法的最坏复杂度为Ｏ（ｍ－ｎ）ｌｏｇｍ），平均复杂度为Ｏ（（ｍ－ｎ）ｌｏｇｎ），就复杂度的常数因子而言，均优于Ｋｒｕｓｋａｌ算法与ｋｉｍ算法，其中ｍ为图的边数，ｎ为图的顶点数。     

识别非环的数据库模式的一组分布式算法

各种非环的数据库模式有许多好的性质，特别是在分布式环境中，研究关系数据库的非环性程度是一个重要的课题，对Ａｌｐｈａ Ｂｅｔａ，Ｇａｍｍａ，Ｂｅｒｇｅ这几各非环数据库模式，我们给出一组颁式算法，该算法的最坏消息复杂度是Ｏ（／Ｎ／），而最坏时间复杂度是Ｏ（／Ｎ／＾２），／Ｎ／是给定的网络中结点的个数。     

判定凸多边形可碰撞性的并行算法

设Ｐ与Ｑ是平面内任意两个互不相交的凸多边形，为任一给定方向，研究并行判定Ｐ沿以平移方式移动可与Ｑ碰撞的问题。采用Ｓ分搜索策略，在ＭＩＭＤ－ＣＬ模型上给出了求解此问题的并行算法，并证明了算法的正确性．最坏情况下，在超立方结构上算法的时间复杂度为Ｏ（ｌｏｇ＿２（ｍ＋ｎ）），通讯复杂度为Ｏ（ｅｌｏｇ＿２（ｍ＋ｎ）／ｌｏｇ＿２Ｓ）     

判定凸多边形可碰撞性的并行算法

设Ｐ与Ｑ旬平面内任意两个互不相交的凸多边形，ｄ为任一给定方向。研究并行判定Ｐ沿ｄ以平移方式移动与Ｑ碰撞的问题，采用Ｓ分搜索策略，在ＭＩＭＤ－ＣＬ模型上给出了求解此问题的并行算法，并证明了算法的正确性。最坏情况下，在超立方结构上算法的时间复杂度为Ｏｌｏｇ２（ｍ＋ｎ），通讯复杂度为Ｏ（ｅｌｏｇ２（ｍ＋ｎ）／ｌｏｇ２Ｓ）。     

BSC（2^m,2^n）密码的递归表示与双对称性证明

在已有研究成果的基础上,进一步研究了双对称密码ＢＳＣ（２＾ｍ,２＾ｎ）算法设计,给出了ＢＳＣ（２＾ｍ,２＾ｎ）算法的递归表示,并严格证明了ＢＳＣ（２＾ｍ,２＾ｎ）密码是双对称的。     

A Clas of Distributed Recognition Algorithms for Acyclic Database Schemes

各种非环的数据库模式有许多好的性质，特别是在分布式环境中，研究关系数据库的非环性程度是一个重要的课题．对Ａｌｐｈａ，Ｂｅｔａ，Ｇａｍｍａ，Ｂｅｒｇｅ这几种非环数据库模式，我们给出一组分布式算法．该算法的最坏消息复杂度是Ｏ（｜Ｎ｜２），而最坏时间复杂度是Ｏ（｜Ｎ｜２），其中｜Ｎ｜是给定的网络中结点的个数．     

求解货郎担问题的几何算法

提出了求解货郎担问题的一种几何算法，它的时间复性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次求距离运算与Ｏ（ｎ＾３／ｍ＾３）次加法运算，其中ｎ，ｍ分别为点集的点数和凸包顶点数。     

逻辑堆与树排序

树排序算法是堆排序算法的变体，本文给出了逻辑堆的结构并将其应用于树排序算法中使得树排序算法的最坏复杂度由原来的４ｎｌｏｇｎ＋Ｏ（ｎ）降低到２ｎｌｏｇｎ＋Ｏ（ｎｌｏｇｌｏｇｎ）＋Ｏ（ｎ），接近于最优堆排序算法（复杂度为ｎｌｏｇｎ＋ｎｌｏｇｌｏｇｎ＋Ｏ（ｎ），并且对几乎已有序的输入，算法的复杂度为Ｏ（ｎｌｏｇｌｏｇｎ），这在ｎ＜２１８的实际应用中基本保持了原树排序算法的优势．