一个基于异构型局域网的雕塑实体布尔操作并行算法

为了在某些限时操作下得到实时交互的速度 ,提出了一个分布式的雕塑实体模型布尔操作并行算法 .该算法在各个阶段抽取的并行性和原串行算法的拓扑相关性之间采取了折中的策略 ,并对于不同的并行任务 ,采用了不同的任务均衡手段 .该算法已经在一个由 10台 P /35 0微机和由 5台 SGI O2工作站组成的异构型局域网上得到实现 .实验结果显示 ,该算法获得了理想的加速比 ,对于复杂雕塑实体的造型 ,操作平均可在 3s～ 4 s完成 ,因此能满足实时交互的需要 .     

雕塑实体的精确求交算法

提出了一个雕塑实体布尔操作中的精确求交算法．为了确保算法的高效率、精确性和鲁棒性,采用了先确定拓扑、再跟踪的策略来进行曲线－曲面求交,以及层次求交和交线跟踪的方法,来保证裁剪曲面片分割和区域分类的一致性,从而克服实践中常见的退化情况．该算法已经在一个基于Ｗｉｎｄｏｗｓ／ＮＴ平台的雕塑实体造型器ＴｉｇｅｒＳｕｒｆ上实现,并通过大量造型实体实例的测试．     

一个雕塑实体的布尔操作算法

给出了一个雕塑实体布尔操作的现实算法,在保证效率和精确性的同时确保鲁棒性是算法的目标,实体模型通过裁剪曲面片和半边数据结构来表达几何和拓扑信息。采用了层次求交和交线跟踪的方法来保证曲面片分割和区域分类的一致性,从而克服实践中常见的退化情况。该算法也可以方便地扩展到非流形模型的布尔操作。作为一个实体造型系统的一部分,该算法已经在ＳＧＩ工作站上实现。     

采用配置完成优先策略的可重构任务调度算法

如何隐藏和减少配置时间是相依性可重构任务调度的关键问题.提出一种采用配置完成优先策略的相依性可重构任务调度算法,通过基于预配置优先级的列表调度算法,实现将后续任务的配置时间隐藏于前驱任务的运行时间中,并采用基于配置完成优先策略的配置重用机制,减少了任务调度后的配置过程,从而在总体上缩短了相依性任务集合的运行时间.仿真结果表明,该调度算法能有效避免调度死锁,并可减少相依性可重构任务的整体运行时间.     

多信息加权融合实体对齐算法

针对已有实体相似度计算方法在实体对齐任务上准确率较低的问题,提出一种多信息加权融合实体对齐算法.分别采用动态规划求解最小编辑距离及Doc2 vec模型训练文本获取包含语义信息的特征向量等方法,对实体的结构化属性及非结构化文本进行相似度求解;通过加权平均获取实体综合相似度,完成实体对齐任务.对比实验表明,所提出算法有效提高了实体对齐的准确率,并具有更好的算法迁移性.     

LVS集群中的动态反馈调度算法

提出了动态反馈算法,该算法需要监视和评估各个服务器的当前负载,然后依此选出一台服务器去处理新的任务。测试结果表明,相比其它调度算法,动态反馈算法能够更好地完成负载均衡的任务。采用动态反馈算法,能使系统具有错误冗余的功能。     

雕塑曲面型腔粗加工刀位轨迹生成算法

在深入研究复杂形状雕塑曲面型腔的粗加工的基础上，提出一种合理的平面样本刀位轨迹生成方法和回避凸台的刀位轨迹裁剪技术，给出了型腔粗加工刀位轨迹生成算法，该算法具有稳定、高效的特点，可用于压铸模具加工生产。     

基于GPGPU的实体表面实时提取

为实时提取三维实体表面,提出一种基于GPGPU并行计算的实体表面实时提取方法。在分析深度剥离算法原理和GPU图形绘制管线的基础上,给出在GPU上利用深度剥离算法实现实时提取三维实体表面的算法;通过OpenGL的高级着色语言GLSL控制GPU的图形绘制管线实现了该算法,给出其伪代码。以龙、叶轮和刀具扫描体的模型为应用实例验证了该算法效果良好,特别是对于刀具扫描体表面的提取,可满足实时性要求。     

云环境下基于任务分类和LPM优化模型的调度算法

针对用户任务预算不足或期望完成时间较短,云服务方无法保障任务全部完成,提出基于任务分类和线性规划优化模型调度策略,使任务完成数最大化,同时考虑任务重要性。算法根据任务长短及重要性进行分类,然后建立任务计算资源关系矩阵及3个相关约束条件,以任务完成数最大化为目标函数,搭建线性规划模型,并给出算法实现。模拟实验表明,在同样的用户任务预算和期望完成时间条件下,该算法任务完成数最大值明显高于经典算法。     

