随机算法 (Fall 2011): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
No edit summary
Line 1: Line 1:
{{Infobox
|name        = Infobox
|bodystyle    =
|title        = 随机算法
Randomized Algorithms
|titlestyle  =
|image        = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle  =
|caption      = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle  = background:#ccf;
|labelstyle  = background:#ddf;
|datastyle    =
|header1 =Instructor
|label1  =
|data1  =
|header2 =
|label2  =
|data2  = 尹一通
|header3 =
|label3  = Email
|data3  = yitong.yin@gmail.com  yinyt@nju.edu.cn  yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5  =
|data5  =
|header6 =
|label6  = Class meetings
|data6  = 10 am-12 am, Tuesday, <br>馆III-101
|header7 =
|label7  = Place
|data7  =
|header8 =
|label8  = Office hours
|data8  = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9  =
|data9  =
|header10 =
|label10  =
|data10  = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|belowstyle = background:#ddf;
|below =
}}
This is the page for the class ''Randomized Algorithms'' for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.
There is also a backup page for off-campus users. The URL is http://lamda.nju.edu.cn/yinyt/random2010wiki/
= Announcement =
* (07/01/2010) 期末考试：时间7月6日，上午9点至11点；地点：教202。可携带一页A4打印纸（可双面）的笔记。
* (06/26/2010) 由于要统计考试人数，请参加期末考试的同学给我发email，把名字和学号告诉我。请看到通知的同学互相告知一下。
* (06/24/2010) 第四次作业答案公布。第三次作业答案已经补完。Sorry for the delay!
* (06/11/2010) 由于端午节轮休，6月15日的课改在13日星期日。
* (06/01/2010) The fifth homework is out. Due on Tuesday June 15, in class.
* (05/26/2010) 第十三课中的Estimator Theorem中有一处笔误，<math>\epsilon</math>应为<math>\epsilon^2</math>。感谢钱超同学发现这个问题。
::[[Randomized_Algorithms_(Spring_2010)/class announcements|(''older announcements...'')]]
= Course info =
* '''Instructor ''': 尹一通，
:*email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn
:*office: MMW 406.
* '''Class meeting''': 10am-12 am, Tue; 馆III-101.
* '''Office hour''': 2-5pm, Sat; MMW 406.
= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后，是一些共通的随机化原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会介绍以下内容：
* 一些重要的随机算法的设计思想和理论分析；
* 概率论工具及其在算法分析中的应用，包括常用的概率不等式，以及数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，包括典型的随机算法模型，以及概率复杂度模型。
作为一门理论课程，这门课的内容偏重数学上的分析和证明。这么做的目的不单纯是为了追求严格性，而是因为用更聪明的方法去解决问题往往需要具备有一定深度的数学思维和数学洞察力。
=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论。
* 推荐：算法设计与分析。
=== Course materials ===
* [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书清单]]
=== Policies ===
* [[Randomized Algorithms (Spring 2010)/Policies|Policies]]
= Assignments =
* (06/29/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 6 | Problem Set 6]] makeup assignment, hand in before the final exam.
* (06/01/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 5 | Problem Set 5]] due on June 15 , Tuesday, in class. 中英文不限。
* (05/18/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 4 | Problem Set 4]] due on June 1 , Tuesday, in class. 中英文不限。
* (04/20/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 3 | Problem Set 3]] due on May 4, Tuesday, in class. 中英文不限。
* (03/30/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 2 | Problem Set 2]] due on April 13, Tuesday, in class. 中英文不限。
* (03/16/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 1 | Problem Set 1]] due on March 30, Tuesday, in class. 中英文不限。
= Lecture Notes =
= Lecture Notes =
# Introduction
# Introduction
Line 86: Line 183:
#* [[随机算法 (Fall 2011)/Volume Estimation|Volume Estimation]]
#* [[随机算法 (Fall 2011)/Volume Estimation|Volume Estimation]]
# Complexity
# Complexity
= The Probability Theory Toolkit =
* [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of expectation]
* [http://en.wikipedia.org/wiki/Independence_(probability_theory)#Independent_events Independent events] and [http://en.wikipedia.org/wiki/Conditional_independence conditional independence]
* [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability] and [http://en.wikipedia.org/wiki/Conditional_expectation conditional expectation]
* The [http://en.wikipedia.org/wiki/Law_of_total_probability law of total probability] and the [http://en.wikipedia.org/wiki/Law_of_total_expectation law of total expectation]
* The [http://en.wikipedia.org/wiki/Boole's_inequality union bound]
* [http://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trials]
* [http://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution]
* [http://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution]
* [http://en.wikipedia.org/wiki/Markov's_inequality Markov's inequality]
* [http://en.wikipedia.org/wiki/Chebyshev's_inequality Chebyshev's inequality]
* [http://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound]
* [http://en.wikipedia.org/wiki/Pairwise_independence k-wise independence]
* [http://en.wikipedia.org/wiki/Martingale_(probability_theory) Martingale]
* [http://en.wikipedia.org/wiki/Azuma's_inequality Azuma's inequality] and [http://en.wikipedia.org/wiki/Hoeffding's_inequality Hoeffding's inequality]
* [http://en.wikipedia.org/wiki/Doob_martingale Doob martingale]
* The [http://en.wikipedia.org/wiki/Probabilistic_method  probabilistic method]
* The [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma  Lovász local lemma]  and the [http://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma algorithmic Lovász local lemma]
* [http://en.wikipedia.org/wiki/Markov_chain Markov chain]:
::[http://en.wikipedia.org/wiki/Markov_chain#Reducibility reducibility], [http://en.wikipedia.org/wiki/Markov_chain#Periodicity Periodicity], [http://en.wikipedia.org/wiki/Markov_chain#Steady-state_analysis_and_limiting_distributions stationary distribution], [http://en.wikipedia.org/wiki/Hitting_time hitting time], cover time;
::[http://en.wikipedia.org/wiki/Markov_chain_mixing_time mixing time], [http://en.wikipedia.org/wiki/Conductance_(probability) conductance]

Revision as of 16:15, 19 July 2011

随机算法 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 10 am-12 am, Tuesday,
馆III-101
Office hours 2pm-5pm, Saturday, MMW 406
Textbook
Motwani and Raghavan, Randomized Algorithms. Cambridge Univ Press, 1995.
v · d · e

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

There is also a backup page for off-campus users. The URL is http://lamda.nju.edu.cn/yinyt/random2010wiki/

Announcement

  • (07/01/2010) 期末考试：时间7月6日，上午9点至11点；地点：教202。可携带一页A4打印纸（可双面）的笔记。
  • (06/26/2010) 由于要统计考试人数，请参加期末考试的同学给我发email，把名字和学号告诉我。请看到通知的同学互相告知一下。
  • (06/24/2010) 第四次作业答案公布。第三次作业答案已经补完。Sorry for the delay!
  • (06/11/2010) 由于端午节轮休，6月15日的课改在13日星期日。
  • (06/01/2010) The fifth homework is out. Due on Tuesday June 15, in class.
  • (05/26/2010) 第十三课中的Estimator Theorem中有一处笔误，[math]\displaystyle{ \epsilon }[/math]应为[math]\displaystyle{ \epsilon^2 }[/math]。感谢钱超同学发现这个问题。
(older announcements...)

Course info

  • Instructor : 尹一通，
  • email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn
  • office: MMW 406.
  • Class meeting: 10am-12 am, Tue; 馆III-101.
  • Office hour: 2-5pm, Sat; MMW 406.

Syllabus

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

  • 一些重要的随机算法的设计思想和理论分析；
  • 概率论工具及其在算法分析中的应用，包括常用的概率不等式，以及数学证明的概率方法 (the probabilistic method);
  • 随机算法的概率模型，包括典型的随机算法模型，以及概率复杂度模型。

作为一门理论课程，这门课的内容偏重数学上的分析和证明。这么做的目的不单纯是为了追求严格性，而是因为用更聪明的方法去解决问题往往需要具备有一定深度的数学思维和数学洞察力。

先修课程 Prerequisites

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

Course materials

Policies

Assignments

  • (06/29/2010) Problem Set 6 makeup assignment, hand in before the final exam.
  • (06/01/2010) Problem Set 5 due on June 15 , Tuesday, in class. 中英文不限。
  • (05/18/2010) Problem Set 4 due on June 1 , Tuesday, in class. 中英文不限。
  • (04/20/2010) Problem Set 3 due on May 4, Tuesday, in class. 中英文不限。
  • (03/30/2010) Problem Set 2 due on April 13, Tuesday, in class. 中英文不限。
  • (03/16/2010) Problem Set 1 due on March 30, Tuesday, in class. 中英文不限。


Lecture Notes

  1. Introduction
  2. Probability Basics
  3. Balls and Bins
  4. Moment and Deviation
  5. Hashing and Fingerprinting
  6. Chernoff Bound
  7. Concentration of Measure
  8. Dimension Reduction
  9. The Probabilistic Method
  10. Approximation Algorithms, On-line Algorithms
  11. Markov Chain and Random Walk
  12. Random Walk Algorithms
  13. Coupling and Mixing Time
  14. Expander Graphs I
  15. Expander Graphs II
  16. Sampling and Counting
  17. MCMC
  18. Complexity

The Probability Theory Toolkit

reducibility, Periodicity, stationary distribution, hitting time, cover time;
mixing time, conductance
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4462"