One-to-one disjoint path covers on multi-dimensional tori

The multi-dimensional torus is one of the most popular underlying topologies for massively parallel systems. In this study, we consider a non-bipartite n-dimensional torus where n≥2 and prove that for 1≤m≤2n, m vertex disjoint paths exist that cover all vertices between any two distinct vertices. In other words, we construct the one-to-one m-disjoint path cover of a non-bipartite torus for any m where 1≤m≤2n.     

On finding optimal covers

After a statement of the general problem underlying Quine's methods of simplifying logical expressions, a few examples, and a survey of various approaches to the problem, attention is focussed on the question of how to branch when the straightforward simplication rules give no further progress. An algorithm is suggested that takes advantage of the freedom of choice at the branching step in order to split the given problem into several smaller problems. As the difficulty of the problem grows exponentially with its size, this results in a great saving of effort. Both the hand and computer versions of the algorithm are described since they differ appreciably. The pattern recognition example used to illustrate the paper is chosen as typical of the wide variety of practical questions in which the above general problem arises.     

Solving #SAT using vertex covers

We propose an exact algorithm for counting the models of propositional formulas in conjunctive normal form. Our algorithm is based on the detection of strong backdoor sets of bounded size; each instantiation of the variables of a strong backdoor set puts the given formula into a class of formulas for which models can be counted in polynomial time. For the backdoor set detection we utilize an efficient vertex cover algorithm applied to a certain “obstruction graph” that we associate with the given formula. This approach gives rise to a new hardness index for formulas, the clustering-width. Our algorithm runs in uniform polynomial time on formulas with bounded clustering-width. It is known that the number of models of formulas with bounded clique-width, bounded treewidth, or bounded branchwidth can be computed in polynomial time; these graph parameters are applied to formulas via certain (hyper)graphs associated with formulas. We show that clustering-width and the other parameters mentioned are incomparable: there are formulas with bounded clustering-width and arbitrarily large clique-width, treewidth, and branchwidth. Conversely, there are formulas with arbitrarily large clustering-width and bounded clique-width, treewidth, and branchwidth.     

Efficient data dissemination using locale covers

Location-dependent data are central to many emerging applications, ranging from traffic information services to sensor networks. The standard pull- and push-based data dissemination models become unworkable since the data volumes and number of clients are high.We address this problem using locale covers, a subset of the original set of locations of interest, chosen to include at least one location in a suitably defined neighborhood of any client. Since location-dependent values are highly correlated with location, a query can be answered using a location close to the query point. Typical closeness measures might be Euclidean distance, or a $k$-nearest neighbor criterion.We show that location-dependent queries may be answered satisfactorily using locale covers. Our approach is independent of locations and speeds of clients, and is applicable to mobile clients.We also introduce a nested locale cover scheme that ensures fair access latencies, and allows clients to refine the accuracy of their information over time. We also prove two important results: one regarding the greedy algorithm for sensor covers and the other pertaining to randomized locale covers for $k$-nearest neighbor queries.     

基于地形熵和地形差异熵的综合地形匹配算法

水下运载体的导航主要以惯性导航为主，但是，由于水下运载体在海底的运行速度比较慢，惯性导航系统随着时间的累积出现了定位误差增大的缺点，因此需要地形辅助导航来纠正惯导的误差。文中将地形熵和地形差异熵的概念引入到水下地形匹配算法中，设计了基于地形熵和地形差异熵的综合地形匹配算法，并将该算法应用于水下地形辅助导航系统中，经验证该算法取得了良好的纠正惯导定位的效果，实现了水下地形辅助导航的任务。     

基于地形熵和地形差异熵的综合地形匹配算法

水下运载体的导航主要以惯性导航为主,但是,由于水下运载体在海底的运行速度比较慢,惯性导航系统随着时间的累积出现了定位误差增大的缺点,因此需要地形辅助导航来纠正惯导的误差。文中将地形熵和地形差异熵的概念引入到水下地形匹配算法中,设计了基于地形熵和地形差异熵的综合地形匹配算法,并将该算法应用于水下地形辅助导航系统中,经验证该算法取得了良好的纠正惯导定位的效果,实现了水下地形辅助导航的任务。     

图像分割的熵方法综述

