q树的色性

称为q树的图是递归定义的,最小的q树是q阶完全图K_q,一个n+1阶的q树是在n阶的q树上添上一个新点,并且添上邻接这个点与n阶的q树上任意选取的q个两两相邻的点的边而得到。     

高度近似最佳2-3树

2-3树是一种很重要的平衡搜索树。文献[1]中叙述了2-3树(也叫3-2树)的定义(在每个内点上存放一个或两个关键字,且分别具有两个或三个儿子点;所有外点在同一层上)。显然,具有N个关键字的2-3树,其高度h在log_3(N 1)≤h≤log_2(N 1)之间。在这种树上的最坏搜索时间是O(h)。文献[1]中还给出了对它的O(h)时间的插入算法。通过该插入算法插入每个随机关键字而生成的2-3树叫动态自由2-3树。文献[2]研究了N→∞时这     

关于Newton迭代的点估计

S.Smale在1986年国际数学家大会上报告了他关于连续复杂性理论的开创性工作。这个理论是借鉴计算机科学中关于代数与组合算法复杂性研究的观点,来处理分析算法的整体复杂性的。报告的基础性工作和在摘要中列为     

雨林精灵——树袋鼠

谁都知道澳大利亚以有袋类动物多而闻名于世,特别是袋鼠尤为突出,堪称这块大陆的"大地之子".其实袋鼠也并非澳大利亚的特产,在其附近的巴布亚新几内亚的热带雨林中也有一种袋鼠,它们生活在约30m高的树上,当地人称之为"雨林精灵".这些袋鼠的皮毛呈黄褐色,与树上的苔藓混为一体.它们可以在树枝上灵巧地移动,只有在获取食物时才冒然来到地面.     

q树的可重构性

对正整数q,称为q树的图是这样归纳定义的:最小阶的q树是q阶完全图K_q一个n+1阶的q树是在任意取定的一个n阶q树之外添加一个新点,并且添加邻接这个点与该n阶q树上任意取定的q个两两相邻     

O(n)时间有限Abel群同构检验算法

计算群论和复杂性理论中的一个重要问题是,有限群同构检验是可行的,还是NP完全的?这个问题迄今没有解决。C.Savage和陈溧分别得到一个O(n~2)时间的n阶Abel群同构检验算法。 本文得到,存在O(n)时间的n阶Abel群同构检验算法。即使使用对数成本的RAM,完成这样     

双周期阵列的迹表示

二维线性递归阵列在二维信息加密、雷达定位、声纳系统等方面有重要应用,因而得到数字通讯、密码学、信息加工和数学等领域专家的重视,二维线性递归阵列的研究主要涉及到多变元的多项式环,而不是主理想环,故与一维序列的研究方法有本质的不同,本义主要给出二维线件递归阵列的一个好的表示,称为迹表示,从而提供一个研究二维阵列结构的有力工具,目前,对于具有极大周期的二维线性递归阵列(即m-阵列)的迹表示在文献中已给出,进而对阵列的线性递归关系对应的理想只有2个生成元,且其一生成元在没有重根的条件下也得到迹表示,本文是研究一般的线性递归阵列,其对应的主理想只要求是Nother环中的理想,我们利用Gr(?)bner基理论,先找出阵列空问的一组特殊的基底,进而得到阵列的迹表     

具有给定叶数的T叉树的组合参数

D.E.Knuth曾广泛地讨论树结构的组合性质及其在计算机科学的应用,为了作更精确的算法分析,我们需要考察具有给定叶数的树结构。近年,王振宇研究了T叉树的几个组合参数(科学通报,28(1983),3:14)     

是"树"还是"网"?

一旦认识到基因水平转移并非次要因素,生物学家就开始重新审视进化树的意义.早在1993年,就有科学家指出,细菌和古生菌在进化树上更像一个网络.1999年,又有科学家声称："进化树已经不再适合被画成一棵树了.它并不存在于自然界中,而是人类擅自对自然界进行的归类."     

具有多值约束的广义左线性递归查询的有效计算

Ullman及Naughton等提出的左线性变换是一种类似于魔集变换的规则改写算法。由于左线性递归是实践中最常见的递归类型之一,并且变换后的规则的自底向上处理相当有效,因此左线性变换已被斯坦福大学的NAIL!系统、MCC的LDL系统用作递归     

图的二分问题唯一全局最优解实例与骨架计算复杂性

骨架分析是近年来理论计算机科学研究的热点, 对于NP-难解问题的启发式算法设计具有重要意义. 由于骨架计算复杂性研究十分困难, 现有的骨架分析方法多采用实验统计手段. 针对现有方法中存在的骨架规模小的缺陷, 给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法, 有效提高了骨架的规模. 同时, 利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题, 即在P≠NP的假设下, 不存在多项式时间的算法可以确保得到GBP问题的完整骨架. 本文的工作拓广了骨架计算复杂性研究的范围, 所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.     

多元线性递归序列的Lie双代数结构

