大学计算机基础（第六版）课件 01计算思维导论.pptx

第1章计算思维导论

01计算与计算思维02计算理论03数与计算工具04计算与信息社会Contents目录

01计算与计算思维

计算就是一种思考过程或执行过程。计算的特点：①计算要有可用的数据；②在一定的时间内完成计算，故要有速度；③计算是个过程；④要有适合和科学的方法（算术、规则、变换、算法、策略等）；⑤计算过程和结果要有精度；⑥计算对错都要有结果。计算的含义

计算需要硬件与软件算筹和算盘都属于硬件，而摆法和算盘的使用规则就是它们的软件，它们的计算功能是加、减、乘、除、开方等运算，这就是计数与计算。计数与计算

逻辑（Logic）：本质是寻找事物的相对关系，并用已知推断未知数理逻辑：德国人莱布尼茨逻辑代数：爱尔兰的数学教授布尔逻辑与计算

算法是对特定问题求解步骤和方案的一种描述或解法算法是一组确定的、有效的、有限的解决问题的步骤6-5=1和6+（-5）=1的区别：前者是算数，后者为算法算法可分为数值计算类、非数值计算类算法的过程正好就是可以在计算机上执行的过程计算：计算的过程就是执行算法的过程算法与计算

科学思维（ScientificThinking）：人脑对科学信息的加工活动，它是主体对客体理性的、逻辑的、系统的认识过程。科学思维必须遵守的基本原则：在逻辑上要求严密的逻辑性，达到归纳和演绎的统一；在方法上要求辩证的分析和综合两种思维方法；在体系上要求实现逻辑与历史的一致，达到理论与实践具体的、历史的统一。科学思维

理论思维（TheoreticalThinking）又称逻辑思维，对应于理论科学实践思维（ExperimentalThinking）又称实证思维，对应于实践科学计算思维（ComputationalThinking）对应于计算机科学科学思维的分类

计算思维的精髓是运用计算机科学的思想与方法分析问题、行为理解、系统建模与设计实现计算机科学成为计算思维的基础计算机的出现强化了计算思维的意义和作用计算思维的概念人与环境人与人环境与人行为理解的社会性什么是“行为理解”？

计算思维定义、本质和特征科学思维美国学者周以真（JeannetteMWing）教授2006年提出：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为的理解等涵盖计算机科学之广度的一系列思维活动计算思维的三大部分：问题求解、系统设计和工程组织（人类行为理解）本质：抽象（Abstract）和自动化（Automation）；特征：能行性，构造性和确定性计算思维的概念

计算思维的实践基础为计算系统（机器）与程序，当程序被加载到计算系统（机器）中之后，它会被自动执行。这种思维方式就是要将现实信息进行符号化。计算思维的实践环境是指应用计算系统（机器）与程序的通用领域，是将计算思维转化成物理环境的过程。“冯?诺依曼计算机”“个人计算环境”“并行与分布式计算环境”“云计算环境”计算思维的实践计算系统（机器）程序递归0和1计算思维的实践基础

02计算理论

计算模型是指用于刻画计算概念的抽象形式系统或数学系统。计算模型控制器读/写头纸带读/写头纸带（a）模型图（b）概念图y=5/20;z=x+y;F=b1?b2…………状态x状态n初始条件变量状态0图灵机模型和概念示意图

可计算性理论是研究计算的一般性质的数学理论，也称算法理论和能行性理论。可计算性具有如下几个特征确定性有限性设备无关性可用算术运算可计算性

计算复杂性是指利用计算机求解问题的难易程度计算复杂性的度量标准时间复杂度常数、对数阶、线性阶、线性对数阶、平方阶、立方阶、k次方阶、指数阶空间复杂度人们对算法空间复杂度分析的重视程度要小于时间复杂度的分析计算复杂性

P问题是指问题可以在内的多项式时间内解决P问题成为了区分问题是否可以被计算机求解的一个重要标志NP问题是指算法时间复杂度不能使用确定的多项式来表示可计算与计算复杂性理论可知，一个问题理论上是否能行，取决于其可算性，而现实是否能行，则取决于其计算复杂性。P问题与NP问题

印度古老传说。三根柱子，最终64个盘子在其中一根柱子上从下到上由大到小的地穿好。按照下面的法则移动这些盘子：①一次只移动一个盘子，且只能在柱子上来回移动②不管在哪根柱子上，盘子必须在大片上面。汉诺塔求解当n=64时，假如每秒钟移动一次，共需要多长时间呢？5,849亿年以上，时间复杂度不可行问题。

问题的抽象问题的映射设计问题求解算法问题求解的实现求解问题过程

数学模型已成为处理各种实际问题的重要工具建立数学模型的一般步骤①模型准备阶段②模型假设阶段③模型构成阶段④模型确定阶段问题抽象的思维过程

问题的映射是将客观世界的问题求解映射到计算机中求解开发软件进行问题求解的过程实现问题域→建立模型→编程实现→到计算机世界执行