超立方体计算机上的平面凸壳算法

给出了在超立方体结构的计算机上，求平面点集的凸壳的一个算法，并分析了算法的正确性和时间复杂性。     

用于成对PPI网络比对的分治与整合算法

生物网络比对是分析不同生物间进化关系的重要手段,它可以揭示不同物种间的保守功能并为物种间的注释转移提供重要信息。网络比对与子图同构类似,是一个NP-hard问题。本文提出了一种新的分治与整合策略的生物网络比对算法。首先进行模块划分,并根据已有的比对信息计算模块相似性;然后根据模块间结点的子比对获取候选结果集,最终通过超图匹配获得比对结果。使用已有的比对信息的集体行为预估模块间的相似性,大大提高了模块匹配的效率。基于路径和结点的得分函数保证了模块内结点的相似性。对于不同网络间结点的相似性,分别从结点自身和结点间的差异进行相似性判断。与现有算法相比,本文算法在生物和拓扑指标上均表现最佳。     

平面最接近点对算法

描述了平面最接近点对问题,针对这一问题给出了3种算法,循环遍历算法、分治算法和平面扫描算法,并详细分析了3种算法的时间复杂度.     

基于地图划分的选址方法

无线基站、公共设施等的选址问题是关系到其能否发挥到最大效用的问题,在无线通讯、城市规划等领域十分重要。论文利用地图划分理论,充分考虑选址时应注意的覆盖城市路口点数、覆盖城市范围和城市密度梯度等因素,给出一种实用的基于地图划分的选址方法和算法实现。论文以无线基站选址为背景,阐明该算法在满足基站选址的必要条件和可选条件下,采用自适应分治地图的策略,求出无线基站在地图上的分布情况,从而达到有效指导选址的目的。算法思想主体包括三步:分治地图,考察约束条件,以及选址。论文利用上海城市电子地图进行了算法实验,取得较好的效果。     

基于分治的背包问题DNA计算机算法

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2\\+\\{q/2\\}),其中q为背包问题的维数.与最近文献结论进行的对比分析表明：算法将求解背包问题所需的DNA链数从O(2\\+q)减少至O(2\\+\\{q/2\\}),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.     

带复杂计算的金融领域自然语言查询的SQL生成

研究金融领域基于自然语言查询的结构化查询语言(SQL)生成问题(Text-to-SQL), 构建一个金融领域Text-to-SQL数据集,称为SOFT数据集. 该数据集覆盖了金融领域的常见查询,具有鲜明的特点,并对Text-to-SQL提出了挑战. 提出金融领域Text-to-SQL模型FinSQL,该模型优化了对金融领域复杂查询的支持. 通过分析一类复杂计算查询（行计算查询）的特点,提出一种基于分治的方法,即先将一个行计算查询分解为若干个子查询,分别针对每个子查询生成SQL语句,再将子查询的SQL语句组合在一起得到原始查询的SQL语句. 在SOFT数据集上进行验证,结果显示,本研究所提的方法在复杂查询上效果优于已有方法. 特别地,所提出的模型FinSQL能够较好地支持行计算查询.     

Classification trees with bivariate splits

We extend the recursive partitioning approach to classifier learning to use more complex types of split at each decision node. The new split types we permit are bivariate and can thus be interpreted visually in plots and tables. In order to find optimal splits of these new types, a new split criterion is introduced that allows the development of divide-and-conquer type algorithms. Two experiments are presented in which the bivariate trees—both with the Gini split criterion and with the new split criterion—are compared to a traditional tree-growing procedure. With the Gini criterion, the bivariate trees show a slight improvement in predictive accuracy and a considerable improvement in tree size over univariate trees. Under the new split criterion, accuracy is also improved, but there is no consistent improvement in tree size.Much of this work was completed while the author was an employee of AT&T Bell Laboratories.     

A GLOBAL FLOOR PLANNING TECHNIQUE FOR VLSI LAYOUT

Over the years, many CAD tools for VLSI macrocelf design have become available that automatically perform some of the physical synthesis phases to reduce development costs. Although floor planning imposes global constraints on the quality of the final layout, state-of-the-art tools do not completely support floor planning synthesis. A new floor planning method for macrocell layout style is presented. The floor plan state space is characterized by an equivalence relation to apply efficient solution techniques. A new pseudo-polynomial area optimization algorithm is proposed that derives from a given hierarchical floor plan tree the optimal slicing tree. The order of this floor plan tree is at least 2 and at most 5. Extensions of this approach to cover non-slicing floor plans are also described. Since floor planning and routing are interdependent tasks, an improved dynamic updating scheme is proposed to consider the interconnection area around each cell during the floor plan assembly. The method has been successfully applied to an industrial design with about 260,000 transistors.     

Using euler partitions to edge color bipartite multigraphs

An algorithm for finding a minimal edge coloring of a bipartite multigraph is presented. The algorithm usesO(V ^1/2 ElogV + V) time andO(E + V) space. It is based on a divide-and-conquer strategy, using euler partitions to divide the graph. A modification of the algorithm for matching is described. This algorithm finds a maximum matching of a regular bipartite graph with all degrees 2ⁿ, inO(E + V) time andO(E + V) space.This work was partially supported by the National Science Foundation under Grant GJ36461.     

插值三次B样条曲线的并行计算

三次Ｂ样条曲线是计算机图形学和ＣＡＧＤ中最常用的曲线描述工具。本文采用分治策略，对插值三次Ｂ样条曲线进行了并行计算，并讨论了插值问题的并行效率。