MisakaTang's Blog

发表于 更新于 分类于

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

发表于 更新于 分类于

Lec10.

Search

  • ordered - binary - log n
  • unordered - liner - n

Divide & conquer(分治)

  • split the problem into several sub-problem of the same type
  • solve independently
  • combine solutions

MergeSort(归并排序)

  • divide list in half.
  • continue until we have single lists.
  • merge of the sublists

复杂度:n(每一次要操作的数的个数)logn(归并的次数)
适用的场合:要归并的元素不是很复杂而且归并的操作简单

Hashing:

  • 牺牲空间来换取时间效率
  • hard to create(需要寻找一个好的哈希函数)

Python语法.Exception:

  • unhandle
  • handle:捕获可以预期的异常并且处理.

Exception vs Assert

  • 断言是一种测试,保证断言的语句为真才能继续执行下去
  • 异常保证程序在出现预期的出错的时候可以处理它

使用异常的原因:为了保证在异常出现的时候可以正确的捕获和处理它,而不是使得异常向别的地方抛出并且扩散,使得错误无法正确的定位(难以Debug).

Lec11.

Testing && Debugging:

Validation:(验证过程)

  • process to uncover problems & inciease confidence
  • Testing & Reasoning

Debugging:

  • process of ascertaining why program failing
  • function(程序是否按照希望的那样完成了操作) & performance(为什么程序运行的效率低)

Defensive programing:(防卫性程序)

  • abet validation & debugging
  • 使用断言(assert)来尽早发现程序中的问题,给模块添加注释和说明

Testing:

  • examine input/output pairs
  • Unit testing:单独测试程序中的每个部分:
    • Functions classes
  • integration testing(集成测试):把整个程序组合起来看能否正常运行
    • overall program

在做集成测试之前要对每个单元先做单元测试保证其正确.

Test suite(测试集):

  • small enough:保证可以运行完测试集中的数据
  • large enough:保证我们对程序有足够的信心

Myth:

  1. bugs crawl into programs
  2. bugs breed into programs(bug不会繁殖)

Goal: Not to eliminate one bug, is to move towards a bug-free program:不只是要去消除一个bug,而是要让程序中没有bug出现(消除一个bug做的不好,会带入更多的bug).

最好的debug工具:

  • print statement
  • reading,阅读代码是最重要的debug技能
  • be systematic:形成系统化的调试
  • reduce search space(缩减问题的空间来定位问题)
    • localize source of problem

如何形成系统化的测试?

  • study program text
    • how could it have produced this result(阅读代码并且搞清楚程序为什么会产生这个结果)
    • is it part of family:是不是在整个系统中重复犯了同一个错误,然后一次性修复一系列相同的问题
    • how to fix it?
  • scientific method
    • study avaliable data:test results(所有的测试结果),program test
    • form hypothesis
    • design & run repeatable experiment
    • refute hypothesis
    • useful intermediate results
    • expected result(自己对实验的预期结果)

设计一个好的测试:

  • find simplest input:找到最简单的输入并且在程序中缩小问题的范围然后定位
  • binary search:如果每次能排除掉一半的数据或者代码,定位问题的速度就会很快

Lec12.

调试的一些技巧(习惯):

  • 参数的顺序问题
  • 拼写
  • 初始化变量
  • object vs value equality
  • aliasing: deep vs shallow copy
  • side-effects:副作用
  • Keep record of what you tried:记录你做过的操作
  • Reconsider assumption:重新思考你的猜测
  • Debug code, not comments
  • Get help, explain:向别人获取帮助,并且向别人解释你这段程序的作用
  • walk away
  • haste makes waste:欲速则不达,在修改之前好好考虑清楚修改引起的变化
  • code should not always grow:不能依靠增加代码的方式来修复bug
  • make sure that you can revert:确保你可以还原你的代码,如果修改失败,最起码可以回到问题的起点重新开始.

optimization problem:(最优化问题)

  • a function to maximize(min):最大化或者最小化一个函数
  • a set of constraints(一系列的约束条件)

经典的最优化问题:

  1. 最短路
  2. 旅行商问题(TSP)
  3. bin packing(装箱问题)
  4. sequence alignment(序列调整)
  5. Knapsack(背包问题)
  6. problem reduction(问题约束):把新的问题规约到老的问题上,解决它

continuous knapsack(连续背包):->Greedy algorithm:每一步都选择最优的策略,但是局部最优叠加并不一定导致全局的最优

0/1 knapsack(01背包):
最大化的函数:sum(i=1,n)=Pi*Xi
约束条件:sum(i=1,n)=Wi*Xi <= C
对于暴力来说复杂度是指数级增长,不适用于这个问题

dynamic programming:(动态规划)

  • overlapping sub-problems(重叠子问题)
  • optimal sub-structure(最优子结构)

从求Fibnacci序列来看什么是重叠子问题:fib(0),fib(1),fib(2)…都被重复计算==>重叠子问题

0%