The Boyer–Moore–Horspool heuristic with Markovian input

The Boyer–Moore–Horspool string‐matching heuristic is an algorithm for locating occurrences of a fixed pattern in a random text. Under the assumption that the text is an independently and identically distributed sequence of characters, the probabilistic behavior of this algorithm was investigated by Mahmoud, Smythe, and Régnier [Random Struct Alg 10 (1997), 169–186]. Here, we obtain similar results under the assumption that the text is generated by an irreducible Markov chain. A natural Markov renewal process structure is exploited to obtain the asymptotic behavior of the number of comparisons. Under suitable normalization, it is shown that a central limit theorem holds for the number of comparisons. The analysis is completely probabilistic and does not use the shift generating function. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 153–163, 2001     

On generalized hamiltonian systems

1. PreliminaryIt is well known that{1] a 8ymPlectic form is invariant along the trajectory of a Hamilto-nian system. Based on this fundamental property, certain techniques have been developed.The purpose of this paper is to extend such an approach to a wider class of dynamic systeIns,namely, genera1ized Hamiltonian systems. Our purpose is to investigate a class of dynaInicsystems, which possess a certain "geometric structure".Deflnition 1.1[1'2]. Let M be a tIlallifo1d. w E fl'(M) is call…     

A fixed-parameter-tractable algorithm for set packing

1. IntroductionIt is a useful and challenging task to find efficient algorithms for many computationalhard problems. Recently, the research on Fixed-Parameter nactable Theory arouses muchinterest. FOr example, different fixed- p ax amet er- t rac t ab le- algori t hms for many well- knowndecisio11 pruble11ls illc1udi11g 3-dimellsio11al IIlatchiIlg: a11d vertex--cover Problen1 have beenPrese11ted in [1 8]. Jia11er Chen, DoIlald K. FYiesen al1d Weijia Jia proPosed a coll1pletelynew appro…     

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k₁, k₂, is there a vertex cover taking at most k₁ vertices from one and at most k₂ vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999^{k₁ + k₂} + (k₁ + k₂)n) time. Our algorithm is efficient and practical for small values of k₁ and k₂, as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.     

There exists no (15,5,4) RBIBD

An (n, M, d)_q code is a q‐ary code of length n, cardinality M, and minimum distance d. We show that there exists no (15,5,4) resolvable balanced incomplete block design (RBIBD) by showing that there exists no (equidistant) (14,15,10)₃ code. This is accomplished by an exhaustive computer search using an orderly algorithm combined with a maximum clique algorithm. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 227–232, 2001     

卫星舱内长方体群布局的优化模型及全局优化算法

本文研究了卫星舱内长方体群优化问题,建立了一个三维布局优化模型,并用图论,群论等工具克服了布局优化问题时断时续性质带来的困难,在此基础上构造了一个全局收敛的优化算法,文中所用的方法可用于求解类似问题。     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

块循环矩阵方程组的新算法

1　基本概念形如 A=a1 a2 … a Na N a1 … a N- 1?彙?廰2 a3 … a1的矩阵称为由 a1 ,a2 ,… ,a N 生成的循环矩阵 .力学和工程中的轴对称结构的计算产生上述循环矩阵 [2 - 3] .以循环矩阵A为系数矩阵的方程组 ,称为循环矩阵方程组 .已有的求解循环矩阵方程组的办法主要是各种迭代法 ,如递推法及 SOR,SSOR,SAOR超松弛迭代法[2 - 6] 等 .定义 1　形如A =A1 A2 … ANAN A1… AN- 1?彙?廇2 A3… A1　 (Ai,i =1 ,2 ,… ,N为 m阶矩阵 )的矩阵称为由 A1 ,A2 ,… ,AN 生成的块循环矩阵 .定义 2　系数矩阵 A为块循环矩阵的方程组AX …     

建立模糊诊断矩阵的一种新方法

本文首先提出了一个新的模糊逻辑算子——模糊加权综合算子“#”,进而给出建立模糊诊断矩阵的新方法——网络法 ,并给出了相应的算法     

Analytical solution of stochastic differential equation by multilayer perceptron neural network approximation of Fokker–Planck equation

The Fokker–Planck equation is a useful tool to analyze the transient probability density function of the states of a stochastic differential equation. In this paper, a multilayer perceptron neural network is utilized to approximate the solution of the Fokker–Planck equation. To use unconstrained optimization in neural network training, a special form of the trial solution is considered to satisfy the initial and boundary conditions. The weights of the neural network are calculated by Levenberg–Marquardt training algorithm with Bayesian regularization. Three practical examples demonstrate the efficiency of the proposed method.