交互式马尔科夫链上弱模拟关系的计算

对交互式马尔可夫链模型(IMCs)上的弱模拟前序关系的计算算法进行讨论.在IMCs上判断弱模拟关系时,重点对概率转移关系进行弱模拟前序关系的判断,同时考虑内部动作对系统的影响.通过引入适当的变量,将IMCs上弱模拟定义中的马尔可夫转移条件转化为求解一个线性规划问题的解.利用该线性规划问题的数值求解方法,可在多项式时间内求得该线性规划问题的解.从而得到判定IMC上两个进程是否弱模拟的多项式时间算法.     

论复杂性科学视野中的教学观

教学是一个由教学主体、教学目标、教学内容、教学方法、教学信息、教学媒体和教学环境等诸要素组成的开放系统,纷繁复杂的非线性和不确定性是它的特点。教学过程是在教学环境中向着教学目标不断演化的过程,它不是一个被动的、机械式的运作系统,而是通过对环境的开放和师生积极的自我调控与自我构建而形成的一个能动的自组织系统,存在高度的自组织现象。     

出厂物流调度问题及其启发式算法

针对出厂物流调度问题,建立了一类出厂物流问题的调度理论模型,证明了该问题的强NP-hard特性.基于对问题的特征分析,提出求解问题的近似算法,证明了算法的最坏性能比为3且为紧界,并通过数值仿真验证了该算法的有效性.结果表明,所提出算法对两台流水作业机器的完工时间有一定的优化.     

A FRAMEWORK FOR REAL-VALUED CIPHER SYSTEMS

Most cipher systems designed thus far are binary-valued or integer-valued cipher systems. Their security relies on the assumption that one-way functions exist. Though the existence of one-way functions has not been proved yet, most cryptographic researchers believe that one-way functions exist. In addition, many candidates for one-way functions have been proposed. Therefore, the key step for developing real-valued cipher systems is to define real one-way functions and to propose candidates for them. In this paper, based on computational complexity theory over the real field, we give two definitions of real one-way functions; one is for digital one-way functions and the other is for general one-way functions. Candidates for these two classes of one-way functions are also proposed. Moreover, we present two examples to demonstrate that the candidates for both digital one-way functions and general one-way functions can be applied to construct secure real-valued cipher systems.     

求解0-1背包问题的两种方法的分析与比较

背包问题(KP)是计算机科学中典型的NP-hard问题,不存在多项式时间的精确算法。本文首先给出了求解0-1KP问题的一种改进的近似算法,讨论了算法复杂度与近似比;然后,给出了求解0-1KP的动态规划算法描述,并分析了算法的复杂度;最后,对两种方法进行了理论分析,并利用3个较大规模0-1KP实例的仿真计算结果与GDPSO进行比较。     

启发式搜索的一种新技术─SA算法

在一定的假设下，可把启发式搜索看作一种随机取样的过程。从而把统计推断方法引进搜索。根据上述思想．把Ｗａｌｄ序贯概率比检验方法与Ａ（Ａ＊）搜索结合，得到一种新算法──ＳＡ算法。文中讨论了该算法的优点及细节。最后通过一个实例说明算法的原理。     

人类群体的复杂系统研究刍议

“人”的系统具有其特定的涵义,“人”具有诸多复杂性,在其生存和发展过程中充满着特殊矛盾;“人”的系统是一个高层次的复杂巨系统;关于“人”的研究是最重要的研究,对于促进社会发展具有重要意义。     

不同生理状态时脑电时间序列的皮层信息传输

引用一种“信息传输”理论来研究不同生理状态时的脑电时间序列，比较了正常人和在急性缺氧条件下、睡眠条件下及局灶性癫痫病患者的大脑皮层信息传输，发现在各种情况下的大脑皮层信息传输有非常特殊的现象：在急性缺氧时，人的大脑皮层信息传输量各导联均较正常人高；当深睡时，各导联的信息传输量均较正常人低；局灶性癫痫病人痫性导联与其他导联间的皮层信息传输量有明显增加，而非痫性导联信息传输量 对降低，用脑皮层信息传输量来分析在不同生理状态下的脑电信号是一个极有潜力的方法，可能为研究和理解大脑的活动机理提供一条新的途径。     

COMPUTATIONAL COMPLEXITY OF INTEGRATION AND DIFFERENTIATION OF CONVEX FUNCTIONS

In this paper,we study the computational complexity of the integrals and the derivatives ofconvex functions defined on the interval [0,1].     

一类复合并行机排序问题的多项式时间算法

在经典排序论中，一般都作以下两条假设：每台机器在任一时刻至多加工一个零件，每个零件在任一时刻至多被一台机器加工。本文研究在并行加工中多台机器可同时加工一个零件的排序问题，且每个零件可在固定的一个机器的子集上加工。在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究这种问题的计算复杂性。