自适应多分辨图像跟踪算法

针对实时图像跟踪中目标尺度不断变化的问题,提出了一种新的最大后验概率指标下尺度自适应的多分辨图像跟踪算法.首先证明了后验概率指标的像素级计算特性,在该特性的基础上提出了一种最大后验跟踪算法.由于后验概率指标不仅可以按照特征进行计算,还可以按照像素进行计算,从而可以方便地实现不同尺度上的像素相似度贡献值的计算和比较,据此提出了一种新的目标尺寸自适应算法.此外,当目标尺寸较大时,可以采用不同的分辨率来计算候选匹配区域的匹配概率值,大大降低计算量,从而保证实时跟踪的时间需求.综合上述特点,给出了最大后验概率指标下目标尺寸自适应的多分辨图像跟踪算法.多组视频跟踪实验结果表明了本算法的有效性.     

一种长序列小波变换的快速实现方法

在对Mallat算法结构进行改进的同时，将长序列快速卷积算法中的重叠保留法引入Mallat算法中，提出了一种适合长序列小波变换的快速算法，给出了数学推导过程和具体实现步骤。该方法大大降低了小波变换的计算量，且并行性很好。仿真实验结果验证了算法的正确性。且运算速度较直接线性卷积实现方法有很大提高。     

K-median问题贪心近似算法的分析与实验

讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法,证明该算法的近似度为O(ln(n/k)),通过实验证明该贪心算法在实际应用当中可以取得较好的效果,大约有90%的客户能被距离其最近、次近和第三近的设备服务。     

计算两凸多边形交集面积的计算机算法

该文提出了计算两凸多边形交集面积的新的计算机算法。算法设计的思路简单,易于实现,实际应用中具有鲁棒性（ｒｏｂｕｓｔｎｅｓｓ）。     

Comments on ‘Parallel procedure for the design of observers in high-order multivariable systems’

Shafai (1988) proposed a state observer design algorithm which is very slightly different from an earlier algorithm of Tsui (1985). Furthermore, the change made by Shafai severely worsens the parallel computation property, the only key property of his algorithm claimed by Shafai. It is important to mention that this comment is obviously valid for the dual version of Shafai's algorithm (state feedback design for pole assignment), which has appeared elsewhere several times recently.     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

Distributed Symbolic Bounded Property Checking

In this paper we describe an algorithm for distributed, BDD-based bounded property checking and its implementation in the verification tool SymC. The distributed algorithm verifies larger models and returns results faster than the sequential version.The core algorithm distributes partitions of the state set to computation nodes after reaching a threshold size. The nodes proceed with image computation on the nodes asynchronously. The main scalability problem of this scheme is the overlap of state set partitions. We present static and dynamic overlap reduction techniques.     

参数可调的克隆多播路由算法

近年来,时延受限的代价最小多播树问题备受关注.到目前为止,BSMA(bounded shortest multicast algorithm)算法被认为是最好的受限多播路由算法;然而,过长的计算时间限制了其应用.作为一种全局优化算法,遗传算法(genetic algorithm,简称GA)被越来越多地应用于多播路由问题.与传统的算法相比,遗传算法的全局搜索能力更强,但其易"早熟"的特点使它并不总是能得到最优多播树.提出的基于克隆策略的多播路由算法,有效地解决了"遗传"多播路由算法中的"早熟"问题,并通过引入一个可调因子缩小了搜索空间,加快了算法的收敛速度.算法实现简单、控制灵活.仿真结果表明,该算法的性能优于BSMA算法和传统的遗传算法.     

Testing 2-asummability using a property of canonical extremal vertices

An interesting property of canonical extremal vertices of a switching function is obtained. Use of this property for testing of 2-asummability requires very little computation, and thus a fast algorithm can be developed.     

A Mechanically Checked Proof of a Multiprocessor Result via a Uniprocessor View

We describe a mechanically checked correctness proof for a system of n processes, each running a simple, non-blocking counter algorithm. We prove that if the system runs longer than 5n steps, the counter is increased. The theorem is formalized in applicative Common Lisp and proved with the ACL2 theorem prover. The value of this paper lies not so much in the trivial algorithm addressed as in the method used to prove it correct. The method allows one to reason accurately about the behavior of a concurrent, multiprocess system by reasoning about the sequential computation carried out by a selected process, against a memory that is changed externally. Indeed, we prove general lemmas that allow shifting between the multiprocess and uniprocess views. We prove a safety property using a multiprocess view, project the property to a uniprocess view, and then prove a global progress property via a local, sequential computation argument. Our uniprocessor view is a formal compositional semantics for a shared memory system.