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

计算机学报 2009年第07期杂志 文档列表

计算机学报杂志综论

粗糙集理论与应用研究综述1229-1246

摘要：在阐释粗糙集理论基本体系结构的基础上，从多个角度探讨粗糙集模型的研究思路，分析粗糙集理论与模糊集、证据理论、粒计算、形式概念分析、知识空间等其它理论之间的联系，介绍国内外关于粗糙集理论研究的主要方向和发展状况，讨论当前粗糙集理论研究的热点研究领域以及将来需要重点研究的主要问题．

以数字图像为载体的隐写分析研究进展1247-1263

摘要：隐写和反隐写的对抗是关系到信息安全的重要课题．文中针对常用隐写载体之一即数字图像，回顾反隐写技术的最新进展．根据隐写技术快速发展对反隐写研究提出的挑战，对近几年提出的新方法和新思路进行梳理和归纳，给出系统和扼要的评述，供隐写和反隐写研究者参考．重点围绕三方面展开讨论：对于克服了统计不对称性的LSB匹配嵌入法如何进行有效的检测或嵌入率估计；对于小嵌入率隐写进行分析的研究中有哪些进展；面对层出不穷的隐写新方法，如何实现不针对具体嵌入算法的通用隐写分析．对于反隐写研究的发展趋势和面临的新问题也作了讨论．

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

值传递诊断过程的抽象和重用1264-1279

摘要：提出了一种基于值传递的系统模型，重新定义了诊断，并给出了快速找到一个极小诊断的算法．在此基础上，提出了独立于系统输入输出的值传递路径的概念，实现了值传递诊断过程的抽象，并根据等价路径对系统值传递路径空间进行约简．以约简的值传递路径空间为基础，给出了一种故障诊断算法，在一定条件下多项式时间结束．

描述逻辑μALCIO的语义及推理1280-1290

摘要：循环术语集是描述逻辑长期以来的研究难点，它的最基本的问题即语义及推理问题没有得到合理的解决．分析了描述逻辑循环术语集的研究现状和存在的问题，基于混合“一演算将不动点构造算子引入到含有枚举构造算子的描述逻辑ALCIO中，提出了一种允许包含循环术语集的描述逻辑μALCIO．给出了μALCIO的语法和语义，证明了μALCIO的可满足性推理等价于混合旷演算的可满足性推理，并利用树自动机理论给出了μALCIO的可满足性推理算法以及给出了推理算法正确性证明和复杂性定理．

量子可逆逻辑电路综合的快速算法研究1291-1303

摘要：可逆逻辑有许多应用，尤其在量子计算领域，量子可逆逻辑电路是构建量子计算机的基本单元，量子可逆逻辑电路综合就是根据电路功能，以较小的量子代价自动构造量子可逆逻辑电路．文中结合可逆逻辑电路综合的多种算法，提出了一种新颖高效的算法，自动构造正极性Reed-Muller展开式（RM），在生成量子可逆逻辑电路的解空间树上，采用总体层次遍历，局部深度搜索，借鉴模板优化技术，构造限界函数快速剪去无解或非最优解的分枝，优先探测RM中的因子，以极高的效率生成最优电路．以国际公认的3变量可逆函数测试标准，该算法不仅能够生成全部最优电路，而且运行速度远远超过同类算法．

可信计算中远程自动匿名证明的研究1304-1310

摘要：远程证明是可信计算的一个重要特征，目的是证明远程平台的身份或配置信息是否可信．常用的二进制证明方法不仅暴露了本地平台的配置信息，而且在现实情况中很难处理平台多样性问题．文中提出的可信计算中远程自动匿名证明方案利用环签名实现直接匿名证明，隐藏了平台的身份信息，以属性证书代替平台配置信息，可以有效防止私有信息的暴露，同时兼顾到对系统的升级和备份的可信评测．证明协议避免了使用零知识证明．分析结果显示，具有较高的实现效率．

Pcanel／V2——基于Intel VT-x的VMM架构1311-1319

摘要：个人计算机硬件性能的迅速增强使得通过虚拟化技术建立多个相互隔离的计算域成为未来个人计算机的一种重要发展趋势．为避免传统的IA－32架构在软件虚拟化领域所面临的VMM的设计和实现的困难，作者设计并实现了基于Intel VT—X技术的VMM架构——Pcanel／V2．该架构利用最新的硬件虚拟化技术，通过配置出一个可控制的虚拟运行环境，可以直接虚拟运行多个不修改源代码的客户操作系统．在允许客户操作系统正常运行的同时控制它们对各种硬件资源的访问，并能对客户操作系统运行过程中出现的各种情况进行相应的处理．Pcanel／V2实现了Linux和Vxworks的同时运行，相应的数据测试表明Pcanel／V2架构在简化了VMM设计复杂度的同时总体运行效率比软件虚拟化技术提高了约10％．

