网络优化中一个组合问题的探讨

文[4]提出了网络优化中若干有待解决的组合问题，本文围绕其中之一“减小直径问题”进行了探讨．设P（n，t）表示长为n的路径增加t条边后所得图直径的最小值，C（n，t）表示长为n的圈增加t条边后所得回直径的最小值．本文取得如下进展：1）给出P（n，2），P（n，3）及C（n，2）的精确值，并得出P（n，4）的一更精细的上界及一种更好的加边方式．上述结果均满足小极大度原则．2）在有极大度限制的条件下，分别对t为偶数和奇数给出了P（n，t）的上界．     

Vandermonde行列式的快速并行算法

n阶Vandermonder行列式的求值通常需要O(n~2)次算术运算．本文从计算复杂性的角度出发，给出一种求Vandermonde行列式、合流型Vandermonde行列式、广义Vandermonde行列式的快速算法．该算法仅需O(nlog~2n)次算术运算．若在n台处理机上并行计算，该算法需并行步数O(nlog_(2~2)n)．速度倍数为s_p=O(n)．并行效率为O(1)．     

基于最钝角规则的亏基对偶单纯形Ⅰ阶段算法

对偶单纯形算法或原始对偶单纯形算法都需要一个初始对偶可行基．就此目的而言，基于最钝角行主元规则的对偶Ⅰ阶段算法非常有效[15].本文将其思想应用于亏基情形，建立一个不含比值检验的新的亏基对偶Ⅰ价段算法．初步的数值实验表明，该算法可在总体上减少运行时间和迭代次数，极具竞争性．     

多边形链图中的完美匹配数

多边形链图的完美匹配数（即多边形碳氢链状聚合物的Ｋｅｋｕｌｅ结构数）是数学化学研究的重要内容之一。我们给出了一个求该数的简洁算法，并证明该数是一个多项式。做为应用，对于一类特殊的多边形链图，给出了具体的表达式。     

均聚物结晶与熔融化的稳态和亚稳态转变统计理论 分子分凝统计结晶动力学——从微晶核和微晶粒演化方程的解来推导总转化方程E(t)和动力学Avrami方程及DSC谱图表征式

从高分子结晶是连接受阻无规链段上可结晶基元(stem)分凝的事实出发,认为高分子的结晶是结晶体系内微晶核和微晶粒-高分子链组中连接受阻无规链段的长度连续缩短同微晶核和晶粒的体积和形状连续增大的统一效应,而这两者间既存有并存性又存有简并性. 故在计算结晶体系的总转化方程E(t)和同转化方程对应的Avrami方程时,可采用以下两种计算方法来计算微晶核-高分子链组和微晶粒-高分子链组的增长速率(n(t))和(c(t)):方法1 微晶核和晶粒表面上连续受阻链段分子分凝式体积收缩法,即计算结晶体系微晶核和晶粒表面上连接受阻链段的长度连续收缩的速率( nfT(t))和(RcfT(t)); 方法2 微晶核和微晶粒的形状和体积连续增大法,即计算微晶核和晶粒的形状和体积连续增大的速率( n(-pf)(t))nnT和( c(-pf)(t))nvT.当把用这两种计算方法所得到的两种链组的4种速率(nfT(t)),(n(-pf)(t))nn T,(cfT(t))和(c(-pf)(t))nvT引入f维多元核和f维晶粒增长下总转化方程后就分别得到了两套总转化方程E(t)nT和E(t)cT表达式. 再把两套表达式中微晶核和微晶粒的摩尔数n改为用由求解微晶核-高分子链组和微晶粒-高分子链组两种演化方程所得到的微晶核和微晶粒-高分子链组的尺寸大小和平均末端距几率密度分布函数Fn和Fc来表征后,就又分别得到了两套常规的总转化方程E(t)nT和E(t)cT,以及同它们相对应的动力学Avrami方程: 其Ⅰ为晶核和晶粒表面上连接受阻无规链段中可结晶基元(stem)数连续缩小的微观总结晶动力学Avrami方程E(t)cT; 其Ⅱ为微晶核和晶粒的体积和形状连续增大的宏观总结晶动力学Avrami方程E(t)nT. 该E(t)nT正是人们常规定义的宏观结晶成核方式和生长方式的Avrami方程,它的指数n可为1～3的正整数;而E(t)cT为分子分凝式的微观总结晶动力学Avrami方程,它的指数可取1～4间的非零的任意常数,它并随着结晶程度的增加而减少. 最后我们全面地讨论了这两种总结晶动力学Avrami方程E(t)nT和E(t)cT的特征、差异和适用性.从E(t)cT形式的总结晶动力学Avrami方程出发,从理论上推导出等速降温下4种增长方式、4种不同结晶体系的DSC谱图表征式.结果表明,谱图的分布形状和峰的个数均因成核和增长机制而变.     

基于DNA链置换与荧光标记的0-1规划问题的计算模型

