MIT计算机科学及编程导论笔记_Introduction to Computer Science and Programing Note

1.Goal of the course;what is computation;introduction to data types,operators,and variables
what is knowledge?
I can divide knowledge into at least two categories.
are declarative and imperative knowledge.
So,any place it’s legal to use the value.

2.Operators and operands statements;branching,conditionals,and iteration

a branching program is something that can change the order of instructions based on some test

3.Common code patterns:iterative programs

you’d like to be able to assrue yourself that they will always terminate,and then the second thing you’d like to do,is to assure yourself that it does give you back a reasonable answer.
4.Decomposition and abstraction through functions;introcuction to recursion
the key of the function is that it’s going to provide both of these.
it’s going to let us break up into modules.
suppress detail.
it is to create new primitives.and i’m going to put those in quotes,it’s a generalization.
The idea of a function is,that i’m going to capture a common pattern of computation.

These local bingdings do not affect any global bindings.

The idea of recursion is that I’m going to take a problem and break it down into a simpler version of the same problem plus some steps

Pairs(0) = 1;
Pairs(1) = 1;
Pairs(n) = Pairs(n-1) + Pairs(n-2);

5.Floating point numbers,successive refinement,finding roots
when we represent something,the mantissa is between one and two.Strictly less than two.
The exponent,is in the range,-1022 to +1023
So this lets us represent numbers up to about 10 to the 308th,plus or minus to the 308th,plus or minus.
the words today in a modern computer are 64 bits
we get one bit for the sign is it a positive or negative number 11 for the exponent,and that leaves 52 for the mantissa

有些10进制的数如1/10 ,在转变为二进制的时候会无限循环下去

So on most computers,if you were to print the decimal value of the binary approximation

对于浮点数 计算机截至第17位数
for floats,it rounds it to seventeen digits

warry about == on floats
that each guess is better than the previous guess
This is what’s called successive approximation
which would be the initial guess,you then iterate

Bisection method二分法
because I am getting logarithmically progressed

6.Bisection methods,Newton/Raphson,introduction to lists

we are looking a equation f of guess equals the guess squared minus x.

and we trying to solving the equation that f of guess equals 0.Looking for the root of this equation.

F(guess) = guess^2 -x;

You take a guess and you find the tangent of that guess.

My next guess is going to be where the tangent crosses the x axis.

This is where derivatives come in.

What we know is that the slope of the tangent is given by the first derivative of the function f at the point of the guess.Which dy over dx.

guess(i+1) = guess(i) -F(guess(i))/2*guess(i);

we’ll know that we can choose guess i plus 1 to be equal to the old guess guess i,minus whatever the value is of the new guess–of the old rather the old guess– divided by twice the old guess.

F(3) = 9 -16 = -7;
guess(i+1) = 3 -(-7/6) = 4.1666

7.Lists and mutability,dictionaries,pseudocode,introduction to efficiency

order of grows
-choice of algorithm
-map problem into class of algorithms

8.Complexity; log,linear,quadratic,exponential algorithms

Rate of growth as the size of the problem grows.
If it was,how much bigger does this get
Big Oh notation - is basically going to be an upper limit to the growth of a function as the input grow–as the input gets large.

ab = (a*a)(b/2) b even;
= a(a**(b-1)) b odd;
ef exp3(a,b):
if b==1:
return a;
2 == b:
return exp3(aa , b/2);
else: return a
b even t(b) = 6 + (b/2);
b odd t(b) = 6 + (b-1) = 12 + t((b-1)/2)

t(b) = 12 + (b/2);

k=log2 b;
In the b even case, again i’m going to let t of b be the number of steps I want to go through.
if b is eqaul to 1,and then I’ve got to do the remainder(求余数),the multiplication,and the test,i’m up to four.

And then in the even case I’ve got to do a square(求平方) and the divide.
So i’ve got six steps
log,Linear ,quadratic,exponential algorithm

9.Binary search,bubble and selection sorts

