:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :So, last time, we've discussed the TSP, and then introduced the P = NP problem.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Tonight, to go on the TSP, I'd like to discuss first about "Steiner's tree"
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The Steiner's ratio is the following :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :1 - sqrt(3)/2 = 0.133974596216...
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :And, here's Steiner's conjecture :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Between a direct spanning tree and the optimized tree, the maximal gain in terms of length is 13.4%.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Because of the difficulty to find the optimal length of this network and of the small expected gain, the network constructors use only the direct tree or locally optimized :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :*case of the electricity distribution
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :*buses lines
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :*gas
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :*TV network
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :*and even the genetic code of the genome of DNA
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :*etc.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The conjecture of the Steiner's ratio is important for the economy of any network.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :1/ Case of the equilateral triangle
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :A city assigned to each vertex : what's the shortest network?
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The tree AB, AC (BC is not necessary) is 2 units long.
:XsupremeX!XsupremeX4@RDR-5238F7C9.hsd1.mi.comcast.net JOIN :#lecture
:XsupremeX!XsupremeX4@RDR-5238F7C9.hsd1.mi.comcast.net PART #lecture :Leaving
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The tree AO, OC, OB for which we have to introduce a new point is only sqrt(3) = 1.73.. units.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The ratio is : sqrt(3)/2 = 0.866..
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :And the gain : 1-0.866 = 0.134
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :So, it is better to use the central network.
:Noise4Heroes!HP_Owner@RDR-D4F25A05.range86-128.btcentralplus.com JOIN :#lecture
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :2/ Let's build the Steiner point for any triangle!
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :For the triangle ABC:
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :draw the equilateral triangle ACX and its circumcircle.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :S is Steiner's point.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :See Torricelli and Fermat's point !
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture ::
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :http://mathworld.wolfram.com/TorricelliPoint.html
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :http://mathworld.wolfram.com/FirstFermatPoint.html
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :3/ Case of 6 cities into two adjacent squares
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :yet, the optimization is not obvious at all!
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :4/ The method of the greedy algorithm.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :It allows you to draw a direct optimal network, that is, without any intermediary point.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :We pairwise join the cities ordering them in increasing distances without making loops.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :5/ Another approach.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Solving the general case is a "difficult" geometry problem.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :That is to say : the exploring of the combinatorics is long and non-generalizable.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :But! we have showed (Ding Zhu Du and Frank Hwang) that, 
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :if the cities are the vertices of a lattice of right triangles,
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :only the Steiner's points of these triangles;
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :will be implied in the optimization of the network.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :And this considerably reduces the analysis.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Now, you may want to have a look at this : http://en.wikipedia.org/wiki/Steiner_tree .
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Is it OK?
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :hmm, I think so
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :alright
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :So, now, we may move on the 2nd and last part of this lecture, id est :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The "drunken walk." (or "drunkard's walk)
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :0.125 = 1/8 : average probability that the drunk falls down into the gutter.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :A drunk man, who just got out of the pub, goes randomly forward and backward between the pub and the gutter.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The gutter is 3 meters wide, and his paces are 0.5 meters large.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :What's the probability that he falls down into the gutter?
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :If he goes from the pub, he'd have to move forward 6 times consecutively.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :(equivalent with getting 6 heads consecutively at the game of head/tail)
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The probability is :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :(1/2)^6 = 1/64.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :If he goes from the middle, if he's 1.5 meter away from the gutter, he has to move forward three times consecutively.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :So, that gives a probability of (1/2)^3 = 1/8 = 0.125.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :In fact, one can easily notice that the guy will always end his walk (and maybe his night :P) in the gutter.
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :lol
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Indeed, on the pub's side, if it's closed, the backward pace will always be blocked.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Now, what about the generalization?
:militia!militia@RDR-6196749F.lns4-c10.dsl.pol.co.uk PRIVMSG #lecture :*generalisation, you yank.
:militia!militia@RDR-6196749F.lns4-c10.dsl.pol.co.uk PRIVMSG #lecture :;)
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture ::P
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :A system in a linear movement, physically limited by a wall on one of the extremities, and submitted to a purely random dynamic, will always see his average position going away from the wall, whatever the starting point is.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :(@militia : http://en.wikipedia.org/wiki/Generalization ;P)
:militia!militia@RDR-6196749F.lns4-c10.dsl.pol.co.uk PRIVMSG #lecture :point taken.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Now, let's see the biological point of view, with the evolution of the species.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Cope's rule says that the organisms tend to get bigger as the evolution goes on.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :This rule is true at about 70%, which is yet, in biology, something cool to affirm something.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :We should find 50/50.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Case of application of an increasing proability with a wall on the bottom.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :It is not paradoxical to see people being taller as time goes..
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :To read more about Cope's rule, I suggest :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :http://www.blackwellpublishing.com/ridley/a-z/Copes_rule.asp
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :and
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :http://en.wikipedia.org/wiki/Cope's_law
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :I _knew_ it would be wikipedia! ;P
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :;)
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Jay Gould even made a thesis on it.
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :
ACTION doesn't know who he is

:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :http://www.goodbyemag.com/apr02/gould.html
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :you see, he even appeared in an episod of The Simpsons! ;)
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :ah :P
:Megahertz!Megahertz@RDR-52CF4071.cpe.net.cable.rogers.com JOIN :#lecture
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Now, for a quick sum up on the interest of random walks : http://mathworld.wolfram.com/RandomWalk.html
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :and, for a longer explanation.. (guess where it comes from? :P)
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :http://en.wikipedia.org/wiki/Random_walk
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :For those who think they're comfortable with their math, you can try : http://www.physics.harvard.edu/academics/undergrad/probweek/prob26.pdf .
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :And, to check your answers :  http://www.physics.harvard.edu/academics/undergrad/probweek/sol26.pdf .
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :cool
:Ch4r!Ch4r@RDR-BBA3FD18.hsd1.ca.comcast.net PRIVMSG #lecture :lots of links to keep me busy ;D
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :hehe :)
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Now, we will see two points of view w.r.t. evolution of the species
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Evolution : according to Lamarck - according to Mendel
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The organism determines the favorable and adaptative things and transmits them via heredity.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :-
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Statistical developement with wall, developement of the diversity with time.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The evolution would reach his aim pretty quickly, but it does not work this way. - It is the evolution of the species. It goes slowly and in an indirect way.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The giraffe does not have a long neck to reach the leaves of the trees. - The giraffe, which happens to have a long neck, could resist because she could feed herself.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Maybe the cultural change is Lamarckian..
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :We transmit the knowledge via education. (like lectures, etc. ;P)
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :But the phenomenon is deeper.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :The Lamarckian evolution of the cultural things give the history of the technology a cumulative and direct character, completely different from the natural evolution of the species.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :You can have a look at this evolution tree : http://www.mun.ca/biology/scarr/Tree_of_Life4.gif .
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :To conclude this lecture, I'll just say two sentences :
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :Excellence is present in thousand places and we have to struggle in each of these places to preserve it.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :ONE HAS TO AVOID THE SPREADING OF UNIFORM MEDIOCRITY.
:qwertydawom!qwertydawo@RDR-61EE8C6D.fbx.proxad.net PRIVMSG #lecture :So, that's it for tonight. ;)