DNA链置换技术和荧光标记是近年生物计算领域的新兴的方法,并且因为它们都有着操作简单的优势而成为DNA计算的常用方法.DNA自组装算法是以DNA分子作为数据存储和运算的一种新型计算模式.为了提高算法的特异性和检测的灵敏度,在自组装算法的基础上,首次将DNA链置换技术和荧光标记结合引入到自组装模型中,提出了一个解决0-1规划问题的DNA计算新模型.与以往DNA计算模型相比,该模型提高了运算的可靠性和准确性,而且可以逐步缩小解空间,降低运算的复杂度,同时也使检测的方法更加灵活,易于引入到其他自组装算法模型中.     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

子图识别的层分解方法

子图识别问题(SRP)就是在一个图G中确定并寻找是否存在和另一个图H相同构的子图．本文将引入图的层分解概念，并以此为基础建立识别图的同构子图的算法．该算法的复杂性为O(n(△-1)^k-1)，其中△是图G的度，即G中点的最大度，n，k分别是图G，H的阶．     

转移概率的估计与检验

马氏链预测方法有非常广泛的应用前景．然而，使用这种方法，首先需要确定马氏链的转移概率，在以往的文献中．通常介绍的都是利用马氏链的要本路线来估计转移概率．但是有些问题，例如市场占有率问题，样本路线难以获得，因而需要考虑新的方法．本文采用最小二乘法，通过求矩阵方程的最佳逼近解来确定转移矩阵的估计，实际上归结成一个二次规划问题，此时，我们给出了算法，并给出了计算例题．     

多峰多维密度模拟退火的可逆算法

在对多峰多维密度作模拟退火时,使用Markov链Monte Carlo方法常会遇到从逸出一个峰底进入另一个峰底的困难,因为这常常需要指数长的时间,从而在实际上使算法不可能实现.为了克服这个困难,建议用一个可逆设计生成一个Markov 链,运用它为工具所得到的模拟密度,在相当一般的情形下,可以成功地避免使算法陷入局部峰底的困难.     

An O(n log n) algorithm for finding all repetitions in a string

Any nonempty string of the form xx is called a repetition. An O(n log n) algorithm is presented to find all repetitions in a string of lenght n. The algorithm is based on a linear algorithm to find all the new repetitions formed when two strings are concatenated. This linear algorithm is possible because new repetitions of equal length must occur in blocks with consecutive starting positions. The linear algorithm uses a variation of the Knuth-Morris-Pratt algorithm to find all partial occurrences of a pattern within a text string. It is also shown that no algorithm based on comparisons of symbols can improve O(n log n). Finally, some open problems and applications are suggested.     

Calculating distances for dissimilar strings: The shortest path formulation revisited

Fast detection of string differences is a prerequisite for string clustering problems. An example of such a problem is the identification of duplicate information in the data cleansing stage of the data mining process. The relevant algorithms allow the application of large-scale clustering techniques in order to create clusters of similar strings. The vast majority of comparisons, in such cases, is between very dissimilar strings, therefore methods that perform better at detecting large differences are preferable. This paper presents approaches which comply with this requirement, based on reformulation of the underlying shortest path problem. It is believed that such methods can lead to a family of new algorithms. An upper bound algorithm is presented, as an example, which produces promising results.     

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     

Finding the maximum suffix with fewer comparisons

It is shown how to compute the lexicographically maximum suffix of a string of n?2 characters over a totally ordered alphabet using at most (4/3)n−5/3 three-way character comparisons. The best previous bound, which has stood unchallenged for more than 25 years, is (3/2)n−O(1) comparisons. We also prove an interesting property of an algorithm for computing the maximum suffix both with respect to a total order < and with respect to its inverse order >.     

Recognizing String Graphs Is Decidable

Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

A unifying look at the Apostolico–Giancarlo string-matching algorithm

String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function (“matching shift”) of the well-known Boyer–Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer–Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text).     

Recognizing String Graphs Is Decidable

   Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

A string searching algorithm

This paper is an attempt to develop a string searching algorithm that begins the search for a match in the middle of the strings being compared. The algorithm uses information gained from mismatches and the location of the search area in the large string, to make decisions and direct the search. Several elements of this algorithm can be useful in string searching applications. The algorithm is developed in FORTRAN IV (IBM 370?145), and the entire program is written in modular replacement form so that modification can be efficient.     

KMP算法的一种新的简化算法

通过对字符串模式匹配算法BF与KMP的分析,提出了一种简化KMP算法的方法,构造了一种新的计算next函数的方法,简化后的算法比KMP更清晰直观.经过复杂性分析和上机实验,得出当模式串的长度不大时,简化算法是一种高效的模式匹配算法.     

The problem of reconstructing a quasihomogeneous string from its part

We consider quasihomogeneous strings with piecewise constant density and derive the quasihomogeneity condition. For a small number of string components, we present explicit formulas for reconstructing a string from its part. For an arbitrary number of string components, we construct a theory of matrices of special form (that we call distinguished) and present an algorithm for string reconstruction from its part.