但如果我们用的是保存列表的列表呢?如果列表存储的不同的东西 比如存储的是整数 字符串 浮点数 列表 列表的列表 列表的列表的列表 或者其他各种东西呢?
if i know that i have things stored in constant size.But what if i have a list of lists?What if i have a homogeneous list,a list of integers and strings and floats and lists and lists of lists and lists of lists of lists
So in this case,one of the standard ways to use linked list
Start again,we’ll point to the beginning of the list.
在第一点,我们存下一个元素的地址偏移量,然后 用之后连续的几个单元表示第一个元素 如果你喜欢也可以说是第0个元素.在这里 我可能需要五个内存单元在下一个位置中 存放需要多大的内存偏移量跳转到下一个元素然后无论你想存放什么都可以放在接下来的单元中 可能只是些空格

in the first spot,I am going to store something that says,here’s how far you have to jump to get to the next element.And then,I am going to use the next sequence of things to represent the first element,or the zero-th element,if you like.In this case I might need five.And then in the next spot,I am going to say how far you have to jump to get to the next element.All right,followed by whatever i need to represent it,which might only be a blank one.And in the next spot,maybe I’ve got a really long list

here is the problem.How do i get to the nth er,the k’th element in the list,in this case?
Well i have to go to the zero-th element,and say OK,gee,to get to the next element,I’ve got to jump this here.And to get to the next element,I’ve got to jump to here,and to get to the next element,I’ve got to jump to here,until i get there.
primarily Lisp.
盒状指南针每个元素实际上由两部分组成这里我们颠倒了顺序 这里有指针指向内存包含实际值的地址 可能实际值也是一系列指针 这里还有指向实际指向下一个元素的指针
Python store list, it is called a box pointer diagram,what we really have for each element is two things.And i’ve actually just reversed the order here.we have a pointer to the location in memory that contains the actual value,which itself might be a bunch of pointers,and we have a pointer to the actual a pointer the value and we have a pointer

I am just going to take an unsorted list and search it,i cound do it in linear time,right?One at a time.Walk down the elements until i find it.That wound be order n.
另一种方法,先排序再搜索,需要花nlog n时间排序,然后花log n时间搜索
On the other hand,sort it first,and search.take n logn time to sort it,then i can search it in log n time.

amortize the cost.
Linear sort + search
kn nlog n + klog n

bubbule sort
我遍历一次列表 每次取两个值 确认最大的元素在后面一个
I’m walking along the list once,taking two things,and saying, make sure the biggest one is next.

所以无论最大的元素在列表的什么位置 跑完了一遍 它总是在最下面 然后我回来再做一次,下一个最大元素又能跑到倒数第二的位置.
So wherever the largest element started out in the list,by the time i get through it,it’s at the end.And then i go back and i start again,and i do the same thing.The next largest element has to end up in the second last spot.

divide and conquer algorithm

10. Divide and conquer methods,merge sort,exceptions

merge sort

所以我在树的每个层次都要做O(n)的操作,因为在每一层 我都是把问题分解成两半,以n开始 然后是n/2 n/4 n/8 所以我log n遍的n次操作
have order n operations at each level in the tree.And then we have Log n level,Beacause at each stage i cute problem in half.So i start off with n then it’s n over two n over four n over eight.So i have n operations log n times, n log n

Trade space for time 用空间换时间

11. Testing and Debugging

progress to uncover problem and increase confidence.
So we need to have a method not designed to give us unwarranted confidence.

是两件事情的组合 测试和推理
It’s typically a combination of two things.Testing and reasoning.
测试就是 我们输入一些信息并且运行我们的程序 然后查看答案
Testing we run our program on some set of inputs.And check the answers,and say yeah

And that’s basically the process of ascertaining why the program is not working.

Defensive programming.防卫性程序设计

And that’s basically writing your programs in such a way that it will facilitate both validation and dubugging.

what must this experiment have the potential to do,to be a valid scientific experiment?
It must have the potential to refute the hypothesis.

12. More about debugging,knapsack problem,introduction to dynamic programming

first,keep in mind that the bug is probably not where you think it is.

simple things you can care:

Reversed order of arguments.


Object versus value equality.

Aliasing deep vs shallow capy.

