返回资讯中心
外部精选
软件工程
#开发者实时流

剑桥大学开设随机算法课程,由 Thomas Sauerwald 主讲

来源标题:Randomised Algorithms – University of Cambridge

剑桥大学计算机科学 Part II 开设随机算法课程,由 Thomas Sauerwald 博士主讲,共 12 小时面授讲座。课程聚焦随机算法的设计与分析,涵盖概率论、优化和图论工具,并通过 MAX-CUT、Chernoff 界和 Quick-Sort 等实例展开。选课需先修 Algorithms 1、Algorithms 2、计算机科学基础和概率论导论。

Hacker News 最新vismit20002026/11/10 · 8 天前7 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

主讲教师:Dr Thomas Sauerwald 适用:Part II CST 学期:Lent 学时:12 形式:线下授课 建议辅导学时:3 先修课程:Algorithms 1、Algorithms 2、Foundations of Computer Science、Introduction to Probability 考试:Paper 8 Question 12;Paper 9 Question 12 历年考题、Moodle、课程表

本课程旨在介绍算法设计与分析中的进阶技术,重点聚焦随机算法。课程涵盖概率论、优化与图论中的核心工具和思想,并通过多种算法与过程的示例来展开这些知识。本课程将展示:随机性不仅是一种重要的设计技术——它往往能带来更简单、更优雅的算法——而且在时间和空间受限的场景中可能不可或缺。

引言。课程概览。为什么需要随机算法?针对 MAX-CUT 问题的第一个随机算法。[1 讲]

集中不等式。矩生成函数与 Chernoff 界。扩展:有界独立差分方法。应用:球入箱、快速排序与负载均衡。[约 2 讲]

马尔可夫链与混合时间。图上的随机游走。应用:2-SAT 问题的随机算法。马尔可夫链的混合时间。应用:网络上的负载均衡。[约 2 讲]

线性规划及其应用。定义与应用。线性规划的建模。单纯形算法。寻找初始解。如何利用线性规划与分支定界求解一个经典 TSP 实例。[约 3 讲]

随机近似算法。随机近似方案。期望的线性性、去随机化。线性规划的确定性与随机舍入。应用:MAX3-SAT 问题、带权顶点覆盖、带权集合覆盖、MAX-SAT。[约 2 讲]

谱图理论与聚类。图与矩阵的特征值:特征值与图性质之间的关系、谱图绘制。谱聚类:电导、Cheeger 不等式。谱划分算法。[约 2 讲]

课程结束时,学生应能够:

  • Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis., Cambridge University Press, 2nd edition.
  • David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011
  • Cormen, T.H., Leiserson, C.D., Rivest, R.L. and Stein, C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN 978-0-262-53305-8

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →