TCS Wiki - User contributions [en]

Randomized Algorithms (Spring 2010)

2009-12-26T15:52:02Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容将更加侧重数学上的分析和证明。这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:51:32Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:51:10Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:34:04Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)/Course materials

2009-12-26T15:32:06Z

172.21.11.85:

= Course textbook =
* '''[MR]''' Rajeev Motwani and Prabhakar Raghavan, ''Randomized Algorithms''. Cambridge University Press, 1995.
:《随机算法》已被高等教育出版社翻译引进。

= References and readings =
* '''[CLRS]''' Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. ''Introduction to Algorithms'', 2nd edition. MIT Press, 2001.
:《算法导论》，算法的经典教材之一，已被高等教育出版社原文引进。该书在这门课中可作为一本算法方面的工具书使用。

* '''[MU]''' Michael Mitzenmacher and Eli Upfal. ''Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. Cambridge University Press, 2005.
:《概率与计算》，机械工业出版社翻译引进。与[MR]相比，该书内容覆盖面较小，着重于分配问题 (allocation problems, balls-into-bins model)，但结构更加清晰。

* '''[Feller]''' William Feller, ''An Introduction to Probability Theory and Its Applications'', volumes 1, 3rd edition. Wiley, 1968.
:《概率论及其应用》，人民邮电出版社翻译引进。概率论的经典教材和工具书。

* '''[AS]''' Noga Alon and Joel Spencer. ''The Probabilistic Method'', 2nd edition. Wiley, 2000.
:组合数学的概率方法。

* '''[Chang]''' Joseph Chang. ''Stochastic Processes''. Lecture notes. http://www.stat.yale.edu/~jtc5/251/stochastic-processes.pdf
:耶鲁大学随机过程课程讲义。

* '''[HLW]''' Shlomo Hoory, Nathan Linial, and Avi Wigderson. ''Expander Graphs and Their Applications''. American Mathematical Society, 2006. [[media:Expanders.pdf|[PDF]]]
:原为普林斯顿高等研究院和以色列希伯来大学的课程讲义，是目前扩展图理论最好的介绍。

Randomized Algorithms (Spring 2010)/Course materials

2009-12-26T15:26:05Z

172.21.11.85:

= Course textbook =
* '''[MR]''' Rajeev Motwani and Prabhakar Raghavan, ''Randomized Algorithms''. Cambridge University Press, 1995.
:《随机算法》已被高等教育出版社翻译引进。

= References and readings =
* '''[CLRS]''' Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. ''Introduction to Algorithms'', 2nd edition. MIT Press, 2001.
:《算法导论》，算法的经典教材之一，已被高等教育出版社原文引进。该书在这门课中可作为一本算法方面的工具书使用。

* '''[MU]''' Michael Mitzenmacher and Eli Upfal. ''Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. Cambridge University Press, 2005.
:《概率与计算》，机械工业出版社翻译引进。与[MR]相比，该书内容覆盖面较小，着重于分配问题 (allocation problems, balls-into-bins model)，但结构更加清晰。

* '''[Feller]''' William Feller, ''An Introduction to Probability Theory and Its Applications'', volumes 1, 3rd edition. Wiley, 1968.
:《概率论及其应用》，人民邮电出版社翻译引进。概率论的经典教材和工具书。

* '''[AS]''' Noga Alon and Joel Spencer. ''The Probabilistic Method'', 2nd edition. Wiley, 2000.
:组合数学的概率方法。

* '''[Chang]''' Joseph Chang. ''Stochastic Processes''. Lecture notes. [http://www.stat.yale.edu/~jtc5/251/stochastic-processes.pdf|PDF]]
:耶鲁大学随机过程课程讲义。

* '''[HLW]''' Shlomo Hoory, Nathan Linial, and Avi Wigderson. ''Expander Graphs and Their Applications''. American Mathematical Society, 2006. [[media:Expanders.pdf|[PDF]]]
:原为普林斯顿高等研究院和以色列希伯来大学的课程讲义，是目前扩展图理论最好的介绍。

Randomized Algorithms (Spring 2010)/Course materials

2009-12-26T15:25:38Z

172.21.11.85:

= Course textbook =
* '''[MR]''' Rajeev Motwani and Prabhakar Raghavan, ''Randomized Algorithms''. Cambridge University Press, 1995.
:《随机算法》已被高等教育出版社翻译引进。

= References and readings =
* '''[CLRS]''' Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. ''Introduction to Algorithms'', 2nd edition. MIT Press, 2001.
:《算法导论》，算法的经典教材之一，已被高等教育出版社原文引进。该书在这门课中可作为一本算法方面的工具书使用。

* '''[MU]''' Michael Mitzenmacher and Eli Upfal. ''Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. Cambridge University Press, 2005.
:《概率与计算》，机械工业出版社翻译引进。与[MR]相比，该书内容覆盖面较小，着重于分配问题 (allocation problems, balls-into-bins model)，但结构更加清晰。

* '''[Feller]''' William Feller, ''An Introduction to Probability Theory and Its Applications'', volumes 1, 3rd edition. Wiley, 1968.
:《概率论及其应用》，人民邮电出版社翻译引进。概率论的经典教材和工具书。

* '''[AS]''' Noga Alon and Joel Spencer. ''The Probabilistic Method'', 2nd edition. Wiley, 2000.
:组合数学的概率方法。

* '''[Chang]''' Joseph Chang. ''Stochastic Processes''. Lecture notes. [http://www.stat.yale.edu/~jtc5/251/stochastic-processes.pdf[PDF]]
:耶鲁大学随机过程课程讲义。

* '''[HLW]''' Shlomo Hoory, Nathan Linial, and Avi Wigderson. ''Expander Graphs and Their Applications''. American Mathematical Society, 2006. [[media:Expanders.pdf|[PDF]]]
:原为普林斯顿高等研究院和以色列希伯来大学的课程讲义，是目前扩展图理论最好的介绍。

Randomized Algorithms (Spring 2010)

2009-12-26T15:21:19Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:20:04Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计聪明的算法通常都需要人们对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-26T15:18:55Z

172.21.11.85:

{{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 = 8 am-10 am, Wednesday
|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.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 算法的概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
最为一门理论课，这门课程的内容将侧重数学上的分析和证明，这么做的目的不仅仅是为了结果的严格性，而是因为设计聪明的算法通常都需要人们对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/policies|规则 Policies]] ===

= Assignments =

= Lecture Notes =