关于矩阵张量积计算的研究

利用矩阵张量积有关理论,讨论了矩阵张量积的计算问题,分析了算法的复杂性,并研究了并行算法及计算复杂性问题。     

素数分解两种实现算法

用计算机做大素数分解，基于计算复杂性理论原理，当分解的素数是NP－完全问题的时候，采用了二种查找验算程序即：试除法、素数因子法、并给出了算法流程图和程序清单。     

AKS算法对现代密码学的影响

最近,印度的三个计算机科学家ManindraAgrawal、NeerajKayal和NitinSaxena提出了一个称为AKS的算法。笔者使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定,从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意义。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上,因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。     

谈计算机专业实践教学中计算思维能力的培养

阐述了计算理论(可计算性与计算机复杂性理论)中的几个典型问题,以图灵机模型、停机问题、近似算法及装箱问题等为例从不同角度分析计算理论与计算思维的密切联系,强调计算机专业实践教学中计算思维能力培养的必要性。     

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

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

精确覆盖问题的O(1.414n)链数DNA计算机算法

DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.     

MCC-SIMD数据并行卷积计算方法的研究

主要研究卷积计算的数据并行方法在MCC-SIMD计算机的设计和实现问题。在参考国内外现有资料的基础上，从图论的角度用卷积路径的方法对卷积计算的有关概念进行了严格的形式化定义；分析了4-连接卷积路径下数据并行卷积计算时处理元阵列的移动规律；在此基础上给出了数据并行卷积计算算法；最后对算法的计算复杂性和通信复杂性进行了简要分析。文中还对有关结论进行了证明。     

一种多限制路径的预计算路由算法

该文研究了多限制路径选择问题,提出了一种基于有限选择洪泛的源路由预计算的服务质量路由算法。算法通过限制节点保存的优化路径的数目和链路的广播次数降低计算复杂性。计算机仿真表明算法是有效的,可扩展的,并能提供满意的呼叫阻塞性能。     

子集和问题的O(1.414n)链数DNA计算机算法

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.     

数值计算程序的存储复杂性分析

由于越来越多的技术用于缩小处理器与存储器之间的日益加大的速度差距,计算机的存储系统变得日趋复杂．现在,任何一个程序设计者,尤其是数值计算程序的设计者,若不考虑其所用计算平台存储系统的特点是很难获取高性能的．因此公用传统的算法评价方法,从时间复杂性和空间复杂性着手来解释一个算法的不同实现在同一计算平台上很大的性能差异,显然是不够的．计算平台存储系统的特点必须在分析算法的复杂性时加以考虑．孙家昶１９９     

有向哈密尔顿路问题的研究

DNA计算是在分子水平上进行的计算,与传统的基于电子计算机的线性计算系统相比较,具有如可并发计算、耗能量小等无法比拟的特点。目前的研究主要集中在一些特定问题上,如NP完全问题,而这些问题在电子计算机上需要指数时间。本文利用已有的Adleman实验[1]解决有向图哈密尔顿路问题,给出了剪贴计算模型的形式化模型,并从算法复杂性角度分析其复杂性。     

美国2001‘计算教程综述

1.Computing’91教程回顾 1991年,美国计算学科主要的专业学会ACM和IEEE-CS联合颁布了Computing’91教程。该教程力图覆盖计算学科的计算机科学、计算机工程、计算机科学与工程的各类本科生专业。Computing’91教程的提出对国内外计算机教育界产生了较大影响,该教程的系统性、完整性、合理性和灵活性均受到普遍的称赞。中国计算机学会教育委员会和全国高等学校计算机教育研究会也联合制定了类似的教程:“计算机学科教学计划1993”。Computing’91教程第一次对计算学科给出了透彻的定义:计算学科系统地研究信息描述和变换的算法,研究算法的理论、分析、设计、效率、实现和应用。一切计算的基本问题是“什么能被有效地自动化?”计算学科具有科学与技术的双重性。显然“计算”是广义的,并用这个术语来统一地指称现行的各类计算机专业。该定义是科学的、动态的,反映了学科的共性及     

基于粒计算的双权网络分层算法