对图像分割的熵方法进行较全面地分析和综述,其中包括一维最大熵、最小交叉熵、最大交叉熵图像分割方法等。对Shannon熵、Tsallis熵及Renyi熵之间的关系等进行分析与评述。对二维(高维)熵及空间熵等进行分析与评述。最后指出一维熵与其它理论的有机结合、高维熵模型的计算效率等未来研究方向。     

一种基于信息熵的Internet宏观行为模型研究

具有开放、分布式、不协作、异构、无中心控制等特点的Internet复杂系统的管理、规划以及新一代网络体系结构的设计都离不开对网络行为的充分理解。该文从系统科学的角度出发提出了Internet系统结构三维模型;并在该三维模型的基础上利用信息熵原理建立了用于分析Internet宏观行为的Internet系统信息熵模型,根据信息熵模型可以分析Internet各组成部分之间的相互作用关系以及它们怎样引起Internet的宏观行为;最后,给出了信息熵模型的有效性和稳定性定量分析的判别式,其中稳定性判别式可以作为Internet宏观行为的整体控制的一个重要依据。     

基于熵的运动目标检测

目前，运动目标的检测是计算机视觉领域中最活跃的研究主题之一。本文介绍了光流法、帧间差分等运动目标的检测方法，提出了一种基于熵的运动目标检测方法，实验结果表明了该方法的鲁棒性和有效性。     

基于熵的密码强度估计

密码是电子认证的基础,密码的保护以及密码强度或抗破解能力对受保护信息或信息系统的安全至关重要。目前还没有一个准确定义密码强度的方法,基于熵的概念,借助猜测熵和最小熵对密码强度进行大致估计,将对密码的选择具有一定的指导作用。本文介绍了基于熵对密码的强度进行估计的方法。     

基于信息熵的DNA免疫遗传算法

针对标准遗传算法在优化应用中遇到的诸如局部搜索能力差、计算量大、对较大搜索空间适应能力差和早熟收敛等问题,该文通过将免疫算法引入到遗传算法中,利用免疫算法的免疫记忆、自我调节和多样性保持功能弥补其不足,提出了一种基于信息熵的DNA免疫遗传算法.该算法采用DNA链对抗体进行编码,利用信息熵来表示抗体间的亲和度及浓度,并提出了一种新的评估指标--聚合亲和度,有效地实现了抗体群的自我调节和多样性保持策略.最后,利用典型测试函数验证了本文方法的有效性.     

基于估计熵的模糊滤波

介绍了近年来出现的一种度量信号复杂程度的统计量——估计熵（Ａｐｐｒｏｘｉｍａｔｅｅｎｔｒｏｐｙ），并将其用于信号的模糊滤波。这种滤波器具有能随信号的特征自动调节滤波器结构的优点，特别是当信号为非平稳时有较好的效果。这种滤波方法具有一定的自适性，适合于工程应用。     

新的信息熵属性约简

在粗糙集不确定性度量公式中,模糊熵和模糊度是重要的度量方式。根据粗糙集不确定性度量中模糊熵和新的模糊度公式,提出了在决策信息系统中修正条件信息熵和相对模糊熵的概念,并分别用两种方式证明了熵在属性约简过程中的单调性。然后利用向前添加属性算法进行属性约简,约简结果在RIDAS(roughset based intelligent data analysis system)平台上进行识别率测试,通过实验对比分析了两种新的信息熵与条件信息熵的约简结果,为基于信息熵的属性约简提供了参考。     

一种基于熵的聚类算法

给出了一种以Reny熵为评价准则的聚类算法,通过非参数估计法估计密度函数,再利用类内熵和类间熵进行聚类和确定聚类的数目。这种算法不需要用户输入与聚类有关的参数,能根据由数据的分布的特性自动获取要聚类的数目,并能发现任意形状和任意大小的聚类。实验结果显示了算法的有效性和优越性。     

Text extraction from colored book and journal covers

The automatic retrieval of indexing information from colored paper documents is a challenging problem. In order to build up bibliographic databases, editing by humans is usually necessary to provide information about title, authors and keywords. For automating the indexing process, the identification of text elements is essential. In this article an approach to automatic text extraction from colored book and journal covers is proposed. Two methods have been developed for extracting text hypotheses. The results of both methods are combined to robustly distinguish between text and non-text elements.