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=3> The first [[http://tcs.nju.edu.cn/wiki/index.php/%E9%9A%8F%E6%9C%BA%E7%AE%97%E6%B3%95_(Spring_2013)/Problem_Set_1|homework assignment]] is out, due in two weeks.</font>
| |
| | |
| = 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.
| |
| | |
| = 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
| |
| # Universal hashing
| |
| # Moment and Deviation
| |
| # Chernoff Bound
| |
| # Concentration of Measure
| |
| # The Probabilistic Method
| |
| # Markov Chain and Random Walk
| |
| # Coupling and Mixing Time
| |
| # Expander Graphs
| |
| # Sampling and Counting
| |
| | |
| = The Probability Theory Toolkit =
| |