第7章 算法与计算思维.pptx

《第7章 算法与计算思维.pptx》由会员分享，可在线阅读，更多相关《第7章 算法与计算思维.pptx（25页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、课程主讲人：第7章 算法与计算思维智慧教育学院第7章 算法与计算思维目录CONTENTS03. 03. 典型算法设计典型算法设计04. 04. 计算思维基础计算思维基础01. 01. 算法基础算法基础02. 02. 算法的表示算法的表示7.1 算法基础l 什么是算法l 算法的性能评价l 算法的分类l 算法与程序的区别l 算法的特性什么是算法通俗的说，算法是对特定问题求解步骤的一种描述，是一组如何做某件事情的指令，是一组有序的动作。算法是处理解决问题的思路及办法，是程序的灵魂。欧几里得算法圆周率求解算法算法的分类数值型算法用于科学计算，其特点是少量的输入、输出，复杂的运算。例如，求解高次方程的近

2、似根、求函数的定积分等计算问题。例如圆周率的计算就属于数值计算算法。非数值型算法用于数据管理，其特点是大量的输入、输出，简单的算术运算和大量的逻辑运算。例如，对数据的排序、查找等算法。随着计算机技术的发展和应用面的普及，非数值计算算法涉及面更广，研究任务更为繁重。常见的图书检索、工资管理、库存管理等方面的应用都属于非数值计算算法。算法的特性五大特性能行性输入输出有穷性确定性算法的性能评价 正确性可读性健壮性时空复杂度1234算法与程序的区别算法可以被不同程序实现程序中的指令计算机可以执行，算法无此限制算法具有有穷性，程序不一定7.2 算法的表示l 自然语言l 伪代码l 传统流程图l 计算机语言

3、自然语言算法描述最简单的方法就是使用自然语言，只要将问题的求解步骤清晰的描述出来即可。在步骤描述上，要求语言简练、层次清晰。流程图流程图是一种用图框和流程线组成的图形，图框表示各种类型的操作，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序。伪代码伪代码是介于自然语言和计算机语言之间的、用文字和符号来描述算法的工具。伪代码不能被计算机理解，但接近某种语言编写的程序，便于转换为编程语言。根据编程语言的不同，有不同的描述语言。计算机语言只有用计算机语言编写的程序才能被计算机执行（当然还要被翻译成目标程序 ）。因此，最终还是要将它转换成计算机语言程序。用计算机语言描述算法必须严格遵循所选择

4、变成语言的语法规范。7.3 典型算法设计l 基本算法l 迭代l 穷举l 递归传统流程基本算法图求和、求积对一组数据进行累加或乘积运算1234最大值、最小值有很多问题需要求最大值和最小值。例如大奖赛评分问题， 需要求最高分和最低分。查找（顺序、二分）查找又称为检索，计算机最重要的应用之一就是在浩瀚的数据中找到用户需要的信息。排序（选择、冒泡）计算机科学中一个最普遍的应用是排序，即根据数据的值对它们进行排列，一个有序的数列更便于查找。插入排序、选择排序、冒泡排序等。穷举法举例概念穷举法穷举法正是利用了计算机的这一特性，并可以把这一特性发挥到极致。穷举法也叫枚举法，它的基本思想是根据题目的部分条件确

5、定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。例如中国古代的“百鸡问题”。假定小鸡每只0.5元，公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，问共有几种购鸡方案？迭代法举例概念迭代法迭代法也称为递推法，其基本思想是利用问题本身所具有的某种递推关系求解问题。在许多情况下，对求解问题不能归纳出简单的关系式，但在其前、后项之间却能找到某种普遍适用的关系。求解方程xex-1=0在0.5附近的解，可以利用牛顿迭代法来解方程：xn+1=xn - f(xn)/f(

6、xn)，这是著名的牛顿迭代公式，通过1n次不断地用切线代替曲线，接近f（x）=0时，当|xn+1-xn|（为要求的误差）时，我们认为xn+1就是要求的根。递归法举例概念递归法递归法是一个非常有趣且实用的算法设计方法。递推是从已知项的值递推出未知项的值，而递归呢？它则是从未知项的值递推出已知项的值，再从已知项的值推出未知项的值。如根据求n!的定义n!=n(n-1)!，进行求解。该定义可给出具体形式如下: 7.4 计算思维基础l 什么是计算思维l 计算思维的基本方法l 计算思维的特征l 计算思维应用案例什么是计算思维1理论思维23实验思维计算思维又称逻辑思维，是指通过抽象概括，建立描述事物本质的概

7、念，应用科学的方法探寻概念之间联系的一种思维方法。它以推理和演绎为特征，以数学学科为代表。理论源于数学，理论思维支撑着所有的学科领域。正如数学一样，定义是理论思维的灵魂，定理和证明是它的精髓，公理化方法是最重要的理论思维方法。又称实证思维，是通过观察和实验获取自然规律法则的一种思维方法。它以观察和归纳自然规律为特征，以物理学科为代表。实验思维的先驱是意大利科学家伽利略，被人们誉为“近代科学之父”。与理论思维不同，实验思维往往需要借助某种特定的设备，使用它们来获取数据以便进行分析。又称构造思维，是指从具体的算法设计规范人手，通过算法过程的构造与实施来解决给定问题的一种思维方法。它以设计和构造为特

8、征，以计算机学科为代表。计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们能借助计算机，逐步实现人工智能的较高目标。诸如模式识别、决策、优化和自控等算法都属于计算思维范畴。02计算思维的特征0103040506计算思维是根本的技能，不是刻板的技能计算思维是思想，不是人造物计算思维是面向所有的人，所有的领域计算思维是概念化思维，不是程序化思维计算思维属于人的思维方式，不是计算机的思维方式计算思维是数学和工程思维的互补与融合01020304计算思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个人们知道怎样解决的问题。计算思维是利用启发式推理寻求

9、解答，也即在不确定情况下的规划、学习和调度的思维方法。计算思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法。计算思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是一种基于关注点分离的方法。计算思维是一种选择合适的方式去陈述一个问题，或对一个问题的相关方面建模并使其易于处理的思维方法。计算思维是按照预防、保护及通过冗余、容错和纠错方式，从最坏情况进行系统恢复的一种思维方法。050607计算思维是利用海量数据来加快计算，在时间和空间之间，在处理能力和存储容量之间进行折中的思维方法。计算思维的方法计算思维应用案例1234这充分体现了计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法。奇偶校验缓存是将未来可能会被用到的数据存放在高效存储区域中，使得将来用到这些数据时能够非常迅速的获取。高速缓存并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。并行处理数据加密目前仍是计算机系统对信息进行保护的一种最可靠的办法。它利用密码技术对信息进行加密，实现信息隐蔽，从而起到保护信息的安全的作用。数据加密