随机算法 (Spring 2013) and Carmichael number: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Addbot
m (Bot: 21 interwiki links moved, now provided by Wikidata on d:q849530)
 
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 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 =

Latest revision as of 08:08, 11 March 2013

In number theory a Carmichael number is a composite positive integer [math]\displaystyle{ n }[/math], which satisfies the congruence [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ n }[/math]. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.

All prime numbers [math]\displaystyle{ p }[/math] satisfy [math]\displaystyle{ b^{p-1}\equiv 1\pmod{p} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ p }[/math]. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number [math]\displaystyle{ 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. Template:Math-stub

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Spring_2013)&oldid=7723"