English 字幕

← 01-06 Algorithms Are Cool


Showing Revision 1 created 06/27/2012 by Amara Bot.

  1. Now, what I've shown you so far is not really an algorithm,
  2. but it has some elements in common with them.
  3. Algorithms are really cool. That's what the focus of this class is about.
  4. One of the reasons algorithms are cool is that they're really useful.
  5. Without careful algorithm design we just don't see fast enough responses from
  6. things like websites and user interfaces--stuff that we really depend on
  7. to be able to have the computers react quickly.
  8. Another is that they're really clever. They're really pretty, mathematically.
  9. Just like a magic trick, sometimes learning how it does what it does
  10. can be just as exciting as what it actually does accomplishes.
  11. The practical part of algorithm design is trying to figure out how to make your programs fly--
  12. that is to say, go really, really fast.
  13. There are a couple different ways that you can do this when you're programming.
  14. One, you should take a great deal of care in organizing your programs
  15. so that they're not doing a lot of wasteful stuff.
  16. That goes without saying, but I said it anyway.
  17. There's a lot of time that you can spend tweaking loops and other things in your program
  18. to just get rid of little bits and pieces of inefficiency, and that's important.
  19. But perhaps the most important thing is good algorithm design.
  20. Whenever your program is doing something that involves a great deal of computation
  21. you need to think hard about how to organize that computation
  22. so it does what you want it to do, but it does it fast.
  23. That's the focus of this course.
  24. We can think of the problem of developing algorithms for particular problems
  25. as a kind of algorithm itself.
  26. Here I've written it as kind of faux Python. You can't actually run this.
  27. I would not suggest running this, but it should give you a sense of the flow here.
  28. What we start off with is some kind of problem specification.
  29. We'll talk about a couple different examples of those over the course of the course.
  30. For the problems specification we're currently concerned with,
  31. what we're going to do is we're going to start off devising an algorithm for that problem.
  32. That mean thinking about it, coming up with some kind of strategy or plan
  33. for doing the computation. We'll call that our algorithm.
  34. They're not really done yet. We need to make sure that this algorithm is actually correct.
  35. The first thing that we want to do when we propose an algorithm
  36. is actually analyze the correctness with respect to the problem specification
  37. to see if it actually accomplishes what the problem says you're supposed to accomplish.
  38. Sometimes that is kind of obvious and straightforward.
  39. Sometimes that involves a fair amount of mathematical analysis.
  40. We'll see different examples of those as we go.
  41. Once we've analyzed our algorithm to make sure that it's correct,
  42. we can analyze it's efficiency.
  43. It does what it's supposed to do, but does it to it fast enough?
  44. We eventually determine the running time of the algorithm.
  45. If it's not correct or if it's not fast enough,
  46. then we need to continue this process, redevise an algorithm, and reanalyze it,
  47. and keep doing this until we have something that both solves the problem
  48. and solves it fast enough.
  49. That's the algorithm that we declare to be our solution.