Lec7

Python数组:

解释: L2 = L1 ==> 创建了一个L2和L1进行绑定,事实是L1和L2绑定了同一个对象,所以在通过L1改变了该对象的时候,L2也会发生变化,其实不是L1,L2的变化而是他们共同绑定的对象的变化.
Dictionaries(字典):

  • mutable
  • not ordered
  • generalized indexing

Pseudo code(伪代码):利用伪代码来控制程序流,拆分模块以及搞清对数据的操作

模块性和封装:不需要关心内部的具体实现,只需要调用就可以

efficiency-orders of growth(算法复杂度,运行效率):

  • 为什么我们需要考虑效率:因为问题的复杂度的增长速度远比计算机的发展更快
  • choice of algorithm:在遇到问题时,能够选择现有的算法并使得解决问题的效率加快
  • map problem into class of algorithm:将问题映射到一类算法

Space & Time:

  • how much memory to complete
  • what is it of basic steps needed as a function of the input size

Random access model:假定我们在读取任意一块内存区域的时候花费的时间是恒定的(理想状态)

  • best case -> Min
  • worst case -> Max
  • expected case -> Avg

Lec8

例子 整数a的b次幂的计算:

Iterative exponent:

1
2
3
4
5
6
def exp1(a,b):    
ans = 1
while (b>0):
ans += a
b -= 1
return ans

总共进行了2+3b步
O(b) -> liner

复杂度增长:

  • Asymototic notation
  • Big O notation - upper limit to growth

Recursive exponent:

1
2
3
4
5
def exp2(a,b):    
if b == 1:
return a
else:
return a*exp2(a,b-1)

分析递归式程序的复杂度:

1
2
3
4
t(b) = 3 + t(b-1)     
= 3 + 3 + t(b-2)
= 3*k + t(b-k)
Done b-k = 1

==> O(b)

二分:

1
2
a ** b = (a*a) ** (b/2) -> b even       
= a*(a**(b-1)) -> b odd
1
2
3
4
5
6
7
def exp3(a,b):    
if b == 1:
return a
if (b%2)*2 == b:
return exp3(a*a, b/2)
else:
return a*exp3(a,b-1)

==> O(log b)

1
2
3
4
5
b even t(b) = 6+t(b/2)
b odd t(b) = 6+t(b-1)
==>t(b) = 12 + t(b/2)
= 12k + t(b/2**k)
k = log2(b)

汉诺塔:

  • 经典的递归
  • O(2**n) -> 指数爆炸

Lec9

二分查找算法:
思想:

  • 1.确定first, last, mid=(first+last)/2
  • 2.判断如果mid是要找的值==>找到,否==>小于找左边,大于找右边
  • 3.mid=first || mid=last goto 1

缺点: 列表(list)不能用二分查找(效率低,复杂度变成线性复杂度)

Generalize:

  1. pick the mind point
  2. check to see if this is answer
  3. if not, reduce to smaller problem.Repeat

Question:

  • should we sort before search? ==>
    liner search n || sort & search nlogn+logn
  • can we sort in sub-liner time? - No
  • how fast can we sort? — nlogn

Amortize the cost:(平摊花费),如果只搜索一次的话,liner search效率更高,如果搜索多次的话,那么先排序就会体现优势在平摊了排序的花费,而查找的效率是logn.

排序算法

  • 选择排序 循环不变量:数组被分成2部分,pre和suff,前部分在排序中是有序的部分,每次只对后部分进行排序到有序为止.
  • 冒泡排序

前言

许久未写博客,最近将环境迁移到linux之后在看课程的时候想要记一点笔记,就拾起了Markdown,在尝试了各种的Markdown编辑器都不是很称心之后又想起了自己的博客,就打算着把博客重用起来顺便拿来保存笔记也是个不错的想法,但又想着只用来记笔记有点浪费就想着写一些杂事在上面,正好最近开始了一个Group的讨论,在看完之后又冒出了很多的想法和讨论,就有了这篇杂想.

由一篇博客说起

本文是由对于代码之谜(一)- 有限与无限的讨论所引起的一些想法的记录,在博客中作者提出了一个问题: 负数的绝对值可能等于自己吗? 当然既然作者提出了这个问题,肯定不能轻易的说不或者是了,

我要告诉你方法,而不是答案

在看完之后当然会有一种恍然大悟的感觉,但是所依据的概念和方法又是如此的简单:计算机数的表示,而最小的负数的反码和补码相同这个结论的得出也是自然而然的,但是在没有人提问的情况下,却很难把这二者结合在一起来看.

有限和无限

这篇文章的标题中便提到了这个关键词:有限和无限,作者在文中也抛出了关于在经典数学中的绝对值的定义:

从原点到点A的距离,称为A的绝对值,它是一个非负数

在下面的讨论中,看到了一个能与之对应的关于计算机的绝对值的理解:

其实这整数可以理解成是一个环,取绝对值可以看成把这个环压扁,把其中两面的数都映射到正数的那一面上

很有意思不是吗,我记得在大一的导论课上,我也在书本上看到过类似的图片,一个由数字构成的环,从0开始到8结束又回到了0,当时的图片是为了说明计算机的数字这一个概念,和这个解释如此的一致,我们现在当然可以想当然的说:计算机中的数字是有限的,而数学中的数字是无限的,从而结束这一个讨论,但是为什么从一开始进入计算机的世界的时候,就被人告知,计算机的数字表示是有限的,但是在实际的coding中,我们却自然而然的把计算机的世界和数学世界等同起来.