使用压缩函数的非平衡Feistel结构的伪随机性和超伪随机性1320-1330

摘要：从可证明安全的角度研究使用压缩函数的非平衡Feistel结构（UFN—C）的安全性，证明了k＋1轮UFN-C是伪随机的，k＋2轮UFN—C是超伪随机的；进一步地，探讨了UFN—C的有效构造，降低了Naor和Reingold在1999年文章中类似结构对伪随机函数个数的要求．最后，针对一类具体的UFN—C——SMS4，分析其广义形式SMS4-like结构的伪随机性和超伪随机性，为设计与使用该类结构的分组密码提供了可证明安全的理论依据．

右边正则纠删码中二部图的构造算法1331-1336

摘要：通过深入研究右边正则度序列的分析性质，设计了右边正则纠删码度序列的参数优化算法．基于此算法，提出了右边正则纠删码设计中随机二部图的连边构造算法．数值结果证明了所给的度序列参数优化算法的有效性．仿真结果表明基于右边正则度序列的级联型纠删码的性能优于Tornado码．随机二部图的连边构造算法和度序列的参数优化算法有助于右边正则纠删码的设计及其工程应用．

判断集合包含关系的安全计算协议1337-1345

摘要：研究了安全计算中关于集合的问题：A拥有一个秘密的集合SA，B拥有一个秘密的集合SB（Sn和SB来自一个全集），双方希望知道SA是否包含SB，但是不希望泄漏关于集合SA和SB的其它有用信息．针对此问题，提出了3个具有不同效率和安全性的安全计算协议．设集合SB的大小为NB．第1个协议基于叠加密（或者支持门限解密的加法同态加密方案），需要NB轮通信．另外两个协议基于普通的加法同态加密方案，仅需一轮通信．与同类成果比，前两个协议使用了新的集合表示法，第3个协议在输出结果阶段不需要门限解密，通信效率较好．

根据序列变化率预测软件阶段成本1346-1355

摘要：针对软件阶段成本因少数据、不确定性使得用现有方法（如回归）难以预测的问题，文中提出一种新颖的预测方法，该方法从项目已完成阶段的成本序列中，通过变换得到反映序列变化快慢的“变化率”，并用机器学习方法从历史项目中学习得到变化率阈值，然后用不同的灰色模型进行预测．在10个现实世界软件工程数据集上的实验结果表明，该方法平均预测误差比线性回归方法低20％～80％，显示出较大的潜力．

无源RFID系统中能量有效的物理层设计1356-1364

摘要：在前向链路，为使标签获得更多能量，结合ASK调制提出了一种新的用于无源RFID系统的能量有效的数据编码方法．通过在一个码元周期内采用可调的非对等的高低电平持续时间，使高电平持续时间更长．分析结果表明，在40kbps的典型速率下，该编码使前向链路的基带信号所携带的能量最多可高于Manchester编码的84％．同时该编码可以提高系统性能．测试结果与理论分析相符合．在反向链路，提出了编码的OOK和编码的BPSK调制．采用截止速率研究编码对系统性能的影响．分析结果表明，编码调制更为能量有效．在几乎不增加芯片复杂度的前提下，提升了系统性能．分析并估算了不同截止速率时编码对系统信息速率和通信距离所带来的增益．

基于社会网络的人名检索结果重名消解1365-1374

摘要：人物重名现象十分普遍，搜索引擎的人名检索结果通常是多个同名人物相关网页的混合．该文依据同名的不同人物具有不同的社会网络的思想，利用检索结果中共现的人名发现并拓展检索人物相关的潜在社会网络，结合图的谱分割算法和模块度指标进行社会网络的自动聚类，在此基础上实现人名检索结果的重名消解．在人工标注的中文人名语料上进行实验，整体性能达到较好水平，图聚类算法能帮助连通社会网络的进一步划分，从而提高消解效果．

基于索引排序的快速动态区域匹配算法1375-1381

摘要：数据分发管理实现基于值的过滤，可进一步减少大规模仿真中盟员接收冗余数据的可能性和网络中的数据流量．数据分发管理实现的关键是区域匹配算法的实现，高效、精确的区域匹配一直是数据分发管理追求的目标．现有的区域匹配算法如直接匹配法、网格法、基于分类的算法等都不很理想，或者过滤效果不佳，或者耗时较大，难以适应大规模分布式仿真的需要．论文针对在区域比较多的大规模分布式仿真系统中，区域大都需要随着仿真的推进而频繁地被动态修改的实际特点，提出了一个基于索引排序的快速动态区域匹配算法——IOBM算法，该算法将范围的上下界分别各用一个节点表示，使用指针数组来索引每一维上的范围节点，数组元素的下标值表示对应的节点值，利用区域范围更新前后的信息，将匹配限定在移动区间之内，通过对移动区间之内的链表进行直接操作来完成匹配工作，因而大大减少了匹配计算的时间，实现了高效、精确的动态匹配．该算法尤其适合区域比较多的大规模分布式仿真的需要．

