пожалуйста, возвращайтесь позднее
пожалуйста, возвращайтесь позднее
Welcome to this first course in the design and analysis of algorithms. I mentioned many of you are already clear on your reasons for taking this course, but let me begin by justifying the course's existence and giving you several different motivations for learning about algorithms. So what is an algorithm? Well, we're not going to be needing a precise definition in this course, but essentially, an algorithm is a well defined set of rules. A recipe in effect for solving some kind of computational problem. So for example, maybe you're given a bunch of numbers and you want to rearrange them into sorted order. Maybe you're given a road network with an origin and a destination and you want to compute the shortest path from point A to point B. Maybe you're given a bunch of tasks with deadlines and you want to know whether or not it's feasible to accomplish all of those tasks by the respective deadlines. So, why study algorithms. Well first of all, understanding the field of algorithms and also the related field of data structures, is crucial for doing serious work in pretty much any other branch of computer science. That's the precise reason why, here at Stanford University, this is the course that's required for all of the degrees that the computer science department grants. Be it at bachelors, a masters, or PHD degree, we insist that you have mastery of the field of algorithms. So what are some examples of uses in the rest of computer science. Well, if your doing routing in a communication network, that piggybacks on classical shortest path algorithms. The effectiveness. The public key photography really rests on that, of number theoretic algorithms. In safe computer graphics, you need to [inaudible] primitives. They're supplying those study of geometric algorithms. Data base industries rely on balance search [inaudible] data structures as covered in this course. [inaudible] Biology using dynamic programming algorithms to measure similarity among genomes. And the list goes on and on. A second reason to study algorithms is that they play a key role in modern technological innovation. Obviously, I could give any number of examples here, and let me just state one super obvious one. Which is that search engines use a tapestry of algorithms to efficiently compute the relevance of various webpages. The most famous such algorithm which you may have heard of is the PageRank algorithm, in use by Google. Indeed. In a December, 2010 report to the United States White House, the President Council of Advisors on Science and Technology argued that, in many areas, performance gains due to improvement in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed, as you'd be familiar with in the form of [inaudible]Law. Third, although this is getting significantly outside the scope of this course, algorithms are increasingly being used to provide a novel lense on processes outside of computer science and technology. For example, the study of quantum computation has provided a new and computational view point on quantum mechanics. Price fluctuations in economic markets can be fruitfully viewed as an algorithmic process. And even evolution can be usefully thought of as a surprisingly effective search algorithm. The last two reasons I'm gonna give you might sound a little flippant, but, I think there's more than a grain of truth to both of them. Now, I don't know about you, but back when I was a student my favorite classes were always challenging classes.