Holographic algorithms on bases of rank 2

An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized under a suitable basis transformation (SRP). For holographic algorithms with matchgates on domain size 2, , ,  and  have built a systematical theory. In this paper, we reduce SRP on domain size k≥3$k\ge 3$ to SRP on domain size 2 for holographic algorithms with matchgates on bases of rank 2. Furthermore, we generalize the collapse theorem of [3] to domain size k≥3$k\ge 3$.     

Drawing non‐layered tidy trees in linear time

The well‐known Reingold–Tilford algorithm produces tidy‐layered drawings of trees: drawings where all nodes at the same depth are vertically aligned. However, when nodes have varying heights, layered drawing may use more vertical space than necessary. A non‐layered drawing of a tree places children at a fixed distance from the parent, thereby giving a more vertically compact drawing. Moreover, non‐layered drawings can also be used to draw trees where the vertical position of each node is given, by adding dummy nodes. In this paper, we present the first linear‐time algorithm for producing non‐layered drawings. Our algorithm is a modification of the Reingold–Tilford algorithm, but the original complexity proof of the Reingold–Tilford algorithm uses an invariant that does not hold for the non‐layered case. We give an alternative proof of the algorithm and its extension to non‐layered drawings. To improve drawings of trees of unbounded degree, extensions to the Reingold–Tilford algorithm have been proposed. These extensions also work in the non‐layered case, but we show that they then cause a O(n²) run‐time. We then propose a modification to these extensions that restores the O(n) run‐time. Copyright © 2013 John Wiley & Sons, Ltd.     

大规模水电系统优化调度降维方法研究I:理论分析

中国水电系统规模持续扩张,使得已有方法在求解大规模水电调度问题时,存在严重维数灾及早熟收敛等不同程度局限,亟需分析已有方法以便发现其瓶颈所在,为探寻能均衡求解效率与计算精度的实用化方法提供有益参考。为此,首先深入研究了线性规划、二次规划和动态规划等多种方法的计算复杂度,然后定量对比分析了各方法在不同情景下的适用性,最后提出“四维一体可拓降维”总体思想,并给出具体的降维方法与策略,建议从空间维、时间维、状态维和组合维等4个方面开展综合研究,以切实服务于大规模水电系统优化调度的高效优质求解。     

一种高效的多模式字符串匹配算法

在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%,ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。     

嵌入式系统中硬件规模估计

运用Delphi方法进行硬件规模估算,对硬件规模进行量化,运用平均生产率的概念计算项目的人工成本,从而得出项目的投入时间,为项目开发计划的制定以及成本估算提供参考.     

基于角色的供需网工作流建模与分析*

目前的工作流建模大多是基于过程的,并没有强调工作流中的角色及其交互过程。基于此,从角色及其交互角度,结合以活动和角色描述工作流的优点,将角色的概念引入到对供需网工作流的研究中来,提出了基于角色的供需网工作流模型,通过实例分析系统地总结了模型建模的方法与步骤。这种建模思想有利于模型结构的完善,有利于提高工作流模型的安全性和正确性。     

基于在线鲁棒LSSVM的自适应PID算法

为了解决在线最小支持向量机在每个采样周期更新模型带来计算量大的问题,提出了在线鲁棒最小二乘支持向量机(LSSVM)的自适应PID控制算法.通过2步加权策略提高LSSVM的鲁棒性,把样本预测误差与过程先验知识相结合给出控制模型复杂度准则,有效地提高了模型的精度、速度以及稀疏性;结合预测控制思想,把在线鲁棒LSSVM算法用于PID非线性控制.仿真结果表明:鲁棒Huber函数与ε-不敏感函数相结合的鲁棒代价函数,能够有效地对系统局部非线性区域进行建模,随系统工作点变化而自适应地辨识,不仅有较高的控制精度,而且具有较强的鲁棒性和建模速度,能够适应时变参数对象的控制.     

基于视觉注意力模型的红外人体图像兴趣区域提取*

由于红外人体图像所处背景的复杂性,使用阈值分割定位红外人体图像往往把大量的非人体图像一起分离出来,这给后续工作带来了巨大的计算量.研究了红外人体图像的典型特点和人眼视觉判断人体轮廓图像的敏感特征,使用该特征建立了简单的人眼视觉对人体的注意力模型,并构建特征判别概率函数,对待定目标进行概率的估算,最终使用该模型快速地剔除非人体红外图像的干扰,并准确地定位人体兴趣区域.     

利用干扰提高容量的低复杂度预编码方法

在接收用户配置单天线的多输入多输出广播系统(MIMO BC)中,提出了一种利用干扰提高系