并发程序设计的互斥、同步及其复杂性

并行性指同时性和并发性.由于进程的并发执行,产生资源共享问题,必须考虑进程的互斥与同步问题,这增加了程序设计的难度.本文讨论并发程序设计中的互斥及同步方法,并以SISD,SIMD,MIMD等3种计算机系统结构为例,分析各种并发程序的复杂性函数.这里主要讨论程序执行时的时间复杂性问题.     

一种只需4N~2单元的N阶矩阵快乘法及其实现

本文改进了V.Strassen矩阵快乘算法,在时间复杂性保持相同,但将其空间复杂性从ON~(2.81)降至4N~2。文中还给出了改进算法的实现技术。     

一种求单源单汇点无环图最短路径的新算法

用Ｄｉｊｋｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ２）．笔者提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）（其中ｎ是图中顶点数，ｅ是边数），且两种算法的空间复杂性基本相同。     

递归程序的复杂性问题

递归是一种程序设计方法。递归算法能将很复杂的问题用十分简洁的形式加以表达。然而递归程序的复杂性很高,所以通常光用递归程序描述问题,然后设法变换为效率较高的程序。本文给出计算递归程序复杂性的公式,并讨论了降低递归程序复杂性的几种方法。     

一种新的子空间聚类算法

通过对数据空间进行网格划分并寻找稀疏区域来发现类的边界，提出了一种基于密度与网格的新的子空间聚类算法．该算法使用投影寻踪的搜索策略来发现存在于子空间内的类，同时运用基于竞争的修剪方式来有效地控制算法的计算复杂性．实验结果表明，所提算法在精度、时间复杂性等方面具有优良性能.     

算法的时间复杂性的讨论

本文按程序的结构分类确定时间的数量级．当找到算法对应的程序时，便得出算法的时间复杂性．这是解决在最坏情况复杂性的一般性问题的新方法．     

信息系统结构复杂性与可扩展性关系

目的研究信息系统结构复杂性与可扩展性之间的内在联系.方法利用基于信息系统的Petri网模型,并借助于网论中的数学工具,定量地分析了结构复杂性对网络结点耦合特性的影响.结果分析结果表明,要想获得一个结构上相对稳定、又具有一定应变能力的信息系统,其首要的目标是从设计上降低其结构的复杂性,尤其要考虑的是降低其关联复杂度.结论该分析结果可有效地用于信息系统设计方案的优选和综合性能分析.     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

论科学研究与复杂性

科学研究目的在于追求真理，探索世界的奥秘。然而，复杂性却一直与科学研究相伴面生，可以说科学研究的目的就是探索复杂外部世界的简单规律。20世纪80年代兴起的复杂性研究，直接将复杂性作为其研究对象，试图建立描述复杂真实世界的复杂性科学。本文通过对科学研究发展历程的回顾，论述了科学研究与复杂性之间的关系，阐明了复杂性的基本含义，探讨了复杂性研究以及复杂性研究的科学性等问题。     

从均衡到经济复杂性

在对经济均衡理论和均衡分析的概括和评述的基础上,探讨了经济复杂性的基本涵义及其主要表现形式:涌现复杂性和演化复杂性,强调了归纳推理以及多主体模型方法在经济复杂性研究中的重要地位.从均衡到复杂性是回归经济本原,提升经济学科学化的有效途径.     

分类大规模数据的核向量机方法研究

标准的支持向量机算法需要求解二次规划问题,因此,在处理大规模样本的时候,求解二次规划问题的时间复杂度和空间复杂度就成为支持向量机应用的一个瓶颈.核向量机将传统支持向量机中的二次规划问题转化为求解最小包围球问题,从而显著降低了二次规划的复杂程度.使用核向量机对大规模数据进行分类,所选用的数据样本数均超过2000,并与标准的支持向量机作了对比实验结果表明:核向量机在处理大规模数据分类时,比标准的支持向量机计算复杂度低,训练速度快,耗费空间少.     

基于LPSVR的区域经济发展预测算法

