一种在元素与颜色规模相近时的有效着色算法及其应用

着色算法(color-coding)是求解NP难问题的重要手段之一.而在应用着色算法时,着色算法所产生的着色方案的规模极大地影响着问题的求解性能,故构造一个尽可能小的着色方案是着色算法所寻求的目标.目前存在的着色算法均基于完全散列函数,并要求元素数目n远大于颜色数目k,且k比较小,这个限制条件使得这些着色算法在一些实际情况下无法应用.该文主要研究在元素与颜色规模相近时(n2k)的有效着色算法,并着重分析在n2k情况下着色算法的性能.该文提出了一种基于划分思想的着色方案构造算法PBCC,证明了由PBCC产生的着色方案确实可以覆盖到所有的子集,并具体给出了可应用于(l,d)-(20,16)Motif查找问题的403种着色的构造方法.文章进一步分析了PBCC产生的着色方案规模,并证明了在n2k且n-k2的情况下,任何着色算法所产生的着色方案的规模|S(n,k)|都不小于[n/2 n-k] [[n n-k]-n/2 n-k]2~(n-k)]/(2~(n-k)-2).此外,文中也采用了渐进分析技术,证明了PBCC算法生成着色方案规模为O(e2Rootof(ex-eμx 1)(n-k)),在n=2k的情况下结果是O(2.62n-k);同时,文中也证明了n2k情况下着色方案规模的下界为2n-k.     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

带权Matching和Packing问题的一种固定参数可解算法

带权的m-D MATCHING和m-SET PACKING问题(m≥3)以前是用近似算法来求解的.本文首先根据参数计算理论对这两个带权问题进行了参数化定义,然后运用最新的着色技术和动态规划技术对带权的m-SET PACKING问题设计了一个时间复杂度为O*(12.8mk)的固定参数可解算法, 接着在此基础上利用问题本身的结构特点对带权的m-D MATCHING问题提出了一个时间复杂度为O*(12.8(m-1)k)的固定参数可解算法,表明带权的m-SET PACKING问题和带权的m-D MATCHING问题都是固定参数可解的.     

基于小波变换的图像二维直方图分割方法

鉴于二维直方图阈值分割方法利用灰度的空间相关性取得高的分割效果和小波变换多尺度滤波思想,提出了一种基于小波变换的二维直方图分割结合方案;实验结果表明本文方法的有效性。     

构件组装技术在虚拟实验室中的应用研究

基于构件的软件复用技术是实现软件工程化开发和工业化生产的重要途径,其中构件的集成组装是关键。目前虽然提出了许多构件组装理论,但如何在特定领域根据实际要求实施基于构件组装的软件开发过程仍是值得进一步研究的课题。本文针对计算机硬件类虚拟实验室芯片设备复杂多样、难于开发的问题,在深入分析芯片工作原理与结构特征的基础上,提出一种基于数据驱动的构件组装方法。该方法通过充分重用已有芯片构件以可视化组装的方式开发新芯片构件及建模实验,从而有效提高了开发效率同时软件具有很好的易维护性和可扩展性。     

层次分析法在高校专业设置中的应用

介绍了层次分析法在高校专业设置中的应用,通过建立专业设置指标系统层次结构模型,构建决策成对比较阵,计算单层次排序权重和层次总排序权重,得出各个因素对专业设置的影响程度,能够对高校专业设置和调整制度提供借鉴.整个算法是用Java语言来实现的.     

Set Cover和Hitting Set问题的研究进展

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。     

“计算机网络”课程的阶梯化教学研究

本文从社会对"计算机网络"技术人才的需求出发,依据"计算机网络"课程的特点,深入讨论了"计算机网络"阶梯化教学的六层阶梯:理论教学、实验教学、课程设计教学、实用技术教学、专项指导和毕业设计。六层阶梯由易至难、层层递进、步步深入,从不同的角度全面提高学生的理论基础和实践水平。     

认知描述逻辑ALCKR＋：描述逻辑的一个非单调扩展

描述逻辑是语义Web的逻辑基础,是形式化表达领域知识的工具.但是描述逻辑只能表达单调推理,不能处理不完全知识.认知描述逻辑因其非单调特性和良好的时间复杂度等特点在处理不完全知识方面有较好的优势.本文在认知描述逻辑ALCK的基础上提出了新的认知描述逻辑语言ALCKR ,保留了描述逻辑原有的优点,加入传递角色属性,增强了表达能力,并通过认知查询拥有了非单调推理的能力.设计了ALCKR 的语法、语义以及表算法.     

单体型组装问题计算模型的比较与分析

单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。单体型组装问题指如何利用个体的基因测序片断数据,根据不同的优化准则确定该个体单体型的计算问题。对MSR,MFR,MEC,WMLF,MEC／GI等单体型组装模型做了详细的分析比较,得出了如下结论：在没有引入测序误差情况下,上述模型的重构精度基本一致。随着测序误差的增加,MEC／GI模型的容错性最好,重构精度最高;MSR模型受测序误差的影响最大,只适用于测序误差极小的情形。