Optimal search for signals in a multichannel system: Arbitrary initial distribution in state space merging scheme

Markovian and semi-Markovian random processes are used to analyze the problem of optimal search for signals in a multichannel communication system with arbitrarily distributed random outputs. The search efficiency factor is found in explicit form based on state space merging, and a mathematical programming problem is set up to find a numerical suboptimal solution. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 144–150, May–June 2007.     

Cubic Bézier approximation of a digitized curve

In this paper we present an efficient technique for piecewise cubic Bézier approximation of digitized curve. An adaptive breakpoint detection method divides a digital curve into a number of segments and each segment is approximated by a cubic Bézier curve so that the approximation error is minimized. Initial approximated Bézier control points for each of the segments are obtained by interpolation technique i.e. by the reverse recursion of De Castaljau's algorithm. Two methods, two-dimensional logarithmic search algorithm (TDLSA) and an evolutionary search algorithm (ESA), are introduced to find the best-fit Bézier control points from the approximate interpolated control points. ESA based refinement is proved to be better experimentally. Experimental results show that Bézier approximation of a digitized curve is much more accurate and uses less number of points compared to other approximation techniques.     

Metaheuristic downhill simplex method in combinatorial optimization

The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented. The study was supported by INTAS (Project 06-1000017-8909). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–79, November–December 2007.     

A novel document similarity measure based on earth mover’s distance

In this paper we propose a novel measure based on the earth mover’s distance (EMD) to evaluate document similarity by allowing many-to-many matching between subtopics. First, each document is decomposed into a set of subtopics, and then the EMD is employed to evaluate the similarity between two sets of subtopics for two documents by solving the transportation problem. The proposed measure is an improvement of the previous OM-based measure, which allows only one-to-one matching between subtopics. Experiments have been performed on the TDT3 dataset to evaluate existing similarity measures and the results show that the EMD-based measure outperforms the optimal matching (OM) based measure and all other measures. In addition to the TextTiling algorithm, the sentence clustering algorithm is adopted for document decomposition, and the experimental results show that the proposed EMD-based measure does not rely on the document decomposition algorithm and thus it is more robust than the OM-based measure.     

Binary rewriting and call interception for efficient runtime protection against buffer overflows

Buffer overflow vulnerabilities are one of the most commonly and widely exploited security vulnerabilities in programs. Most existing solutions for avoiding buffer overflows are either inadequate, inefficient or incompatible with existing code. In this paper, we present a novel approach for transparent and efficient runtime protection against buffer overflows. The approach is implemented by two tools: Type Information Extractor and Depositor (TIED) and LibsafePlus. TIED is first used on a binary executable or shared library file to extract type information from the debugging information inserted in the file by the compiler and reinsert it in the file as a data structure available at runtime. LibsafePlus is a shared library that is preloaded when the program is run. LibsafePlus intercepts unsafe C library calls such as strcpy and uses the type information made available by TIED at runtime to determine whether it would be ‘safe’ to carry out the operation. With our simple design we are able to protect most applications with a performance overhead of less than 10%. Copyright © 2006 John Wiley & Sons, Ltd.     

广义AND／OR图的自底向上的启发式搜索算法BHAO

本文首先根据三角模概念，定义了一类新的更具普遍意义的广义ＡＮＤ／ＯＲ图．根据新定义的启发式函数ｈ（ｎ，ｘ）以及广义ＡＮＤ／ＯＲ图的最佳解树之所有子树亦是最佳子解树的原理，提出了广义ＡＮＤ／ＯＲ图的自底向上的启发式搜索算法ＢＨＡＯ．文中证明了算法ＢＨＡＯ的可采纳性．本文还提出了两类新的启发式函数的单调限制概念，并据此研究了算法ＢＨＡＯ的单调限制性质，研究了两个ＢＨＡＯ算法间的比较性质．     

以数字搜索树表示的二值图象的几何变换

本文介绍以数字搜索树表示的二值图象的一种几何变换算法，文中讨论了四分区与正四边区的基本关系，输出ＤＳＴ结点成立的充分条件，给出了完整的几何变换算法并对算法的复杂性作了分析。     

具有多重焦点的波带透镜的设计

本文提出了一种新型的具有多重焦点的波带透镜的概念及其设计方法。可提供某些特定的光场分布,而且具有性能稳定、微型化和可实际制作等特点。     

基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.