随机算法6.856J / 18.416J Randomized Algorithms |
|
课程网址: | http://ocw.mit.edu/courses/electrical-engineering-and-computer-sc... |
主讲教师: | Prof. David R. Karger |
开课单位: | 麻省理工学院 |
开课时间: | 信息不详。欢迎您在右侧留言补充。 |
课程语种: | 英语 |
中文简介: | 本课程探讨如何通过随机抽样、随机选择证人、对称断裂和马尔可夫链, 使用随机化使算法更简单、更高效。所涉及的主题包括: 随机计算;数据结构 (哈希表、跳过列表);图形算法 (最小生成树、最短路径、最小切割);几何算法 (凸壳, 固定或任意尺寸的线性规划);近似计数;并行算法;在线算法;去分解技术;和算法概率分析工具。 |
课程简介: | This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Topics covered include: randomized computation; data structures (hash tables, skip lists); graph algorithms (minimum spanning trees, shortest paths, minimum cuts); geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension); approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms. |
关 键 词: | 随机算法; 算法; 高效的时间和空间; 计算问题; 数据结构; 图形算法; 优化; 马尔可夫链; 采样; 几何算法; 并行和分布式算法 |
课程来源: | 麻省理工大学公开课 |
最后编审: | 2016-03-12:cmh |
阅读次数: | 19 |