首页> 正文

算法设计中的若干前沿问题

2020-12-07阅读(351)

算法设计中的若干前沿问题

论文摘要

在这篇论文中,我们详细地研究了数据流模型、计算几何、扩展图理论和计算生物学领域中的若干算法设计的前沿问题。数据流模型是伴随着互联网技术和大规模数据库的应用而日益受到重视的算法设计理论。自1996年N.Alon等人的开创性工作后,这一理论受到了广泛的关注。在本文中,我们将探讨如下三个问题:在区间有效的零次频率矩估测问题的研究中,我们系统地改进了2002年Z.Bar-Yossef等人和2005年A.Pavan等人的工作,给出了这一问题的目前最优实现算法。依赖于数据流问题的规约技术,我们给出了最大支配范数的时间复杂度更低的算法。在XML流相关性的研究中,针对树编辑距离这一测度的非直观性,我们定义了两个树之间的Hamming测度这一直观的比较方法。依赖于N.Nisan伪随机数发生器理论和稳态分布,我们给出了在数据流模型下计算这一测度的算法。实验结果表明Hamming测度能够很好地表示不同XML文档的相似性。针对互联网应用中选举问题的需要,并结合已有的冰川、频繁出现元素等统计信息的局限,我们在第四章定义了真实冰川的概念。运用误差函数、Count-Min摘要技术和Loglog计数摘要,我们给出了数据流模型下计算真实冰川的概率算法。论文的第二部分探讨最小Manhattan网络的计算复杂度和近似算法。这一问题于1999年由J.Gudmundsson等人提出。在那篇被广泛引用的文献中,J.Gudmundsson提出了这一领域的三个最重要的问题:（1）这一问题是否是NP-完全的;（2）这一问题是否存在PTAS算法;（3）这一问题是否存在2-近似算法。在论文的第五章中,我们首次回答了J.Gudmundsson的第一个问题:最小Manhattan网络问题是强NP-完全的。在同一章中,我们将详细探讨将3-SAT问题规约到最小Manhattan网络问题的证明细节。在第六章中,我们给出时间复杂度为O（n log n）的2-近似最小Manhattan网络构造算法。与已有的基于动态规划或线性规划的2-近似算法相比,本章证明了贪心策略即可以给出问题的2-近似算法。在扩展图这一部分中,我们分析Ramanujan图的构造算法。基于Ramanujan猜想,G.A.Margulis等人在二十世纪70年代首次运用数论的方法给出了谱扩展参数达到最优的扩展图——Ramanujan图。此后的一系列构造大多基于高深的数论和拓扑理论。随着理论计算机科学中退随机和编码理论的需要,人们希望运用组合数学的方法构造任意正则的Ramanujan图。在论文的第九章,我们首先定义了标准Z-积的一个自然推广。其次,结合A.Ben-Aroya等人在2008年的工作,我们给出了构造近-Ramanujan图的组合算法。本文的最后一部分考察了计算生物学领域中的DNA序列编码问题。与传统的编码理论不同,DNA序列的编码不仅需要满足传统意义上的Hamming距离约束,而且由于DNA序列需要满足特定的热力学性质等生物约束,从而使得对这一问题的研究变得更加复杂。M.-Y.Kao等人在2005年第一次系统化地提出了这一问题,并给出解决问题的概率算法。本文的第十章给出了满足特定计算生物学约束的DNA序列的确定性构造算法。与M.-Y.Kao等人的概率构造相比较,我们的构造效率更高。

