并行计算-多媒体课件-并行算法设计及分析-ch18 Randomized Algorithms.ppt

credential: bring a computer die photo wafer : This can be an hidden slide. I just want to use this to do my own planning. I have rearranged Culler’s lecture slides slightly and add more slides. This covers everything he covers in his first lecture (and more) but may We will save the fun part, “ Levels of Organization,” at the end (so student can stay awake): I will show the internal stricture of the SS10/20. Notes to Patterson: You may want to edit the slides in your section or add extra slides to taylor your needs. credential: bring a computer die photo wafer : This can be an hidden slide. I just want to use this to do my own planning. I have rearranged Culler’s lecture slides slightly and add more slides. This covers everything he covers in his first lecture (and more) but may We will save the fun part, “ Levels of Organization,” at the end (so student can stay awake): I will show the internal stricture of the SS10/20. Notes to Patterson: You may want to edit the slides in your section or add extra slides to taylor your needs. Y.Xu Copyright USTC Parallel Algorithms * / Ch18 Parallel Algorithms * / Ch18 Y.Xu Copyright USTC Y.Xu Copyright USTC *  Parallel Algorithms  Chapter 18 Randomized Algorithms * Y.Xu Copyright USTC 主要内容 18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法 18.2 低度顶点部分独立集 - 串行算法 - 随机并行算法 18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证 * Y.Xu Copyright USTC 18.1 引言 18.1.1 基本知识 1.随机算法的定义 - 定义: 是一个概率图灵机. 也就是在算法中引入随机因素, 即通过随机数选择算法的下一步操作. - 三要素: 输入实例、随机源和停止准则. - 特点: 简单、快速和易于并行化. - 一种平衡: 随机算法可以理解为在时间、空间和随机三大 计算资源中的平衡(Lu C.J. PhD Thesis 1999). - 重要文献 Motwani R. and Raghavan P., Randomized Algorithms. Cambridge University Press, New York, 1995 * Y.Xu Copyright USTC 18.1 引言 18.1.1 基本知识 2.背景和历史 (1)重要方法 - Monte Carlo求定积分法 - 随机k-选择算法 - 随机快排序 -素性判定的随机算