• 2006年第17卷第7期文章目次
    全 选
    显示方式: |
    • 考虑样本不平衡的模型无关的基因选择方法

      2006, 17(7):1485-1493.

      摘要 (4380) HTML (0) PDF 655.99 K (5083) 评论 (0) 收藏

      摘要:在基因表达数据分析中,鉴别基因是后续研究中非常重要的信息基因.有很多研究致力于从基因表达数据中选出信息基因这一挑战性工作,并提出了一些基因选择方法.然而,这些方法(特别是非参数选择方法)都没有考虑不同样本类别中样本大小的不平衡性问题.考虑样本不平衡性和基因选择方法的稳定性,给出一个全新的与数据分布模型无关的基因选择方法.在类内变化小和类间差别大的策略下,选择敏感的度量函数提高方法的鉴别能力,同时,利用类内变化和类间差别的一致性来增加方法的稳定性和适用性.这一方法不但可以应用于两个类别的情况,也可以应用于多个类别的情况.最后,使用两组真实的基因表达数据对所提出的方法进行了验证.实验结果表明,这一方法比其他方法具有更高的有效性和稳健性.

    • 测试集问题的集合覆盖贪心算法的深入近似

      2006, 17(7):1494-1500.

      摘要 (4795) HTML (0) PDF 421.39 K (5293) 评论 (0) 收藏

      摘要:测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).

    • RNA二级结构预测中动态规划的优化和有效并行

      2006, 17(7):1501-1509.

      摘要 (4688) HTML (0) PDF 705.47 K (4805) 评论 (0) 收藏

      摘要:基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.

    • 不可否认协议时限性的形式化分析

      2006, 17(7):1510-1516.

      摘要 (4480) HTML (0) PDF 560.69 K (4483) 评论 (0) 收藏

      摘要:虽然SVO逻辑由于其简单性在对不可否认协议的形式化分析中得到了广泛的应用,但它在时间描述能力上的不足使得它无法分析不可否认协议的时限性.通过向SVO逻辑添加一种简单的时间表达和分析方法扩展了SVO逻辑,并使用扩展后的逻辑对Zhou和Gollmann于1996年提出的一个公平不可否认协议及其一个改进协议进行了分析.分析结果表明,原协议不具有时限性,而改进协议具有时限性,因此也说明了扩展后的新逻辑能够分析不可否认协议的时限性.另外,新逻辑还能用来分析一般密码协议中的时间相关性质.

    • MAX(1)和MARG(1)中公式改名的复杂性

      2006, 17(7):1517-1526.

      摘要 (4041) HTML (0) PDF 621.77 K (4350) 评论 (0) 收藏

      摘要:改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.

    • 多连通多边形的内部Voronoi图的顶点和边数的上界

      2006, 17(7):1527-1534.

      摘要 (4377) HTML (0) PDF 472.52 K (4464) 评论 (0) 收藏

      摘要:多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中nk分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.

    • 虚拟环境下基于语义的三维交互技术

      2006, 17(7):1535-1543.

      摘要 (3956) HTML (0) PDF 503.58 K (9618) 评论 (0) 收藏

      摘要:自然、高效的三维交互技术是虚拟现实系统成功应用的关键.现有的交互技术主要是从几何层次上考虑如何有效实现交互任务,而对面向高层应用的交互任务的支持还不够.借鉴人类在真实世界中的认知原理,虚拟环境中的交互对象不仅具有外观意义上的几何属性,而且包含了与交互有关的规则、约束和供给等语义属性,这些虚拟对象称为语义对象.在系统导航、对象选择/操作等交互任务的执行中,通过语义对象可以实现高层交互语义的封装和解析.从应用角度提高交互技术的效率和可用性,为用户提供"直接操纵"之上的面向高层语义的交互隐喻,屏蔽交互技术的底层实现细节,使用户专注于应用领域相关的高层交互控制.

    • 基于改进稀疏场算法的水平集形状过渡

      2006, 17(7):1544-1552.

      摘要 (3822) HTML (0) PDF 555.30 K (4564) 评论 (0) 收藏

      摘要:水平集进化是基于体模型进行三维形状过渡的常用方法,窄带算法和稀疏场算法能高效实现水平集进化,窄带算法的结果较为平滑,稀疏场算法速度更快.一方面通过改进稀疏场算法应用于欧氏距离模型提高速度,另一方面运用窄带算法弥补稀疏场算法的误差.提出用拓扑关系代替距离值范围定义各层体素集,并通过单侧活动集定义使算法更为高效和鲁棒.稀疏场算法因为欧氏距离的近似计算引起误差,在过渡的中后期走样明显,为此,提出了均值平移和窄带回退两种反走样方法对过渡模型进行平滑,前者简单、快速,后者失真度低.

    • 高性能的EBCOT编码及其VLSI结构

      2006, 17(7):1553-1560.

      摘要 (4607) HTML (0) PDF 524.85 K (4548) 评论 (0) 收藏

      摘要:提出了比特平面与编码过程全并行处理的EBCOT(embedded block coding with optimizedtruncation)编码结构.通过分析JPEG2000和国内外提出的EBCOT编码结构,指出不仅每一个比特平面,而且对应的编码过程的编码信息可以同时获得,从而给出了比特平面与编码过程全并行处理的块编码方法,并且详细说明了实现的VLSI结构.理论分析以及具体实验结果表明,比特平面与编码过程全并行处理所需的时钟周期最少,FPGA原型系统最高时钟频率可达65MHz,对于512×512的灰度图像,处理速度可达30fps,完全可以实时处理,图像质量达到了公布的JPEG2000标准.

    • 基于三维多项式映射的广义Julia集表示与绘制

      2006, 17(7):1561-1570.

      摘要 (4111) HTML (0) PDF 661.28 K (4295) 评论 (0) 收藏

      摘要:研究了基于三维多项式映射的三维广义Julia集表示方法.从理论上分析并证明了三维多项式映射满足等变的条件,精确地给出了关于正四面体群和正八面体群具有旋转不变对称性的两类三维等变映射的具体公式,在此基础上讨论并证明了三维多项式映射的广义Julia集所具有的性质.提出了基于逃选距离色彩调配的光线跟踪体绘制算法,对给定三维空间中属于Julia集的离散点根据其逃逸距离赋予颜色和不透明度,并采用光线跟踪法进行体绘制.实验结果表明,利用三维多项式映射来构造三维Julia集,不仅可以根据映射的性质预知Julia集的总体结构特征,并且能够通过调控映射的参数来获得多种具有不同旋转对称结构的Julia集,因而有效地克服了现有三维分形集生成方法所构造的分形集包含信息量少、形状结构单一和分形形状无法预测等缺陷.进一步地,三维多项式映射可以应用于其他三维分形的构造,从而为三维分形的生成提供一个新的有效途径.

    • 运用流体模拟的油画生成方法

      2006, 17(7):1571-1579.

      摘要 (4051) HTML (0) PDF 590.51 K (5158) 评论 (0) 收藏

      摘要:与真实感绘制技术关注于传统的3D图形学不同,非真实感绘制技术更加强调艺术表现力、主观意识与情绪的传递以及强化重要信息、忽略非关键信息等方面.提出了一种自动的、基于流体模拟的方法来生成具有凡高后期风格的油画图像.提出以流体线条参考图颜色梯度的法线方向作为画笔方向,对原图进行多层绘制;同时,提出一种改进的多光源局部光照模型,以有效地反映不同光照条件下艺术图像的不同表征力.另外,设计了一种在光照条件下模拟画笔物理特征的方法,该方法通过bump-mapping增强绘制图像的涂料层叠感.为了使生成的绘制图像具有凡高油画的色彩风格,采用了一种颜色转换方法,将特定的艺术原画色彩特征转换到绘制图像上.实验结果表明,对于给定的输入图像,该算法能够有效地生成具有凡高后期艺术风格的油画.

    • 基于相似性的图像融合质量的客观评估方法

      2006, 17(7):1580-1587.

      摘要 (4623) HTML (0) PDF 748.72 K (6978) 评论 (0) 收藏

      摘要:研究图像融合结果的质量评估问题,提出一种新的基于相似性的图像融合质量客观评估方法.这种方法考虑人类视觉对局部变化更加敏感的特性,用源图像和融合结果的梯度场相似性来衡量融合的性能.这种相似性度量相对于现有的对比度度量,有了全方向的边缘辨识能力;相对于互信息量的度量方法,考虑了图像像素的局部关系,更加符合人的视觉特征.实验结果表明,这种客观评估方法很好地反映了图像融合的质量,与主观评价具有高度的一致性.

    • >综述文章
    • 无线传感器网络分簇路由协议

      2006, 17(7):1588-1600.

      摘要 (13637) HTML (0) PDF 808.73 K (14503) 评论 (0) 收藏

      摘要:在无线传感器网络体系结构中,网络层的路由技术至关重要.分簇路由具有拓扑管理方便、能量利用高效、数据融合简单等优点,成为当前重点研究的路由技术.分析了无线传感器网络分簇路由机制,着重从簇头的产生、簇的形成和簇的路由角度系统地描述了当前典型的分簇路由算法,并比较和分析了这些算法的特点和适用情况.最后结合该领域当前研究现状,指出分簇路由算法未来的研究重点.

    • 一个非确定系统的不干扰模型

      2006, 17(7):1601-1608.

      摘要 (4125) HTML (0) PDF 500.41 K (4410) 评论 (0) 收藏

      摘要:提出系统动作对信息域的不干扰概念,并在此基础上将不干扰模型推广到非确定系统.由于基于系统动作的不干扰概念简化了系统动作序列的提取操作,该模型的单步展开条件具有简洁的形式并易于理解和使用.推广后的不干扰模型不仅能够验证静态信息流策略,还可以验证各种动态信息流策略.最后设计了一个基于动态标记的访问控制模型,并在该模型中定义了读、写、执行等操作的具体语义,然后利用不干扰模型对其安全性进行了形式化验证.

    • 基于区分服务的分层多播拥塞控制算法

      2006, 17(7):1609-1616.

      摘要 (4069) HTML (0) PDF 495.32 K (4348) 评论 (0) 收藏

      摘要:多媒体多播应用在Internet上的广泛部署对拥塞控制提出了要求,分层多播是适应网络异构性较为有效的方案.为了克服现有分层多播存在的拥塞响应延时大、吞吐率抖动剧烈和不满足TCP友好的问题,给出了一个基于区分服务的分层多播模型,提出了一种基于区分服务的分层多播拥塞控制算法DSLMCC(DiffServ-based layered multicast packet dropping),在边缘路由器上引入了基于概率的区分优先级的分组标记算法,在核心路由器上采用区分优先级的分组丢弃算法.仿真结果表明,该算法能够有效地改进区分服务网络上的分层多播拥塞控制的性能,具有较快的拥塞响应速度、较好的稳定性和公平性,并且较好地适应了网络的异构性.

    • 合谋安全的卷积指纹信息码

      2006, 17(7):1617-1626.

      摘要 (4225) HTML (0) PDF 767.71 K (4876) 评论 (0) 收藏

      摘要:数字指纹是一种发行商通过在数字作品拷贝中添加唯一用户身份标记,使得能够识别出制作非法拷贝"叛逆者"的技术.目前,数字指纹方案中普遍存在着大用户数下指纹码构造过长以及无法有效叛逆跟踪的问题和缺陷.为了解决这些问题,在Boneh-Shaw的基础上,给出了指纹信息码的定义,并将卷积码与一般指纹码相结合,提出一种实际构造方法.同时,通过引入"备选子码集"的概念对Viterbi译码算法予以改进,给出了指纹信息码的译码算法.在理论与实例两方面对编码安全性质和性能的证明和分析结果均表明,所提出方案具有更短的用户信息编码长度,并实现了大用户集下有效叛逆用户的搜索.

    • 对一种多重密钥共享认证方案的分析和改进

      2006, 17(7):1627-1632.

      摘要 (4041) HTML (0) PDF 371.29 K (4518) 评论 (0) 收藏

      摘要:在(t,n)密钥共享方案中,密钥管理者将一个秘密密钥分成n个子密钥,然后让n个成员中的每个成员保存一个子密钥.当需要恢复秘密密钥时,任意t个成员拿出他们持有的子密钥后,就可以按既定的公开算法恢复出所需密钥.而多重密钥共享使得密钥管理者可以安全且有效地共享多个密钥.Shi给出了一种高效率的多重密钥共享认证方案.在其方案中,不仅成员持有的子密钥能够重复使用,而且管理者分发的子密钥和成员提供的影子子密钥也都是可认证的.对Shi方案的安全性进行了分析:首先指出该方案的一个设计错误;然后给出两个攻击,以表明该方案中的子密钥和影子子密钥认证方法实际上都是不安全的.准确地说,利用所提出的攻击,不诚实的管理者可以将假的子密钥分发给成员;而不良成员可以很容易地伪造假的但能满足认证等式的影子子密钥,从而欺骗诚实成员,使得诚实成员误以为他们恢复出的密钥是正确的.另外,还给出了改进方法,以避免上述设计错误和攻击.

    • 基于可靠性理论的分布式系统脆弱性模型

      2006, 17(7):1633-1640.

      摘要 (4985) HTML (0) PDF 1.12 M (5842) 评论 (0) 收藏

      摘要:对现有的脆弱性分析方法进行分析和比较,提出基于可靠性理论的分布式系统脆弱性模型.针对影响分布式系统安全性的各项因素进行脆弱性建模,利用模型检验方法构造系统的脆弱性状态图,描述系统脆弱性的完整利用过程,引入可靠性理论对分布式系统的脆弱性进行分析和量化评估,从而为增强分布式系统的安全性提供理论依据.

    • 基于逻辑"或"约束优化的实时系统设计

      2006, 17(7):1641-1649.

      摘要 (4381) HTML (0) PDF 595.12 K (4582) 评论 (0) 收藏

      摘要:标准约束优化问题的等式或不等式约束之间是逻辑"与"关系,目前已经有很多高效、收敛的优化算法.但是,在实际应用中有很多更一般的约束优化问题,其等式或不等式约束之间不仅包含逻辑"与"关系,而且还包含逻辑"或"关系,现有的针对标准约束优化问题的各种算法不再适用.给出一种新的数学变换方法,把具有逻辑"或"关系的不等式约束转换为一组具有逻辑"与"关系的不等式,并应用到实时单调速率调度算法的可调度性判定充要条件中,把实时系统设计表示成混合布尔型整数规划问题,利用经典的分支定界法求解.实验部分指出了各种方法的优缺点.

    • 能量受限的软件预取优化问题

      2006, 17(7):1650-1660.

      摘要 (4292) HTML (0) PDF 887.43 K (4636) 评论 (0) 收藏

      摘要:在移动设备和嵌入式设备中,能量的供给是十分有限的,它受限于能量供给设备的容量和节电能力的大小.在能量受限的环境下,电池所提供的能量不足以使系统达到最优的性能目标.因此,提出了一种能量受限环境下最优化预取性能的方法.该方法通过软件控制的手段,能在有限的能量供给条件下达到最优的性能.该方法是基于动态频率可调的CPU和存储器的.根据CPU和存储器的忙闲情况,通过插入频率调节指令,指导调节CPU和存储器的频率,使得预取优化的两个性能指标(一是时间,二是处理器收益)在一定的能量约束条件下达到最优.对该问题建立了详细的模型及模拟环境,并通过一组以数组访问为主的测试程序验证了该方法的有效性.模拟结果表明,该方法对能量受限预取优化问题是有效的.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号