在前文中, 我们谈到了定义在半环上的动态规划及其适用范围, 以及动态规划在图模型中的一些应用。本文我们将沿着这个思路继续探索, 并把目光从图模型转向树结构. 我们首先提出以下几个问题:
Problem 1.1
试判定一个字符串是否属于一个上下文无关文法生成的语言.
Problem 1.2
给定一个字符串和一个随机上下文无关文法 (PCFG) , 则按照 PCFG 中的某个生成方式生成该字符串会有一个概率 p . 试求 p 的最大值.
本文将对上述问题展开讨论. 在涉及分析树的内容之前, 我们先对前文的内容做一个小小的总结, 之后我们解决上述的两个问题. 除此之外, 我们还将提及一个数据库系统中的查询模型. 笔者的研究不涉及数据库领域的很多内容, 对这个模型的理解也比较粗浅, 在这里只是提供一个树结构上的算法思路.
Problem 2.1
现在有一个数据库系统, 其中不同的机器存储不同的数据. 试设计一个查询系统, 使得用户可以在最短的时间内查询到特定的数据被存储在哪个机器.
Problem 2.2
弱化Problem 2.1的需求. 现在我们查询特定的数据后, 允许得到一个机器的列表, 只要列表中存在一个机器存有我们所需的数据即可. 试优化这个查询系统.
Problem 1.1
试判定一个字符串是否属于一个上下文无关文法生成的语言.
Problem 1.2
给定一个字符串和一个随机上下文无关文法 (PCFG) , 则按照 PCFG 中的某个生成方式生成该字符串会有一个概率 p . 试求 p 的最大值.
本文将对上述问题展开讨论. 在涉及分析树的内容之前, 我们先对前文的内容做一个小小的总结, 之后我们解决上述的两个问题. 除此之外, 我们还将提及一个数据库系统中的查询模型. 笔者的研究不涉及数据库领域的很多内容, 对这个模型的理解也比较粗浅, 在这里只是提供一个树结构上的算法思路.
Problem 2.1
现在有一个数据库系统, 其中不同的机器存储不同的数据. 试设计一个查询系统, 使得用户可以在最短的时间内查询到特定的数据被存储在哪个机器.
Problem 2.2
弱化Problem 2.1的需求. 现在我们查询特定的数据后, 允许得到一个机器的列表, 只要列表中存在一个机器存有我们所需的数据即可. 试优化这个查询系统.
RSS Feed
