|
1.
|
基于余归纳的最小Kripke结构的求解
|
|
|
|
|
|
|
高建华 蒋颖《软件学报》,2014年第25卷第1期
|
|
|
状态空间爆炸问题是模型检测的最大障碍.从余归纳（特别是余代数）的角度研究了这个问题.用余归纳的方法证明：（1） 对于任意给定的一类Kripke结构（记为K），在互模拟等价意义下K中最小Kripke结构（记为K0）的存在唯一性.K0描述了K中所有Kripke结构的行为而且没有冗余的状态；（2） 对于任意的M∈K（M可能包含无穷多个状态），在互模拟等价意义下的相对于（M且基于K0）的最小Kripke结构（记为KM）的存在唯一性.由此提出一种求解KM的算法，并用Ocaml予以简单实现.其应用之一在于可以用状态空间更小的KM代替M进行模型检测.该方法可自然地推广到基于其他类型函子的余代数结构.
|
|
2.
|
具有O(n)消息复杂度的协调检查点设置算法 被引次数：9
|
|
|
|
|
|
|
汪东升 邵明珑《软件学报》,2003年第14卷第1期
|
|
|
协调检查点设置及回卷恢复技术作为一种有效的容错手段,已广泛地运用在集群等并行/分布计算机系统中.为了进一步降低协调检查点设置的时间和空间开销,提出了一种基于消息计数的协调检查点设置算法.该算法无须对底层消息通道的FIFO特性进行假设,并使同步阶段引入的控制消息复杂度由通常的O(n2)降低到O(n),有效地提高了系统的效率和扩展性.
|
|
3.
|
L1/2正则子在Lq (0 < q < 1)正则子中的代表性: 基于相位图的实验研究
|
|
|
|
|
|
|
徐宗本 郭海亮 王尧 张海 《自动化学报》,2012年第38卷第7期
|
|
|
近期, 正则化方法吸引了越来越多的关注. 在L1正则子之后，Lq (0 < q <1) 正则子被提出用于更好的求解稀疏性问题. 一个自然的问题是：在所有Lq (0 < q <1) 正则子中, 哪一个q是最好的选择？通过采用相位图, 以及一组关于信号恢复与误差校正问题的实验, 我们表明: (i) 随着q减小, Lq正则子得到更稀疏的解; (ii) 当1/2L1/2正则子始终产生最好的稀疏解，且当0 < q <1/2时，正则子的性能没有显著的区别. 因此, 我们认为L1/2正则子可被看作是一个Lq (0 < q <1) 正则子的代表.
|
|
4.
|
不可满足公式的同态证明系统 被引次数：1
|
|
|
|
|
|
|
许道云《软件学报》,2005年第16卷第3期
|
|
|
合取范式(CNF)公式H到F的同态φ是一个从H的文字集合到F的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于1的极小不可满足公式类.一个三元组(H,φ,F)称为的一个来自H的同态证明,如果φ是一个从H到F的同态.利用基础矩阵的方法证明了:一个不可满足公式F的树消解证明,可以在多项式时间内转换成一个来自MU(1)中公式的同态证明.从而,由MU(1)中的公式构成的同态证明系统是完备的,并且由MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的.
|
|
5.
|
图象处理中边界转换的并行算法及其实现
|
|
|
|
|
|
|
杨 勃 陈 虎 陈国良《软件学报》,1998年第9卷第2期
|
|
|
本文提出了一种把图象中边界转换成区域四分树的并行方法.该方法基于MIMD模型,并在曙光1000上实际运行.整个算法用P个处理器可以在时间O((B×logB)/P)内完成其中B是循环代码长度.该算法可应用于图象处理、计算机图形学、模式识别等领域.
|
|
6.
|
有Mate-Pairs的个体单体型MSR问题的参数化算法
|
|
|
|
|
|
|
谢民主 陈建二 王建新《软件学报》,2007年第18卷第9期
|
|
|
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2kn2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k1-1)k222h+(k1+1)2h+nk2+mk1)的新算法,其中,k1为一个片断覆盖的最大SNP位点数(不大于n),k2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.
|
|
7.
|
基于高斯方法及Sherman-Morrison公式的暂态稳定性并行计算方法
|
|
|
|
|
|
|
廖小兵 汪芳宗 杨萌《继电器》,2017年第45卷第4期
|
|
|
并行计算是实现大规模电力系统暂态稳定性实时分析计算的有效途径。将s级2s阶的高斯方法和扩展的Sherman-Morrison矩阵求逆公式相结合，提出了一类新的暂态稳定性并行计算方法。该方法首先利用s级2s阶的高斯方法对微分-代数方程组进行多级离散，并利用严格的牛顿法对离散后的非线性方程组进行整体求解。在此基础上，按s个时间点将整体雅可比矩阵分裂成为一个分块对角矩阵和一个分块常系数矩阵。然后，以分裂后的分块对角矩阵为基础，利用扩展的Sherman-Morrison矩阵求逆公式将s个时间点上的计算任务进行“解耦”。所提方法在保持严格牛顿法的收敛性的同时具有很好的并行性。利用OpenMP并行计算技术在多核计算机上对2个不同的系统算例进行了测试，结果表明，所提出的并行方法可以获得较好的加速比以及并行效率。
|
|
8.
|
3x+1推广函数T(x)不动点的存在区域分析与数值算法
|
|
|
|
|
|
|
刘帅 车翔玖 王钲旋《电子学报》,2011年第39卷第10期
|
|
|
3x+1推广函数T(x)的不动点性质及存在区域分析是分形中的一个重要研究问题.T(x)是结构复杂的超越函数,其在复平面上的不动点难于求解,不动点性质难于估计,这成为进一步研究T(x)动力系统的一个障碍.首先通过T(x)的拓扑不变性,给出了T(x)在复平面上存在不动点的构造性证明,分析了不动点的存在区域及其性质.根据存在区域,给出了T(x)的不动点在复平面上的分布.通过不动点的分布,提出了一种求T(x)不动点的数值算法.找到了T(x)在复平面上的多个收敛域,并绘制了收敛域处的分形图形.数值实验结果表明,本文算法正确、简捷.
|
|
9.
|
面向时序数据的矩阵分解
|
|
|
|
|
|
|
黄晓宇 潘嵘 李磊 梁冰 陈康 蔡文学《软件学报》,2015年第26卷第9期
|
|
|
研究一类特殊的矩阵分解问题:对由多个对象在一组连续时间点上产生的数据构成的矩阵R,寻求把它近似地分解为两个低秩矩阵U和V的乘积,即R≈UT×V.有为数众多的时间序列分析问题都可归结为所研究问题的求解,如金融数据矩阵的因子分析、缺失交通流数据的估计等.提出了该问题的概率图模型,进而由此导出了其约束优化模型,最终给出了模型的求解算法.在不同的数据集上进行实验验证了该模型的有效性.
|
|
10.
|
具有模态词□φ=□1V□2φ且可靠与完备的公理系统
|
|
|
|
|
|
|
邓少波 黎敏 曹存根 眭跃飞《软件学报》,2015年第26卷第9期
|
|
|
提出具有模态词□φ=□1V□2φ的命题模态逻辑,给出其语言、语法与语义,其公理化系统是可靠与完备的,其中,□1与□2是给定的模态词.该逻辑的公理化系统具有与公理系统S5相似的语言,但具有不同的语法与语义.对于任意的公式φ,□φ=□1V□2φ;框架定义为三元组W,R1,R2,模型定义为四元组W,R1,R2,I;在完备性定理证明过程中,需要在由所有极大协调集所构成的集合上构造出两个等价关系,其典型模型的构建方法与经典典型模型的构建方法不同.如果□1的可达关系R1等于□2的可达关系R2,那么该逻辑的公理化系统变成S5.
|
|
11.
|
RB模型实例集上置信传播算法的收敛性
|
|
|
|
|
|
|
王晓峰 许道云《软件学报》,2016年第27卷第11期
|
|
|
置信传播算法求解RB（k，n，α，rc，p）模型实例时非常有效，几乎能够有效求解接近可满足性相变点的难解实例.然而，因子图带有回路的实例，置信传播算法不总有效，常表现为不收敛.对于这种现象，至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法，对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k，n，α，rc，p）模型中，取k=2，α>（1/k），rc>0均为常数，且满足ke-（α/（rc））≥1.证明了如果p∈（0，n-2α），则置信传播算法在RB（k，n，α，rc，p）模型产生的随机实例集上高概率收敛.最后，在RB（k，n，α，rc，p）模型上选取了几组不同的数据进行数值模拟，实验结果表明该结论有效.当问题规模n增大时，在RB（k，n，α，rc，p）模型的可满足区域，实验收敛区间趋于一个固定范围，而理论收敛区间逐渐变窄.原因在于，RB（k，n，α，rc，p）模型是一个具有增长定义域的随机CSP实例产生模型，不协调赋值的数目与参数p及问题规模n有关.
|
|
12.
|
有限时段源一维水质模型的求解及其简化条件 被引次数：1
|
|
|
|
|
|
|
武周虎《中国水利水电科学研究院学报》,2017年第5期
|
|
|
有限时段源一维水质模型的求解及其简化为按瞬时源处理的判别条件，对事故性排放污水的应急计算具有十分重要的意义。在等强度有限时段源条件下，采用变量替换和拉普拉斯变换方法，求解了河流污染物浓度分布的解析解。在不同的简化条件下，讨论了该解析解与可对比解析解的一致性。定义了排放数Wt=u2t0/Dx，提出了有限时段源可以按瞬时源计算的临界时间tk（Wt）方程和简化判别条件：当扩散历时t<tk，按有限时段源的浓度分布公式计算；当扩散历时t ≥ tk，按瞬时源的浓度分布公式计算。
|
|
13.
|
提高电网攀峰响应能力的研究
|
|
|
|
|
|
|
刘长义 柳进 柳焯《水电自动化与大坝监测》,2002年第26卷第2期
|
|
|
高峰负荷时,许多大型发电机组运行于上限, 因此电力系统攀登陡峻峰荷的响应能力往往十分短缺。文中提出了一种借助快速优化调整来提高响应能力的方法。发电机组被分为调节余量充裕的机组集合(Cabund)和调节余量匮乏的机组集合(Cpinch)。基于响应能力分析，对各机组集合的输出功率进行调整：Cpinch压荷，Cabund增发,两集合分别进行优化，作为提高系统调峰响应能力快速而经济的手段。上述方法可用于替代添置燃汽轮机组，而前者的费用比后者少得多。
|
|
14.
|
排序的相互k-Skyband查询算法
|
|
|
|
|
|
|
蒋涛 张彬 余法红 柳晴 周傲英《软件学报》,2015年第26卷第9期
|
|
|
不同于传统的k-Skyband 查询方法,提出一种相互k-Skyband 查询(MkSB),它从对称角度执行Skyline查询,找出所有既在q的动态k-Skyband(DkSB)中又在q的反向k-Skyband(RkSB)中的数据对象.进一步地,为了更好地支持用户决策和数据分析,排序操作被引入到MkSB算法中.因为MkSB 需要执行q的DkSB 和反向RkSB,故它需要遍历索引多次,从而导致了大量冗余的I/O 开销.利用信息重用技术和若干有效的修剪方法,MkSB 将多次的索引搜索合并成单次,极大地降低了I/O访问次数.同时,证明了基于窗口查询的MkSB(WMkSB)算法具有最低的I/O 代价.在真实与合成数据集上的实验结果表明,所提出的算法是有效的且明显胜过基于BBS 的算法,尤其WMkSB 算法具有极少的I/O 开销,通常能够减少95%以上的冗余I/O.
|
|
15.
|
用擂台赛法则构造多目标Pareto最优解集的方法 被引次数：13
|
|
|
|
|
|
|
郑金华 蒋浩 邝达 史忠植《软件学报》,2007年第18卷第6期
|
|
|
针对多目标进化的特点,提出了用擂台赛法则(arena's principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0＜m/N＜1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN2)和O(Nlog(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.
|
|
16.
|
独立多处理机任务静态调度问题的近似算法 被引次数：1
|
|
|
|
|
|
|
黄金贵 李荣珩《软件学报》,2010年第21卷第12期
|
|
|
研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的√2m +1近似算法和问题Pm|fix|Cmax的2√m 近似算法,优于目前已有文献的最好结果.
|
|
17.
|
UNIX/XENIX系统PC仿真终端软件设计
|
|
|
|
|
|
|
丁隆厚《计算机系统应用》,1993年第2卷第11期
|
|
|
本文介绍了UNIX/XENIX系统PC仿真终端软件的设计思想，并给出了UNIX/XENIX与DOS间直接文件传输的实现方法。整个软件包可在各类PC机上运行。
|
|
18.
|
一种基于彩色编码技术的基序发现算法 被引次数：2
|
|
|
|
|
|
|
王建新 黄元南 陈建二《软件学报》,2007年第18卷第6期
|
|
|
从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K.
|
|
19.
|
一种新的细分曲线方法研究 被引次数：4
|
|
|
|
|
|
|
赵宏庆 彭国华 叶正麟 郑红婵 任水利 柯小玲《软件学报》,2004年第15卷第Z1期
|
|
|
对经典的四点细分格式进行推广，提出了可通过对形状参数的适当选择来实现对极限曲线形状调整和控制的三参数四点细分曲线造型方法，并对其收敛性进行了分析，同时给出了曲线C0到C3连续的克分条件，并加以证明．
|
|
20.
|
风力机流场速度数值模拟
|
|
|
|
|
|
|
胡丹梅 郑筱凯《上海电力学院学报》,2016年第32卷第5期
|
|
|
为了研究风力机在不同来流风速下和额定风速下运行时的尾流情况，采用数值模拟计算的方法，对美国可再生能源实验室（NREL）5 MW 风力机进行建模并选择不同来流风速进行数值模拟计算.通过模拟计算数据可以看出，风力机下游的风速在0D~4D区域内恢复迅速，在4D~12D区域内恢复缓慢，在12D~16D区域内恢复迅速.其中，在风力机下游6D距离处，来流风速恢复到接近来流风速的60%，在20D处恢复到来流风速的92.8%.由此表明，初始来流风速越大，风力机下游风速越容易恢复到初始风速，并且可以认为在下游20D处下游风力机不再受上游风力机的影响.
|
