English 字幕

← 01-07 Case Study


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

  1. Now, a lot of computer science students bristle a little bit when they take an algorithms class,
  2. because of the heavy emphasis on mathematics.
  3. A lot of us got involved in computer science because we really like doing stuff
  4. and not necessarily doing math.
  5. But nevertheless, I think there's a very strong case to be made for the importance
  6. of mathematics in computer science and in algorithm design in particular.
  7. I'd argue that there are three natural ways that theory stuff or math can really help.
  8. One is to just get you thinking clearly about what it is that you're trying to accomplish.
  9. It's very easy when you're in the depths of writing code to lose track
  10. of what it is that you want the code to actually do.
  11. Just thinking formally about what you're doing is something
  12. that using your mathematical background can help with.
  13. Another thing that it can be very helpful with is analyzing the efficiency of what you've produced.
  14. You can actually know where there are spots where you could be doing a better job
  15. and have the code be running more effectively and more efficiently
  16. without producing incorrect code.
  17. Just taking a moment to think a little mathematically can be a huge win
  18. and save you tremendous amounts of time.
  19. It sounds very important, right?
  20. Now, this notion of efficiency is actually very important to think about.
  21. What is it that you want your program to do efficiently.
  22. Do you want it to be fast in terms of time?
  23. Do you want it to be efficient in terms of the amount of memory
  24. on the computer that it uses, so it does its work with as little memory as possible?
  25. These days more and more people are worrying about energy usage.
  26. Are there ways of organizing your computation so that it is efficient
  27. in terms of the amount of power that it uses.
  28. The tools that we develop in this course are going to be useful across the board here,
  29. but we're going to mainly focus on issues of time.
  30. To get you thinking about algorithms and how they work and what makes them correct
  31. and how to make them more efficient, let's go through an example together.
  32. Here is a little bit of Python code that I wrote.
  33. It's a routine called naïve, because I'm not telling you yet what it actually is doing.
  34. What it takes in as input are two integer-valued variables
  35. that are none negative, and then it does some assignments
  36. and recalculations and a while loop.
  37. It runs for a little bit and then it returns z.
  38. What I'd like you to do is take a look at this. It's not very long.
  39. It's probably not completely obvious to you right away what it is that it's doing.
  40. I encourage you to run this in Python.
  41. Give it some example inputs and outputs.
  42. See if you can come up with a pattern for what it is that it's doing,
  43. and then convince yourself why.
  44. Once you have a hypothesis as to what it's doing,
  45. see if you can figure out how you can convince yourself that this program actually
  46. is computing what you think it's computing.
  47. Then I want you to fill out the following quiz.
  48. You can take this code, and you can run it for any particular value of a and b,
  49. but I want you to think about what it does in general as a function of a and b.
  50. When you run naive(a, b) does it return whichever of a or b is the larger one?
  51. Does it calculate a - b, or for that matter, does it calculate b - a?
  52. Does it calculate the sum of a and b?
  53. Does it calculate the product of a and b?