imported>Etone |
imported>Addbot |
| Line 1: |
Line 1: |
| {{Infobox | | In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]]. |
| |name = Infobox
| |
| |bodystyle =
| |
| |title = <font size=3>随机算法
| |
| <br>Randomized Algorithms</font> | |
| |titlestyle = | |
|
| |
|
| |image =
| | All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. |
| |imagestyle =
| | {{Math-stub}} |
| |caption =
| | [[Category:Number theory]] |
| |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
| |
| |header4 =
| |
| |label4= office
| |
| |data4= 计算机系 804
| |
| |header5 = Class
| |
| |label5 =
| |
| |data5 =
| |
| |header6 =
| |
| |label6 = Class meetings
| |
| |data6 = Tuesday, 10am-12pm <br> 仙逸B-207
| |
| |header7 =
| |
| |label7 = Place
| |
| |data7 =
| |
| |header8 =
| |
| |label8 = Office hours
| |
| |data8 = Wednesday, 2-4pm <br>计算机系 804
| |
| |header9 = Textbooks
| |
| |label9 =
| |
| |data9 =
| |
| |header10 =
| |
| |label10 =
| |
| |data10 = [[File:MR-randomized-algorithms.png|border|100px]]
| |
| |header11 =
| |
| |label11 =
| |
| |data11 = Motwani and Raghavan. <br>''Randomized Algorithms''.<br> Cambridge Univ Press, 1995.
| |
| |header12 =
| |
| |label12 =
| |
| |data12 = [[File:Probability_and_Computing.png|border|100px]]
| |
| |header13 =
| |
| |label13 =
| |
| |data13 = Mitzenmacher and Upfal. <br>''Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. <br> Cambridge Univ Press, 2005.
| |
| |belowstyle = background:#ddf;
| |
| |below =
| |
| }} | |
| | |
| This is the page for the class ''Randomized Algorithms'' for the Spring 2013 semester. Students who take this class should check this page periodically for content updates and new announcements.
| |
| | |
| = Announcement =
| |
| * <font color=red size=4>The last [[随机算法 (Spring 2013)/Problem_Set_4|homework assignment]] is out, due on the date of the final exam.</font>
| |
| * 前几堂课的讲义已经补上，足够完成第三次作业。
| |
| * The third [[随机算法 (Spring 2013)/Problem_Set_3|homework assignment]] is out, due in two weeks.
| |
| * The second [[随机算法 (Spring 2013)/Problem_Set_2|homework assignment]] is out, due in two weeks.
| |
| * 第1次作业第3题新增一问。由于是在作业发布之后修改，是否做这一问题不会影响分数，但增加此问会使该题目更有意义。
| |
| * The first [[随机算法 (Spring 2013)/Problem_Set_1|homework assignment]] is out, due in two weeks.
| |
| | |
| = Course info =
| |
| * '''Instructor ''': 尹一通，
| |
| :*email: yitong.yin@gmail.com, yinyt@nju.edu.cn
| |
| :*office: 计算机系 804.
| |
| * '''Class meeting''': Tuesday 10am-12pm, 仙逸B-207.
| |
| * '''Office hour''': Wednesday 2-4pm, 计算机系 804.
| |
| | |
| = Syllabus =
| |
| | |
| === 先修课程 Prerequisites ===
| |
| * 必须：离散数学，概率论，线性代数。
| |
| * 推荐：算法设计与分析。
| |
| | |
| === Course materials ===
| |
| * [[随机算法 (Spring 2013)/Course materials|<font size=3>教材和参考书</font>]]
| |
| | |
| === 成绩 Grades ===
| |
| * 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
| |
| * 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
| |
| | |
| === <font color=red> 学术诚信 Academic Integrity </font>===
| |
| 学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
| |
| | |
| 作业完成的原则：署你名字的工作必须由你完成。允许讨论，但作业必须独立完成，并在作业中列出所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
| |
| | |
| 本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为，<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。
| |
| | |
| 学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
| |
| | |
| = Assignments =
| |
| *[[随机算法 (Spring 2013)/Problem Set 1|Problem Set 1]], due on March 26, Tuesday, in class.
| |
| *[[随机算法 (Spring 2013)/Problem Set 2|Problem Set 2]], due on April 23, Tuesday, in class.
| |
| *[[随机算法 (Spring 2013)/Problem Set 3|Problem Set 3]], due on June 4, Tuesday, in class.
| |
| *[[随机算法 (Spring 2013)/Problem Set 4|Problem Set 4]], due on June 24, before final exam.
| |
| | |
| = Lecture Notes =
| |
| # [[随机算法 (Spring 2013)/Introduction and Probability Space|Introduction and Probability Space]]: checking matrix multiplication, polynomial identity testing
| |
| # [[随机算法 (Spring 2013)/Conditional Probability|Conditional Probability]]: polynomial identity testing, min-cut
| |
| # [[随机算法 (Spring 2013)/Random Variables and Expectations|Random Variables and Expectations]]: random quicksort, balls and bins
| |
| # [[随机算法 (Spring 2013)/Moment and Deviation|Moment and Deviation]]: stable marriage, Markov's inequality, Chebyshev's inequality, median selection
| |
| # [[随机算法 (Spring 2013)/Threshold and Concentration|Threshold and Concentration]]: random graphs, threshold phenomenon, Chernoff bound
| |
| # [[随机算法 (Spring 2013)/Applications of Chernoff Bound|Applications of Chernoff Bound]]: error reduction, set balancing, packet routing
| |
| # [[随机算法 (Spring 2013)/Concentration of Measure|Concentration of Measure]]: martingales, Azuma's inequality, Doob martingales, chromatic number of random graphs
| |
| # [[随机算法 (Spring 2013)/Random Projection|Random Projection]]: Johnson-Lindenstrauss Theorem
| |
| # [[随机算法 (Spring 2013)/Universal Hashing|Universal Hashing]]: <math>k</math>-wise independence, universal hash families, perfect hashing
| |
| # [[随机算法 (Spring 2013)/The Probabilistic Method|The Probabilistic Method]]: MAX-SAT, conditional probability method, Lovász Local Lemma
| |
| # [[随机算法 (Spring 2013)/Markov Chain and Random Walk|Markov Chain and Random Walk]]: Markov chain, random walk, stationary distribution, convergence of Markov chain, hitting/cover time
| |
| # [[随机算法 (Spring 2013)/Mixing Time and Coupling|Mixing Time and Coupling]]: mixing time, coupling lemma, coupling of Markov chain, rapid mixing by coupling
| |
| # [[随机算法 (Spring 2013)/Expander Graphs and Mixing|Expander Graphs and Mixing]]: expander graphs, graph spectrum, spectral gap, Cheeger's inequality, rapid mixing of expander walk
| |
| # Sampling and Counting
| |
| | |
| = The Probability Theory Toolkit =
| |
| * [http://en.wikipedia.org/wiki/Probability_space Probability space] and [http://en.wikipedia.org/wiki/Probability_axioms probability axioms]
| |
| * [http://en.wikipedia.org/wiki/Independence_(probability_theory)#Independent_events Independent events]
| |
| * [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability]
| |
| * [http://en.wikipedia.org/wiki/Random_variable Random variable] and [http://en.wikipedia.org/wiki/Expected_value expectation]
| |
| * [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of 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/Variance Variance] and [http://en.wikipedia.org/wiki/Covariance covariance]
| |
| * [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/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]
| |
| * [http://en.wikipedia.org/wiki/Pairwise_independence k-wise independence]
| |
| * 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]
| |