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

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
imported>Etone
 
imported>Macdonald-ross
mNo edit summary
 
Line 1: Line 1:
{{Infobox
{{otheruse|biological fitness}}
|name        = Infobox
'''Fitness''' in [[biology]] is the relative ability of an organism to survive and pass on its [[gene]]s to the next generation.<ref>King R.C. Stansfield W.D. & Mulligan P.K. 2006. ''A dictionary of genetics'', 7th ed. Oxford.</ref><sup>p160</sup> It is a central idea in [[evolution|evolutionary theory]]. Fitness is usually equal to the proportion of the individual's [[gene]]s in all the genes of the next generation. 
|bodystyle    =
|title        = <font size=3>随机算法
<br>Randomized Algorithms</font>
|titlestyle  =


|image        =
Like all terms in evolutionary biology, fitness is defined in terms of an interbreeding [[Population genetics|population]], which might or might not be a whole [[species]]. If differences in individual genotypes affect fitness, then the frequencies of the genotypes will change over generations; the genotypes with higher fitness become more common. This is the process called [[natural selection]].
|imagestyle  =
|caption      =
|captionstyle =
|headerstyle  = background:#ccf;
|labelstyle  = background:#ddf;
|datastyle    =


|header1 =Instructor
An individual's fitness is caused by its [[phenotype]], and passed on by its [[genotype]]. The fitnesses of different individuals with the same genotype are not necessarily equal. It depends on the [[environment]] in which the individuals live, and on accidental [[event]]s. However, since the fitness of the genotype is an [[average]]d quantity, it reflects the reproductive outcomes of ''all'' individuals with that genotype.
|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.  
== Relatedness ==
Fitness measures the number of the ''copies'' of the genes of an individual in the next generation. It doesn't really matter how the genes arrive in the next generation. For an individual, it is equally "beneficial" to reproduce itself, or to help relatives with similar genes to reproduce, ''as long as similar number of copies of individual's genes get passed on to the next generation''. Selection which promotes this kind of helper behaviour is called [[kin selection]].


= Announcement =
Our closest relatives (parents, siblings, and our own children) share on average 50% (half) of our genes. One step further removed are grandparents. With each of them we share on average 25% (a quarter) of our genes. That is a measure of our relatedness to them. Next come first cousins (children of our parents' siblings). We share 12.5% (1/8) of their genes.<ref name=JMS>Maynard Smith, John. 1999. ''Evolutionary genetics''. 2nd ed, Cambridge University Press.</ref><sup>p100</sup>
* <font color=red size=4> 第1次作业第3题新增一问。由于是在作业发布之后修改,是否做这一问题不会影响分数,但增加此问会使该题目更有意义。</font>
* <font color=red size=4> The first [[随机算法 (Spring 2013)/Problem_Set_1|homework assignment]] is out, due in two weeks.</font>


= Course info =
=== Hamilton's rule ===
* '''Instructor ''': 尹一通,
[[W.D. Hamilton|William Hamilton]] added various ideas to the notion of fitness. His rule suggests that a costly action should be performed if:
:*email: yitong.yin@gmail.com, yinyt@nju.edu.cn
:<math>C < R \times B </math>  where:
:*office: 计算机系 804.
* <math>c \ </math> is the reproductive cost to the altruist,
* '''Class meeting''': Tuesday 10am-12pm, 仙逸B-207.
* <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and
* '''Office hour''': Wednesday 2-4pm, 计算机系 804.
* <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".
Fitness costs and benefits are measured in [[fecundity]].<ref>Hamilton W.D. 1964. The genetical evolution of social behavior. ''Journal of Theoretical Biology'' '''7''' (1): 1–52. doi:10.1016/0022-5193(64)90038-4.</ref>


= Syllabus =
=== Inclusive fitness ===
Inclusive fitness is a term which is essentially the same as fitness, but emphasises the group of genes rather than individuals.


=== 先修课程 Prerequisites ===
Biological fitness says how well an organism can reproduce, and spread its genes to its offspring. The theory of inclusive fitness says that the fitness of an organism is also increased to the extent that its close relatives also reproduce. This is because relatives share genes in proportion to their relationship.
* 必须:离散数学,概率论,线性代数。
* 推荐:算法设计与分析。


=== Course materials ===
Another way of saying it: ''the inclusive fitness of an organism is not a property of itself, but a property of its set of [[genes]]''. It is calculated from from the reproductive success of the individual, plus the reproductive success of its relatives, each one weighed by an appropriate coefficient of relatedness.<ref>Adapted from Dawkins R. 1982. ''The extended phenotype''. Oxford: Oxford University Press, p186.  ISBN 0-19-288051-9</ref>
* [[随机算法 (Spring 2013)/Course materials|<font size=3>教材和参考书</font>]]


=== 成绩 Grades ===
== History ==
* 课程成绩:本课程将会有六次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
The [[British]] [[Sociology|social]] [[philosopher]] [[Herbert Spencer]] coined the phrase ''[[survival of the fittest]]'' in his 1864 work ''Principles of biology'' to mean what [[Charles Darwin]] called [[natural selection]].<ref> Herbert Spencer 1864. ''Principles of Biology'' London, vol 1, 444, wrote “This survival of the fittest, which I have here sought to express in mechanical terms, is that which Mr. Darwin has called ‘natural selection’, or the preservation of favoured races in the struggle for life. </ref> The original phrase was "survival of the best fitted".
* 迟交:如果有特殊的理由,无法按时完成作业,请提前联系授课老师,给出正当理由。否则迟交的作业将不被接受。


=== <font color=red> 学术诚信 Academic Integrity </font>===
== References ==
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线,本课程将不遗余力的维护学术诚信规范,违反这一底线的行为将不会被容忍。
{{Reflist}}


作业完成的原则:署你名字的工作必须由你完成。允许讨论,但作业必须独立完成,并在作业中列出所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
[[Category:Classical genetics]]
 
[[Category:Evolutionary biology]]
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中,对他人工作(出版物、互联网资料、其他人的作业等)直接的文本抄袭和对关键思想、关键元素的抄袭,按照 [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 
# [[随机算法 (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
# Universal Hashing
# Concentration of Measure
# The Probabilistic Method
# Markov Chain and Random Walk
# Coupling and Mixing Time
# Expander Graphs
# 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/Chebyshev's_inequality Chebyshev's inequality]
* [http://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound]

Latest revision as of 14:26, 23 June 2016

Template:Otheruse Fitness in biology is the relative ability of an organism to survive and pass on its genes to the next generation.[1]p160 It is a central idea in evolutionary theory. Fitness is usually equal to the proportion of the individual's genes in all the genes of the next generation.

Like all terms in evolutionary biology, fitness is defined in terms of an interbreeding population, which might or might not be a whole species. If differences in individual genotypes affect fitness, then the frequencies of the genotypes will change over generations; the genotypes with higher fitness become more common. This is the process called natural selection.

An individual's fitness is caused by its phenotype, and passed on by its genotype. The fitnesses of different individuals with the same genotype are not necessarily equal. It depends on the environment in which the individuals live, and on accidental events. However, since the fitness of the genotype is an averaged quantity, it reflects the reproductive outcomes of all individuals with that genotype.

Relatedness

Fitness measures the number of the copies of the genes of an individual in the next generation. It doesn't really matter how the genes arrive in the next generation. For an individual, it is equally "beneficial" to reproduce itself, or to help relatives with similar genes to reproduce, as long as similar number of copies of individual's genes get passed on to the next generation. Selection which promotes this kind of helper behaviour is called kin selection.

Our closest relatives (parents, siblings, and our own children) share on average 50% (half) of our genes. One step further removed are grandparents. With each of them we share on average 25% (a quarter) of our genes. That is a measure of our relatedness to them. Next come first cousins (children of our parents' siblings). We share 12.5% (1/8) of their genes.[2]p100

Hamilton's rule

William Hamilton added various ideas to the notion of fitness. His rule suggests that a costly action should be performed if:

[math]\displaystyle{ C \lt R \times B }[/math] where:
  • [math]\displaystyle{ c \ }[/math] is the reproductive cost to the altruist,
  • [math]\displaystyle{ b \ }[/math] is the reproductive benefit to the recipient of the altruistic behavior, and
  • [math]\displaystyle{ r \ }[/math] is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".

Fitness costs and benefits are measured in fecundity.[3]

Inclusive fitness

Inclusive fitness is a term which is essentially the same as fitness, but emphasises the group of genes rather than individuals.

Biological fitness says how well an organism can reproduce, and spread its genes to its offspring. The theory of inclusive fitness says that the fitness of an organism is also increased to the extent that its close relatives also reproduce. This is because relatives share genes in proportion to their relationship.

Another way of saying it: the inclusive fitness of an organism is not a property of itself, but a property of its set of genes. It is calculated from from the reproductive success of the individual, plus the reproductive success of its relatives, each one weighed by an appropriate coefficient of relatedness.[4]

History

The British social philosopher Herbert Spencer coined the phrase survival of the fittest in his 1864 work Principles of biology to mean what Charles Darwin called natural selection.[5] The original phrase was "survival of the best fitted".

References

Template:Reflist

  1. King R.C. Stansfield W.D. & Mulligan P.K. 2006. A dictionary of genetics, 7th ed. Oxford.
  2. Maynard Smith, John. 1999. Evolutionary genetics. 2nd ed, Cambridge University Press.
  3. Hamilton W.D. 1964. The genetical evolution of social behavior. Journal of Theoretical Biology 7 (1): 1–52. doi:10.1016/0022-5193(64)90038-4.
  4. Adapted from Dawkins R. 1982. The extended phenotype. Oxford: Oxford University Press, p186. ISBN 0-19-288051-9
  5. Herbert Spencer 1864. Principles of Biology London, vol 1, 444, wrote “This survival of the fittest, which I have here sought to express in mechanical terms, is that which Mr. Darwin has called ‘natural selection’, or the preservation of favoured races in the struggle for life.