摘要:通过视赋值集为通常乘积拓扑空间,利用其上的Borel 概率测度在n 值及连续值Łukasiewicz 命题逻辑系统中引入了命题的Borel 概率真度概念,讨论了它的基本性质,特别是给出了n 值情形中概率真度函数的积分表示定理,并得到了其与连续情形概率真度函数之间关系的一个极限定理.结果表明,计量逻辑学中命题的真度概念只是所研究工作的一个特例,因而基于概率真度概念可以为不确定性推理建立一种更为宽泛的计量化模型.

摘要:排序是计算机学科中的一类特殊问题,其算法设计策略的灵活性使得求解算法更具多样性.基于形式化方法PAR(partition-and-recur),研究了排序算法的自动生成问题.刻画了排序问题的代数性质,形式化构建了排序算法领域的泛型类型构件和算法构件,建立了排序领域特定语言和算法生成形式化模型,以参数替换的方式自动生成了一组排序算法,包括快速排序、堆排序、Shell 排序等典型的已知算法以及增量选择排序等若干未见于现有文献的算法,并在程序生成系统中予以了实现.通过上层框架研究和底层构件支持,显著提高了特定领域算法的开发效率和可靠性.

摘要:对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k).与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.

摘要:真核细胞前体mRNA的剪接加工包含内含子剪切和外显子拼接两个过程,是真核细胞基因表达过程中的一个重要环节.针对这一环节,提出了一种模拟真核细胞前体mRNA 内含子剪切及其选择性剪接的算法,并在自主研发的电子细胞模型Analog-Cell 中实现了该算法,且获得了符合生物学原理的模拟结果.模拟结果表明,该算法可使剪接体高效、准确地模拟内含子的剪接过程,并形成套索结构,同时有选择地将外显子片段拼接起来,最终形成成熟的mRNA.

摘要:为求解等球packing 问题,在拟物模型基础上提出两个启发式策略:伪球策略和序列对称换位策略.前者旨在保证获取精确解;后者则用于从局部最优布局出发搜索到紧凑的可行布局.在处理器为Pentium E6500 2.93GHz的PC 机上进行了实算.在球形容器内对多达200 个等球、在立方体内对多达150 个等球进行了紧密装填.结果在质量和算例数量上均显著改进了国际上已知最好记录.特别地,在半径小于5 的大球中装下了68 个半径为1 的等球,证明否定了一个猜想,其认为半径为5 的大球最多只能装下67 个半径为1 的等球.

摘要:领域适应(或跨领域)学习旨在利用源领域(或辅助领域)中带标签样本来学习一种鲁棒的目标分类器,其关键问题在于如何最大化地减小领域间的分布差异.为了有效解决领域间特征分布的变化问题,提出一种三段式多核局部领域适应学习(multiple kernel local leaning-based domain adaptation,简称MKLDA)方法:1) 基于最大均值差(maximum mean discrepancy,简称MMD)度量准则和结构风险最小化模型,同时,学习一个再生多核Hilbert 空间和一个初始的支持向量机(support vector machine,简称SVM),对目标领域数据进行初始划分;2) 在习得的多核Hilbert 空间,对目标领域数据的类别信息进行局部重构学习;3) 最后,利用学习获得的类别信息,在目标领域训练学习一个鲁棒的目标分类器.实验结果显示,所提方法具有优化或可比较的领域适应学习性能.

摘要:在空间信息处理中,一些常识空间信息通常结合多方面空间关系,而且这些空间关系是动态变化的.为了有效地表示这些复杂的空间关系,并对其进行推理,提出了一种结合拓扑、方向和大小关系的空间信息处理模型TDSC (topology-direction-size calculus),并基于TDSC 模型提出了处理动态空间关系变化的表示推理框架.首先,利用同对象多属性的方法建立了融合大小、拓扑和方向关系的完备互斥基本关系表示;然后提出了复合表生成算法和推理算法,使得原有模型的表示和推理结果可以直接在新模型中使用.同时提出处理动态空间关系的邻域划分图,给出了邻域划分图的自动生成算法,以及TDSC 模型的邻域划分图.最后给出基于TDSC 模型邻域划分图的表示和推理框架,并结合实例说明框架的正确性和有效性.

