线性时间选择算法时间复杂度深入研究

算法研究是计算机科学的核心领域之一。文中针对元素选择问题及解此问题的线性时间选择算法进行了深入研究,详细分析并论证了期望情况下与最坏情况下线性时间选择算法的时间复杂度,并对拟中位数元素选择问题进行了深层次的拓展,通过计算比较求出了线性时间下的最小复杂度因子。以期有助于该算法在相关领域的应用。     

高阶累积量计算优化的仿真研究

高阶累积量由于计算量大而未得到广泛的应用,所以对其进行计算优化以及算法的简化能更好的发挥其优越性,根据推导的非平稳随机过程四阶累积量精确递推估计公式,从减少四阶累积量估计的计算量,增强四阶累积量的工程实用性出发,给出了四阶累积量近似递推估计定理.只要四阶累积鼍的更新因子满足定理的条件,就能减少计算量,并且使估计的四阶累积量保持抑制高斯噪声的性能,并且根据四阶累积量的优化给出了五阶累计量的优化和仿真.从时域和频域进行了优化仿真,仿真结果证实了估计的有效性.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

梯形子模式非对称逆布局二值图像表示方法

虽然树形分层结构在图像表示和处理中有很多优点,但是它们都过分地强调分割的对称性和节点的对称性,因此不是最优的图像表示方法.借鉴Packing问题研究的方法,基于非对称逆布局模式表示模型(Non-symmetry An-ti-paeking pattern representation Model,NAM),提出了一个梯形子模式非对称逆布局二值图像表示方法,给出具体的编码算法和解码算法,并分析了算法的时空复杂度和表示的数据量.理论分析和试验结果表明,与流行的基于分层结构的线性四元树表示方法相比,梯形子模式非对称逆布局二值图像表示方法在子模式数量和数据量方面具有较大的优势.     

空间最近点对的计算机算法研究

最近点对问题是空中交通控制系统中的一个重要问题,并且在许多领域都有应用,也是计算几何学研究的基本问题之一.利用分治法解决该问题的线性和平面情况,算法可以在O(n*logn)时间内完成.本文在此基础上,进一步实现空间最接近点的算法,并对算法的复杂性进行分析.     

基于物品移动的局内装箱算法的改进

局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用.提出一个新的局内线性算法MAMOV, 算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值.     

基于运动区域划分的H.264低复杂度模式选择

为降低H.264编码器的复杂度,提出基于运动区域划分的模式选择算法.首先利用已编码宏块的运动信息识别运动对象的内部区域和边界区域,然后利用已编码宏块的模式信息对边界区域的运动剧烈程度和细节复杂程度进行进一步的划分,从而将视频内容划分为运动性质不同的区域,并选择合适的模式对其进行编码.实验结果表明,该算法平均节省编码时间达47.95%,有利于实时应用;同时PSNR平均下降约0.06 dB,不影响主观视觉效果.     

Prim算法在架设通信网络系统中的应用

通信网络系统架设属于典型的图论优化问题,针对通信网络系统的特点,抽象问题,简化模型,以通信网络系统架设费用最小为优化目标,应用Prim算法进行通信网络系统架设模型研究.首先简述了七城市之间架设通信网络系统问题,然后应用数学建模知识对隐含在该问题中的图论模型进行抽象研究,进而构造问题的数学模型,最后应用Prim算法设计了该通信网络系统架设的实现流程及相应代码的编写.程序执行结果表明:准确构建了问题的数学模型及应用Prim算法正确求解了该数学模型;并且权值因子的可变性使得该程序具有较强的通用性,易于在实际中使用.     

复杂社会网络的介数性质近似计算方法研究

随着计算机和互联网的迅猛发展,面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大,这对网络分析算法的性能提出了更高的要求 。介数值作为图的重要结构性质,广泛应用于基于图的聚类、分类算法,如何降低其计算的复杂性是急需解决的问题。目前,常用的方法是利用对最短路径长度的近似来降低低网络分析算法的复杂性,但已有的近似方法没有考虑现实大规模网络的复杂网络特性,对最短路径长度的近似方 近似计算方法,其基本思想是结合复杂网络的结构特性,利用通过网络中枢节点的路径来近似最短路径,以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算算提供了一种新颖的思路。通过与传统的介数计算方法和近的分析得到了若干有益的结论,为进一步的研究工作奠定了基础。     

Efficient realization of frequently used bijections on cube-connected cycles

CCC has lower hardware complexity than hypercube and is suited for current VLSI technology.LC-permutations are a large set of important permutations frequently used in various parallel computations.Existing routing algorithms for CCC cannot realize LC-permutations without network conflict.We present an algorithm to realize LC-permutations on CCC.The algorithm consists of two periods of inter-cycle transmissions and one period of inner-cycle transmissions.In the inter-cycle transmissions the dimensional links of CCC are used in a “pipeline” manner and in the inner-cycle transmissions the data packets are sorted by a part of its destination address.The algorithm is fast (O(log2N)) and no conflict will occur.