计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2010年第04期杂志 文档列表

计算机学报杂志综论

基于P2P的视频点播系统综述613-624

摘要：近十年来,基于对等网络（Peer-to-Peer,P2P）的视频点播系统（Video-on-Demand,VoD）受到了越来越多的关注.它吸引人的原因在于,与传统的基于服务器/客户机结构的视频点播系统相比,P2P技术具有成本低、扩展性好的优点.但是,由于对等网络内在的不稳定性、异构性,这类系统在实现上面临着诸多挑战.文中对现有的该类系统的体系结构进行模块划分,并对各模块的实现策略进行讨论;特别是对VoD/P2P实现中的3个主要方面,即数据传输、数据存储、激励机制进行了综述.

计算机学报杂志研究论文与技术报告

DUCG：一种新的动态不确定因果知识的表达和推理方法（Ⅰ）：离散、静态、证据确定和有向无环图情况625-651

摘要：贝叶斯网络（BN）是国际上流行的处理不确定因果知识的表达和推理模型.文中指出：即使所有变量均为二状态,BN中的子变量也有单赋值和多赋值之分.在单赋值情况下适用的知识的简洁表达和推理方法在多赋值情况下不适用.为克服BN的上述及其它缺陷,文中提出了DUCG（Dynamical Uncertainty Causality Graph）理论模型,以图形方式简洁表达任何情况下的不确定因果关系,并基于证据化简图形和展开事件,以得到所关注假设事件及其状态概率表达式.此外,DUCG允许知识表达不完备,使其超越了BN理论框架.一个入侵者报警系统被用来解释DUCG理论.

d-子树划分问题652-665

摘要：边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分（d为非负实数）,如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.

分类超曲面算法复杂度研究666-671

摘要：分类超曲面算法是一种简单的基于覆盖的分类算法.实验证明该算法具有分类正确率高、速度快的优点.但是,关于该算法的相关理论问题需要深入研究.文中对该算法的几个相关理论问题进行了研究.首先给出并证明了在分割的最大层数给定时算法假设空间的VC维,在此基础上结合可能近似正确（Probably Approximately Correct,PAC）学习框架,得出了对算法样本复杂度的估计,使得分类超曲面算法保证可PAC学习到任意目标概念.其次,分析了算法的时间复杂度和空间复杂度.最后,给出了无矛盾样本集的概念,并证明当输入样本集是有限无矛盾样本集的条件下,算法一定是收敛的.

基于协同进化的异构种群挖掘混沌迭代函数672-686

摘要：混沌迭代序列是复杂系统动力学研究的一个分支,其序列值在不同参数条件下时会出现分叉及混沌现象.已有的方法不能同时挖掘拟合迭代序列的迭代函数的结构及其相应条件参量.文章则旨在同时挖掘出二者,主要工作包括：（1）提出了基于协同进化的异构种群挖掘模型,能融合不同种群的优势;（2）提出了新的适合挖掘迭代序列的适应度计算方式;（3）从理论上证明了多种群协同挖掘的进化难度远大于单种群进化难度,通过实验证实了在有效协同策略下,多种群进化得到的结果远优于单种群的进化结果;（4）提出3种协同进化策略,在对迭代序列的函数拟合以及参数拟合两方面,多路并行式结合策略能达到相对较优效果;（5）在合成数据和真实数据上进行了实验,证实了算法的正确性和有效性.

大规模语音语料库及其在TTS中应用的几个问题687-696

摘要：首先介绍了大规模语音语料库以及基于大规模语音语料库的文语转换技术的研究现状,接着介绍了一个大规模连续汉语语音语料库的实例Slib的结构和内容;在此基础上,讨论了面向大规模语音语料库的索引技术,提出了语料库检索中的集合运算和最小包容问题,证明了最小包容问题是NP完全的,给出了求解该问题的贪婪算法以及算法的近似比;最后,讨论了基于集合运算的大规模语音语料库的检索技术在文语转换系统中的应用,特别是在基本语言单位实例的选取问题上实现了一种基于最小包容的优化方法,对提高文语转换系统的自然度有实用价值.

基于shell命令和多重行为模式挖掘的用户伪装攻击检测697-705

摘要：伪装攻击是指非授权用户通过伪装成合法用户来获得访问关键数据或更高层访问权限的行为.近年来,伪装攻击检测在保障网络信息安全中发挥着越来越大的作用.文中提出一种新的用户伪装攻击检测方法.同现有的典型检测方法相比,该方法在训练阶段改进了对用户行为模式的表示方式,通过合理选择用户行为特征并基于阶梯式的序列模式支持度来建立合法用户的正常行为轮廓,提高了用户行为描述的准确性和对不同类型用户的适应性;在充分考虑shell命令审计数据时序特征的基础上,针对伪装攻击行为复杂多变的特点,提出基于多重行为模式并行挖掘和多门限联合判决的检测模型,并通过交叉验证和等量迭代逼近方法确定最佳门限参数,克服了单一序列模式检测模型在性能稳定性和容错能力方面的不足,在不明显增加计算成本的条件下大幅度提高了检测准确度.文中提出的方法已应用于实际检测系统,并表现出良好的检测性能.

可信网络连接研究706-717

摘要：文中详细地介绍了可信网络连接的发展历程、体系结构、消息流程、相关规范,对TCG的可信网络连接架构的优点与局限性进行了分析.针对如何将可信计算机制拓展到网络,使得网络成为可信的计算环境这一问题进行了分析论述,并对可信网络连接技术未来的发展趋势进行了展望.

