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

第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亿年以上，时间复杂度不可行问题。问题的抽象问题的映射设计问题求解算法问题求解的实现求解问题过程数学模型已成为处理各种实际问题的重要工具建立数学模型的一般步骤①模型准备阶段②模型假设阶段③模型构成阶段④模型确定阶段问题抽象的思维过程问题的映射是将客观世界的问题求解映射到计算机中求解开发软件进行问题求解的过程实现问题域→建立模型→编程实现→到计算机世界执行求解的过程。问题的映射过程①将算法作用于特定的输入集或问题描述时，可导致有限步动作构成的动作序列。②该动作序列具有唯一的初始动作。③序列中的每一动作具有一个或多个后继动作。④序列或者终止于某一个动作，或者终止于某一个陈述。设计问题求解算法编写求解算法的程序程序调试或测试完成相关文档问题求解的实现循环（行）in=5个数两两比较循环（列）j比较次数（n–i）i：由1到4（n-1）第1轮初始排序数据表[563478219]j=1到44次第2轮第1轮两两比较4次后结果[3456219]78j=1到33次第3轮第2轮两两比较3次后结果[34219]5678j=1到22次第4轮第3轮两两比较2次后结果[219]345678j=11次

第4轮两两比较1次后结果[9]21345678

最后排序结果表[921345678]

数据有序排列——排序算法冒泡排序算法过程求出n=48770428433377171的一个真因子，一天之内交卷一人计算：顺序求解多人同时计算：并行计算并行处理技术的形式①时间并行，指时间重叠②空间并行，指资源重复③时间并行和空间并行，指时间重叠和资源重复的综合应用。国王婚姻问题——并行计算假设给定4个城市A、B、C、D相互连接，间距已知。由以下路径的总距离可以求出来：①路径ABCDA的总距离是：4.5+2.5+4.5+2.5=14.0②路径ABDCA的总距离是：4.5+6.0+4.5+5.5=20.5③路径ACBDA的总距离是：5.5+2.5+6.0+2.5=16.5④路径ACDBA的总距离是：5.5+4.5+6.0+4.5=20.5⑤路径ADBCA的总距离是：2.5+6.0+2.5+5.5=16.5⑥路径ADCBA的总距离是：2.5+4.5+2.5+4.5=14.0最优化方法用于研究各种有组织系统的管理问题及其生产经营活动，对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。旅行商问题——最优化思想ABCD4.52.54.55.56.02.503数与计算工具传统的计算工具算筹是世界上最古老的计算工具之一算筹在算板上按照需要排列形成筹式，同样的筹，所在的位置不同，表示的数也不同，这是十进制的思想算筹空表示0横排式：多位数：纵排式：数字：（a）算筹布袋

（b）算筹计数算盘是中国古代伟大发明之一珠算有完整、成熟的运算口诀，算盘是方便、实用的器械算盘计算尺由上下两条相对固定的尺身，中间一条可以移动的滑尺和可在尺上滑动的游标三部分组成计算尺除了对数刻度，还可以有其他数学函数刻度，如常用的三角函数、乘方、开方等，来实现复杂的运算计算尺A尺刻度1.26B尺刻度1A尺刻度4.30B尺刻度3.38A尺log(1.26)B尺log(3.38)传统的计算工具的计算能力和数据分析能力有限计算的自动化：1642年，法国科学家帕斯卡发明了加法器计算机的雏形查尔斯·巴贝奇（CharlesBabbage，1792—1871年）差分机设计闪烁出了程序控制的灵光差分机（a）查尔斯·巴贝奇

（b）1822年设计的差分机分析机：“存储库”和“运算室”奥欧古斯塔·爱达（AugustaAdaByron，1815—1852年）巴贝奇的分析机的设想可以说是现代通用计算机的雏形，同现代计算机一样可以编程分析机1834年设计的分析机机械式计算机器：1642年，法国科学家布莱斯·帕斯卡（BlaisePascal）乘法器：1674年，德国著名数学家莱布尼茨（GottfriedWilhelmLeibniz）手摇计算器：中国机械式计算器（a）中国制造的飞鱼牌机械式计算器

（b）国外制造的机械式计算器电子式计算器：采用集成电路的便携式电子式计算器既可以是硬件，也可以是开发出的软件计算器电子式计算器（a）硬件电子式计算器

