Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

Dynamics of Single-Pulse Echo Signals under the Conditions of Zeeman Switching

The signals of a single-pulse echo (SE) generated on nonresonant excitation of an inhomogeneously broadened two-level system by a radio-frequency pulse (RFP), against the background of which a magnetic video pulse (MVP) of certain length has been switched on, have been described analytically. It is established that under the conditions of such excitation several SE signals are formed whose generation moments are determined by the duration and amplitudes of the RFP and MVP. The amplitudes of some of these signals depend on the Rabi frequency according to a quadratic law, and the amplitudes of others depend on this frequency according to a biquadratic law. It has been established that the mechanism underlying the appearance of these signals is associated with zero beats arising as a result of superposition of the magnetization fluctuations at variable frequencies and at a frequency of detuning from resonance. It is shown that in the limiting case, where the RFP duration considerably exceeds the duration of the MVP or is comparable with it, the number of SE signals decreases to two. Theoretical results on the formation of SE and the dependence of the amplitude of these signals on the MVP amplitude agree with the experimental data on NMR pulsed signals in ferromagnetic materials.     

The Asymmetric Avalanche Process

An asymmetric stochastic process describing the avalanche dynamics on a ring is proposed. A general kinetic equation which incorporates the exclusion and avalanche processes is considered. The Bethe ansatz method is used to calculate the generating function for the total distance covered by all particles. It gives the average velocity of particles which exhibits a phase transition from an intermittent to continuous flow. We calculated also higher cumulants and the large deviation function for the particle flow. The latter has the universal form obtained earlier for the asymmetric exclusion process and conjectured to be common for all models of the Kardar–Parisi–Zhang universality class.     

酵母蛋白质网络的动力学性质

蛋白质-蛋白质、蛋白质-DNA相互作用网络决定了细胞中各种关键功能的执行．基于芽殖酵母(budding yeast saccharomyces cerevisiae)的蛋白质-蛋白质相互作用网络数据和相关的实验文献，我们建立了调控细胞周期和生命周期(cell cycle and life cycle)的蛋白质网络，并利用离散模型研究了该网络的动力学性质，研究表明：细胞周期网络的动力学性质具有很强的稳定性，约94％的蛋白质初态将演化到对应于生物学G1基态的稳定态，使其成为惟一的全局吸引点；同时，绝大多数的初态的演化路径都通过由G1激发态到G1基态的细胞周期演化路径，使细胞周期路径成为全局性的“吸引”路径。     

一种改进的数字散斑相关方法用于检测人的口型变化

提出了一种基于数字散斑相关测量技术的口型变化检测技术,该技术以白光数字散斑相关测量方法为基础,根据实际应用的需要,引入重心算法并进行了改进,可以实时地检测人说话时的口型变化。通过实验表明,提出的方法是一种实用的、快速、高精度的口型变化测试方法,可为今后的唇语识别技术奠定基础。     

Liminf results on the increments of an (N,d)-Gaussian process

We establish some liminf theorems on the increments of a (N,d)-Gaussian process with the usual Euclidean norm, via estimating upper bounds of large deviation probabilities on the suprema of the (N,d)-Gaussian process. This revised version was published online in June 2006 with corrections to the Cover Date.     

一类随机过程的多尺度建模

基于多尺度随机模型具有有效性和高度并行算法这一优势，提出如何用三阶树多尺度模型来表示1-D Reciprocal过程；并如何获得多尺度模型的参数。这就为具有Markov统计特性的信号或过程建立起一般的三阶树多尺度随机模型，为更有效的解决实际问题提供了理沦基础，同时，给出了一类定义在单位区间上的随机过程三阶树多尺度表示的仿真示例。     

基于USB接口的低速率声码器设计研究

以专用语音信号处理器CT8020为核心，应用单片机控制技术及通信接口电路，介绍了一种基于USB接口的低速率声码器的设计与实现方法，在给出系统硬件总体结构的基础上，重点讨论了声码器和上位机软件设计中的若干问题。