PH的一种复杂性类分解

本文基于ΔPK-复杂性类给出多项式时间谱系PH的一个分解,并讨论了相关的一些性质。利用该分解给出PH是否只有有限个层次这一重要计算复杂性理论问题的两个充分条件,并证明了NP中稀疏集构成的语言类在LP2∧中。     

一种广义分子计算模型及其在 NP问题中的应用

目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题（SAT）,比现有分子计算模型在计算准确性和通用性上存在明显优势。     

基于分层着色Petri网的增强现实装配系统建模

为弥补场景图在增强现实装配应用中的不足,提出一种将层次着色Petri网与图灵机模型结合的方法,建立了增强现实装配环境系统模型。该模型借鉴图灵机的思想,以虚拟手的手势代号及位姿矩阵作为输入,输出具体操作事件更新场景图,记录系统的当前内部状态并根据用户输入给出下一步的操作响应。相对于单一的碰撞检测方法,该方法能更好地满足增强现实装配系统的动态实时响应等性能要求。开发建立了该模型的原型系统,并通过网络状态生成图分析验证了模型实时响应的能力。     

图灵，电脑的思想领袖

图灵提出的图灵机概念,为研制通用计算机奠定了思想和理论基础。1954年6月,图灵因为吃了有毒的苹果而在家中死去,年仅42岁。图灵一生虽短,但是他可谓是电脑的先驱,正是他提出的图灵机,成为计算机的思想和理论基础。后人为纪念这位"计算机科学之父",在英国曼彻斯特的Sackville公园为他建造了一尊真人大小的青铜坐像,这尊塑像是2001年6月23日,也就是图灵89岁诞辰那天揭幕的。图灵去世     

时间复杂性和空间复杂性研究

计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性,可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念,论述了时间复杂性（包括P、NP、NP-hard、NP-complete和EXPTIME）和空间复杂性（包括PSPACE、NPSPACE、PSPACE-hard和PSAPCE-complete）中的各个主要分类。最后分析了各个复杂性类之间的关系。     

“单片机原理”课程逐步启发式的课程设计

本文针对“单片机原理”的教学要求,设计了一个启发式的课程设计,通过在单片机平台上的一个计算器程序的逐步实现,在调试中让学生掌握单片机的硬件资源编程方法、领悟软硬件的统一性、理解图灵机计算的本质和图灵计算的限制。最为重要的,课程启发了学生们从学科体系的高度去理解课程的内容。     

基于角色访问控制管理模型的安全性分析

在基于角色的访问控制管理模型中,采用安全查询来描述系统安全策略,引入状态变换系统定义基于角色的访问控制管理模型及其安全分析,用图灵机理论和计算复杂性理论进行安全分析.将安全查询分类为必然性安全查询和可能性安全查询,证明了必然性安全查询和与状态无关的可能性安全查询能在多项式时间内被有效解决,给出了满足NP-完全问题的可能性安全查询的条件,而一般的可能性安全查询是不可判定的.     

时间Petri网模拟能力的研究

模型的模拟能力一直是系统建模方面的一个重要研究课题。本文先用一个直观的“零检验”例子说明时间Petri网的模拟能力比传统Petri网要强，并首次证明了时间Petri网与计算科学的最高模型——图灵机有相等的模拟能力；最后给出了另外一种含时间因素的时延Petri网向时间Petri网的转换方法，这说明了时间Petri网虽然形式上较为简单，但其模拟能力却并不比其它含时间因素的Petri网逊色，同时为时延Petri网的研究提供了另外一种有效方法。     

计算机免疫系统中识别器的改进

抓住入侵位串往往具有的相似性。在KMP字串匹配算法思想的基础上，结合图灵机模型抽象出了一种基于状态转移的字串匹配方案。通过对图灵机状态跳转函数的思索和状态树的构造，得到对于任意状态节点的最大后缀状态，从而大大地加快了识别器的识别效率。通过模拟实验，证明确实得到了较明显的提高。