计算思维

2011年秋来源:1.JeannetteWing(周以真)ofCMU.该领域的展望：计算思维将是到21世纪中叶时，世界上每个人的基本技能。-就如同读、写、以及算数。-想象：每个孩子都知道像计算机科学家那样思考！-计算技术和计算机将使计算机思维得以普及。计算思维：计算思维所完成的一些问题，单凭人本身不能完成。如：-求解问题。-设计系统-理解人和机器智能的能力和局限计算思维的两个A：Abstraction（抽象）-计算思维同时在多个抽象层次上同时进行。-计算思维定义层次之间的关系。Automation（自动化）-计算思维的思考方式是：使抽象层次及其关系机械化。机械化的可行性是由精确和严格的符号和模型所保证。-在下面是一些“机器”（人或计算机，虚拟或实际的）。这就给我们以伸缩的能力和胆识。计算思维的影响：计算思维，尤其是机器学习，使统计学产生了变革。计算思维将会生物学产生巨大影响。计算思维正在影响经济学。博弈论计算思维正在影响化学。纳米计算计算思维正在影响物理。量子计算其它：脑科学、地质学、天文学、电气、土木、机械、航空航天、社会科学、医学、法律、娱乐、艺术、体育等。类比：大胆展望：计算思维不仅对于其他领域的科学家，而且对每个人都适用。普适计算是昨天的梦想，今天的现实。计算思维是今天的梦想，明天的现实。计算思维是什么？不是什么？是概念化，不是编程计算机科学不仅是编程是基本原理，不是生搬硬套的技能是人，而不是计算机的思考方式。是数学思维和工程思维的互补和结合。-数学是基础，工程是要处理现实问题。是思想，而不是制品。-不仅是软件/硬件，而是计算概念。适用于任何人，任何地方。–C.T.willbearealitywhenitissointegraltohumanendeavorsthatitdisappearsasanexplicitphilosophy.教育/课程的改革：大学应该在1年级开始介绍：计算机科学家的思考方式，而不仅仅是程序设计。联合国内和国际组织进行课程改革。这是一个综合效应。实例：约束满足问题的应用设想：当你有了一项特殊才能的时候，你能更好更有效地做更多的事情。比如：你有杰出的计算才能。再比如：你有超常的记忆能力。再再比如：你有强大的推理能力。冯.诺依曼：1903，12，28–1957，2，8传奇学问广博的数学家。在集合论、泛函分析、量子力学、测度论、几何、流体力学、经济学、线性规划、博弈论、计算机科学、数值分析、统计学，以及其他很多领域都做出了杰出的贡献。被认为是历史上最伟大的数学家之一。HansBethestated“IhavesometimeswonderedwhetherabrainlikevonNeumann‘sdoesnotindicateaspeciessuperiortothatofman”.冯.诺依曼：1903，12，28–1957，2，8神童1903年生于布达佩斯的一个犹太家庭。在语言、记忆、数学方面是神童。被6岁以前就能用古希腊语讲笑话，对电话簿过目不忘，并表现出杰出心算能力。6岁时，就能凭脑力立即计算8位数除法。8岁时，就精通了微积分。15岁时，跟随著名数学家GáborSzegő学习。第一次会面时，GáborSzegő对这个孩子的数学极为震惊，以至于broughttotears。冯.诺依曼：1903，12，28–1957，2，8轶事冯·诺依曼思考问题的速度真是令人敬畏。G.波列亚也承认，“约翰尼是我唯一感到害怕的学生。如果我在讲演中列出一道难题，讲演结束时，他总会手持一张潦草写就的纸片向我走来，告诉我他已把难题解出来了。”无论是抽象的求证还是运算，他做起来都是得心应手的。曾经碰到别人问他一个中国小学生都很熟的问题，就是两个人相向而行，中间有一只狗跑来跑去，问两个人相遇之后，狗走了多少的这种。应该先求出相遇的时间，再乘狗的速度。诺依曼瞬间给出了答案，提问的人很失望，说你以前一定听说过这个诀窍吧，他指的是上面的这个做法。诺依曼说：“什么诀窍？我所做的就是把狗每次跑得都算出来，然后算出那个无穷的级数。”一则国内的报导:中国奥数题让我思路混乱事件：1、2、3、2、3、4、3、4、5、4、5、6……前500个数的和是多少？这是一道小学奥数题，可鼎鼎有名的数学家也没能一下子解出答案。中广网北京5月8日消息“我能不能不做这道题，感觉我现在的思路比较混乱……”，这是奥昆科夫被一道小学奥数题“为难”后告诉记者的。当中国记者把这道题递给俄罗斯数学家奥昆科夫，他一时也不能很快算出。奥昆科夫2006年获得菲尔茨奖，这个奖项被誉为数学中的“诺贝尔奖”。奥昆科夫对中国小学生拼命学奥数感到十分不解，他本人就从来没有参加过这类数学竞赛。他认为：“做太难、太刁钻的题目，反而会伤害孩子们学习数学的兴趣。”一则国内的报导:中国奥数题让我思路混乱答案：这个数列的前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+2×2＋2×168+3(3+167)÷2×165=42416。解法二：把1、2、3；2、3、4；3、4、5……；165、166、167；166、167、168；167、168写成三个数列：1、2、3、165、166、1672、3、4、166、167、1683、4、5、167、168这样，所求的数列的和就等于上述三个数列的和，也就是：(1+167)÷2×167+(2+168)÷2×167+(3+168)×166÷2=42416。关于奥昆科夫：安德烈·奥昆科夫。俄罗斯数学家，普林斯顿大学教授。2006年因为“将概率论、表示论和代数几何联系起来所做出的贡献”而获得菲尔兹奖。命题：*国际数学大师的解题能力低于中国的小学生？*中国小学生将来会取得更高的数学成就？冯.诺依曼：1903，12，28–1957，2，8轶事一位青年科学家有一个复杂的式子需要求值。第一个特解，他花了十分钟，第二个特解，他用笔和纸运算了一个小时。第三个特解，即使是用计算机还是得花上半天的功夫。这位青年科学家向约翰尼求教。约翰尼自然乐于相助。“让我们先来看看前面几个特解的情况。如果我们令n=1，我们可求得……”——他昂首凝思，喃喃而语。年轻的提问者便插嘴说，答案“是2.31吧？”约翰尼听了后不解地看了他一眼并说：“我们现在令n=2，……”他思索着，嘴唇微微启动。在约翰尼就要算出答案前的一瞬间，这位青年科学家插嘴说：“是7.49吗？”这次，约翰尼听了不免蹙起了眉头，他连忙接下去说：“如果令n=3，那末……”还没等约翰尼运算完毕，青年科学家就喊了出来：“答数是11.06。”这下约翰尼可受不了啦。这完全不可能。他从未见过有初出茅庐之辈能胜过他的！他一时陷入了心烦意乱之中，一直到开玩笑的家伙自己向他承认事先已作过笔算以后，他才平息了心头的愠怒。冯.诺依曼：1903，12，28–1957，2，8轶事据说有一次，维纳有个问题想了一个月，没想明白。正好诺伊曼喜欢研究院到处串门。这天跑到维纳那里去，维纳就跟他诉苦，诺伊曼问了一遍问题，然后就开始站在窗户那里对着外面发呆。过了半个小时，他给了维纳答案。冯.诺依曼维纳关于维纳控制论的创始人，美国数学家，有名的神童。从小聪明过人，3岁能读会写，14岁大学毕业，18岁通过博士论文答辩，成为哈佛大学科学博士。维纳9岁时，他的数学成绩已经超过普通大学一年级的水平。学校里不管老师还是同学们，都称维纳“小神童”。维纳也为这个称号沾沾自喜，但父亲列奥严肃地告诉周围的人：“请不要叫他神童！”转身又对儿子说，“记住，你不是神童！”维纳父亲在哈佛任教，也可以给儿子更多的关照，但他没有这样做，反而将儿子送进一所偏僻的普通大学。直到维纳14岁大学毕业，才允许儿子报考哈佛大学攻读博士学位。维纳时常感慨，“我之所以成功，因为我从没将自己当成神童。9岁那年，如果父亲没将我送进一所普通大学，而是直接将我送进哈佛大学，那么就没有今天的我，我已经被人们当成神童，扼杀在早慧的摇篮里。冯.诺依曼：1903，12，28–1957，2，8轶事有人回忆听冯·诺依曼讲演必须有足够聪明，极度专心，否则绝对跟不上他。每次演讲，只有极少数的数学家能够勉强听得懂，奉陪到底。演讲的时候，冯·诺依曼的思维敏捷，内容充实丰富，边讲边写，板书飞快，一会儿功夫就写满了整块的黑板，只好擦去旧的，再写新的。当要回过头来引用前面结果的时候，他会不断地指着黑板的某个位置说：根据擦过三次之前，写在这个位置的一个式子，再加上擦过六次之前，写在那个地方的一条定理，就可以得到以下结论。听惯了他演讲的数学家们笑称：冯·诺依曼是“用板擦来证明定理的人”。因为他经常是根据早已擦掉的步骤，进行推理证明。假设你被赋予这样的能力：对于给定的一组约束条件，你都能迅速找到满足这组约束条件的解。那么：你将表现出不凡的智力。你能迅速解决别人凝思苦想很长时间后，才能解决的问题。如果每个人都有这种能力，世界将大大不同。例子：字母算数约束满足问题（CSP）：人工智能的一个分支。应用广泛。定义：*给定一组变量V={v1,v2,v3,…}；*每个变量vi都有其取值范围；*给定一组约束条件；*寻找变量V的取值，使得所有约束都满足。例子：解：约束满足问题的求解及其工具：其求解过程是一个搜索过程。因而形成各种工具。这里我们采用Minion：*快速、开源的求解工具。*输入语言简单。采用Minion求解问题的步骤：理解问题描述问题：用Minion提供的语言。问题求解例：农场主问题问题：一个农场主有两种牲畜：猪和鸡。共7头，22条腿。则猪和鸡各有多少呢？问题理解：寻找pigs,hens:int(0..7)使得pigs+hens=7,pigs*4+hens*2=22例：农场主问题问题描述MINION3**VARIABLES**DISCRETEpigs{0..7}DISCRETEhens{0..7}**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([hens,pigs],7)**EOF**例：密码算数问题SEND+MORE=MONNEY问题理解：寻找S,E,N,D,M,O,R,Y:int(0..9)使得1000*S+100*E+10*N+D+1000*M+100*O+10*R+E=10000*M+1000*O+100*N+10*E+Yalldiff([S,E,N,D,M,O,R,Y])例：密码算数问题问题描述MINION3**VARIABLES**DISCRETES{0..9}DISCRETEE{0..9}DISCRETEN{0..9}DISCRETED{0..9}DISCRETEM{0..9}DISCRETEO{0..9}DISCRETER{0..9}DISCRETEY{0..9}**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