屏蔽差集偶与伪随机屏蔽二进序列偶的研究

为了进一步研究伪随机屏蔽二元序列偶,提出了一类新的区组设计——屏蔽差集偶,证明了一类特殊的屏蔽差集偶和伪随机屏蔽二元序列偶是等价的,并研究了伪随机屏蔽二元序列偶存在的充分必要和必要条件;最后利用差集构造出一类伪随机屏蔽二元序列偶,丰富了伪随机屏蔽二元序列偶的研究内容。     

具有四值自相关特性的二元序列的构造

本文给出了具有四值自相关特性的二元序列的一种构造方法.对于任意给定的素数p和正整数m、n,当m|n时,我们利用周期为pm-1的具有三值自相关特性的二元序列构造了周期为pn-1的具有四值自相关特性的二元序列,给出了新的二元序列的自相关取值及其分布,同时还讨论了这些序列的陪集不变性和线性复杂度等性质.     

基于差集的高效能分布式请求集生成算法

在折半循环编码算法的基础上,提出了一种增加算法初始化节点数量和松弛正向差集的对称分布式互斥请求集生成算法,使算法的时间复杂度大幅度降低,而所生成的请求集长度仍然保持（2N）^1/2～2N^1/2之间。     

如何编程实现快速LCS算法

LCS即最长公共子串,例如给定两个序列,A={abcbdab},B={bdcaba},那么序列{bcba}就是它们的最长公共子串。当然这样的子串不一定唯一,比如{bcab}也是,只要找到其中一个即可。这个问题已经研究得很深入,一般是用动态规划法求解,时间复杂度为O(MN),即两个序列长度的乘积。很多算法书都有介绍,是根据状态转移方程求解。但     

两类具有极低自相关性的二元序列

对两类周期分别为 N=2(mod 4)和N=0(mod 4)的二元序列的自相关性进行了研究。通过利用周期为 N=1(mod 4)的平衡二元序列的相关性分布特征对用其构造出的上述两类序列的自相关性进行了分布研究及出现频率研究,同时给出上述两类序列的自相关性只存在固定取值且每个取值出现的频率是一定的。结果表明,这两类序列具有良好的周期自相关性,且自相关分布频率是确定的,在密码学和通信领域具有潜在的应用价值。     

具有低相关值的新的修改的二元Jacobi序列

根据修改的二元Jacobi序列的构造方法,利用任意起点的二元Jacobi序列,构造了大量的新的二元序列。并利用kgendre特征函数的求和公式,给出了其中一类序列的自相关值及其它类序列在一定条件下的互相关值。结果表明,这类序列在一定条件下具有非常平坦的相关值分布。     

大线性复杂度三值自相关的二元三阶分圆序列的构造

对于一类周期为素数p,p≡1(mod 3)的二元三阶分圆序列提出了一种构造方法,确保其少自相关值及大线性复杂度。利用分圆的知识计算其自相关值,并进一步考虑序列的自相关值为三值时,素数p应满足的条件。此时p应满足p=a²+12,a为整数。当p满足此形式时,序列的线性复杂度为p-1,否则为2(p-1)/3。通过计算机实验,找出了满足所给形式的p,并能生成对应的序列集,验证了序列的自相关性及线性复杂度。新序列的线性复杂度和已有的三元三阶分圆序列的相同;和二元偶数阶分圆序列的相比,大部分相同或较优(已有的有些情况为(p-1)/2、(p+1)/2或1+(p-1)/6)。所提出的构造方法可推广至其他少自相关值、大线性复杂度的奇数阶分圆序列集的构造上。大奇数阶分圆序列的平衡性也会提高,能被较好地应用于密码与通信系统中。     

具有O(n)时间复杂度的分布式请求集生成算法

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。     

基于Chebyshev映射的快速伪随机序列发生器

为克服多比特量化算法抗逆向迭代弱的缺点,提出了一种基于Chebyshev映射的中间多比特伪随机序列量化算法。首先对理想条件下Chebyshev映射的统计特性进行分析,在此基础上分析了生成序列的平衡性与自相关、互相关性,证明了该序列为二元Bernoulli序列并且其自相关与互相关函数服从标准正态分布N（0,1／N）。同其他算法相比,该算法在有限精度条件下增强了混沌序列的抗逆向迭代能力,扩展了序列的周期,提高了长序列的自相关与互相关性能。     

基于椭圆曲线的二元伪随机序列构造与分析

基于有限域 上的椭圆曲线,利用乘法逆构造一类二元伪随机序列,通过素域上椭圆曲线的指数和,计算该类伪随机序列的一致分布测度和k阶相关测度。结果表明,周期为N的二元伪随机序列一致分布测度的上界为p1/2lbplbN,k阶相关测度的上界为p1/2(lbp)klbN,2个测度的数量级都是O(N),说明该类序列具有很好的伪随机性质。     

On the k-th root in circular arithmetic

The representation of thek-th root of a complex circular intervalZ={c;r} is considered in this paper. Thek-th root is defined by the circular intervals which include the exact regionZ ^1/k={z:z ^k ∈Z}. Two representations are given: (i) the centered inclusive disks \( \cup \{ c^{{1 \mathord{\left/ {\vphantom {1 k}} \right. \kern-0em} k}} ; \mathop {\max }\limits_{z \in Z} |z^{{1 \mathord{\left/ {\vphantom {1 k}} \right. \kern-0em} k}} - c^{{1 \mathord{\left/ {\vphantom {1 k}} \right. \kern-0em} k}} |\} \) and (ii) the diametrical inclusive disks with the diameter which is equal to the diameter of the regionZ ^1/k.     