摘要:对应物理论(counterpart theory)是一阶逻辑的一种理论.Lewis 利用谓词模态逻辑到对应物理论的翻译来研究谓词模态逻辑的性质,但是Lewis 的翻译存在把不可满足的公式翻译为可满足公式的情况.针对这个问题,提出了一种扩展语义的谓词模态逻辑,建立了扩展语义后谓词模态逻辑模型与对应物理论模型的一一对应关系,并在此基础上建立了谓词模态逻辑到对应物理论的语义忠实语义满翻译(faithful and full translation),其可确保将谓词模态逻辑的可满足公式和不可满足公式分别翻译为对应物理论的可满足公式和不可满足公式.由对应物理论是可靠的、完备的一阶逻辑的理论且语义忠实语义满翻译保持可靠性和完备性,进一步证明了扩展语义的谓词模态逻辑也是可靠和完备的.

摘要:为了研究偏置对支持向量回归(support vector regression,简称SVR)问题泛化性能的影响,首先提出了无偏置SVR(NBSVR)的优化问题及其对偶问题.推导出了NBSVR 优化问题全局最优解的必要条件,然后证明了SVR 的对偶问题只能得到NBSVR 对偶问题的次优解.同时提出了NBSVR 的有效集求解算法,并证明了它是线性收敛的.基于21 个标准数据集的实验结果表明,在对偶问题解空间上,有偏置支持向量回归算法只能得到无偏置支持向量回归算法的次优解,NBSVR 的均方根误差要低于SVR.NBSVR 的训练时间不仅低于SVR,而且对核参数变化不太敏感.

摘要:当前,系统融合是在机器翻译的后处理上进行.提出了在解码过程中来融合翻译模型,融合了主流两个翻译系统的翻译模型(层次化的基于短语的文法Hiero 和括号转录文法BTG).并从理论和实践的角度探索了现在主流的两种解码方法.同时,所提出的解码方法解决了伪歧义或一致性问题.在实验结果上得出:多文法模型融合的标志性要好于成员翻译模型;新的解码方法标志性好于传统解码方法(Viterbi 解码).

摘要:人体自适应行为仿真是实现人机工程学评估的前提条件.针对已有技术存在的不足,提出了一种基于多Agent 合作式博弈的虚拟人作业行为自主优化模型.该模型将工作环境中人体自适应行为定义为一个多目标优化问题,提出了人体工作状态空间和人体行为元素的概念,以实现人体行为的离散化.设计了人体行为仿真算法以求解上述模型.算法采用梯度上升的策略来搜索满足模糊多目标Nash 谈判条件的人体作业姿态的Pareto 最优解.仿真实验表明,该方法可以在缺少相关数据的情况下推导出舒适的人体工作姿态,在工程领域中表现出较好的适用性.

摘要:差分进化(differential evolution,简称DE)算法解决约束优化问题(constrained optimization problems,简称COPs)时通常采用可行解优先的比较规则,但是该方法不能利用种群中不可行解的信息.设计了可以利用不可行解信息的ε-DE 算法.该算法通过构造一种比较准则,使得进化过程可以充分利用种群中优秀不可行解的信息.该准则通过引入种群约束允许放松程度的概念,在进化初始阶段使可行域边界上且拥有较优目标函数的不可行解进入种群;随着进化代数增加,种群约束允许放松程度不断减小,使得种群中不可行解数量减少,直到种群约束允许放松程度为0,种群完全由可行解组成.此外,还选择了一种改进的DE 算法作为搜索算法,使得进化过程具有较快的收敛性.13 个标准Benchmark 函数实验仿真的结果表明:ε-DE 算法是目前利用DE 算法解决COPs 问题中效果最好的.

摘要:准确评估节点的重要性,是增强网络生存性的基础.由于域间路由系统路由策略的复杂性,已有的面向静态拓扑的节点重要性评估方法不能真实反映各个自治系统(autonomous systems,简称AS)在路由中的重要性.首次从动态路由的角度基于AS 之间的最优路径从路由上评估各个AS 的重要性,经过AS 的最优路径数量越多,它就越重要.提出了基于首选路由的AS 重要性评估方法,其时间复杂性为O(l×nm),它与面向静态拓扑的评估方法中最好的时间复杂性相同,并且能够更准确地描述节点的实际重要性.通过真实路由数据进行实验,与两种典型的面向静态拓扑的基于顶点度、强度中心性的评估方法对比,其结果表明,基于首选路由的评估方法可以有效发现AS 网络中连接较少但很重要的节点,并且评估的重要性与实际的重要性更吻合.

