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