计算思维

《计算思维》由会员分享，可在线阅读，更多相关《计算思维（38页珍藏版）》请在金锄头文库上搜索。

1、计算思维,2011年秋,如何像计算机科学家那样思考？,来源:,1. Jeannette Wing (周以真) of CMU.,该领域的展望： 计算思维将是到21世纪中叶时，世界上每个人的基本技能。- 就如同读、写、以及算数。- 想象：每个孩子都知道像计算机科学家那样思考！- 计算技术和计算机将使计算机思维得以普及。,计算思维： 计算思维所完成的一些问题，单凭人本身不能完成。如：- 求解问题。- 设计系统- 理解人和机器智能的能力和局限,计算思维的两个A： Abstraction（抽象）- 计算思维同时在多个抽象层次上同时进行。- 计算思维定义层次之间的关系。 Automation（自动化） -

2、 计算思维的思考方式是：使抽象层次及其关系机械化。机械化的可行性是由精确和严格的符号和模型所保证。- 在下面是一些“机器”（人或计算机，虚拟或实际的）。 这就给我们以伸缩的能力和胆识。,计算思维的影响： 计算思维，尤其是机器学习，使统计学产生了变革。 计算思维将会生物学产生巨大影响。 计算思维正在影响经济学。博弈论 计算思维正在影响化学。纳米计算 计算思维正在影响物理。量子计算 其它：脑科学、地质学、天文学、电气、土木、机械、航空航天、社会科学、医学、法律、娱乐、艺术、体育等。,类比： 大胆展望：计算思维不仅对于其他领域的科学家，而且对每个人都适用。 普适计算是昨天的梦想，今天的现实。 计算思

3、维是今天的梦想，明天的现实。,计算思维是什么？不是什么？ 是概念化，不是编程 计算机科学不仅是编程 是基本原理，不是生搬硬套的技能 是人，而不是计算机的思考方式。 是数学思维和工程思维的互补和结合。- 数学是基础，工程是要处理现实问题。 是思想，而不是制品。- 不仅是软件/硬件，而是计算概念。 适用于任何人，任何地方。 C.T. will be a reality when it is so integral to human endeavors that it disappears as an explicit philosophy.,教育/课程的改革： 大学应该在1年级开始介绍：计算机科学

4、家的思考方式，而不仅仅是程序设计。 联合国内和国际组织进行课程改革。 这是一个综合效应。,实例：约束满足问题的应用 设想：当你有了一项特殊才能的时候，你能更好更有效地做更多的事情。 比如：你有杰出的计算才能。 再比如：你有超常的记忆能力。 再再比如：你有强大的推理能力。,冯.诺依曼：1903，12 ，28 1957，2，8 传奇 学问广博的数学家。 在集合论、泛函分析、量子力学、测度论、几何、流体力学、经济学、线性规划、博弈论、计算机科学、数值分析、统计学，以及其他很多领域都做出了杰出的贡献。 被认为是历史上最伟大的数学家之一。Hans Bethe stated “I have sometim

5、es wondered whether a brain like von Neumanns does not indicate a species superior to that of man”.,冯.诺依曼：1903，12 ，28 1957，2，8 神童 1903年生于布达佩斯的一个犹太家庭。 在语言、记忆、数学方面是神童。 被6岁以前就能用古希腊语讲笑话，对电话簿过目不忘，并表现出杰出心算能力。 6岁时，就能凭脑力立即计算8位数除法。 8岁时，就精通了微积分。 15岁时，跟随著名数学家Gbor Szeg学习。第一次会面时，Gbor Szeg对这个孩子的数学极为震惊，以至于brought

6、to tears。,冯.诺依曼：1903，12 ，28 1957，2，8 轶事 冯诺依曼思考问题的速度真是令人敬畏。G. 波列亚也承认，“约翰尼是我唯一感到害怕的 学生。如果我在讲演中列出一道难题，讲演结 束时，他总会手持一张潦草写就的纸片向我走 来，告诉我他已把难题解出来了。”无论是抽 象的求证还是运算，他做起来都是得心应手的。 曾经碰到别人问他一个中国小学生都很熟的问题，就是两个人相向 而行，中间有一只狗跑来跑去，问两个人相遇之后，狗走了多少的这种。应该先求出相遇的时间，再乘狗的速度。诺依曼瞬间给出了答案，提问的人很失望，说你以前一定听说 过这个诀窍吧，他指的是上面的这个做法。诺依曼说：“