摘要:编码机会路由是有损无线Mesh 网络中提供高吞吐量和高可靠性传输的理想方案.该路由机制建立在无线广播的多用户分集优势和随机网络编码的纠删特性之上,为广播MAC 的设计引入了新的机会和挑战.基于最优停止理论,研究面向编码机会路由的机会广播信道接入问题,提出一种在接入延迟和信道交付能力之间加以折衷,以获得最优的平均有效速率的方法,并在IEEE 802.11 DCF 协议基础上设计实现面向NCOR 的广播MAC 协议O-BCast.仿真结果表明,该协议显著提高了编码机会路由的端到端吞吐量,具有网络负载自适应的良好特性.

摘要:目前已经提出的代理签名方案缺乏在完整的代理签名安全模型下证明方案的安全性.在Boldyreva 等人提出的代理签名安全模型的基础上,对代理签名的可证安全模型进行详细的形式化定义,提出一种完整的代理签名可证安全模型.同时,为了展示该安全模型的有效性和可扩展性,对Paterson 等人提出的标准模型下基于身份的签名方案进行扩展,提出在标准模型下基于身份的代理签名方案,并在可证安全模型下,证明新方案具有在自适应选择消息攻击下存在基于身份的代理签名不可伪造性,其安全性在标准模型下可归约于CDH 问题假定.新方案与标准模型下基于公钥密码体制的代理签名方案相比,不仅增加了用户身份的概念,还具有更完备的安全性.

摘要:0-1 矩阵常用于设计分组密码的扩散结构.首先证明,当GF(2ⁿ)上的矩阵重新定义在扩域GF(2^mn)上时其分支数保持不变,据此补充了Choy 等人关于GF(2ⁿ)上二元矩阵分支数上界的证明.构造了一批分支数达到最优的8 阶二元可逆矩阵,给出了一类差分分支数和线性分支数相等的二元可逆矩阵,并从中搜索出了大量16 阶分支数达到最优的二元矩阵和对合二元矩阵.

摘要:在无线传感器网络中,由于sink 附近的节点承担远方节点数据的转发,故能量消耗较高,容易在sink 附近形成能量空洞而使网络提前死亡.针对由初始能量较大节点充当簇头节点与初始能量较小的节点作为普通节点组成的异构分簇无线传感器网络,提出了不等簇半径工作能量空洞避免策略.策略的核心是让近sink 的簇半径较小,而远sink 的簇半径较大,这样,近sink 部署的初始能量较大的簇头节点较多,因而能够减弱能量空洞的影响,以达到能量消耗均衡的目的.将能量空洞避免问题转化为在保证网络寿命满足应用需求约束前提下如何使部署的节点最小的优化问题,并详细给出了不等簇半径的取值与优化方法.理论分析与实验结果表明,所提出的策略对网络寿命与性能有较大的改善,对于异构传感器网络建设有较好的指导意义.

摘要:基于属性的签名(attribute-based signature,简称ABS)方案可以隐藏签名者的身份.为了防止签名者滥用签名,Escala,Herranz 和Morillo 提出了一种可追踪签名者身份的基于属性签名方案(EHM-ABS),其中使用了自同构签名,并多次使用了非交互证据不可区分(non-interactive witness indistinguishable,简称NIWI)的证明.在Boyen 和Waters 的基于ID 的紧致群签名方案的基础上,在标准模型下提出了一种可追踪身份的ABS 方案.在颁发属性私钥时嵌入签名者的身份,并对身份使用比特加密的NIWI 证明来实现可追踪性.与EHM-ABS 相比,当声明的属性集合的阶大于ID 的比特长度的1/4 时,该方案减少了使用NIWI 证明的次数,且无须使用自同构签名.该方案的安全性基于子群判定假设和CDH 假设.

摘要:接入认证是层次型移动IPv6(HMIPv6)网络安全的基本需求.构建了适于HMIPv6 的分层认证框架,设计了一种节点证书与身份相结合的签名方案,并以此为基础提出了HMIPv6 网络双向接入认证机制.该机制利用基于身份密码技术简化了公钥基础设施的复杂密钥管理过程;以节点证书为接入认证的主要依据,消除了接入网络与家乡网络间的消息交互;采用提出的层次化签名方案,实现了用户与接入网络的双向认证.机制经过简单扩展,能够支持多层HMIPv6 网络的接入认证.性能与安全性分析表明,与传统的及其他基于身份的认证方案比较,所提出的机制拥有更高的认证效率和安全性.

