Lec19.

biased random walks:有偏好的随机运动 子类继承Drunk并且修改move的规则但是调用父类的move来实现移动.

polymorphism(多态性):继承的优势

在只能在两个相反的方向上走动的随机模拟时,结果不是像想的那样会在原点附近徘徊(其实和四方向同理),所以说在随机事件中,在一系列的随机之后是很难回到初始的状态的,因为当你向某一方向走动一次之后,你的起点就发生了变化,已经不再是原点而是你现在站的点位.

**图像化:**更好的看到结果并且可以对结果进行可视化的分析来判断结果的正确性

**模拟的优势:**生成一个有代表性的样本来进行测试,可以用来模拟真实的问题,但是又比穷举节省了更多的时间和性能.

• generate a simple of representation scenarios
• experimental devices
• description not prescriptive:optimization,描述性

Lec20.

分析问题的分歧:

• stochastic vs deterministic:确定性问题还是非确定性问题
• static vs dynamic:在动态的情况下时间变得很重要
• discrete vs continues:离散 vs 连续

蒙特卡洛:inferential statistics,推论统计(演绎),random smaple tonds to exhisit same properties as the population from which it is drawn:可以从一些简单的样本看到事物中的共同的地方(共性).

Lec21.

如何选择一个合理的样本对于实验很重要.我们需要知道在选择的样本上进行的实验是否能够很好的模拟问题.
一个答案是统计可靠的并不代表是正确的答案.==>检查答案和物理现实是不是符合

• data
• models that explain data
• consequence of models

直线拟合:

• objective function:目标函数
• least squares fit:最小二乘法

Liner regression:线性回归

• 评估一个拟合:R2
• 并不是越高次的多项式永远是拟合更好的.(过拟合?)
• closer != better:我们不需要一个模型解释已经测量的数据都出现在哪里,而是需要模型有更好的预测能力,能够更好的解释未知的数据.

Lec16.

Class:

• template for data type
• cluster data & method
• modularity/abstraction
• data hiding:only acess the parts though a method
• class used to make instances

Encapsulation:(封装)

• data hide
• inheritance:继承
• shadow/override methods
• hierarchy of classes

Lec17.&Lec18.

• Informal problem description to a formal problem statement:把一个非正式的问题转化到一个更加通用的模型上来
• Inventing computational models:创造计算模型
• dealing with & exploiting randomness:探索随机性
• making sense of data:让数据变得有意义,如何理解数据
• evaluating quality of answers:如何来判断和分析程序给出的答案是不是我们所想要的答案

随机走动:

• simolate(模拟) random walk(无规则运动)
• 数据抽象
  • Location
  • compass Pt
  • Field
  • Drunk
• pseudo random(伪随机)

课程使用的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

import mathimport randomimport pylab

class Location(object):    
    def __init__(self, x, y):        
        self.x = float(x)        
        self.y = float(y)    
    
    def move(self, xc, yc):        
        return Location(self.x + float(xc), self.y+float(yc))    
    
    def getCoords(self):        
        return self.x, self.y    
    
    def getDist(self, other):        
        ox, oy = other.getCoords()        
        xDist = self.x - ox        
        yDist = self.y - oy        
        return math.sqrt(xDist**2 + yDist ** 2)


class CompassPt(object):    
    possibles = ('N', 'S', 'E', 'W')    
    def __init__(self, pt):        
        if pt in self.possibles:            
            self.pt = pt        
        else:            
            raise ValueError('in CompassPt.__init__')    
    
    def move(self, dist):        
        if self.pt == 'N':            
            return (0, dist)        
        elif self.pt == 'S':            
            return (0, -dist)        
        elif self.pt == 'E':            
            return (dist, 0)        
        elif self.pt == 'W':            
            return (-dist, 0)        
        else:            
            raise ValueError('in compassPt.move')


class Field(object):    
    def __init__(self, drunk, loc):        
        self.drunk = drunk        
        self.loc = loc    
        
    def move(self, cp, dist):        
        oldLoc = self.loc        
        xc, yc = cp.move(dist)        
        self.loc = oldLoc.move(xc, yc)    
    
    def getLoc(self):        
        return self.loc    
    
    def getDrunk(self):        
        return self.drunk


class Drunk(object):    
    def __init__(self, name):        
        self.name = name    
    
    def move(self, field, time=1):        
        if field.getDrunk() != self:            
            raise ValueError('Drunk.move called with drunk not in field')        
        for i in range(time):            
            pt = CompassPt(random.choice(CompassPt.possibles))            
            field.move(pt, 1)
    
def performTrial(time, f):    
    start = f.getLoc()    
    distances = [0.0]    
    for t in range(1, time+1):        
        f.getDrunk().move(f)        
        newLoc = f.getLoc()        
        distance = newLoc.getDist(start)        
        distances.append(distance)    
    return distances

# assert False
drunk = Drunk('a man')
for i in range(3):    
    f = Field(drunk, Location(0, 0))    
    distances = performTrial(500, f)    
    pylab.plot(distances)
pylab.title('random walk')
pylab.xlabel('time')
pylab.ylabel('distance from origin')

pylab.show()

assert False

perform trial 的解释:

1. inner loop that simolates 1 trial
2. ‘enclose’ inner loop in a loop that conducts appropriate of trials
3. calculate and present statics

随机运动的应用:

• Browning motion:布朗运动
• stock market:预测股票
• kinetics
• evolution

Lec 13. & Lec14.

**Fibnacci:**在递归的方法来计算Fib的时候有非常多的重复的计算->重复子问题->可以优化
Overlapping subproblems:

• memoization(记忆化):record value 1st time,then look it up subsequently:记录计算的值,在之后的过程中先去查找有没有计算过,如果计算过,就直接使用
• table lookup(查表)

**Optimal substructure(最优子结构):**Global optimal solution can be contructed from optimal solutions to sub-problems:全局最优解可以被分解成每一个子问题的最优解

背包问题:(knapsack)

• decision tree(决策树): ==> 先序遍历 ==> 复杂度O(2**n)(爆炸增长)

  1. 深度左优先树
  2. 回溯
  3. 优化方式==>记忆化:存数组

• 虽然时间和空间复杂度都是O(nS),但是随着n和S的增大,算法的复杂度还是会接近爆炸(伪多项式)

• 背包问题的变种:增加约束条件

总结:

• tarding time for space:基本理念就是空间换时间
• don’t be intimidated by exponential problems
• dynamic problems broadly useful:递归问题往往可以使用动态规划来降低复杂度(比最坏的好)
• problem reduction:要有把复杂问题拆分和简单化的思想(important)

Lec15.

**Module:**collection of related functions

object-oriented programming <==> data abstraction <==> abstract data types

object = collection of data and functions:将数据和操作数据的函数组织在一起(封装,Encapsulation)

Message passing metaphor:隐秘消息传递,在OOP的对象传递中包含了消息传递

**Class:**collection of objects with characteristics in common

• template for creating instances of an object
• instance has some internal attribues