Keep record of what you tried.

Think about reconsidering your assumptions.

Bin packing

sequence alignment

Knapsack problem 背包问题

Continuous problem 连续问题
4/bs Au dust
3/bs Ag dust
10/bs Raisins

function is cost value of gold times how many pounds of gold.Plus the cost of silver times however many pounds of silver.Plus cost of raisins times the number of pounds of raisins.
maximize the function Cg PG + Cs PS + Cr * PR

the constraint is PG + PS + PR <=8
Greedy algorithm
at every step you do what maximizes your value at that step.So there’s no planning ahead.You just do what is ever best.

Locally optinal not always lead to global optimums.

zero-one knapsack problem 0/1 背包问题
exhaustive enumeration 穷举法

E(n ,i = 1) W i X i <= C

Dynamic programming

there are overlapping sub-problems and what’s called optimal substructrue.

redundant computation 累赘计算

13.Dynamic programming: overlapping subproblems,optimal substructure

Overlapping subproblems 重叠子问题
we record a value the first time it’s computed,then look it up the subsequent times we need it.

And this is what lies at the heart of this very general technique called dynamic programming.

实际上 它也是很多保存结果的计算技巧的核心
And in fact,it lies at the heart of a lot of useful computational techniques where we save results.

Decision Tree 决策树
Back track

14.Analysis of knapsack problem,introduction to object-oriented programming

Size of solution
how long it takes to run is related to how many items i end up being able to fit into the knapsack.
So the number of items i have to remember is related to how many items i can fit in the Knapsack.

so we’d much rather define big O in terms of the inputs.

通常我们查看计算复杂度O的时候 我们会把它定义为实现输入的代码的大小
computational complexity,big O,what we’ll define the in terms of,is the size of the coding of the input.
size of coding of input

Pseudo polynomial algorithm 伪多项式

polynomial in the numeric value of input

In dynamic programming, one of the things that’s going on is we’re trading time for space.

2. 不要被指数型问题吓到
Two,don’t be intimidated by exponential problems.

3. 动态编程有广泛的应用,每当你在处理一个看上去有自然而然的递归算法的时候

Dynamic programming is broadly useful.Whenever you’re looking at a problem that seems to have a natural recursive solution,think about whether you can attact it with dynamic programming.

4. 减少问题 problem reduction

Module (modularity)
what i want to be talking about is modules of one sort,and of course that’s because what we’re interested in is modularity.

Now i think of a module as a collection of related functions.

我们将要通过圆点标记法来使用函数( . )
and we’re going to refer to the functions using dot notation.

a particular kind of module,and those are the modules that include classes or that are classes.

In this subject we’re going to emphasize using classes in the context of what’s called object-oriented programming.

data abstractions
Abstract data type

An object is a collection of data and functions.
The key idea here is to bind together the data and the functions that operate on that data as a single thing.

user defind types
This combining of data and functions on that data is a very essence of object-oriented programming.

we also call it encapsulation 封装

消息传递 传递隐喻的消息
we talk about it in terms of message pass, a message passing metaphor.

one object can pass a message to another object and the receiving object responds by executing one of its methods on the object.

这个对象传递一个消息sort 这个消息让我们去找sort方案,然后应用到对象I
pass the object I the message sort,and that message says find the method sort,and apply it to the object I.

notion of an instance.
A class is a collection of objects with characteristics in common.

and extend the language.

15.Abstract data types,classes and methods

Class ,a template for creating instances of an object.

shallow equality and deep equality.

The first thing is testing shallow equality.
is essentially saying,given 2 things,do they point to exactly the same referent?
is saying,do these things point to exactly the same spot in memory.

that’s going to let us build versions of these things.

There’s this weird extra variable in there called self.

When i create a instance,i have to be able to get access to the things that characterize that instance.
what characterizes an instance here,it’s the internal parameters that specify what is going on.

init –when we call it, create an instance
–use “self” to refer to that instance

Init create a pointer to the instance.

And then it needs to have access to that,so it calls it passing in self as the pointer to the instance.