针对区域经济社会系统指标数据存在的高度非线性和二次规划过程涉及的计算复杂性,建立了基于线性规划支持向量回归的区域经济发展预测算法LPSVR。针对预测结果的可信度问题,在LPSVR算法中引入了预测信任度的概念,并给出了具体的计算方法。LPSVR算法在优化过程中折中考虑了经验风险和置信范围,因而具有良好的泛化能力。LPSVR采用线性规划取代二次规划,使得计算的时间和空间复杂度大为降低。以江门市的经济发展预测作为研究实例,LPSVR算法给出了满意的预测结果和预测信任度。     

基于高分片段对的双序列比对分治算法SPDCA

针对传统双序列比对算法的高时空复杂性,在动态规划比对算法的基础上,引入了片段对和分治思想,提出了一个新型的基于高分片段对的分治算法.模拟结果表明:该算法在降低了双序列比对算法的时空需求的同时,还能发现双序列之间微弱的相似关系,可适用于序列数据库相似性的搜索.     

基于效率最优的单纯形法的改进

提高单纯形法的运算效率是运筹学一直在研究的一个重要问题.文章通过对传统单纯形法的计算机程序化算法的改进,降低了时间和空间复杂度,使两者的效率均达到了o（1）.经过大量实例证明,改进后的算法还减少了进行单纯形法变换时所用到的迭代次数.     

基于动态筛选算法的二元判定图的优化

作为逻辑布尔函数的一种高效简洁的描述方法,BDD规模结构对应着计算机实现算法的空间和时间复杂性。随着应用领域的不同,BDD的节点和路径的规模成为关注的两个焦点。文章讨论利用基于动态规划的筛选算法来实现从节点规模和路径的大小两方面对BDD的优化。在将筛选算法用于节点优化的基础上,从理论上提出了优化路径的思路及可行算法。     

基于多目标规划和业务区分的多QoS约束路由算法

针对大多数QoS路由选择算法所存在的问题,采用多目标规划和业务区分的方法建立了满足多QoS需求和网络资源利用率的路由选择数学模型,对Fallback＋算法作了进一步扩充和改善．提出了一种新的Fallback＋＋算法,它不仅能满足多QoS约束,而且能高效地利用网络通信资源．分析得出该算法的时间复杂度和空间复杂度均为O（n＊N^2）．仿真实验验证了该模型和算法的有效性和正确性．     

冒泡排序算法及其改进算法的实验分析

排序是计算机科学的基本问题之一.通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算法,总结出它们的时间复杂度为O(n2)和空间复杂度为O(1).通过编程验证了四种排序算法在不同随机度情况下的性能,指出它们的适用原则:当随机度比较小时,应选取非传统冒泡排序算法;当随机度比较大时,则应选取传统冒泡排序算法.实验表明,四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系,传统冒泡排序算法的时间消耗与输入序列随机度近似地呈水平直线关系,而其它三种算法的时间消耗与输入序列随机度呈40?左右的斜线关系.     

求解一类整数规划问题最优解的算法

本文给出了求解一类整数规划问题所有最优解的两个算法．一个算法较为简单，其时间复杂性为O（n）,另一个算法求解较为快速，其时间复杂性为O（log n）.     

应用邻接多重表存储结构的配电网可靠性评估算法

结合复杂配电网的特点,提出基于邻接多重表的复杂配电网可靠性评估分块算法。首先给出适合于配电网数据存储的邻接多重表构造方法及存储结构,解决了网络搜索的空间、时间复杂度问题。基于此提出配电网前推回代潮流计算方法及配电网可靠性评估的分块形成算法。该算法可使配电网潮流计算与可靠性评估分块算法采用同种存储结构,简化了配电网可靠性计算程序的编制,并可节省计算时间。应用该算法对RBTS-BUS6及实际工程系统进行了可靠性评估,算例表明该算法可有效减少计算时间,具有较高的工程实用价值。     

考虑不均匀发车间隔的公交网络时刻表优化模型

公交网络时刻表设计就是通过优化各线路车次的发车时间,使不同线路的车辆协同到达换乘站点,以方便乘客换乘.研究了不均匀发车间隔情况下公交网络时刻表设计问题.使用数学不等式描述了乘客的换乘等待时间,构建了以最小化乘客总换乘等待时间为目标的混合整数规划模型,分析了该模型的计算复杂性和可行解的空间结构特征.基于模型特征分析,设计了能缩减求解空间的预处理方法.采用CPLEX优化软件对预处理后的模型进行求解.通过计算不同算例,验证了求解方法和模型的有效性.