（b）软件电子式计算器语言的发展中，逐渐有了数的概念最早的数的概念是“有”和“无”随着问题的复杂，把“有”逐步分解，产生数的概念数的起源原始的结绳计数计数、符号和数量阿拉伯数字由1、2、3、4、5、6、7、8、9、0十个符号组成，采用十进制计数法，笔画简单，书写方便20世纪初阿拉伯数字才在中国逐渐推广使用。阿拉伯数字中国人于公元前14世纪，发明了十进计数制，到了商朝，中国人就已经能够用0～9十个数字来表示任意大的自然数十进制在计算机科学和计算技术的发展中起了非常重要的作用中国人发明十进制计算机之父：冯·诺依曼（JohnvonNeumann，1903—1957年）EDVAC（ElectronicDiscreteVariableAutomaticCalculator，离散变量自动电子计算机）：1945年冯·诺依曼的两大设计思想二进制：在电子计算机中采用二进制计算机采用“存储程序和程序控制”工作原理通用电子计算机ENIAC：1946年ENIAC计算机ABC计算机：约翰·阿塔纳索夫（JohnVincentAtanasoff，1904—1995年）ABC计算机的电路系统中装有300个电子真空管执行数字计算与逻辑运算，机器使用电容器来进行数值处理，数据输入采用打孔读卡办法，还采用了二进制ABC计算机现代计算机的发展时代年份器件软件应用一1946—1956电子管、运算速度每秒几万次二进制机器语言、汇编语言科学计算二1957—1964晶体管、运算速度每秒300万次高级语言数据处理工业控制三1965—1969集成电路、运算速度每秒4000万次操作系统文字处理图形处理四1970年至今大规模和超大规模集成电路、运算速度每秒几亿次数据库、网络等社会的各个领域五1980年至今各种光学器件、光纤通信技术以及智能辅助设计系统智能化程序设计及系统、知识库系统所有领域六2000年至今超导、神经网络、生物辅助设计所有领域二进制：1679年，德国杰出的数学家莱布尼茨发明一种计算法，用两个数“0”和“1”代替原来的十位数二进制的特点：①只有两个数字“0”和“1”，从物理上讲更容易实现计数和存储，即数的表示和存储更容易②计算简单，对二进制进行算术运算的规则比十进制简单得多计算机采用晶体管实现二进制，其功能也就是：变换、逻辑运算和加法运算二进制莱布尼茨的逻辑原理①所有的观念或概念都是由非常小数目的简单观念复合而成的，它们形成了人类思维的方式②复杂的观念来自这些简单观念的组合布尔代数：1847年，英国数学家布尔发表了《逻辑的数学分析》数理逻辑布尔认为：逻辑中的各种命题能够使用数学符号来代表，并能依据规则推导出适当的结论两个逻辑值［“真（True）”“假（False）”］３种逻辑关系［“与（And）”“或（Or）”的二元运算，和“非（Not）”的一元运算］基础上的集合运算和逻辑运算克劳德·艾尔伍德·香农（ClaudeElwoodShannon，1916—2001年）：把布尔代数的“真（True）”与“假（False）”和电路系统的“开”与“关”对应起来，用1和0表示布尔代数1956年8月25日我国第一个计算技术研究机构─中国科学院计算技术研究所筹备委员会成立，著名数学家华罗庚任主任。2001年中国双院士、北京大学王选教授作为汉字激光照排系统的创始人和技术负责人获得国家最高科学技术奖。现代计算机在中国的发展年份计算机1958小型通用数字电子管计算机（103型）1964大型通用电子管计算机1964全晶体管计算机1971集成电路计算机目前，我国自主开发的“银河”、“曙光”、“深腾”、“神威”和“天河”等系列高性能计算机，取得了令人瞩目的成果。巨型机和超级计算机的研制、开发和利用代表着一个国家的经济实力和科学研究水平。以“联想”、“清华同方”、“方正”、“浪潮”等为代表的我国计算机制造业也非常发达，已成为世界计算机主要制造中心之一。微型机的研制、开发和广泛应用，标志着一个国家科学技术普及的程度。现代计算机在中国的发展现代计算机在中国的发展云超级计算机加快新药研发速度让天气预报更精准超级计算机在中国的发展04计算与信息社会互联网+是计算机系统网络化技术与其他技术相结合的产物，是信息社会与知识社会推动下由互联网发展产生的新业态。“互联网+”就是“互联网+各个行业”，但这并不是简单的两者相加，而是利用信息通信技术以及互联网平台，让互联网与传统行业进行深度融合，创造新的发展生态。互联网+技术的应用范围为互联网与其他传统产业，应用手段则是通过互联网与传统产业进行联合和深入融合的方式进行。互联网+作为一个整体概念，是指通过传统的计算机网络化技术完成产业升级。互联网+行业融合创新驱动重塑结构尊重人性开放生态连接一切互联网+的特征（1）运算速度快（2）存储容量大，保存时间长（3）计算精确度高（4）逻辑判断能力（5）自动工作的能力计算机的特点（1）科学和工程计算领域（2）数据处理领域（3）办公自动化领域（也称信息管理）（4）电子商务领域（5）自动控制领域（6）计算机辅助领域

（7）人工智能领域（8）计算机网络领域计算机系统的应用微型化大型化网络化智能化计算机系统的发展信息同物质、能源一样重要，是人类生存和社会发展的三大基本资源之一。信息（Information）是自然界、人类社会和人类思维活动中普遍存在的一切物质和事物的属性。广义地说，信息就是人类的一切生存活动和自然存在所传达出来的信号和消息。美国科学家香农1948年发表了著名的《通信的数学原理》一文，使得信息论从此诞生，香农也因此成为信息论的奠基人。信息的概念数据（Data）是指客观世界中记录下来的各种各样的物理符号及其组合，是信息的具体表现形式，反映了信息的内容。数据是信息的载体，数据中包含着信息。例如，数值、文字、声音、图形、图像、视频等都是可识别的不同形式的数据信息是指数据中有用的知识，需要去挖掘，即处理加工。信息既是各种事物的变化和特征的反映，又是事物之间相互作用和联系的表征。信息与数据当数据以某种形式经过处理、描述或与其他数据比较时，才能成为信息，而知识是指人类的认识成果。如规则等，表现为判断、推理、决策等包括事实、信息的描述或在教育和实践中获得的技能。可以是关于理论的，也可以是关