New construction of perfect sequence set and low correlation zone sequence set

For a given binary ideal autocorrelation sequence, we construct a perfect sequence set by changing a few bits of the sequence. The set has a large size with respect to the period of its sequences. Based on the constructed perfect sequence set, a new class of low correlation zone sequence sets whose low correlation zone length can be chosen flexibly is obtained. Moreover, the new constructed low correlation zone sequence sets can attain Tang-Fan-Matsufuji＇s bound with suitably chosen parameters.     

Simultaneously One-Turn Two-Pushdown Automata

Consider two consecutive moves, $m_{1}$ and $m_{2}$ , made by a two-pushdown automaton, M , whose pushdowns are denoted by $\pi_{1}$ and $\pi_{2}$ . If during $m_{1}$ M does not shorten $\pi_{i}$ , for some $i = 1, 2$ , while during $m_{2}$ it shortens $\pi_{i}$ , then M makes a turn in $\pi_{i}$ during $m_{2}$ . If M makes a turn in both $\pi_{1}$ and $\pi_{2}$ during $m_{2}$ , this turn is simultaneous . A two-pushdown automaton is one-turn if it makes no more than one turn in either of its pushdowns during any computation. A two-pushdown automaton is simultaneously one-turn if it makes either no turn or one simultaneous turn in its pushdowns during any computation. This paper demonstrates that every recursively enumerable language is accepted by a simultaneously one-turn two-pushdown automaton. Consequently, every recursively enumerable language is accepted by a one-turn two-pushdown automaton.     

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

Approximately Fair Cost Allocation in Metric Traveling Salesman Games

A traveling salesman game is a cooperative game . Here N, the set of players, is the set of cities (or the vertices of the complete graph) and c _D is the characteristic function where D is the underlying cost matrix. For all S⊆N, define c _D (S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪{0} where is called as the home city. Define Core as the core of a traveling salesman game . Okamoto (Discrete Appl. Math. 138:349–369, [2004]) conjectured that for the traveling salesman game with D satisfying triangle inequality, the problem of testing whether Core is empty or not is -hard. We prove that this conjecture is true. This result directly implies the -hardness for the general case when D is asymmetric. We also study approximately fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let and ∀ S⊆N, x(S)≤ε⋅c _D (S)} be an ε-approximate core, for a given ε>1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log ₂(|N|−1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We improve it further by finding a -approximate core in polynomial time for some constant c. We also show that there exists an ε ₀>1 such that it is -hard to decide whether ε ₀-Core is empty or not. A preliminary version of the paper appeared in the third Workshop on Approximation and Online Algorithms (WAOA), 2005.     

基于信道状态信息的安防监控系统

无线网络的信道状态信息（Channel State Information, CSI）是MIMO系统中反映各个子载波信号频谱特性的重要指标,通过在Linux平台上定制Intel 5300网卡驱动,就可在常规的无线网络通信环境下通过编程实现对CSI数据的实时采集。因CSI信息对环境变化十分敏感,因此可用于构建基于CSI的非接触式环境感知系统。本文以CSI为数据载体,详细梳理基于CSI的无线感知应用,建立基于CSI信号的安防监控系统,能够成功检测人员到访事件。系统提取人员到访时间的CSI信号特征〖WTHX〗v〖WTBX〗*t={σ,MaxPt,MinPt,E}并通过实验求得,当其值为〖WTHX〗v〖WTBX〗*t={1×10－3,［1,2］,［1,2］,2.0×10－4}时,系统可获得高达99.07%的检测成功率。     

基于编码转换的离散演化算法设计与应用

为了利用演化算法求解离散域上的组合优化问题,借鉴遗传算法（GA）、二进制粒子群优化（BPSO）和二进制差分演化（HBDE）中的映射方法,提出了一种基于映射变换思想设计离散演化算法的实用方法——编码转换法（ETM）,并利用一个简单有效的编码转化函数给出了求解组合优化问题的离散演化算法一般算法框架A-DisEA.为了说明ETM的实用性与有效性,首先基于A-DisEA给出了一个离散粒子群优化算法（DisPSO）,然后分别利用BPSO、HBDE和DisPSO等求解集合联盟背包问题和折扣{0-1}背包问题,通过对计算结果的比较表明：BPSO、HBDE和DisPSO的求解性能均优于GA,这不仅说明基于ETM的离散演化算法在求解KP问题方面具有良好的性能,同时也说明利用ETM方法设计离散演化算法是一种简单且有效的实用方法.     

Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.     

A System of Relational Syllogistic Incorporating Full Boolean Reasoning

We present a system of relational syllogistic, based on classical propositional logic, having primitives of the following form: $$\begin{array}{ll}\mathbf{Some}\, a \,{\rm are} \,R-{\rm related}\, {\rm to}\, \mathbf{some} \,b;\\ \mathbf{Some}\, a \,{\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{some}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all} \,b.\end{array}$$ Such primitives formalize sentences from natural language like ‘All students read some textbooks’. Here a, b denote arbitrary sets (of objects), and R denotes an arbitrary binary relation between objects. The language of the logic contains only variables denoting sets, determining the class of set terms, and variables denoting binary relations between objects, determining the class of relational terms. Both classes of terms are closed under the standard Boolean operations. The set of relational terms is also closed under taking the converse of a relation. The results of the paper are the completeness theorem with respect to the intended semantics and the computational complexity of the satisfiability problem.     

Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

We present a fixed-parameter algorithm that constructively solves the $k$-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in $O(4^{9.55\sqrt{k}}n^{O(1)})$ time. Examples of such graph classes are the $K_{3,3}$-minor-free graphs and the $K_{5}$-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.