• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >A monad for randomized algorithms.
【24h】

A monad for randomized algorithms.

机译：用于随机算法的monad。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This thesis presents new domain-theoretic models for randomized algorithms. A randomized algorithm can use random bits from an oracle to control its computation. The possible random bits form a binary tree, where each random choice of a bit is a branching of the tree. The randomized algorithm then determines what the output should be for each branch. This idea forms the basis of our random choice functors. However, the functor only provides one half of the model. We must also show how multiple randomized algorithms can be combined or composed. This is where the monadic structure comes into play. If we wish to join multiple randomized algorithms to form one resulting algorithm, then we can run each algorithm in parallel, using the same random bits for each.;Monads are used to add a computational effect to an existing semantic model. In order to work with models of the lambda calculus, it is important to work in a Cartesian closed category of domains, due to Lambek's theorem and Scott's corollary. Our first random choice monad is shown to be an endofunctor of the Cartesian closed category BCD. If we wish to add multiple computational effects, then we can compose monads as long as the monads enjoy a distributive law. It is shown that in the category BCD, our first random choice monad enjoys a distributive law with the lower powerdomain for nondeterminism. Two variations of the random choice monad are then given. The first variation has a distributive law with the convex powerdomain in the categories RB and FS, while the second variation has a distributive law with the upper powerdomain in BCD.;We use the random choice monads to develop a new programming language, Randomized PCF. This extends the language PCF by adding in random choice, allowing for the programming of randomized algorithms. A full operational semantics is given for Randomized PCF, and a random choice monad is used to give it a mathematical model (denotational semantics). Finally, an implementation of Randomized PCF is developed, and the Miller-Rabin algorithm is implemented in Randomized PCF.
机译：本文提出了一种新的随机算法领域理论模型。随机算法可以使用Oracle中的随机位来控制其计算。可能的随机位形成一棵二叉树，其中，每个位的随机选择都是该树的分支。然后，随机算法确定每个分支的输出应该是什么。这个想法构成了我们的随机选择函子的基础。但是，函子仅提供模型的一半。我们还必须说明如何组合或组合多个随机算法。这就是单子结构的作用。如果我们希望加入多个随机算法以形成一个结果算法，则可以并行运行每个算法，每个算法使用相同的随机位。Monad用于向现有语义模型添加计算效果。为了处理lambda演算的模型，由于Lambek定理和Scott的推论，在笛卡尔封闭域中工作非常重要。我们的第一个随机选择单子表明是笛卡尔封闭类BCD的内爆子。如果我们希望添加多个计算效果，那么只要单子享有分布律，就可以组成单子。结果表明，在BCD类别中，我们的第一个随机选择单子因非确定性而享有较低的幂域分布律。然后给出了随机选择单子的两个变体。第一个变量在RB和FS类别中具有凸幂域的分布定律，而第二个变量在BCD中具有较高幂域的分布定律。；我们使用随机选择单子来开发一种新的编程语言，随机PCF。这通过添加随机选择来扩展PCF语言，从而允许对随机算法进行编程。给出了随机PCF的完整操作语义，并使用了一个随机选择monad为其提供了数学模型（表示语义）。最后，开发了一种随机PCF的实现，并在随机PCF中实现了Miller-Rabin算法。

著录项

  • 作者

    Barker, Tyler C.;

  • 作者单位

    Tulane University School of Science and Engineering.;

  • 授予单位 Tulane University School of Science and Engineering.;
  • 学科 Mathematics.;Theoretical mathematics.;Computer science.
  • 学位 Ph.D.
  • 年度 2016
  • 页码 170 p.
  • 总页数 170
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 物理化学（理论化学）、化学物理学;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号