7、什么诀窍？我所做的 就是把狗每次跑得都算出来，然后算出那个无穷的级数。”,一则国内的报导:中国奥数题让我思路混乱 事件：1、2、3、2、3、4、3、4、5、4、5、6前500个数的和是多少？这是一道小学奥数题，可鼎鼎有名的数学家也没能一下子解出答案。 中广网北京5月8日消息 “我能不能不做这道题，感觉我现在的思路比较混乱”，这是奥昆科夫被一道小学奥数题“为难”后告诉记者的。 当中国记者把这道题递给俄罗斯数学家奥昆科夫，他一时也不能很快算出。奥昆科夫2006年获得菲尔茨奖，这个奖项被誉为数学中的“诺贝尔奖”。 奥昆科夫对中国小学生拼命学奥数感到十分不解，他本人就从来没有参加过这类数学竞赛。他认为

8、：“做太难、太刁钻的题目，反而会伤害孩子们学习数学的兴趣。”,一则国内的报导:中国奥数题让我思路混乱 答案：这个数列的前500项是： 1、2、3； 2、3、4； 3、4、5 ；165、166、167； 166、167、168； 167、168。解法一：这个数列里有1个1、2个2、2个168、3个3、4、5、165、166、167，所求的和=1+222168+3(3+167)2165= 42416。解法二：把1、2、3；2、3、4；3、4、5；165、166、167；166、167、168；167、168写成三个数列： 1、2、3、165、166、167 2、3、4、166、167、168 3、

9、4、5、167、168 这样，所求的数列的和就等于上述三个数列的和，也就是：(1+167)2167+(2+168)2167+(3+168)1662=42416。, 关于奥昆科夫： 安德烈奥昆科夫。俄罗斯数学家，普林斯顿大学教授。2006年因为“将概率论、表示论和代数几何联系起来所做出的贡献”而获得菲尔兹奖。, 命题：* 国际数学大师的解题能力低于中国的小学生？* 中国小学生将来会取得更高的数学成就？,冯.诺依曼：1903，12 ，28 1957，2，8 轶事 一位青年科学家有一个复杂的式子需要求值。第一个特解，他花了十分钟，第二个特解，他用笔和纸运算了一个小时。第三个特解，即使是用计算机还是得

10、花上半天的功夫。这位青年科学家向约翰尼求教。约翰尼自然乐于相助。“让我们先来看看前面几个特解的情况。如果我们令n=1，我们可求得”他昂首凝思，喃喃而语。年轻的提问者便插嘴说，答案“是2.31吧？”约翰尼听了后不解地看了他一眼并说：“我们现在令n=2，”他思索着，嘴唇微微启动。在约翰尼就要算出答案前的一瞬间，这位青年科学家插嘴说：“是7.49吗？”这次，约翰尼听了不免蹙起了眉头，他连忙接下去说：“如果令n=3，那末”还没等约翰尼运算完毕，青年科学家就喊了出来：“答数是11.06。”这下约翰尼可受不了啦。这完全不可能。他从未见过有初出茅庐之辈能胜过他的！他一时陷入了心烦意乱之中，一直到开玩笑的家伙

11、自己向他承认事先已作过笔算以后，他才平息了心头的愠怒。,冯.诺依曼：1903，12 ，28 1957，2，8 轶事 据说有一次，维纳有个问题想了一个月，没想明白。正好诺伊曼喜欢研究院到处串门。这天跑到维纳那里去，维纳就跟他诉苦，诺伊曼问了一遍问题，然后就开始站在窗户那里对着外面发呆。过了半个小时，他给了维纳答案。,冯.诺依曼,维纳,关于维纳 控制论的创始人，美国数学家，有名的神童。 从小聪明过人，3岁能读会写，14岁大学毕业，18岁通过博士论文答辩，成为哈佛大学科学博士。 维纳9岁时，他的数学成绩已经超过普通大学一年级的水平。学校里不管老师还是同学们，都称维纳“小神童”。维纳也为这个称号沾沾自

