Randomized Algorithms (Spring 2010)

随机算法 Randomized Algorithms

Randomized Algorithms by Motwani and Raghavan
Instructor
尹一通
Email	yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
office	蒙民伟楼 406
Class
Class meetings	8 am-10 am, Wednesday
Office hours	2pm-5pm, Saturday, MMW 406
Textbook
Motwani and Raghavan, Randomized Algorithms. Cambridge Univ Press, 1995.

This is the homepage for Randomized Algorithms class for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

Announcement

There is no announcement yet.

Syllabus

随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：

• 一些重要的随机算法的设计与分析；
• 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
• 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。

最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计聪明的算法通常都需要人们对问题本身的数学结构有深刻的认识。

先修课程 Prerequisites

必须：离散数学，概率论。 推荐：算法设计与分析。