SpMT WaveCache：开发数据流计算机中的推测多线程1382-1392

摘要：推测多线程技术（Speculative Multithreading，SpMT）是通过推测地执行多个线程来开发线程级并行性，提高超标量处理器性能．通过增加额外的硬件单元，比如线程同步单元（Thread Synchronization Unit，TSU）、线程上下文表（Thread Context Table，TCT）和线程内存历史表（Thread Memory History，TMH），扩展了事务性内存系统，提高了基于波标量指令集系统结构（Wave Sealar ISA）实现的WaveCache模拟器的性能．同时，还提出了一种新的两级线程级事务提交机制．最后，采用了6个来自SPEC、Media和Mibench测试程序集的真实测试程序，评估了推测多线程WaveCache（SpMT WaveCache）的性能．实验表明，SpMT WaveCache比超标量系统结构提高了2～3倍的性能，是一种有效的开发动态数据流计算机性能的方法．

一种基于进程执行行为分析的图形界面交互系统性能评测方法1393-1403

摘要：传统的系统性能评测方法使用吞吐率等整体性参数作为评测手段．这类参数对于用户输入时间不确定的图形界面交互式应用程序并不适用．图形界面交互系统的评价应更侧重于考虑用户的主观感受．在多用户共享服务资源的图形界面系统中，单个用户可占用的资源受限，用户请求的处理时间可能会被延长．此时程序的“实际执行时间”，即整体执行时间与等待用户响应时间之差，才能够真实地反映用户可察觉的系统处理能力．但如何提取“实际执行时间”是一个问题．文中提出了一种新的基于内核profiling的进程执行行为特征分析的图形界面交互系统性能评测方法，并给出了一种区间最大相关比对算法，能够从整体执行时间中准确地提取实际执行时间．为了能够在引入时空开销小的前提下获取进程执行行为，文中还设计实现了内核trace记录工具Pro．对Impress等4个图形界面交互程序在系统内存大小不同时的性能行为进行记录和分析评测，实验结果显示了该方法的准确性和有效性．

分布式视频编码虚拟依赖信道模型研究1404-1412

摘要：视频信息固有的非平稳特性，如冲突区域等，使时域预测技术变得非常复杂．在分布式视频编码（DVC）中，由于解码端不能获取当前编码帧的信息，精确地对时域相关噪声进行建模变得更为困难．文中以虚拟依赖信道模型为切入点对如何降低时域相关噪声进行了研究．首先对DVC虚拟依赖信道进行了建模，并对影响边信息的主要因素进行了分析，分析结果表明在变换域中不同的频率子带对时域相关噪声的敏感度不同．在此基础上提出了一种新的基于小波变换域的虚拟依赖信道模型VCMDWT，基于分类编码的思想对较为平稳的LL子带进行Wyner—Ziv编码，对非平稳的高频子带进行SPIHT帧内编码．实验结果表明，与基于像素域的方法相比，所提出的VCMDWT模型能够得到更稳定的虚拟信道，提高DVC系统的率失真性能达到2．6dBs以上．

二通道线性相位Neville—Lagrange提升小波滤波器组设计1413-1423

摘要：基于提升格式的第二代小波可以通过对第一代小波滤波器组采用劳伦多项式的欧几里德分解而得到，而直接设计符合提升格式的二代小波一直是需要深入研究的热点问题．文中把Neville滤波器理论和Lagrange插值理论结合起来，构造了二通道线性相位Neville—Lagrange提升小波滤波器组，并证明了其线性相位性质，讨论了其归一化方法．文中给出了二通道线性相位的Nevme—Lagrange-44（简称N—L-44）提升小波滤波器组实例，并与JPEG2000的9／7小波做了图像压缩实验比较．实验结果表明：N-L-44提升小波滤波器组的图像压缩效果要明显好于9／7小波滤波器组，其在低比特率（bpp〈1）时的图像压缩效果要好于9／7小波的lifting格式．而且相对于9／7小波，二通道线性相位Nevme—Lagrange提升小波滤波器组还具有良好的潜在发展空间，例如其可以用来构建自适应提升小波滤波器组，可以扩展到纯二维提升小波滤波器组等等．