构造有限域上具有给定阶点的椭圆曲线

考虑有限域上椭圆曲线的构造.设q是一个奇素数的方幂,l是一个素数.证明了,如果GF(q)[x]上的方程U²-D(x)V2=ε(x-a)^l有本原解,其中,D(x)∈GF(q)[x]是一个首1三次无平方因子的多项式,则椭圆曲线y²=D(x)上的点(a,b)的阶是l.由此,给出了一种构造具有给定阶点的椭圆曲线的算法.     

具有模态词□φ=□1V□2φ且可靠与完备的公理系统

提出具有模态词□φ=□₁V□₂φ的命题模态逻辑,给出其语言、语法与语义,其公理化系统是可靠与完备的,其中,□₁与□₂是给定的模态词.该逻辑的公理化系统具有与公理系统S5相似的语言,但具有不同的语法与语义.对于任意的公式φ,□φ=□₁V□₂φ;框架定义为三元组W,R₁,R₂,模型定义为四元组W,R₁,R₂,I;在完备性定理证明过程中,需要在由所有极大协调集所构成的集合上构造出两个等价关系,其典型模型的构建方法与经典典型模型的构建方法不同.如果□₁的可达关系R₁等于□₂的可达关系R₂,那么该逻辑的公理化系统变成S5.     

一类ω—正则语言

ω—语言是由有穷字母表∑上的某些无穷串组成的集合。被所谓的ω—有穷自动机接受的ω—语言称为ω—正则语言。在[4]中作者曾从集合的角度给出—ω—语言为ω—正则语言的几个充分条件。在本文作者仍从集合的角度给出一个ω—语言为ω—正则语言的充分条件,即若—ω—凸语言L满足L=adh(pref(L))=pref(L)tail(L),则L是—ω—正则语言。从而,确定了ω—正则语言类的一个子类。     

RB模型实例集上置信传播算法的收敛性

置信传播算法求解RB（k,n,α,r_c,p）模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k,n,α,r_c,p）模型中,取k=2,α>（1/k）,r_c>0均为常数,且满足ke^{-（α/（r_c））}≥1.证明了如果p∈（0,n^-2α）,则置信传播算法在RB（k,n,α,r_c,p）模型产生的随机实例集上高概率收敛.最后,在RB（k,n,α,r_c,p）模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB（k,n,α,r_c,p）模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB（k,n,α,r_c,p）模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

不同通信模型下的全光树环网波长分配算法

研究了波分复用全光树环网在不同通信模型下的波长分配算法及其最坏性能分析.对于静态模型,证明了5L/2是树环网所需波长数的紧界.对于动态模型,提出了一种近似比为∑_i=1^hmax_r∈Ri[log|V(r)|]+h的波长分配算法,其中h为树环网的基树的层数,R_i为树环网中处于第i层的环的集合,|V(r)|为环r上的节点数.对于增量模型,提出了一种近似度为O[log₂(t+1)]的波长分配算法,其中t为树环网中的环数.     

模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