摘要:提出一种基于均匀网格的点在多边形内的高效判定算法.它首先建立均匀网格,并从左至右依次计算每个网格单元中心点的位置属性.每个单元中心点的位置属性直接依据其左侧邻接单元已知位置属性的中心点快速获得.在判定点的位置时,确定被测点所在单元,并依据该单元中心点的位置属性判定被测点的位置属性.由于预处理和判定时均利用邻近点的已知位置属性来确定未知点位置属性,可以很好地进行局部化的计算.因此,新方法比现有方法快很多,并且其预处理时间复杂度也由同类网格算法的O(N^3/2)下降为O(N).同时,新方法可以统一处理含有自相交及重叠边的非流形多边形.实验结果表明,相比于其他基于均匀网格的方法,新方法可将预处理的速度提高几倍,将判断计算的速度提高十几到几十倍.其速度甚至优于具有该问题最低判定计算时间复杂度O(logN)的基于凸剖分的判定算法.

摘要:针对血管影像中灰度不均和弱边缘情况下已有水平集模型不能正确分割血管问题,提出一种耦合了血管影像的几何信息、边缘信息和区域信息的水平集分割方法.首先,采用Hessian 矩阵的各向异性性对血管状目标进行识别,对原始影像数据进行多尺度滤波;然后采用拉普拉斯算子零交叉点的快速边缘积分方法将边缘信息嵌入能量泛函中,构建一种基于结构、边缘和区域信息的水平集分割方法.相比于单一依靠影像边缘信息或区域信息模型及其改进模型,该方法在分割严重灰度不均匀的血管造影影像上能够准确提取血管,并精确定位血管边缘.

摘要:图像中存在的纹理、颜色和形状等异构视觉特征,在表示特定高层语义时所起作用的重要程度不同.为了在图像标注过程中更加有效地利用这些异构特征,提出了一种基于组稀疏(group sparsity)的多核学习方法(multiplekernel learning with group sparsity,简称MKLGS),为不同图像语义选择不同的组群特征.MKLGS 先将包含多种异构特征的非线性图像数据映射到一个希尔伯特空间,然后利用希尔伯特空间中的核函数以及组LASSO(groupLASSO)对每个图像类别选择最具区别性特征的集合,最终训练得到分类模型对图像进行标注.通过与目前其他图像标注算法进行对比,实验结果表明,基于组稀疏的多核学习方法在图像标注中能取得很好的效果.

摘要:为提高篡改检测性能和协调安全性与不可见性之间的矛盾,提出一种利用邻域比较判定图像块真实性的JPEG 脆弱水印算法.该算法将原始图像分成8×8 的图像块,基于图像块保护DCT 系数生成的4 比特水印基于密钥随机嵌入到其他4 个图像块量化步长较小的DCT 系数最低位.通过比较该图像块与相应4 个水印嵌入块8 邻域中不一致图像块个数来判定该图像块的真实性,推导给出一般篡改和拼贴攻击下算法的虚/漏警率,并利用统计实验对理论分析结果进行验证.理论分析和实验统计结果表明,通过比较图像块与其相应水印嵌入块8邻域中不一致图像块个数能够提高篡改检测性能,在量化步长较小DCT 系数的最低位嵌入水印,解决了保护DCT 系数个数与不可见性之间的矛盾.

摘要:提高图形用户界面(graphical user interface)的输入效率,是人机交互中的一项重要研究内容.已有的研究包括点击增强技术和自适应界面技术,前者改变光标的控制方式或呈现方式,后者改变界面上控件的位置布局,但两种技术都存在不足.通过分析界面操作,提出了图形用户界面输入效率的评价模型;然后,在此基础上提出一种人机交互效率优化技术:自适应光标.它以自适应的方式,有选择地对界面上用户可能访问的控件通过点击增强技术支持,实现快速访问.该方法既解决了以往的自适应界面技术因频繁调整控件布局而给用户带来额外认知成本的问题,也克服了点击增强技术仅适用于稀疏控件布局的限制.为了检验其可用性,在控件较多的Visual Studio 上实现了自适应光标技术.实验结果表明,使用自适应光标技术可以将获取目标的时间缩短27.7%,显著提高了图形用户界面的输入效率.