Placeholder Image

字幕列表 影片播放

  • The following content is provided under a Creative

  • Commons license.

  • Your support will help MIT OpenCourseWare

  • continue to offer high quality educational resources for free.

  • To make a donation or to view additional materials

  • from hundreds of MIT courses, visit MIT OpenCourseWare

  • at ocw.mit.edu.

  • JOHN GUTTAG: All right, welcome to the 60002,

  • or if you were in 600, the second half of 600.

  • I'm John Guttag.

  • Let me start with a few administrative things.

  • What's the workload?

  • There are problem sets.

  • They'll all be programming problems

  • much in the style of 60001.

  • And the goal-- really twofold.

  • 60001 problem sets were mostly about you

  • learning to be a programmer.

  • A lot of that carries over.

  • No one learns to be a programmer in half a semester.

  • So a lot of it is to improve your skills,

  • but also there's a lot more, I would say,

  • conceptual, algorithmic material in 60002,

  • and the problem sets are designed

  • to help cement that as well as just

  • to give you programming experience.

  • Finger exercises, small things.

  • If they're taking you more than 15 minutes, let us know.

  • They really shouldn't, and they're generally

  • designed to help you learn a single concept, usually

  • a programming concept.

  • Reading assignments in the textbooks,

  • I've already posted the first reading assignment,

  • and essentially they should provide you a very different

  • take on the same material we're covering

  • in lectures and recitations.

  • We've tried to choose different examples for lectures

  • and from the textbooks for the most part,

  • so you get to see things in two slightly different ways.

  • There'll be a final exam based upon all of the above.

  • All right, prerequisites-- experience

  • writing object-oriented programs in Python, preferably

  • Python 3.5.

  • Familiarity with concepts of computational complexity.

  • You'll see even in today's lecture,

  • we'll be assuming that.

  • Familiarity with some simple algorithms.

  • If you took 60001 or you took the 60001 advanced

  • standing exam, you'll be fine.

  • Odds are you'll be fine anyway, but that's

  • the safest way to do it.

  • So the programming assignments are

  • going to be a bit easier, at least that's

  • what students have reported in the past,

  • because they'll be more focused on the problem to be solved

  • than on the actual programming.

  • The lecture content, more abstract.

  • The lectures will be--

  • and maybe I'm speaking euphemistically--

  • a bit faster paced.

  • So hang on to your seats.

  • And the course is really less about programming

  • and more about dipping your toe into the exotic world of data

  • science.

  • We do want you to hone your programming skills.

  • There'll be a few additional bits of Python.

  • Today, for example, we'll talk about lambda abstraction.

  • Inevitably, some comments about software engineering,

  • how to structure your code, more emphasis in using packages.

  • Hopefully it will go a little bit smoother

  • than in the last problem set in 60001.

  • And finally, it's the old joke about programming

  • that somebody walks up to a taxi driver in New York City

  • and says, "I'm lost.

  • How do I get to Carnegie Hall?"

  • The taxi driver turns to the person

  • and says, "practice, practice, practice."

  • And that's really the only way to learn to program

  • is practice, practice, practice.

  • The main topic of the course is what I think

  • of as computational models.

  • How do we use computation to understand

  • the world in which we live?

  • What is a model?

  • To me I think of it as an experimental device

  • that can help us to either understand something that

  • has happened, to sort of build a model that explains phenomena

  • we see every day, or a model that

  • will allow us to predict the future, something

  • that hasn't happened.

  • So you can think of, for example, a climate change

  • model.

  • We can build models that sort of explain how the climate has

  • changed over the millennia, and then we

  • can build probably a slightly different model

  • that might predict what it will be like in the future.

  • So essentially what's happening is

  • science is moving out of the wet lab and into the computer.

  • Increasingly, I'm sure you all see this--

  • those of you who are science majors--

  • an increasing reliance on computation rather than

  • traditional experimentation.

  • As we'll talk about, traditional experimentation

  • is and will remain important, but now it

  • has to really be supplemented by computation.

  • We'll talk about three kinds of models--

  • optimization models, statistical models, and simulation models.

  • So let's talk first about optimization models.

  • An optimization model is a very simple thing.

  • We start with an objective function that's either

  • to be maximized or minimized.

  • So for, example, if I'm going from New York to Boston,

  • I might want to find a route by car or plane

  • or train that minimizes the total travel time.

  • So my objective function would be

  • the number of minutes spent in transit getting from a to b.

  • We then often have to layer on top of that objective function

  • a set of constraints, sometimes empty, that we have to obey.

  • So maybe the fastest way to get from New York to Boston

  • is to take a plane, but I only have $100 to spend.

  • So that option is off the table.

  • So I have the constraints there on the amount

  • of money I can spend.

  • Or maybe I have to be in Boston before 5:00 PM

  • and while the bus would get me there for $15,

  • it won't get me there before 5:00.

  • And so maybe what I'm left with is driving,

  • something like that.

  • So objective function, something you're either

  • minimizing or maximizing, and a set of constraints

  • that eliminate some solutions.

  • And as we'll see, there's an asymmetry here.

  • We handle these two things differently.

  • We use these things all the time.

  • I commute to work using Waze, which essentially is solving--

  • not very well, I believe-- an optimization problem

  • to minimize my time from home to here.

  • When you travel, maybe you log into various advisory programs

  • that try and optimize things for you.

  • They're all over the place.

  • Today you really can't avoid using optimization algorithm

  • as you get through life.

  • Pretty abstract.

  • Let's talk about a specific optimization problem

  • called the knapsack problem.

  • The first time I talked about the knapsack problem

  • I neglected to show a picture of a knapsack,

  • and I was 10 minutes into it before I

  • realized most of the class had no idea what a knapsack was.

  • It's what we old people used to call a backpack,

  • and they used to look more like that than they look today.

  • So the knapsack problem involves--

  • usually it's told in terms of a burglar who breaks into a house

  • and wants to steal a bunch of stuff

  • but has a knapsack that will only

  • hold a finite amount of stuff that he or she wishes to steal.

  • And so the burglar has to solve the optimization problem

  • of stealing the stuff with the most value while obeying

  • the constraint that it all has to fit in the knapsack.

  • So we have an objective function.

  • I'll get the most for this when I fence it.

  • And a constraint, it has to fit in my backpack.

  • And you can guess which of these might be

  • the most valuable items here.

  • So here is in words, written words what I just said orally.

  • There's more stuff than you can carry,

  • and you have to choose which stuff to take

  • and which to leave behind.

  • I should point out that there are two variants of it.

  • There's the 0/1 knapsack problem and the continuous.

  • The 0/1 would be illustrated by something like this.