论文目录

  • 指导小组成员
  • 中文摘要
  • 英文摘要
  • 前言
  • 第Ⅰ部分 数据流理论
  • 第一章 数据流模型
  • 1.1 引论
  • 1.2 取样与摘要设计
  • 1.3 概率论基础
  • 1.3.1 基本概念
  • 1.3.2 数学期望
  • 1.3.3 方差
  • 1.3.4 概率论基本不等式
  • 1.3.5 随机算法
  • 1.3.6 哈希函数
  • 1.3.7 稳态分布
  • 1.3.8 误差函数
  • 1.4 伪随机数发生器
  • 1.5 同余方程
  • 0-估测算法'>第二章 区间有效F0-估测算法
  • 2.1 引论
  • 2.1.1 问题描述
  • 2.1.2 相关工作
  • 2.1.3 本章主要结果
  • 2.2 预备知识
  • 0-估测算法'>2.3 区间有效F0-估测算法
  • 2.3.1 算法框架
  • 2.3.2 计算M（r）与G（r）
  • 2.3.3 算法与复杂度分析
  • 2.3.4 不同数据结构的算法实现
  • 2.3.5 正确性证明
  • 2.4 扩展:最大支配范数问题
  • 2.5 深入研究
  • 第三章 XML流的相关性估测算法
  • 3.1 引论
  • 3.1.1 问题描述
  • 3.1.2 论文主要工作
  • 3.1.3 结果
  • 3.2 算法描述
  • 3.3 算法的时空复杂度分析
  • 3.4 正确性证明
  • 3.5 模拟
  • 3.5.1 实验环境
  • 3.5.2 性能分析
  • 3.6 深入研究
  • 第四章 互联网通讯中的真实冰川
  • 4.1 引论
  • 4.1.1 问题描述
  • 4.1.2 结果
  • 4.2 预备知识
  • 4.2.1 Count-Min摘要
  • 4.2.2 Loglog计数摘要
  • 4.3 算法描述
  • 4.4 分析
  • 4.5 深入研究
  • 第Ⅱ部分 计算几何:Manhattan网络问题
  • 第五章 Manhattan网络问题的复杂度
  • 5.1 引论
  • 5.1.1 相关工作
  • 5.1.2 方法与结果
  • 5.2 预备知识
  • 5.3 规约
  • 5.3.1 部件设计
  • 5.3.2 部件NEGATOR
  • 5.3.3 其他部件
  • 5.3.4 网络的构造
  • 5.4 NP-难解性的证明
  • 第六章 Manhattan网络的近似算法
  • 6.1 预备知识
  • 6.2 算法描述
  • 6.3 近似度分析
  • 第Ⅲ部分 扩展图理论
  • 第七章 扩展图引论
  • 7.1 定义
  • 7.2 邻接矩阵与扩展性
  • 7.3 扩展图的构造
  • 第八章 图谱与图的组合特性
  • 8.1 扩展图收敛引理
  • 8.2 边扩展与导率
  • 8.3 离散拉普拉斯算子
  • 8.4 各种扩展的联系
  • 8.5 拉马努金图
  • 第九章 近-拉马努金图的构造
  • 9.1 预备知识
  • 9.1.1 记号
  • 9.1.2 双覆盖
  • 9.1.3 图的乘方
  • 9.1.4 置换积
  • 9.1.5 Z-积
  • 9.2 Z-积的推广
  • 9.3 推广Z-积的分析
  • 9.4 迭代构造
  • 第Ⅳ部分 计算生物学
  • 第十章 DNA编码设计
  • 10.1 引论
  • 10.1.1 问题描述
  • 10.1.2 本章主要结果
  • 10.2 预备知识
  • 10.2.1 约束条件
  • 10.2.2 编码理论
  • 10.3 基于扩展图的编码
  • 10.4 退随机的编码
  • 10.5 推广
  • 参考文献
  • 索引
  • 攻读博士学位期间的研究成果
  • 致谢

    • 相关论文文献

    • [1].动漫展重返纽约（英文）[J]. 第二课堂(A) 2016(12)
    • [2].发榜[J]. 葡萄酒 2017(08)
    • [3].基于Manhattan距离与随机邻域嵌入的故障特征提取算法[J]. 计算机应用研究 2015(10)
    • [4].清晨印象——“The Six People You Meet in Manhattan Before 8 A.M.”[J]. 新东方英语(大学版) 2014(03)
    • [5].守望Manhattan[J]. 长篇小说选刊 2010(04)
    • [6].INVESTMENT[J]. China's Foreign Trade 2009(23)
    • [7].Sunseeker Manhattan60 典雅浪漫 逐日而行[J]. 流行色 2009(08)
    • [8].高中二册第4单元练习[J]. 中学英语之友(高二版) 2008(08)
    • [9].Avoiding Non-Manhattan Obstacles Based on Projection of Spatial Corners in Indoor Environment[J]. IEEE/CAA Journal of Automatica Sinica 2020(04)
    • [10].WORLD[J]. Beijing Review 2016(29)
    • [11].数据融合和Manhattan距离在液压泵故障诊断中的应用[J]. 机床与液压 2009(10)
    • [12].美国纽约的时代广场[J]. 中学英语园地(初一版) 2008(06)
    • [13].基于Manhattan距离的城市轨道交通布控研究[J]. 浙江师范大学学报(自然科学版) 2015(03)
    • [14].高处的风景[J]. 新东方英语(大学版) 2016(06)
    • [15].中国欲整顿洋地名以维护“民族尊严”(英文)[J]. 大学英语 2016(06)
    • [16].Sunseeker品牌亮相2008上海国际游艇展[J]. 船艇 2008(09)
    • [17].China Overseas Plaza,A Dazzling Newcomer in the CBD[J]. Beijing Review 2008(29)
    • [18].THIS WEEK[J]. Beijing Review 2015(23)
    • [19].What's in a Number?[J]. Beijing Review 2008(18)
    • [20].基于均值置信区间带的高光谱特征波段选择与树种识别[J]. 光谱学与光谱分析 2011(09)
    • [21].一种人脸表情分类的新方法——Manhattan距离[J]. 计算机工程与应用 2008(02)
    • [22].WORLD[J]. Beijing Review 2017(45)
    • [23].如何阻止人类将垃圾填满世界[J]. 英语文摘 2015(09)
    • [24].American Occupation[J]. Beijing Review 2011(42)
    • [25].Yahoo推Cocktails航母:JavaScript框架[J]. 硅谷 2011(23)
    • [26].吴健雄(英文)[J]. 考试(高考英语版) 2009(12)
    • [27].Beijing Time Travel[J]. Beijing Review 2010(43)
    • [28].吉他大师埃里克·约翰逊的演奏分析——以乐曲《曼哈顿(Manhattan)》为例[J]. 明日风尚 2020(13)
    • [29].Shopping and Female Identity in Sophie Kinsella's Confessions of a Shopaholic and Shopaholic Takes Manhattan[J]. Comparative Literature:East & West 2015(02)
    • [30].考研翻译能力训练(3)[J]. 大学英语 2009(09)

    标签：;  ;  ;  ;  ;  ;  

    算法设计中的若干前沿问题
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5