基于不变式生成的循环停机性验证

循环的停机性验证是程序验证中的一个难点。程序不变式用来描述程序变量的取值关系,其中线性不变式可以帮助描述程序变量间的线性关系,循环不变式能够有效刻画循环中的变量关系。本文基于线性不变式和多项式循环不变式的生成,将循环的停机性验证转化为求解一个最优化问题,给出了一个实用的程序停机性验证框架。基于该框架可以自动地验证程序的停机性,并给出循环的复杂度上界。实验结果说明了该方法的实用性。     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

An improved algorithm for finding the median distributively

Given two processes, each having a total-ordered set ofn elements, we present a distributed algorithm for finding median of these 2n elements using no more than logn +O(logn) messages, but if the elements are distinct, only logn +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 logn messages.     

基于样本熵与时频分析的手部抓握运动意图预测

针对上肢外骨骼控制信号产生与外部设备响应存在时间滞后导致脑机接口(BCI)系统实时性差的问题,采集被试手部自主抓握前运动相关皮质电位(MRCP) ,提出基于非线性复杂度特征样本熵 (SampEn)与线性幅值特征融合算法的手部运动意图预测方法. 从时频、神经复杂度分析不同大脑状态之间存在的差异,通过特征融合实现对手部抓握运动意图的预测. 基于特征融合意图离线预测准确率最高可达88.46%,可以在人体手部自主运动发生时刻?1 400 ms实现对手部运动预测. 与平静时期手部静止状态相比,被试产生手部抓握运动意图时脑电信号的功率谱与复杂度均产生明显变化,为基于手部运动意图预测提前驱动机器人实现人机协同提供控制策略.     

2×4 MIMO-OFDM系统中K-Best检测器的设计与实现

基于贝尔实验室V-BLAST结构构建了2×4 MIMO-OFDM系统模型,并确定了该模型下K-Best算法的K值。之后对K-Best检测器进行了硬件架构设计,采用Xilinx Virtex-5芯片对所设计检测器加以实现,并给出检测器资源消耗和时钟频率等性能指标,最后通过仿真验证检测器正确性。     

Stabilization of Rössler chaotic dynamical system using fuzzy logic control algorithm

This paper proposes a fuzzy logic control algorithm (FLCA) to stabilize the Rössler chaotic dynamical system. The fuzzy logic control system is based on a Takagi-Sugeno-Kang inference engine and the stability analysis in the sense of Lyapunov is carried out using Lyapunov’s direct method. The new FLCA is formulated to offer sufficient inequality stability conditions. The asymptotic complexity of our algorithm is analyzed and proved to be lower in comparison with that of linear matrix inequality-based FLCAs. A set of simulation results illustrates the effectiveness of the proposed FLCA.     

变邻域分解多目标自适应差分进化算法

分解方法是处理复杂问题常用的一种手段,而差分进化算法被广泛地应用于多目标优化问题(multiobjective optimization problems,MOP),为了克服经典差分进化算法和分解方法的缺陷,本文提出了一种自适应差分进化算法和变邻域分解方法相结合的新颖算法一ADEMO/D-ENS,该算法采用Tchebycheff方法将多目标优化问题分解成多维标量优化子问题,并利用邻域子问题的信息进行优化,基于邻域种群集依概率自适应选择邻域种群规模;同时采用概率匹配(]probability match,PM)自适应方法从差分策略池中选择差分进化策略;同时分析了算法的复杂度;最后,通过和经典的非支配排序遗传算法(non-dominated sorting genetic algorithmsⅡ,NSGA-Ⅱ)和多目标差分进化算法(multi-objective differential evolution algorithm,MODE)仿真对比,说明ADEMO/D-ENS方法可以更有效的处理多目标优化问题.     

一种基于过零点的时延测量方法

信号传输时间（时延）的测量,是雷达、声纳系统的关键技术之一。本文研究了一种基于过零点的时延测量方法,在建立过零点搜索模型的基础上推导得出时延测量的测量结果表达式;定量分析了高斯白噪声条件下过零点时延测量的测量精度,得到测量误差的理论表达式。仿真与实验表明,过零点时延测量精度与信号频率、过零点数目、信噪比密切相关,当信噪比较高时,其测量精度与经典FFT法相当,而优势在于过零点时延测量的算法简单、计算量小,适用于对实时性要求较高的测量场合。     

On the complexity of role updating feasibility problem in RBAC

In Role Based Access Control (RBAC) systems, it is necessary and important to update the role–permission assignments in order to reflect the evolutions of the system transactions. However, role updating is generally complex and challenging, especially for large-scale RBAC systems. This is because the resulting state is usually expected to meet various requirements and constraints. In this paper, we focus on a fundamental problem of role updating in RBAC, which determines whether there exists a valid role–permission assignment, i.e., whether it can satisfy all the requirements of the role updating and without violating any role–capacity or permission–capacity constraint. We formally define such a problem as the Role Updating Feasibility Problem (RUFP), and study the computational complexity of RUFP in different subcases. Our results show that although several subcases are solvable in linear time, this problem is NP-complete in the general case.