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

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

位的一项重要措施• • 今天我们所熟悉的大数据、可视化及云计算等等今天我们所熟悉的大数据、可视化及云计算等等 均源自于这场运动均源自于这场运动 • • 国内很多大学数学学院中的国内很多大学数学学院中的“ “信息与计算信息与计算” ”专业也专业也 是在这个时期出现的是在这个时期出现的 • • 这场运动对于这场运动对于“ “计算机科学计算机科学” ”的普及和得到政府决的普及和得到政府决 策部门的重视起到了一定的推进作用（像之前的策部门的重视起到了一定的推进作用（像之前的“ “ 人工智能人工智能” ”一样！）一样！） • • 由于相对片面地理解和宣扬所谓的由于相对片面地理解和宣扬所谓的“ “计算科学计算科学” ”，， 也带来很多副作用，至今学术界仍有相当多的人也带来很多副作用，至今学术界仍有相当多的人 混淆混淆“ “计算科学计算科学” ”与与“ “计算机科学计算机科学” ”（或（或“ “信息科学信息科学” ” ）计算思维兴起的缘由• • 更传统意义上、更广义的计算机科学（更传统意义上、更广义的计算机科学（Computer Computer ScienceScience，指围绕计算现象和计算对象的研究）受，指围绕计算现象和计算对象的研究）受 到冷落甚至质疑。

到冷落甚至质疑 • • 进入二十一世纪后，美国报考各大学计算机科学进入二十一世纪后，美国报考各大学计算机科学 相关专业的优秀学生数量开始呈明显下降趋势，相关专业的优秀学生数量开始呈明显下降趋势， 高规格科研资助的力度和水平降低，这标志学科高规格科研资助的力度和水平降低，这标志学科 的影响力和社会认知度出现了危机的影响力和社会认知度出现了危机 • • 计算机科学界开始再次反思并宣扬自身学科的核计算机科学界开始再次反思并宣扬自身学科的核 心价值，有关计算思维的探讨和研究就是在这样心价值，有关计算思维的探讨和研究就是在这样 的背景下产生的的背景下产生的计算思维兴起的缘由• • “ “计算思维计算思维” ”旨在倡导一种所谓的旨在倡导一种所谓的“ “计算机科学家的计算机科学家的 思维方式思维方式” ”，以区别，以区别“ “逻辑（抽象）思维逻辑（抽象）思维” ”、、“ “数学思数学思 维维” ”和和“ “工程化思维工程化思维” ”等等等等这些这些已为学术界普遍认同已为学术界普遍认同 的思维方式的思维方式，，从而从而提高提高社会、学生及家长对学科社会、学生及家长对学科 的认同 • • 比较系统和典型的观点是由比较系统和典型的观点是由J. WingJ. Wing提出的：提出的：Computational Thinking, COMMUNICATIONS OF THE ACM, Vol. 49, No. 3Computational Thinking, COMMUNICATIONS OF THE ACM, Vol. 49, No. 3, , March 2006March 2006 • • J.WingJ.Wing的观点在国内也颇具影响力。

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

同尺度问题的算法效率问题的分析等方面模型与（现实世界中的）问题模型现实世界理论数学模型与数学思维数学模型数学概念数学理论抽象自然现象及对象建模应用概念关联结构规律计算模型与计算思维计算模型计算概念计算机科学理论抽象自然的及人工的 信息处理建模应用概念关联结构规律小问题中的计算思维• •CAPTCHACAPTCHA = = C Completely ompletely A Automated utomated P Public ublic T Turing Tests uring Tests to Tell to Tell C Computers and omputers and H Humans umans A Apart part • •图灵测试的一个现代简单直接应用！图灵测试的一个现代简单直接应用！• •图灵测试的目的是给机器图灵测试的目的是给机器“ “智能智能” ”下一个定义，这个小小的下一个定义，这个小小的 应用与图灵提出应用与图灵提出“ “测试测试” ”的本意相差甚远的本意相差甚远整数乘法的计算量问题 • 两个 n 位的整数相乘的“计算量”大致上与n2成正比 • 用计算理论的术语说：两个 n 位整数乘法的“计算复杂度” 为O(n2). • 例如，两个10000位整数乘法约需要10000 10000 = 1010次 标准运算。