矩阵条件数及高斯算法平滑分析的进一步研究

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n³).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ²≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og₂(n)+3log₂(1/σ)+log₂log₂n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og₂n+3log₂(1/σ)+4√2+log₂n+log₂(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n²)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og₂n+3log₂(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.     

无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

独立多处理机任务静态调度问题的近似算法

研究独立多处理机任务静态调度问题P_m|fix|C_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题P_m|fix|C_max和其中所有任务都是单位处理机时间的特殊情形P_m|fix,p=1|C_max的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题P_m|fix,p=1|C_max的√2m +1近似算法和问题P_m|fix|C_max的2√m 近似算法,优于目前已有文献的最好结果.     

粗糙集的最优近似集

Pawlak教授提出的粗糙集理论是解决集合边界不确定的重要手段,他构建了边界不确定集合的两条精确边界,但没有给出用已有知识基来精确或近似地构建目标概念(集合)X的方法.在前期的研究中提出了寻找目标概念X的近似集方法,但并没有给出最优的近似集.首先,回顾了集合间的相似度概念和粗糙集的近似集R_λ(X)的构建方法,提出并证明了R_λ(X)所满足的运算性质.其次,找到了R_λ(X)比上近似集R(X)和下近似集R(X)更近似于目标概念X的λ成立的区间.最后,提出了R_0.5(X)作为目标概念的最优近似集所满足的条件.     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

微机网上的分布式专家联合系统UNION(上)

本文描述微机网上的分布式专家联合系统UNION的设计思想、目标、体系结构和原理。UNION是继1985年陆汝钤提出分布式专家系统的概念及其设计思想之后于次年夏天开始组织实现的一个实验系统。目标机型是配有UNOS操作系统、PASCAL和C语言的MC68000微机,它们用Ethernet局部网联网。UNION目前已完成支撑系统Sup- port1和通信系统,其余部分正在实现中。UNION的工程实现由中国科学院数学研究所承担。     

利用MODIS数据估计中国黄东海区域测深参数

目的 现有关于漫衰减系数的研究大多是在490 nm波段建立反演模型,且未将相关研究与机载激光雷达测深能力建立联系,本文尝试获取测深参数532 nm漫衰减系数K_d(532)和透明度SD(Secchi disk depth),为机载双色激光雷达测深能力的评估和飞行方案的制定提供了重要技术参数。方法 首先分析了测深参数532 nm漫衰减系数K_d(532)和透明度SD对于评估机载双色激光系统测深能力的重要性。利用2003年春季中国黄东海区域的实测光学数据,对现有的漫衰减系数反演模式进行改进,建立了K_d(532)和K_d(490)=的线性关系以及SD和K_d(532)的幂函数关系。结果 根据2003年春季MODIS的490 nm漫衰减系数产品和上述函数关系获取了K_d(532)和SD参数。结论 本文获取测深参数K_d(532)和SD的方法能够用来有效评估该区域机载激光雷达的测深能力,准确性和精度依赖于实测光学数据的精度、分布和数量以及MODIS的K_d(490)产品的准确性。     

QBF问题中隐蔽集的求解过程

隐蔽集作为QBF问题的重要结构之一,能使QBF这一难求解问题变得更加简单. QBF问题中隐蔽集的求解相当复杂且难以理解. 为了使读者更好的理解QBF问题中隐蔽集的求解过程,本文对QBF问题中隐蔽集的求解过程进行深入研究,结合实例计算变量的深度、选择符合条件的变量X并计算其对应的三角依赖变量集D_ψ^Δ（x）,根据B=B∪{x}=x和ψ''=ψ-D_ψ^Δ（x）的思想求解出问题的隐蔽集,希望本文能为该领域的相关研究人员提供一定的参考.     

有中断时间代价的一致并行机抢先调度问题

提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|C_max):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|C_max的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.     

基于XYZ/E描述和验证容错系统

研究使用XYZ/E描述和验证容错系统.基于XYZ/E中可执行程序P对应的状态转换系统对其错误环境F建模,通过错误转换给出错误影响程序P_F;基于P,F和恢复算法R,通过容错转换给出容错程序P_F-R;定义了程序P,Q之间两种求精关系:容错求精和向后恢复求精,基于这两种求精关系可直接从程序P的规范推导出程序Q满足的一些性质.     

描述逻辑ALC中关于伪子概念极小改变的R-演算

AGM公设是用于信念修正的（被一个单一信念修正）,而DP公设是用于迭代修正的（被一个有限的信念序列修正）.李未给出了对于R-构型（configuration）△|Γ的R-演算,其中,△是一个原子公式或原子公式否定的集合,而Γ是一个有限的公式集合.为了在修正过程中能够保留断言中尽可能多的信息,将考虑一种新的极小改变的定义：伪子概念极小改变（≤-极小改变）,其中,≤是一种伪子概念的关系;之后,在此基础上给出一种新的R-演算T^DL,它是关于≤-极小改变可靠和完备的,使得△|Γ在T^DL中可以被约减为一个理论△∪Θ（记作├_T^DL △|Γ⇒△,Θ）当且仅当Θ是Γ关于△的一个≤-极小改变.     

基于余归纳的最小Kripke结构的求解

状态空间爆炸问题是模型检测的最大障碍.从余归纳（特别是余代数）的角度研究了这个问题.用余归纳的方法证明：（1） 对于任意给定的一类Kripke结构（记为K）,在互模拟等价意义下K中最小Kripke结构（记为K₀）的存在唯一性.K₀描述了K中所有Kripke结构的行为而且没有冗余的状态;（2） 对于任意的M∈K（M可能包含无穷多个状态）,在互模拟等价意义下的相对于（M且基于K₀）的最小Kripke结构（记为K_M）的存在唯一性.由此提出一种求解K_M的算法,并用Ocaml予以简单实现.其应用之一在于可以用状态空间更小的K_M代替M进行模型检测.该方法可自然地推广到基于其他类型函子的余代数结构.     

巧用Borland C++资源编辑器

BorlandC＋＋3.1提供了DOS和Windows两种环境下的软件开发平台。其Windows环境下的可执行文件WORKSHOP.EXE是一个功能强大的资源编辑器（简称编辑器），为开发利用Windows环境下的应用程序提供了强有力的辅助工具。