12、喜，但父亲列奥严肃地告诉周围的人：“请不要叫他神童！”转身又对儿子说，“记住，你不是神童！” 维纳父亲在哈佛任教，也可以给儿子更多的关照，但他没有这样做，反而将儿子送进一所偏僻的普通大学。直到维纳14岁大学毕业，才允许儿子报考哈佛大学攻读博士学位。 维纳时常感慨，“我之所以成功，因为我从没将自己当成神童。9岁那年，如果父亲没将我送进一所普通大学，而是直接将我送进哈佛大学，那么就没有今天的我，我已经被人们当成神童，扼杀在早慧的摇篮里。,冯.诺依曼：1903，12 ，28 1957，2，8 轶事 有人回忆听冯诺依曼讲演必须有足够聪明，极度专心，否则绝对跟不上他。每次演讲，只有极少数的数学家能够勉强

13、听得懂，奉陪到底。演讲的时候，冯诺依曼的思维敏捷，内容充实丰富，边讲边写，板书飞快，一会儿功夫就写满了整块的黑板，只好擦去旧的，再写新的。当要回过头来引用前面结果的时候，他会不断地指着黑板的某个位置说：根据擦过三次之前，写在这个位置的一个式子，再加上擦过六次之前，写在那个地方的一条定理，就可以得到以下结论。听惯了他演讲的数学家们笑称：冯诺依曼是“用板擦来证明定理的人”。因为他经常是根据早已擦掉的步骤，进行推理证明。,假设你被赋予这样的能力： 对于给定的一组约束条件，你都能迅速找到满足这组约束条件的解。 那么： 你将表现出不凡的智力。 你能迅速解决别人凝思苦想很长时间后，才能解决的问题。 如果每

14、个人都有这种能力，世界将大大不同。,例子：字母算数,约束满足问题（CSP）： 人工智能的一个分支。 应用广泛。 定义：* 给定一组变量V=v1,v2,v3,；* 每个变量vi都有其取值范围；* 给定一组约束条件；* 寻找变量V的取值，使得所有约束都满足。,例子：,解：,约束满足问题的求解及其工具： 其求解过程是一个搜索过程。 因而形成各种工具。 这里我们采用Minion：* 快速、开源的求解工具。* 输入语言简单。,采用Minion求解问题的步骤： 理解问题 描述问题：用Minion提供的语言。 问题求解,例：农场主问题 问题：一个农场主有两种牲畜：猪和鸡。共7头，22条腿。则猪和鸡各有多少呢

15、？ 问题理解： 寻找 pigs, hens: int(07) 使得pigs + hens = 7,pigs * 4 + hens * 2 = 22,例：农场主问题 问题描述 MINION 3 *VARIABLES* DISCRETE pigs 07 DISCRETE hens 07 *SEARCH* PRINT pigs,hens VARORDER pigs,hens *CONSTRAINTS* weightedsumgeq(2,4, hens,pigs, 22) weightedsumleq(2,4, hens,pigs, 22) sumleq(hens,pigs, 7) sumgeq(he

16、ns,pigs, 7) *EOF*,例：密码算数问题 SEND+MORE=MONNEY 问题理解： 寻找 S,E,N,D,M,O,R,Y : int(09) 使得 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E +Y alldiff(S,E,N,D,M,O,R,Y),例：密码算数问题 问题描述 MINION 3 *VARIABLES* DISCRETE S 09 DISCRETE E 09 DISCRETE N 09 DISCRETE D 09 DISCRETE M

17、09 DISCRETE O 09 DISCRETE R 09 DISCRETE Y 09 *SEARCH* PRINT S,E,N,D,M,O,R,Y VARORDER S,E,N,D,M,O,R,Y *CONSTRAINTS* alldiff( S, E, N, D, M, O, R, Y) weightedsumgeq( 1,10,100,1000,10000,-1,-1,-10,-10,-100,-100,-1000,-1000, Y,E,N,O,M,D,E,N,R,E,O,M,S, 0) weightedsumleq( 1,10,100,1000,10000,-1,-1,-10,-10,-100,-100,-1000,-1000, Y,E,N,O,M,D,E,N,R,E,O,M,S, 0) *EOF*,