• 对于大整数（如1010 位级别的）的乘法，这个复杂程度是 不可接受的（为什么？） • 1971年，基于Gauss在十九世纪的一个古老的思想，由计 算机科学家们设计的快速乘法算法，其计算复杂度为 O(n log n log log n)• 这个算法每年节省的计算资源价值数以百亿元！小问题中的计算思维小问题中的计算思维XYffXY数学函数数学函数观观点：点：强强调调定定义义域（域（输输入）和入）和 值值域（域（输输出）的具体形式，淡化出）的具体形式，淡化对应对应 本身算法（流程算法（流程图图））观观点：点：强强调调如何将如何将输输入入变换为输变换为输 出，出， 淡化淡化对输对输 入入输输出自身的出自身的描述描述（由数据（由数据结结构来构来处处理！）大问题中的计算思维• •素数判定与大数分解素数判定与大数分解 – – 公公钥钥密密码码学学• •图图着色着色问题问题 （（NPNP难难解解问题问题 ）） – – 身份认证（身份认证（零知零知识协议识协议））• •稀疏矩稀疏矩阵计阵计 算算 – PageRank– PageRank值值（网（网页页排名排名））• •量子力学的范畴基量子力学的范畴基础础零知识协议所谓所谓零零知识知识认证协议指：一方（认证协议指：一方（证明者）在不暴露证明者）在不暴露有可有可能危及秘密的任何能危及秘密的任何信息前提下，向另一方（验证方）证信息前提下，向另一方（验证方）证明明她知道一个她知道一个秘密。

秘密零知识协议在零知识协议在19851985年由以色列计算机科学家年由以色列计算机科学家ShafiShafi GoldwasserGoldwasser等人提出等人提出ShafiShafi GoldwasserGoldwasser图着色与零知识协议• •图图的的3-3-着色着色问题问题 ：任：任给给一个一个图图，，设计设计 一种方案，使用一种方案，使用3 3种种 颜颜色着色色着色图图中的各个中的各个节节点，使得任意相点，使得任意相邻邻两个两个节节点（有点（有边边 相相连连的的节节点）的点）的颜颜色不同• •3-3-图图着色着色问题问题 是一个是一个NPNP难难解解问题问题 ，，简单简单 地地说说，就是没有快，就是没有快 速算法能速算法能对对任何任何给给定的定的图图完成完成3-3-着色• •但反但反过过来可以快速生成来可以快速生成3-3-着色的着色的图图！！图着色与零知识协议协同计算• • 一组人一组人通过通过其各自拥有的私秘信息（如年龄、体其各自拥有的私秘信息（如年龄、体 重等）共同计算出一个共享的信息，但在计算过重等）共同计算出一个共享的信息，但在计算过 程中不透露出个人的秘密程中不透露出个人的秘密。

• • 例如：例如：Alice, Bob, CarolAlice, Bob, Carol想计算他们的体重之和，想计算他们的体重之和， 但都不希望别人知道自己的体重但都不希望别人知道自己的体重协同计算1. 1. 每人随机选择每人随机选择0 0到到10001000之间的两个数，然之间的两个数，然 后再选择后再选择出出第三个数，使得三个数之和模第三个数，使得三个数之和模 10001000后恰好是自己的体重后恰好是自己的体重2. 2. 每人每人将随机选择的两个数分别发送给将随机选择的两个数分别发送给其其 他两人4. 4. 每个人将每个人将三个人的数相加后再模三个人的数相加后再模10001000后后 的余数就是三人的体重之和的余数就是三人的体重之和3. 3. 每人将自己的第三个数与接收到的其他人每人将自己的第三个数与接收到的其他人 的共享数相加，并将结果模的共享数相加，并将结果模10001000计算思维与数学思维的关系• •关注的关注的对对象不同象不同• •关注的关注的问题问题 不同不同• •都有多都有多级级抽象抽象层层次次• •使用数学方法来使用数学方法来证证明或研究算法明或研究算法问题问题• •计计算思算思维维会反作用于数学（会反作用于数学（这这点非常关点非常关键键！）！）• •指数运算、逻辑推理和化简法则指数运算、逻辑推理和化简法则( (a am m) )n n= = a amnmn. . p p  ( (q q  r r) )   p p   q q  r r. .• •两者的共同点是什么？两者的共同点是什么？参见：樊磊等，利用计算直觉理解参见：樊磊等，利用计算直觉理解抽象抽象数学数学概念概念，黑龙江高教研究，，黑龙江高教研究，20052005年。

年计算思维对数学的反作用什么是计算思维？• •计算思维的实质计算思维的实质是将问题表征为关于某种计算模型的信是将问题表征为关于某种计算模型的信息处理，并在此基础上寻求问题的算法解息处理，并在此基础上寻求问题的算法解。