基于子图的随机图点覆盖2度点核化研究

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形予图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(χ)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(х)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.     

加权3D-Matching的改进算法

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的(k+1)-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质: k- matching中存在2列使得该2列至少有2k/3元素被包含在(k+1)-matching中所对应的2列中.基于给出的性质,通过运用color-coding和动态规划技术,给出了一个时间复杂度为O* (4.823k)的参数算法,最终求解加权3D-matching问题.该算法较目前文献中的最好结果O* (5.473k)有了极大的改进.     

面向可靠性和能耗优化的可压缩数据收集方案

现有的无线传感器网络（ WSNs）数据收集方法无法在耗费较低开销的同时保证数据收集的可靠性。基于压缩感知（ CS）理论,设计了基于指数核函数的稀疏矩阵和基于准循环低密度奇偶校验（ LDPC）码的测量矩阵来用于节点的数据采集,以最大化网络生命周期为目标,将测量值传输问题建模为汉密尔顿回路问题,并提出了一种基于树分解的数据收集路径优化算法。仿真实验结果表明：所提方案在数据重构误差和能耗方面的性能要优于目前典型的数据收集方法。     

UWSNs中基于压缩感知的移动数据收集方案

由于水下无线传感器网络(UWSNs)工作环境的特殊性,降低节点能耗和保证数据收集的实时性是至关重要的问题.提出一种基于压缩感知(CS)的移动数据收集方案.以DEBUC协议和CS理论为基础,簇内节点依据设计的稀疏测量矩阵决定是否参与压缩采样,并将获得的测量值传输至簇头.通过AUV的移动来收集各个簇头上的数据到数据中心,该问题被建模为带有邻域的旅行商问题,并提出了近似算法进行求解.在数据中心处利用CS重构算法进行数据重构.仿真实验结果表明:相比于已有的水下移动数据收集算法,该方案在保证数据收集可靠性的同时,降低了数据收集延时,延长了网络寿命.     

WSN中基于压缩感知的高能效数据收集方案

可靠高效的数据收集是无线传感器网络（Wireless sensor networks,WSN）应用中的关键问题.然而,由于无线通信链路的高失效率、节点资源受限以及环境恶劣等原因,网络容易发生丢包问题,使得现有的数据收集方法无法同时满足高精度和低能耗的要求.为此,本文提出了一种基于压缩感知的高能效数据收集方案.该方案主要分为节点上的数据处理和数据收集路径优化两个步骤.首先设计了基于指数核函数的稀疏矩阵来对感知数据进行稀疏化处理,然后综合考虑了数据的传输能耗和可靠性等因素,采用分块矩阵的思路,将单位矩阵和准循环低密度奇偶校验（Low density parity check,LDPC）码的校验矩阵相结合构造了测量矩阵,并证明了它与稀疏矩阵之间满足限制等距性质（Restricted isometry property,RIP）.最后,将数据收集路径优化问题建模为哈密尔顿回路问题,并提出了基于树分解的路径优化算法进行求解.仿真结果表明,在网络存在丢包的情况下,本文方案仍然能够保证数据收集的高精确度,相比于其他数据收集方案而言,本文方案在数据重构误差和能耗方面的性能更优.     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

基于Web的多媒体课件设计

介绍了基于 Ｗｅｂ的多媒体课件设计技术及实现方法。重点讨论分析了软件实现的几个关键技术：Ｗｅｂ数据库访问及连接技术Ｊａｖａ语言及脚本语言实现教学的交互式动态演示技术及ＶＲＭＬ（虚拟现实建模语言）在Ｉｎｔｅｒｎｅｔ上实现三维虚拟交互式教学等动态Ｗｅｂ技术,并详细介绍了关键技术在《计算机网络技术》多媒体课件中的应用。     

杨房沟水电站泄洪消能设计

杨房沟水电站坝址河谷狭窄,洪峰流量大,枢纽最大泄洪功率为10 960 MW,在国内拱坝中处于较高水平.水电站泄洪消能采用“坝身表、中孔泄洪+坝下水垫塘”布置型式.文中通过方案比较,泄洪建筑物采用3个表孔和4个中孔的坝身集中泄洪方案,下游消能建筑物采用水垫塘+二道坝方案.表孔出口采用收缩型式、中孔出口采用收缩型式的宽尾墩.结合泄洪雾化分析,对水垫塘两岸边坡采用混凝土护坡、喷锚支护和排水孔等措施.