init这个方法可以去访问内存中的这一块了 然后在这块内存里面
it says it has access to that piece in memory,and now inside of that piece of memory

self will always point to the particular instance.
same other programming languages do not provide that pointer.

Methods - can access values of the specific instance.

Data hiding

  • one can only access instance values through defined methods.

python doesnot do this

str - printed representation,it converts things into a string type.代表打印,将东西转为字符串格式.

cmp - doing comparisons.

Operate overloading

Instance (

  • methods
  • fields

associated with an instance,we have both methods and fields.these are both called attributes of the instance.


just trying to cluster data together.And this is a notion of modularity slash abstraction,where i’m treating them as primitives.

Class is used to make instances,meaning particular versions,of that structure

when we called the class definition,person,it create an instance,there it is.

Thinkd of it as a pointer to a spot in memory,and then what we do is,then we call,or find that init method.

And the first argument self,points to the instance.

17.Computational models:random walk simulation

Dealing with & exploiting randomness

随机指标 它们包含了一些随机性
Stochastic they incorporate randomness.

Making sense of data

当我们在 再说一次 在对世界进行建模 我们发现里面有大量的数据
As we look at,again,modeling the world,what we discover,there’s a lot of data out there

Evalvating quality of answers

Start Simple

So start with some simple approximation to the real problem.

我会去假设 就像我们之前做的一样 我们有一个笛卡尔坐标系,玩家是站在一片像坐标纸一样的场地上
And I’m going to assume,as we’ve seen before,that we have Cartesian coordinates and that the player is standing on a field that has been cut to resemble a piece of graph paper.

只能选择四个方向中的一个:北 南 东或西
only go in one of four directions: north, south, east, or west.

student is here and takes a step in one direction or another.without loss of generality

three times out of four you get further away.

Simulate random walk

模拟 也就是我们去尝试着建立一个假扮成真实世界的模型然后模拟一些东西
Simulation where we try build the model that pretends it’s the real world and simulates what goes on,and a random walk.

Trying to give you a case study

Thinking about what might be the appropriate data abstractions.


Compass point



罗经点的数据抽象来代表这个学生会朝北 南 东 西 四个方向走
compass point to capture the notion that the student is going north,south,east,or west.

separate the notion of direction

So think of that as the whole Cartesian plain,as opposed to a point in the plane,which is what the location is.
since after all the whole problem talks about where the drunk is.

pseudo random

18.Presenting simulation results,Pylab,plotting

1) we start with an inner loop that simulates one trail.

2)And then i’ll quoto,enclose,unquote the inner loop in another loop that conducts an appropriate number of trials.

3)Calculate and present some relevant statistics about the trials.

19.Biased random walks,distributions


Polymorphism 多态性

Generate a sample of representative scenarios.

Because an exhaustive enumeration of all possible states would be impossible.

you can exhaustively enumerate the space and then see what’s going on.

Experimental device

I’m running an experiment designed to give me some information about the real world.

they are typically descriptive not presciptive.

they describe a situation,they don’t tell you what the answer is.

a simulation is not an optimization procedure.When we looked at optimization,that was prescriptive.We ran an optimization algorithm,and it gives us the best possible solution.

20.Monte Carlo simulations,estimating pi

classify simulation models.
it’s stochastic or deterministic

static vs dynamic time

A third dichotomy is discrete vs continuous.

21.Validating simulation results,curve fitting,linear regression

How many samples?
How accurate?
Biased sample

Models that explain data
Consequences that follow from the models

Whenever we try and fit something,We need some sort of an objective function.

Least squares fit

It turns out that for this particular optimization,there’s something more efficient.

there is a closed form way of attacting this

Linear regression

the relationship of the dependent variable y to the independent variables is assumed to be a linar function of the parameters.

R2 - coefficient of determination

R2 = 1 - EE/Dr

It’s attempting to capture the proportion of the response variation explained by the variables in the model.

So you’ll have some amount of variation that is explained by changing the values of the variables

我有一些预测数据 如果你愿意
So e e is going to be the errors in the estimation.

r2 = 0.9

approximately 90 percent of the variation in the variables can be explained by the model.

lurking variable