<qwertydawom> So, graph theory was firstly (and mainly created because of that actually) used in economy.
<qwertydawom> Indeed, it allows, for example, to find the shortest path to go from one city to another.
<qwertydawom> So, let's show how it works. :)
<qwertydawom> 120 : angle of the shortest path between three points.
<qwertydawom> The length of the shortest road between three cities is obtained like this :
<qwertydawom> you draw three points A, B and C in the plane
<qwertydawom> and now, the aim is to find a fourth point (let's call it D) which is placed such that :
<qwertydawom> m(CDB) = m(BDA) = m(ADC) = 120\uffff
<qwertydawom> where m(stuff) denotes the measure of the angle "stuff"
<qwertydawom> (in degrees)
<qwertydawom> so, come on, take a piece of paper, a pen, and start drawing ;)
<qwertydawom> let me know when you get it
<varu|zZz> 10 years and 4 failed calculus courses later...
<qwertydawom> :)
<varu|zZz> erm..
<varu|zZz> allow me to ask for some.. clarification
<varu|zZz> what exactly is it that you want us to do? :P
<varu|zZz> I mean, alright, points A, B, and C. Randomly drawn.
<SysSpider> oh we're supposed to do something?
<qwertydawom> draw three points
<SysSpider> the traveler salesman problem?
<qwertydawom> yes
<SysSpider> P = NP? ;)
<qwertydawom> well, a special case of it ;)
<SysSpider> yep
<SysSpider> it was my passion for like 2 years
<Daedalus> eh..
<Daedalus> lol
<qwertydawom> haha, no, I am not going to prove (or disprove) P = NP tonight :p
<qwertydawom> and, I don't want to hear :
<SysSpider> i can guess it xD
<qwertydawom> P = NP <==> P - NP = 0 <==> P(1 - N) = 0 <==> P = 0 or N = 1, q.e.d.
<qwertydawom> ;)
<SysSpider> that was my first thought as well lol
<qwertydawom> haha :)
<qwertydawom> So, did you get the case n=3 points?
<Daedalus> Can this be done for any three points?
<qwertydawom> yes :)
<qwertydawom> well
<qwertydawom> it is true if each of the angles of the triangle ABC is less than 120\uffff, to be precise.
<qwertydawom> (only if)
<Daedalus> less?
<Daedalus> argh
<Daedalus> ehh
<Daedalus> wait..
<Daedalus> Oh ah.. nvm. xD
<qwertydawom> :)
<qwertydawom> so, got it?
<Daedalus> ...
<qwertydawom> ok
<qwertydawom> I believe this will REALLY help you :
<qwertydawom> http://www.utdanacenter.org/mathtoolkit/downloads/geoassess/geo_2_steiners.pdf
<qwertydawom> take 5 mins. to look at it
<qwertydawom> then, tell me when you're done
<qwertydawom> for those who think they got the case n=3, have a look at :
<qwertydawom> http://www.delphiforfun.org/Programs/traveling_salesman.htm
<qwertydawom> now, if you think this is still too "childish" for you :
<qwertydawom> http://en.wikipedia.org/wiki/Traveling_salesman
<qwertydawom> so, by now, as soon as you're done with reading and/or understanding, let me know
<Daedalus> I miss my triangle..
<qwertydawom> so, did you have a look at this chapter about the Steiner's point?
<Daedalus> humz.. the quickest way would be to print a dot and 3 lines each 120 degrees with the dot, then just shove the paper around and rotate till it fits. >_>
<Daedalus> Till it meets the requirements noted earlier.
<Daedalus> Where is my geometry triangle..
<Daedalus> I read it alright
<Daedalus> but I can't even answer the first problem in scaffold questions
<qwertydawom> mmk
<qwertydawom> well, look at the solution
<qwertydawom> and then you'll try to solve the second problem by yourself
<qwertydawom> oh, you said the 'scaffolding questions'..
<qwertydawom> in this case, don't worry
<qwertydawom> as long as you managed to understand how to draw the point D
<qwertydawom> and noticed that it is indeed the shortest point (I mean, intuitively)
<qwertydawom> then it's alright! ;)
<qwertydawom> so, are you all done with reading?
<qwertydawom> Ok, I'll go on.
<qwertydawom> Now that we've seen the case with 3 points, guess what we are going to study? :)
<Daedalus> cases with n points?
<qwertydawom> not that quickly
<qwertydawom> simply : n=4.
<qwertydawom> So, we have a quadrilateral ABCD.
<Daedalus> Ouch, long word..
<qwertydawom> haha :)
<Daedalus> you mean a plane right?
<qwertydawom> ?
<adrian> you dont know what a quadrilateral is?
<Ch4r> Daedalus, he means a four-sided shape :P
<qwertydawom> quadrilateral : polygon with 4 sides and four vertices
<SysSpider> a polygon with 4 sides
<SysSpider> that
<adrian> thats grade 3 geometry lol
<Daedalus> yeah, a plane. xD
<SysSpider> err no?
<SysSpider> a plane is an infinite surface
<Daedalus> For me it is..
<qwertydawom> mmm
<qwertydawom> where do you come from? (if I may ask)
<SysSpider> netherlands
<Daedalus> The netherlands.
<Daedalus> *points to IP*
<qwertydawom> okay
<Daedalus> And i'm in the "highest" class of education
<Daedalus> but I'm still feeling stupid.
<qwertydawom> and how do you say so in Dutch? (if I'm not wrong with the language :-/)
<Daedalus> vierkant. (fourside)
<Daedalus> viereck in german I thought. *-)
<qwertydawom> well
<qwertydawom> from what I know, a vierkant (or kwadraat) is just a square
<qwertydawom> meaning that the 4 sides are equal
<SysSpider> and the 4 angles
<Daedalus> each 90 degrees.
<Daedalus> yeah that's right..
<Daedalus> but a plane is a vlak.
<qwertydawom> what I'm talking about is a : vierhoek
<Daedalus> ah.
<qwertydawom> now, it's talking? :)
<Daedalus> yeah continue..
<qwertydawom> okay ;)
<qwertydawom> So, we take a point E in the center of the quadrilateral.
<qwertydawom> With E and two of the points we look for the triangles whose angles are less than 120\uffff, so we are back to our previous case. ;)
<qwertydawom> You have to adjust E little by little.
<qwertydawom> ok?
<Daedalus> yes..
<qwertydawom> alright, now I will let you all finish to read all the links I mentioned. ;)
<qwertydawom> the lecture will be continued in (more or less) 10 mins.
<qwertydawom> for those who have already read it all, consider it as a little free time! ;)
:qwertydawom!qwertydawo@bu-61EE8C6D.fbx.proxad.net TOPIC #lecture :Lecture going on. - Read! :p - 10 mins. until we go on.
<Daedalus> That computer beats me by far.
<Daedalus> The TSP program
<Daedalus> 2000 miles..
<Daedalus> i wasn't too far off this time th
<Daedalus> *tho
<Daedalus> Just pick the points that are closest to each other each time.
<Daedalus> :D
<Daedalus> We got the same result for 20 cities. :D
<qwertydawom> hehe :)
<Daedalus> but that has little to do with the actual math behind the program.. >_>
<qwertydawom> yes lol
<qwertydawom> So, let's go on. ;)
:qwertydawom!qwertydawo@bu-61EE8C6D.fbx.proxad.net TOPIC #lecture :Lecture going on.
<qwertydawom> Let us now study the "Traveling salesman problem".
<qwertydawom> How to minimize the path of our salesman going from city to city.
<qwertydawom> ?*
<Daedalus> easy, from the starting dot, calculate the distance of each next city, then pick the one that's closest.
<Daedalus> *dot == city
<qwertydawom> This problem seems pretty easy, eh?
<Daedalus> it seems? :| It isn't?
<SysSpider> nope
<SysSpider> it's NP
<Daedalus> Damn
<Daedalus> hey my method works okay as well. >_>
<qwertydawom> Well, it becomes extremely complicated when the number of cities increases.
<qwertydawom> Let us illustrate the problem.
<Daedalus> That's why the exhaustive search takes so long. *-)
<qwertydawom> With my car, I say I can take back two of my friend -adrian and bot- to their home.
<qwertydawom> I begin with adrian, and then bot, or the contrary.
<qwertydawom> Then, the day after, I also propose it to Ch4r.
<adrian> what?
<adrian> oh
<adrian> k
<qwertydawom> In the first case, there were two locations, 2 possibilities.
<qwertydawom> Now that I propose to take Ch4r back too,
<qwertydawom> *adrian then bot then Ch4r
<Ch4r> 3! = 6 ;x
<qwertydawom> *adrian then Ch4r then bot
<qwertydawom> *bot then adrian then Ch4r
<qwertydawom> yes Ch4r ;)
<qwertydawom> so, end the list! :)
<Ch4r> *bot then Ch4r then adrian
<Ch4r> *Ch4r then bot then adrian
<Ch4r> *Ch4r then adrian then bot
<qwertydawom> exactly. :)
<qwertydawom> So, we have 3 locations, 6 possibilities.
<qwertydawom> The explanation (of this 6) :
<qwertydawom> 3 choices for the 1st location
<qwertydawom> 2 for the 2nd one
<qwertydawom> and only one for the last one :
<qwertydawom> 3*2*1 = 3! = 6.
<qwertydawom> And then, the week after, Daedalus comes with us.
<Daedalus> yeey
<qwertydawom> *adrian then bot then Ch4r then Daedalus
<qwertydawom> *adrian then Ch4r then bot then Daedalus
<Daedalus> Save the typing, I think we get this part, is it really important?
<qwertydawom> *etc.
<Daedalus> lol
<Daedalus> nvm. xD
<qwertydawom> :)
<qwertydawom> So :
<qwertydawom> 4 locations
<qwertydawom> 4! = 4*3*2*1 = 24 possibilities (no, I wasn't going to write them all! :P)
<Daedalus> 4*3*2= 24 options.
<qwertydawom> yep :)
<Daedalus> 120, 720, (4900+140)..
<qwertydawom> And now, say I want to take 10 people back.. (it appears that my car is in fact a BIG car.. :P).
<Daedalus> hahaha
<qwertydawom> 10 locations
<Daedalus> It increases drasticly
<qwertydawom> 10*9*...*3*2*1 = 3628800 possibilities  ....
<Daedalus> Sweet
<qwertydawom> and with 100 people (do I have a plane or what? :P)
<Ch4r> lol
<qwertydawom> it really goes high..
<Ch4r> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
<qwertydawom> 100! = 0.933*10^(158) possibilities   o_O
<Daedalus> hahaha
<qwertydawom> thank you Ch4r for the exact value :)
<Daedalus> You also got a lot of friends btw.
<Ch4r> np ;)
<qwertydawom> <Daedalus> You also got a lot of friends btw. --> haha, yes :)
<qwertydawom> To have an idea of what this incredibly big number represents :
<qwertydawom> even with the maximum velocity of the computers nowadays
<qwertydawom> let's say 1 nanosecond to examine one possibility
<qwertydawom> it will need 10^(158) ns to examine them all, that is 10^(149) seconds.
<qwertydawom> there are almost 10^7 seconds in a year
<qwertydawom> so, it will take 10^(142) years
<qwertydawom> the age of the universe is almost 10^(10) years
<qwertydawom> so, it will take 10^(132) times the age of the universe
<qwertydawom> OMFG!
<qwertydawom> :)
<Ch4r> lol
<Ch4r> nice
<varu|zZz> so essentially, another 10-20 big bangs will happen till all possibilities are explored
<qwertydawom> !=
<qwertydawom> :)*
<qwertydawom> so, well, if I decide to take back the 157 members of BU, hehe....
<qwertydawom> Now, you're probably interested in knowing the solution to this problem, aren't you?
<Daedalus> I'm very curious, and hoping it doesn't involve really hard math, because i'm kinda bad at it.
<Ch4r> ACTION nods :P
<qwertydawom> Well, the solution giving the optimal path to our salesman is NOT simple.
<qwertydawom> During the past centuries, guides were published to help to organize the tour.
<qwertydawom> In fact, a general solution for any number of locations or any lengths between the steps is not known at the moment I write this.
<qwertydawom> Here, I will show you a possible method :
<qwertydawom> Our salesman wants to go through each dot of the tour, in fact :
<qwertydawom> via the shortest path, without going twice at the same place
<qwertydawom> What's the shortest path passing through all these points?
<qwertydawom> Let us assume the points are the vertices of a parallelepiped in n dimensions.
<qwertydawom> We denote the vertices by 000...00, 000...01, 000...10, etc.
<qwertydawom> So, in 2D, with 4 points, the vertices would be :
<qwertydawom> 00, 01, 10, 11
<qwertydawom> in 3D, with 8 points :
<qwertydawom> 000, 001, 011, 010, 110, 111, 101, 100
<Daedalus> gray code
<qwertydawom> We organize the lengths of the parallelepiped from the greatest to the smallest,
<qwertydawom> and we begin with the vertice 000...00.
<qwertydawom> We can do this without loss of generality.
<Daedalus> *vertex
<qwertydawom> yes, vertex, sorry ;)
<Daedalus> dw, it's the part i got. ;)
<qwertydawom> The solution is unique.
<qwertydawom> It consists, for the salesman, to go from one vertex to another using the Gray code, like you noticed! ;)
<qwertydawom> Adleman managed to build an ADN computer who solve one version of the traveling salesman problem.
<qwertydawom> The ADN computer needed one week, while a classic computer would have needed years..
<Daedalus> but this was just for one problem?
<qwertydawom> oh, by the way : ADN = DNA*
<qwertydawom> Daedalus, you can have a look at (just the beginning) : http://web.cecs.pdx.edu/~mperkows/temp/June16/dna2.pdf
<qwertydawom> So, now, let's introduce the notion of "polynomial problem"
<qwertydawom> 1/ Sorting problem.
<qwertydawom> Sorting 1000000 objects should take about 1000 times more than sorting 1000 objects.
<qwertydawom> In fact, the simplest sorting programs take a time proportional to the square of the number of articles to be sorted.
<qwertydawom> The theoricians of the complexity were able to show that the quickest possible sorting program would require a number of steps proportional to the number of objects, multiplied by its logarithm.
<qwertydawom> (For those who are already confident with this idea of complexity, it means, that, if we have n objects, the simplest algorithm has a complexity of O(n^2) while the 2nd one has a complexity of O(n*ln n))
<qwertydawom> 2/ Polynomial problem.
<qwertydawom> The problems whose solution can be computed in a time at most proportional to a given power of the size of the problem are said to be of polynomial type, or P.
<qwertydawom> Nowadays, with the computers, they are considered as easy.
<qwertydawom> 3/ The T.S.P.
<qwertydawom> Find the shortest path to visit once and only once a set of given cities.
<qwertydawom> The best exact solutions found are tantamount to make the program examine almost all the possible paths.
<qwertydawom> The number increases exponentially with the number of cities.
<qwertydawom> (see the solution above)
<qwertydawom> 4/ Non-deterministic problem
<qwertydawom> To solve the problem of the salesman, we can imagine a computer which would be able to browse simultaneously all the possible paths.
<qwertydawom> When arrived at a "crossroad", the machine separates into two parts and browses simultaneously the two paths.
<qwertydawom> Then, this machine could solve the problem in a polynomial time.
<qwertydawom> These problems are said to be NP.
<qwertydawom> The connection of the components on a circuit is of this type.
<qwertydawom> Same goes for the automatic reasoning.
<qwertydawom> 5/ Practically speaking :
<qwertydawom> We have never been able to transform a NP problem into a succession of problems of type P.
<qwertydawom> We always proceed with approximative methods which do not guarantee the quality of the answer at all, and which are sometimes really.. sucking.<qwertydawom> This problem to know if, yes or not, P = NP is still open, and if you can prove or disprove it, you can win $1 million as it is one of the seven Millenium problems. (cf. http://www.claymath.org/millennium/)
<qwertydawom> And, I will let you meditate on this, as this lecture now comes to its end. :)