计算机这个上帝

这个话题是由最近在看的MIT的CS入门课上,教授在讲到关于浮点数的精度的时候提到的,他说:

我们在计算机的世界中创造事物,甚至把计算机(解释器)当成了上帝,想当然的以为他是对的,然后在其之上工作,但是我们不应该仔细想想:为什么他是对的

似乎就像是一场哲学思辨一样,我们似乎也进入了计算机的哲学世界,开始考虑这个上帝,他真的如我们所想一样吗,还是说,我们所想的上帝和真实存在的上帝是不一致的呢?我更倾向于后者,所以这也使我在很多原本自己为的不容置喙的事情上开始了一些思考,我的代码这么写一定是对的吗?为什么是对的呢?我想这就是MIT的教授和这篇博客所要传达给我们的一些理念,仔细想想为什么.在不断的质疑的过程中不断的重塑自己的知识体系和对计算机的认识,似乎就和科学的发展一样,在不断的质疑,提出观点和继续的质疑中才能得到不断的进步.

有限和无限

这当然不是上面的标题的重复(当然也算是),我想来讨论的是计算机所处的有限的世界和数学所代表的无限的世界的不统一之处,当然人类在数学上从有限走向无限也花费了很多的时间,但是计算机作为(可能吧)数学发展比较成熟的时期的产物,却没有获得在抽象层面上的优雅,当然这是因为物理世界的限制,也可能是人类认知上的限制,所以我们似乎也有理由来幻想这样的计算机,像数学一样可以走向无穷和抽象.

(似乎有点扯远)这里讲的有限和无限似乎更像是一种程序员的方法论(或者说计算机观)和现实世界的一种冲突,在讨论中无限和有限也确实有很多可以深究的地方,但是我们确实还做不到用计算机来讨论无穷小,无穷大之类的有很高的抽象层面的东西(我们只能用更高的精度来模拟:exp),所以似乎计算机或是程序员,在用代码也好解释器也好这样有限的东西来对抗物理世界中的无限的数据或者对象,在大数据的今天更甚(似乎在今天已经离不开大数据这个词了,虽然我个人比较抵触,但是这里还是用了一下).我眼前似乎展现了这么一副景象:程序员就如同斯巴达三百勇士一样拿着自己的武器站在温泉关,抵挡着在他们看来无穷的敌人.

无限和有限,似乎是不可调和的一对,但在SICP课程的学习中,却使我在现在有了一些联想:Stream,我们不应该把数据或者对象看成是一块或者是一堆,而应该看成是流,河流,在我们需要的时候,从数据链的一头抽出一个我们需要的数据,另一头就会自动填充:

1
2
3
         -------     -------     --------  
数据---->| proc|--->|proc |--->| proc|---->抽出
------- -------- --------

这似乎是一个很不错的解决方案(看起来).

之所以会写上面的这些文字,是因为在讨论开始的问题的时候,我就发现,无限和有限这一对,不仅会在数字的表示方法这一点上来刁难(或者说折磨)我们,似乎他体现在计算机的方方面面,我们能处理的始终是一个有限的对象,而我们的工具也是有限的,虽然我们无法设想几百年之后的人是怎么编程的,可能就像几千年前的人也无法理解无穷大一样,但是我想的是:在我们使用有限的工具处理有限的问题的时候,我们应该要仔细的思考一下.我们很容易将数学的思维代入计算机,这当然是好的,会帮助我们解决问题,可是似乎也会在某些地方,在那些并不那么和谐统一互相协调的地方,让我们坠入矛盾的深渊.

总结

  • 写博客确实是一种锻炼,在行文和构思甚至表达上,总是会感觉词不达意,或者说脑中是思维风暴,但是写出来却是一潭死水,但是练习还是有益处的.
  • 就像一开始说的,数学是一条无限延伸的轴,而计算机是一个会头尾相接的环,两者都有其美的地方(现在我很着迷的一点在于fixed point[不动点]).
  • 这场讨论和思辨使得我更加审慎的来看待与我相伴的计算机,使我在coding的时候更加多的进行思考.
  • 还有一点就是,在看过了足够多的事物之后,发现他们的本质是想通的,CS入门课,SICP,上面提到的文章,这也使得我更深思于计算机的本质:什么是几十年的发展以来没有变的.

呓语到此也完结了.

Lec4.

  • Decomposition(分解)
  • Abstraction(抽象)

Function

  • block up into modules
  • suppress detail
  • create “new primitive”(原语)

抽象和规格化在模块化和构造函数时的重要性

作用域和值绑定

Interpretes: -> golbal binding
call function-> local table

穷举算法(brute force algorithm)

遍历每一种情况找到答案

Recursion(递归)

-> base case: -simplest possible solution
-> induction step: break problem into a simple version

Lec5 & Lec6.

  • 大数
  • 浮点数精度
  • 浮点数的’==’
  • 牛顿法求根号
  • 逐次逼近法(guess, check, improve)
  • 二分法(Bisection method)
  • 回归测试
  • 牛顿法和二分法对于求解sqrt问题的复杂度对比: 二分的迭代次数随着x的增加明显增加
  • 浮点数的上溢和下溢问题
0%