复杂网络环境下数据分布优化问题是个NP问题,但由于大多复杂网络有层次性特征,在此情形下可降低优化问题计算复杂性。应用粒计算理论提出了一种双权分层网络数据分布优化模型和算法,将双权复杂网络映射成一个分层网络,在分层网络上计算数据优化解。算法的时间复杂度为O（C×n2）。仿真实验表明,算法能够得到数据分布优化的满意解,且可通过调整子网络的粒度达到实际应用的需求。     

投票理论研究现状及其展望

社会选择理论是研究如何表达和聚合个体选择的一门学问.而社会选择理论与计算机科学的融合产生了称为计算社会选择的交叉学科,该学科成为社会计算的重要研究内容之一,在人工智能、经济和计算性理论领域引起了轰动.其一方面引入了复杂性分析和算法设计等计算机学科中常用的技术来对社会选择机制进行研究;另一方面也通过引入社会选择理论中的概念来推动计算机技术的发展,特别是在多智能体系统研究中有着成功的应用.投票理论是计算社会选择中最重要的研究主题之一.首先介绍常见的投票方法以及投票理论的形式化框架;再对投票理论中所关心的操纵问题做分析;然后介绍在组合域上的投票;最后对其他相关问题作简要介绍,并对该领域未来的发展与应用做出展望.     

一种主动存储计算机模型

提出了一种新型的主动存储计算机模型，其特征是存储器单元不仅可以有传统的读写操作，还可以有执行操作，这个模型扩展了传统的随机访问计算机（RAM）模型，可以用来研究一些新型计算模式的体系结构机制和算法设计与分析，如SoC、可重构计算、并行计算、网格计算、万维网服务等，对于网格计算，这个模型可用于研究网格协议与执行机制、网格算法的正确性和复杂度以及网格客户端与服务器端的有效交互。     

分布式采样理论综述

采样是一类基本的计算问题.从一个解空间中依特定概率分布进行随机采样,这一问题在近似计数、概率推断、统计学习等方面都有着诸多重要的应用.在大数据时代,采样问题的分布式算法与分布式计算复杂性受到越来越多的关注.近年来,有一系列的工作对分布式采样理论展开系统性的研究.综述了分布式采样的重要结论,主要包括有严格理论保障的分布式采样算法、采样问题在分布式模型上的计算复杂性以及采样与推断等问题在分布式计算模型中的相互联系.     

演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

基于智能计算的计算机网络可靠性分析研究

文中的研究对象是计算机网络可靠性分析的智能数值求解,将几种常见的网络系统可靠性分析方法应用于计算机网络。并在一般节点遍历法的理论分析的基础上对改进后的节点遍历法进行了深入的探讨。介绍了计算机网络系统以及可用于计算机网络系统的集中可靠性分析的相关概念及方法,然后着重对节点遍历法等一些算法做了算法分析和具体实现,使繁杂的算法易于理解。网络系统可靠性数值计算量大而繁琐,改进后的节点遍历法可以大大减少其运算量。文中提出的智能粒度分层分析方法可以较好满足一定范围内计算机网络可靠性数值计算的需求。     

基于智能计算的计算机网络可靠性分析研究

文中的研究对象是计算机网络可靠性分析的智能数值求解，将几种常见的网络系统可靠性分析方法应用于计算机网络。并在一般节点遍历法的理论分析的基础上对改进后的节点遍历法进行了深入的探讨。介绍了计算机网络系统以及可用于计算机网络系统的集中可靠性分析的相关概念及方法，然后着重对节点遍历法等一些算法做了算法分析和具体实现，使繁杂的算法易于理解。网络系统可靠性数值计算量大而繁琐，改进后的节点遍历法可以大大减少其运算量。文中提出的智能粒度分层分析方法可以较好满足一定范围内计算机网络可靠性数值计算的需求。     

粒计算在数字逻辑电路分析与设计中的应用

逻辑优化是数字逻辑电路分析与设计的关键,对于降低系统复杂性,减少系统功耗和提高系统安全性有重要作用。随着数字逻辑电路规模的不断扩大,传统的理论将面临新的挑战。从知识工程角度看,逻辑优化的本质是知识约简的过程。粒计算(granular computing,Gr C)是处理大规模、复杂问题的人工智能新方法。在简述现有逻辑优化算法和粒计算理论发展现状的基础上,研究了粒计算理论中的等价关系、相容关系、覆盖等知识模型以及用粒矩阵刻画的知识发现算法,指出了将其应用于大规模数字逻辑电路逻辑优化的研究方向与研究思路。