计算思维-概念、特征与启示(樊磊)x

《计算思维-概念、特征与启示(樊磊)x》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算思维-概念、特征与启示樊磊首都师范大学教育技术系fanlei.cnu@gmail.com计算思维兴起的缘由从二十世纪七十年代中期开始，在诺贝尔物理学奖得主KenWilson等人的积极倡导下，基于大规模并行数值计算与模拟的“计算科学”（ComputingScience）开创了科学研究的第三种范例（理论、实验、计算机模拟）。计算科学协同其它科学领域（如基因组工程、天体物理等等）取得了一系列重要的突破性进展，受到传统科学界的重视和接纳。1991年，美国联邦政府立法将建立联网的大规模超级计算中心（资源）作为保持美国科学技术领先地位的一项重要措施。今天我们所熟悉的大数据、可视化及云计算等等均源

2、自于这场运动。国内很多大学数学学院中的“信息与计算”专业也是在这个时期出现的。这场运动对于“计算机科学”的普及和得到政府决策部门的重视起到了一定的推进作用（像之前的“人工智能”一样！）。由于相对片面地理解和宣扬所谓的“计算科学”，也带来很多副作用，至今学术界仍有相当多的人混淆“计算科学”与“计算机科学”（或“信息科学”）。计算思维兴起的缘由更传统意义上、更广义的计算机科学（ComputerScience，指围绕计算现象和计算对象的研究）受到冷落甚至质疑。进入二十一世纪后，美国报考各大学计算机科学相关专业的优秀学生数量开始呈明显下降趋势，高规格科研资助的力度和水平降低，这标志学科的影响力和

3、社会认知度出现了危机。计算机科学界开始再次反思并宣扬自身学科的核心价值，有关计算思维的探讨和研究就是在这样的背景下产生的。计算思维兴起的缘由“计算思维”旨在倡导一种所谓的“计算机科学家的思维方式”，以区别“逻辑（抽象）思维”、“数学思维”和“工程化思维”等等这些已为学术界普遍认同的思维方式，从而提高社会、学生及家长对学科的认同。比较系统和典型的观点是由J.Wing提出的：ComputationalThinking,COMMUNICATIONSOFTHEACM,Vol.49,No.3,March2006J.Wing的观点在国内也颇具影响力。有关“什么是计算思维？”的问题仍存争议。计算思维兴

4、起的缘由从算法思维到计算思维早在二十世纪五、六十年代，就提出了算法思维的说法，是当时的“算法学家”们为争取将计算机科学从数学中独立出来所进行的努力。著名计算机科学家D.Knuth（高德纳）1985年在《美国数学月刊》（为美国影响最大、读者群最广的数学杂志）上发表了“数学思维与算法思维”的文章。“算法思维”着重强调在（数学）问题求解过程中算法（构造！）的核心作用。现代“计算思维”的含义比“算法思维”要广泛得多，包含了多种抽象层次、发展算法的数学以及跨越不同尺度问题的算法效率问题的分析等方面。模型与（现实世界中的）问题模型现实世界理论数学模型与数学思维数学模型数学概念数学理论抽象自然现象及对

5、象建模应用概念关联结构规律计算模型与计算思维计算模型计算概念计算机科学理论抽象自然的及人工的信息处理建模应用概念关联结构规律小问题中的计算思维CAPTCHA=CompletelyAutomatedPublicTuringTeststoTellComputersandHumansApart图灵测试的一个现代简单直接应用！图灵测试的目的是给机器“智能”下一个定义，这个小小的应用与图灵提出“测试”的本意相差甚远。整数乘法的计算量问题两个n位的整数相乘的“计算量”大致上与n2成正比。用计算理论的术语说：两个n位整数乘法的“计算复杂度”为O(n2).例如，两个10000位整数乘法约需要10000

6、10000=1010次标准运算。对于大整数（如1010位级别的）的乘法，这个复杂程度是不可接受的（为什么？）。1971年，基于Gauss在十九世纪的一个古老的思想，由计算机科学家们设计的快速乘法算法，其计算复杂度为O(nlognloglogn)这个算法每年节省的计算资源价值数以百亿元！小问题中的计算思维小问题中的计算思维XYffXY数学函数观点：强调定义域（输入）和值域（输出）的具体形式，淡化对应本身。算法（流程图）观点：强调如何将输入变换为输出，淡化对输入输出自身的描述（由数据结构来处理！）。大问题中的计算思维素数判定与大数分解–公钥密码学图着色问题（NP难解问题）–身份认证（零知识协

7、议）稀疏矩阵计算–PageRank值（网页排名）量子力学的范畴基础零知识协议所谓零知识认证协议指：一方（证明者）在不暴露有可能危及秘密的任何信息前提下，向另一方（验证方）证明她知道一个秘密。零知识协议在1985年由以色列计算机科学家ShafiGoldwasser等人提出。ShafiGoldwasser图着色与零知识协议图的3-着色问题：任给一个图，设计一种方案，使用3种颜色着色图中的各个节点，使得任意相邻两个节点（有边相连的节点）的