汉语PRECIS的计算机实现

本文叙述了 PRECIS的基本概念和PRECIS的汉语移植。解决了PRECIS应用于汉语中的实际问题。给出了汉语PRECIS的算法,并在PC机上用Turbo C语言实现。该系统具有良好的用户界面,且易于使用。     

随机图G（n，P）中k-团的相变性质

随机图G（n,P）模型是随机图理论中最重要的模型之一。该模型中有两个参数n和P,n表示图中的顶点数,P表示图中的任意两个不同顶点之间独立生成边的概率。证明了随机图G（n,P）中存在k一团的临界值为P=n^-2/k-1;同时证明了随机图G（n,P）中具有k≥3顶点孤立团的连通分量数服从均值λ=e^-x-k3/k!的泊松分布;最后,数值实验分析随机图G（n,P）实例中3-团托：和10一团的相变。数值实验结果表明,实验与理论结果相符。     

两个图算法的改进

Minty算法和Mayeda—Seshu算法是求无向连通图树清单的两个直观算法,它们都比矩阵算法节省计算时间。然而,它们仍然较复杂。本文分别对这两个算法提出了改进措施,大大降低了计算复杂性。改进后的算法既简单又直观易懂。对于Minty算法,我们提出了一个不完全算法;对Mayeda—Seshu算法,我们则避开了求基本割集这一复杂步骤。     

课程安排问题的数学模型及评价方法

本文建立了课程安排问题的数学模型,给出了课程安排优劣的量化评价方法。     

对关系的认识

在非空集合上引入各种关系,目的在于对集合中的元素信息进行研究时,可以借助于关系从其它元素的信息得到帮助。关系的性质是对关系进行限制,性质的闭包是对不具有指定性质的关系进行最小扩充。函数是一种特殊关系,图是关系的直观表示。     

膨胀图在随机算法设计中的应用

介绍了膨胀图的基本理论,组合膨胀与代数膨胀之间的联系,以及膨胀器构造方法等.系统地阐述了膨胀图在随机算法设计中的应用原理和方法.通过对"坏事件"发生的概率上、下界估计,给出了膨胀图在近似算法设计中的应用方法.     

可满足公式到极小不可满足公式MU(1)的扩张复杂性

可满足合取范式（CNF）公式F到极小不可满足公式MU（1）的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var（G）包含var（F）并使得F＋G∈MU（1）。Horn公式到MU（1）公式的扩张问题可在多项式时间内解决,但对一般CNF公式F的扩张问题,至今尚未解决。这里我们将给出一个多项式时间的算法解决这一问题。     

密度算子的性质及其应用

在量子力学中,密度算子作为量子系统的混合状态表示,其表达能力和性质得到广泛应用。本文基于矩阵和密度算子基础理论,利用Bloch向量表示单量子比特,得到纯态和混合态的密度矩阵的奇异值分解表达式和幂形式。通过分析密度矩阵的若尔当标准形,得到密度算子的一些特殊性质。利用密度算子的基本性质,通过选取二进制点作为量子比特的基矢,分析了由密度矩阵表示的多量子比特系统中量子叠加态的相干性,并研究了密度算子作为量子态可区分的数学理论。     

MXX和MARG中公式改名的复杂性

研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．     

大数据计算的基础理论探究

在经典计算中,对前端输入数据的复杂性不做分析。在大数据计算中,前端输入数据的复杂性分析反而成为大数据计算和分析的重点。本文讨论大数据计算的基础理论问题,将大数据计算问题分为目标任务型和内容认知型。大数据计算形式上依赖于一个外部信息源,从计算的有效性,将大数据计算的讨论限制在对数空间复杂类,涵盖了并行计算复杂类。基于带Oracle的图灵计算模型,限制在对数空间内图灵可计算,并且外部信息源能够用一个对数空间可计算的递归函数枚举,引入了大数据可计算的计算模型和大数据可计算性、可判定问题等概念。