PPT《*》

06 * */74 * */74 Algorithms. S. Dasgupta, C.H. Papadimitriou, and U. V. Vazirani. May 2006.Combinatorial Algorithms. Jeff Erickson. University of Illinois, Urbana-Champaign. Lecture Notes. Fall 2002. Concrete Mathematics. Ronald L. Graham, Donald E. Knuth, Oren Patashnik. Addison-Wesley Publishing Company, 2005. ISBN: o-201-14236-8. 参考教材 * */74 Algorithms in Computer Science P = NP ?Can we solve a problem efficiently?Tradeoff between quality of solution and the running timeSolve a problem with optimal solution, but it might cost long timeSolve a problem approximately in short time * */74 $1,000,000 problem P = NP ? http://www.claymath.org/millennium/Solved???!!!! Algorithms in Computer Science Selfish RoutingPrivacy preserve in databaseTSPAd auction * */74 * */74 Perspective Algorithms we can find everywhere They have been developed to easy our daily life Train/Airplane timetable schedule Routing We live in the age of information Text, numbers, images, video, audio * */74 Selfish routing Pigou'

s Example Suburb s, a nearby train station t. Assuming that all drivers aim to minimize the driving time from s to t s t C(x) =

1 C(x) = x, with x in [0, 1] * */74 Selfish routing We have good reason to expect all traffic to follow the lower roadSocial optimal? ? to the long, wide highway, ? to the lower road. selfish behavior need not produce a socially optimal outcome * */74 Braess'

s Paradox s v w t C(x) =

1 C(x) = x C(x) =

1 C(x) = x * */74 Braess'

s Paradox s v w t C(x) =

1 C(x) = x C(x) =

1 C(x) = x C(x) =

0 * */74 Braess'

s Paradox Paradox thus shows that the intuitively helpful action of adding a new zero-cost li........