多元线性递归序列具有广泛的意义,起初对于它在Hurwitz积下,从Hopf代数角度研究者是Perterson和Taft,并在文献中得到推广;在Hadamard积下,本文作者给出了一些刻划.以上均具有局限性,为此,我们首次从Lie双代数的角度探讨了多元线性递归序列的代数结构,避免了Hurwitz积或Hadamard积下且数域特征为零的限制.本文均在特征任意的数域R上进行,且仍以二元线性递归序列为主,多元情形的讨论是     

递归可枚举fuzzy集合的投影定理

B=叫做上完备的递归布尔代数,若它的域B是自然数集N的一个递归子集,它的运算∨(并),∧(交),(?)(补)为部分递归函数,且在B的元素的自然偏序之下,B的任一子集合X在B中有上确界,记为∨X。     

大毒树见血封喉

在我国的武侠小说中，有一种“见血封喉”的暗器，也就是说这些暗器上的毒药进人人的血液后，可以让人立即停止呼吸。善于使用这种暗器的是热带地区的一些少数民族。据传说，在西双版纳最早发现箭毒木汁液含有剧毒的是一位傣族猎人。有一次，这位猎人在狩猎时被一只硕大的狗熊紧逼而被迫爬上一棵大树，可狗熊仍不放过他，紧追不舍，在走投无路、生死存亡的紧要关头，这位猎人急中生智，折断一根树枝刺向正往树上爬的狗熊，结果奇迹突然发生了，狗熊立即落地而死。     

典型的“小欺大”黑熊被猫赶上树

2006年6月4日,一头黑熊误闯进了美国新泽西州维斯特·米尔弗得一个农场主家的后院内,结果遭到农场主家的宠物斑点猫杰克(体重7千克)的“呵斥”和威吓。黑熊最终竟然被吓得爬上了农场主邻居家的一棵大树,而杰克则不依不饶地一直在树下朝着黑熊“咆哮”,逼得黑熊在树上躲了15分钟不敢下来。直到杰克的“态度”稍为缓和后,黑熊才战战兢兢地下来了。不料。杰克再次向黑熊发起进攻,吓得黑熊     

网络最优化中的一个扩容算法

提出了网络最小割集与网络瓶颈的关系。提出了解决网络瓶颈问题的一个优化容算法，并分析了算法复杂性，算法通过在给出了容量的网络中全局正向分段引入虚拟发点，构造扩容网络搜索全部最小割集；对于指定的网络最大流量，算法反向逐级计算各个最小割集弧组相应的调整量，通过增加调整最来重新布局各弧的容量，逐级回代直至恢复原网络拓扑结构，从而改善网络的通行能力，解决网络瓶颈问题。     

典型的"小欺大"黑熊被猫赶上树

2006年6月4日,一头黑熊误闯进了美国新泽西州维斯特·米尔弗得一个农场主家的后院内,结果遭到农场主家的宠物斑点猫杰克(体重7千克)的“呵斥”和威吓。黑熊最终竟然被吓得爬上了农场主邻居家的一棵大树,而杰克则不依不饶地一直在树下朝着黑熊“咆哮”,逼得黑熊在树上躲了15分钟不敢下来。直到杰克的“态度”稍为缓和后,黑熊才战战兢兢地下来了。不料。杰克再次向黑熊发起进攻,吓得黑熊     

二值图像的数字搜索树表示及其线性编码

基于递归分解原则的四元树及八元树是表示二维及三维图像的一类重要的空间数据结构.这类结构传统上以指针方式实现,为了进一步压缩存储,可对结点先序遍历形成线性序列,即线性四元树(Iinear quadtree,简称LQ)及线性八元树(Iinear octree,简称LO)。LQ及LO的压缩编码已接近其极限。本文提出的二值图像的数字搜索树表示及其线性编     

从中性学说到非线性分子进化

盛极一时的分子进化的中性学说,在对分子水平遗传多态性的解释以及近缘物种的亲缘关系分析上,迄今仍不失其重要作用,但对远缘物种关系的分析上往往难以自圆其说.结构分子生物学的发展,证实三维构象比一维序列数据更具进化上的保守性并可揭示分子进化的非线性和复杂性.基于上述特性,一些学者分别提出了比较远缘物种(包含了近缘物种)亲缘关系的算法.本文对这些算法作一些扼要的介绍,并对非线性分子进化的美好前景作—展望.     

低复杂度Chase-2型级联码译码器

由里德-所罗门码(RS码)和递归系统卷积码(RSC)组成的级联码被广泛应用于现有的通信系统中, 如卫星通信系统和WiMAX系统. 介绍了一种用于这类级联码的低复杂度迭代软判决译码算法. 通过减少测试图样的使用数量, 对chase-2型算法进行了简化, 达到了减少运算复杂度的目的; 此外, 通过改进内外码解码器之间软信息的处理方法, 增加了软信息的使用效率, 改善了译码性能. 仿真结果表明, 改进型译码算法在性能和计算复杂度上取得了良好的平衡.