大学计算机教程-dj-8计算思维.pptx

大学计算机;;计算思维;计算思维;2022/10/27;计算思维的本质：抽象（Abstraction）和自动化（Automation）。

计算思维的本质反映了计算的根本问题，即什么能被有效地自动进行。计算是抽象地自动进行，自动化需要某种计算机去解释现象。从操作层面上讲，计算就是如何寻找一台计算机去求解问题，选择合适的抽象，选择合适的计算机去解释执行抽象，后者就是自动化。

计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。其中，数字抽象只是一类特例。自动化就是机械地一步一步自动执行，其基础和前提是抽象。

案例：18世纪著名古典数学问题——哥尼斯堡七桥问题。

著名的格尼斯堡“七桥”问题就是将连接两个岛屿和陆地的七座桥的地图抽象为点与线连接的图，将如何判断不重复走遍所有道路的问题转换为图的形式的数学问题进行处理。;7;问题的描述与抽象;9;10;（1）计算思维是人类求解问题的一条途径，是属于人的思维方式，不是计算机的思维方式。

计算机之所以能够求解问题，是因为人将计算思维的思想赋予了计算机，计算机才能够进行如迭代、递归等计算。

（2）计算思维的过程可以由人执行，也可以由计算机执行。

这些计算人和计算机都可以做，只不过人的速度慢而已。借助于超算能力的计算机，人类就可以去解决那些在计算时代之前不敢尝试的问题，实现只有想不到的，没有做不到的境界。

（3）计算思维是思想，不是人造物。

计算思维不是硬件，而是计算这一概念用于求解问题、管理日常生活以及与他人交流和互动的思想。

（4）计算思维是概念化，不是程序化。

计算机科学并不仅仅是计算机编程，像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维。;计算思维的基本问题

计算思维是研究计算的思维，研究计算思维的基本问题是要了解哪些问题是可计算的，哪些问题是不可计算的，以及计算的复杂性如何度量。

（1）可计算性

一个问题是可计算的是指可以使用计算机在有限步骤内完成计算。

图灵论题给出可计算性的定义：一个问题是可计算的，当且仅当它???图灵机上经过有限步骤之后可以得到正确的结果。

（2）计算复杂性

计算复杂性就是指用计算机求解问题的难易程度，通常可用时间复杂度和空间复杂度来衡量。

计算复杂性理论是用数学方法研究各类问题的计算复杂性学科。它研究各种可计算问题在计算过程中时间和空间的耗费情况，以及在不同计算模型下，使用不同类型的资源和不同数量的资源时，各类问题复杂性的本质特性和相互关系。

;汉诺塔问题;可以采用递归的方法，进行求解。

问题：当n=64时，即有移动64个盘子时，需要移动多少次盘子？耗费多少时间呢？

f(n)=2n-1=264-1=18446744073709551615

假定移动一个盘子1秒，一年365天，则需要约

584042417355年，即5849亿年。

即使使用计算机每秒可进行1亿次移动，也需要花费约5849年时间。;计算思维;;智能时代的计算思维;智能时代的计算思维;智能时代的计算思维