基于人工鱼群的ABC支持型QoS单播路由机制718-725

摘要：下一代互联网NGI（Next Generation Internet）需要提供服务质量QoS（Quality of Service）路由能力,支持总最佳连接ABC（Always Best Connected）.但是,由于链路状态的难以精确测量与用户QoS需求的难以准确表达,因此QoS路由基于的信息实际上是模糊的.同时,在网络运营日益商业化的环境下,支持ABC需要兼顾用户和网络提供方利益,考虑双方效用共赢.为此,文中引入模糊数学、概率论和博弈论知识,设计了一种ABC支持型QoS单播路由机制.该机制采用区间形式描述用户QoS需求和边（链路）参数,引入用户满意度和边评价,通过博弈分析,基于人工鱼群算法,寻找使用户和网络提供方效用达到或接近Nash均衡下Pareto最优的QoS单播路径.仿真结果表明,该机制是可行和有效的.

针对解码转发协作分集的分布式伙伴节点选择算法726-735

摘要：该文研究了在解码转发协作分集系统中的伙伴节点选择问题.文中首先建立了伙伴节点选择问题的数学模型,其能够在伙伴节点和目的节点分别满足一定误比特率性能的前提下,使源节点和伙伴节点的发射功率之和最小化.因此,该模型不仅能够开发多用户无线系统所固有的空间分集能力,显著地提高无线传输性能,而且能够增加无线网络的通信容量和降低移动节点的能耗.文中还推导了在瑞利衰减信道中使用M-QAM（M-ary Quadra-ture Amplitude Modulation）时伙伴节点和目的节点的平均误比特率公式,从而揭示了系统性能与伙伴节点之间的依赖关系.根据数学模型和误比特率公式,文中提出了一种伙伴节点选择算法,能够在分布式的无线网络环境中以极小的控制协议开销,逐个消息地选择最优的伙伴节点参与转发消息.不仅如此,该算法还能够随着信道状态的变化动态地调整所选择的伙伴节点,所以对信道状态具有自适应能力.最后,文中通过仿真验证了所提出的算法.

静动态结合的Java程序不变性分析方法736-746

摘要：程序的不变性（immutability）是指类的实例对象在其生命周期内状态不会发生改变.不变性信息可以用来指导程序的分析、测试和验证等工作.现有分析不变性的技术主要集中于对程序的静态分析,而动态分析方面的工作很少.文中在分析了静、动态分析技术各自的优缺点后,提出了一种静动态结合的混合分析技术.首先通过对程序进行静态分析,即对程序进行分析测试和验证,来获得初步的程序不变性信息,然后对静态分析的结果中不确定的部分再进行动态分析,即通过观察程序运行时各个对象的状态变化进行分析,同时还将动态分析用于对静态分析结果的验证.静动态结合的分析技术比单纯的静态分析提高了分析结果的精度,同时也比单纯的动态分析降低了开销,提高了效率.

DNA序列中基于适应性后缀树的重复体识别算法747-754

摘要：现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了NCBI中的9条典型DNA序列作为测试数据,并对后缀树改进前后的重复体识别算法做了比较分析.结果表明,RepSeeker在没有损失精度的情况下缩短了算法的运行时间.实验结果与理论上的分析一致.

演化多目标优化中的几何热力学选择755-767

摘要：热力学遗传算法（Thermodynamical Genetic Algorithms,TDGAs）借鉴热力学中的自由能极小过程来统一处理多目标优化在逼近性和多样性两方面的任务.为提高TDGA的运行效率和解集分布均匀性,提出了一种几何热力学选择.在该选择中首先定义角度熵通过扇形采样来度量种群逼近方向的多样性.然后利用距离精英定义距离能量来度量种群的逼近程度,避免了耗时的非劣分层操作.此外,引入分量热力学替换规则以较低计算代价驱动种群的几何自由能快速下降.在多目标0/1背包问题上的实验结果表明,几何热力学选择极大地提高了TDGA的运行效率和解集分布均匀性;采用该选择的TDGA算法可生成与NSGA-II在逼近性和分布多样性上性能相当的解,但在运行效率上明显优于NSGA-II.

基于复用计算的大纹理实时合成768-775

摘要：文中提出一种基于复用计算的纹理合成方法,逐步地利用已合成的部分纹理来生成更大的纹理块,以进行后续的纹理合成计算.由此,该方法可节省大量耗时的纹理块选择及缝合计算,提高了合成效率.实验表明,新方法可实时合成2048×2048像素的大纹理,而已有工作至多只能以交互的速度进行这样的合成.

基于时空单词的两人交互行为识别方法776-784

摘要：文中提出一种基于时空单词的两人交互行为识别方法,该方法从行为视频中提取丰富的时空兴趣点,基于人体剪影的连通性分析和时空兴趣点的历史信息,把时空兴趣点划分给不同的人体,并在兴趣点样本空间聚类生成时空码本（spatial-temporal codebook）.对于给定的时空兴趣点集,通过投票得到表示单人原子行为的时空单词（spatial-temporal words）.采用条件随机场模型建模单人原子行为,在两人交互行为的语义建模过程中,人工建立表示领域知识（domain knowledge）的一阶逻辑知识库,并训练马尔可夫逻辑网用以两人交互行为的推理.两人交互行为库上的实验结果证明了该方法的有效性.