图论算法复杂性问题(一)

本文论述了图论算法复杂性的基本理论和分析方法。由它的表示式和阶的运算,可以分析一个具体问题的算法复杂性,进而明确某一具体算法的有效性。     

最长公共子串的快速搜索算法

本文提出了两个字符串之间最长公共子串这一概念,并在对它进行理论分析的基础上,给出了两种求取最长公共子串的快速算法。     

多项式时间、指数时间复杂性类和Tally集

可计算复杂性类之间的差异和联系是结构复杂性理论中主要研究的问题,而多项式时间复杂性类P和NP与指数时间复杂性类E和NE之间的关系更加引人注目.众所周知:如果P=NP,则E=NE.但反过来是否有:如果E=NE,则P=NP,仍是一个未解决问题.有多种途径试图解决这个问题.Book证明了:E=NE当且仅当在NP-P中不存在Tally集;Hartmanis等证明了:E=NE当且仅当在NP-P中不存在稀疏集(sparse set),这就是著名的向上分离结果(upward-separation result).此外是相对化的应用,到目前为止,关于这个问题     

产生式系统的一种新匹配算法

本文提出了产生式系统的一种新匹配算法，并对新算法的时空复杂性作了估计，还进行了模拟试验，结果表明，新匹配算法明显提高了效率。     

关于相对化多项式界计算的一些结果

本文给出了三个相对化的 P 与 NP 的结果。在 S.Homer 及 W.Maass 的基础上,利用递归论中的优先方法,包括有穷损害优先方法。我们进一步研究相对化的 P 与 NP 问题的结构。比如,证明了存在两个互不可比的 P-禁集。此外,类似于递归中的算术分层及破分性,我们讨论了相对化多项式界计算的有关问题。     

EV-DO系统中的终端认证研究

作为CDMA2000 1x现实的演进方向，EV—DO系统能够更好地支持3G分组数据业务。根据3GPP2制订的协议并参考相关RFC，研究了EV—DO系统中存在的接入网络和因特网对终端认证机制的具体过程。在此基础上，对EV—DO系统的安全解决方案也进行了具体分析。     

利用Tsuprem4和Medici对200伏VDMOS进行虚拟制造

通过将已知工艺参数与工艺模拟软件Tsuprem4结合起来，将模拟结果直接导入器件模拟软件Medici，对击穿电压及阈值电压，终端保护环进行了模拟计算，获得了具体的设计参数，并对利用这两个软件进行虚拟制造的过程中需要注意的问题进行了阐述．     

密钥覆盖问题的NP完全性证明

 给出了密钥覆盖问题的模型建立过程,并从顶点覆盖问题的判定形式出发,证明了密钥覆盖问题的判定形式是NP完全问题,为组通信安全的研究,尤其是多播安全的研究奠定了更为坚实的基础.     

科学成果评价的复杂性

科学成果评价的目的是承认杰出研究.中国现行的科学成果评价体系中,评价标准和方法过于简单化,与科学活动及评价工作的复杂性实质相背离,因而存在不少问题和矛盾,也使中国科学研究及成果评价工作逐渐陷入尴尬局面.因此,要建立与完善科学成果评价体系,就必须从哲学层面认识科学成果评价活动的复杂性.从传统认识论的局限与向复杂性范式的转换、复杂系统及其复杂性、科学成果评价的复杂性、从复杂性看成果评价的方法论原则等4个方面探讨了科学成果评价活动的复杂性问题.     

移动机器人的并行免疫计算模型

为了支持未知环境下移动机器人自主导航，提出了移动机器人的并行免疫计算模型，为解决其在线导航优化、病毒／路障识别和计算效率问题提供了基础组织。免疫计算模型分为固有免疫计算层、适应性免疫计算层和并行／分布式计算层，并行免疫计算模型建立在此3个免疫计算模型基础上。探讨了移动机器人并行免疫计算模型的负载极限和负载平衡，分析了此类移动机器人系统的鲁棒性；提出了移动机器人并行免疫计算模型用于路障识别的方法。移动机器人并行免疫计算模型的复杂性分析及仿真结果表明，并行计算能提高其效率；仿真结果表明，移动机器人可消除病毒，并具有较高计算性能。