第3章-计算机发展史和计算思维.ppt

计算机网络如何工作？为什么有些网站正常情况下无法访问，借助“翻墙软件”能访问？有什么风险？通过QQ传输文件时，为何速率总是在变？为什么有时候网页打不开，但QQ能上？上网输入账号和密码时，怎样输入最安全？通过FTP下载文件，系统如何保证传输过程中不出错？网上看视频时，需要保证传输完全正确吗？,第3章 计算机发展史和计算思维,3.1 计算机发展史3.2 计算思维,3.1 计算机发展史,3.1.1计算机的发展史3.1.2计算机的类型3.1.3计算机的发展趋势3.1.4计算机应用领域,3.1.1计算机的发展史,根据使用的主要元器件划分为四代。,3.1.2计算机的类型,中国超级计算机连续第七次荣登全球最快的超级计算机排行榜TOP500榜首第一名：神威太湖之光（中国）第二名：天河二号（中国）第三名：泰坦（美国）太湖之光：运算速度为天河二号的3倍，所有核心部件全国产化,3.1.2计算机的类型,神威太湖之光的中国芯 在25平方厘米的方寸之间，集成了260个运算核心，数十亿晶体管，达到了每秒3万多亿次计算能力。,3.1.2计算机的类型,3.1.2计算机的类型,3.1.2计算机的类型,3.1.2计算机的类型,3.1.2计算机的类型,3.1.2计算机的类型,3.1.3计算机的发展趋势,3.1.3计算机的发展趋势,3.1.3计算机的发展趋势,计算机网络,人工智能,量子计算机,3.1.4 计算机应用领域,计算机应用分为数值计算和非数值应用两大领域。科学计算（或称为数值计算）过程控制（或实时控制）信息管理（或称数据处理）（MIS）办公自动化(OA)辅助系统(CAD)电子商务(EC)电子政务(EG)人工智能(AI)虚拟现实（VR）,3.2计算思维,3.2.1 计算思维的提出3.2.2 计算和计算学科3.2.3 思维和科学思维3.2.4 计算思维,3.2.1 计算思维的提出,计算思维的提出2005年6月，美国总统信息技术咨询委员会(PITAC)给美国总统提交报告计算科学：确保美国竞争力该报告提出：虽然计算机本身是一门学科，但是其具有促进其他学科发展的作用。二十一世纪科学上最重要的、经济上最有前途的研究前沿都有可能通过熟练地掌握先进的计算机技术和运用计算机科学而得到解决。报告建议：将计算科学长期置于国家科学与技术领域中心的领导地位。,计算思维的提出,计算思维在中国2009年，中国至2050年信息科技发展路线图中对“计算思维”给予了足够的重视，认为计算思维的培育是克服计算机学科作为“狭义工具论”的有效途径，是解决其他信息科技难题的基础。,3.2.2 计算和计算学科,什么是计算提出如下几个问题：1）如何计算x2+2x-3=0的根（解）？2）有四个嫌疑人：a说：“我不是小偷。”b说：“c是小偷。”c说：“小偷肯定是d。”d说：“c冤枉人！”四人中有三人说的是真话，问到底谁是小偷？3）已知高考总分750分，张三考了550分。猜张三的高考成绩。每猜一次，提示高了还是低了。问：最少需要猜几次？,3.2.2 计算和计算学科,计算（computation）是算法的执行，即从包含算法和输入数据的初始状态开始，经过一系列的中间状态，直到达到最终的目标状态的过程。算法是由若干条指令组成的有穷序列。,3.2.2 计算和计算学科,什么是可计算和不可计算函数：一组可能的输入值和一组可能的输出值之间的映射关系。对于一个给定的输入，确定其具体输出的值，这一过程称为函数的计算。计算机科学的一个基本问题就是找到一种技术，并用其来计算用于求解问题的函数。如果一个函数，可以依据输入值和一定的计算步骤，来确定其输出值，则称其为可计算的，否则，就是不可计算的。,3.2.2 计算和计算学科,计算科学与计算学科从计算的角度来看，计算科学又称之为科学计算，是一种与数学建模、定量分析方法和采用计算机进行分析、解决科学问题的研究领域。从计算机的角度来说，计算科学是应用高性能计算能力预测和了解客观世界物质运动或复杂现象演化规律的科学，它包括数值模拟、工程仿真、高效计算机系统和应用软件等。,3.2.2 计算和计算学科,计算科学与计算学科计算学科的基本问题是“什么能被（有效地）自动执行”，讨论可行性的有关内容，包括：什么是可计算的，什么是不可计算的，如何保证计算的自动性、有效性和正确性。计算学科包括：计算机科学与技术和计算机科学与工程。,3.2.2 计算和计算学科,计算学科的三个学科形态：理论、抽象和设计。理论源于数学，其主要要素为定义、公理、定理、证明和结果。定义和公理：表达所研究对象的特征；定理：假设对象之间的基本性质和对象之间可能存在的关系； 证明：确定这些关系是否为真，最后得到相应的结果。理论是学科发展的数学支持。,3.2.2 计算和计算学科,计算学科的三个学科形态：理论、抽象和设计。抽象：抽出事物的本质特征，它是从现象中把握本质的认知过程和思维方法。抽象的结果：概念、符号。设计：采用工程科学的研究方法来开发或求解某个特定问题的系统和装备。计算学科中的3个学科形态是该学科中问题求解的3个过程，它们相互交织、相互影响。,3.2.3 思维和科学思维,什么是思维思维是人脑对现实事物的概括、加工，最终揭示其本质特征和内在规律的活动。人脑对信息的加工处理包括分析、抽象、综合、概括、对比等。思维的组成由思维原料（自然界）、思维主体（人脑）和思维工具（认识的反映形式）组成。思维是人类获得知识的途径，加工知识的机器。,3.2.3 思维和科学思维,什么是科学思维科学思维：在科学活动中的思维方式与表现形式，即形成并运用于科学认识活动、对感性认识材料进行加工处理的方式与途径的理论体系。科学思维就是人们认识自然界、社会和人类意识的本质和客观规律性的高级思维活动。科学思维的特点：比日常思维更具理性、客观性、严谨性、系统性与科学性。,3.2.3 思维和科学思维,科学发现三大支柱：理论科学，实验科学，计算科学。科学界一般认为，科学方法分为理论、实验和计算三大类，与三大科学方法相对的是三大科学思维：理论思维、实验思维和计算思维。,3.2.3 思维和科学思维,理论思维源于数学，以推理和演绎为特征，以数学学科为代表。实验思维以观察和总结自然规律为特征，以物理学科为代表。计算思维以设计和构造为特征，以计算机学科为代表。计算思维的根本问题是什么能被有效的自动进行。,3.2.4 计算思维,什么是计算思维计算思维的理解计算思维的特征计算思维的“十化”属性及关联计算思维的作用计算思维举例计算思维的应用,什么是计算思维,2006年3月，美国卡内基梅隆大学计算机系主任认为：计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及理解人类行为等涵盖计算机科学之广度的一系列思维活动。它是如同所有人都具备“读、写、算”（Reading, wRiting, and aRithmetic3R）能力一样，成为适合于每个人的一种普遍的认识和一类普适的技能。计算思维最根本的内容是抽象与自动化。,周以真教授,什么是计算思维,计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。抽象层次是计算思维中的一个重要概念。它使人们可根据不同的抽象层次，有选择地忽视某些细节，最终控制系统的复杂性。计算思维中的抽象最终是要能够利用机器一步步自动执行。为了确保机器的自动化，就需要在抽象的过程中进行精确和严格的符号标记和建模。,计算思维的理解,1）计算思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个人们知道怎样解决的问题。例如：为了有效地求解一个问题，我们可能要进一步问：一个近似解是否就够了？是否有更简便的方法？是否允许误报和漏报？,计算思维的理解,2）计算思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法。例如：评价一个程序时，不仅仅根据其准确性和效率，还有美学的考量；对于系统的设计，还要考虑简洁和优雅。,计算思维的理解,3）计算思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是一种基于关注点分离的方法（Separation of Concerns，简称SOC方法）。例如：选择合适的方式去陈述一个问题，或选择合适的方式对一个问题的相关方面建模使其易于处理；为预期的未来应用进行数据的预取和缓存设计。,计算思维的理解,4）计算思维是按照预防、保护及通过冗余、容错和纠错方式，从最坏情况进行系统恢复的一种思维方法。例如：对于“死锁”，计算思维就是学习、探讨在同步相互会合时如何避免“竞争条件”的情形。哲学家就餐问题,计算思维的理解,问题描述：五个哲学家(AE)围着一张圆桌就餐，每人面前有一盘通心粉。由于通心粉很滑，所以需要两只筷子才能夹住，但每两个盘子之间只放一只筷子。 哲学家只有两个动作：要么就餐，要么思考。而且他们之间从不交谈。 当一个哲学家饿了的时候，就拿起盘子左右两边的筷子开始就餐(不能同时拿起两只筷子)。就餐完以后，就把筷子放回盘子左右，继续思考。,死锁：假如每个人都拿着左边的筷子，则所有人都在等右边的筷子，谁都吃不了。,计算思维的理解,方法：拿着一只筷子等待另一只筷子的时间超过五分钟就放下手中的筷子，并且再等待五分钟之后进行下一次尝试。是否可行？情况：假如这五个人同时拿起左边的筷子，大家都在等另一只筷子，五分钟之后大家同时放下筷子。再过五分钟之后又同时拿起左边的筷子 解决办法？,计算思维的理解,哲学家就餐问题可以抽象成资源抢占问题，筷子就是“资源”。常用计算机技术：给资源“加锁”。一个资源同时只能供一个程序或者一段代码访问。当一个程序要使用的资源被另外一个程序锁定的时候，只能等待资源被解锁。死锁：当两个程序需要访问两个资源时，如果每个程序都锁了一个资源，那么两者都在等待对方解锁另一个资源的解锁，最后谁都无法执行。,计算思维的理解,方法一：服务生引入一个服务生，哲学家要经过服务生同意才能拿筷子，因为服务生知道哪只筷子在使用，他可以阻止死锁的发生。 解决死锁：只有当盘子左右的筷子都空闲的时候，服务生才会同意哲学家就餐，这样就不存在有人拿着一只筷子在等待另一只筷子的情况，也就杜绝了死锁的发生。,计算思维的理解,方法一：资源分级给五只筷子分级为15五个等级。 约定：每位哲学家在就餐拿筷子的时候，只能先拿级别比较低的筷子，然后才能拿级别比较高的。用餐完以后，先放下级别比较高的筷子，再放下编号比较低的。解决死锁：假如大家同时拿起一只筷子，那么级别最高的5号筷子一定还留在桌子上。此时哲学家A或者E就能拿起它凑成两只筷子开始进餐。进餐完以后放下筷子，其他哲学家又能进餐了,其他方法？,计算思维的理解,5）计算思维是利用启发式推理寻求解答，也即在不确定情况下的规划、学习和调度的思维方法。例如：采用各种搜索策略来解决实际问题。,计算思维的理解,6）计算思维是利用海量数据来加快计算，在时间和空间之间，在处理能力和存储容量之间进行折中的思维方法。例如：在数据压缩和解压缩过程中平衡时间和空间的开销。,计算思维的理解,生活中的示例：当你早晨上学时，把当天所需要的东西放进背包，这就是“预置和缓存”；当有人丢失自己的物品，你建议他沿着走过的路线去寻找，这就叫“回推”；在对自己租房还是买房做出决策时，这就是“在线算法”；在超市付费时，决定排哪个队，这就是“多服务器系统”的性能模型；为什么停电时你的电话还可以使用，这就是“失败无关性”和“设计冗余性”。由此可见，计算思维与人们的工作与生活密切相关，计算思维应当成为人类不可或缺的一种生存能力。,计算思维的特征,1）概念化，不是程序化。2）根本的，不是刻板的技能。3）是人的，不是计算机的思维方式。4）数学和工程思维的互补与融合。5）是思想，不是人造物。6）面向所有的人，所有地方。,计算思维的“十化”属性及关联,计算思维的作用,计算思维品质对人的能力影响作用。人的大脑思维方法和思维品质的差异决定着：同一问题解决办法和处理方式各不相同，其付出的代价与取得效果甚至可能天壤之别。例：二分查找法（或：折半查找法） vs 顺序查找法。,计算思维的作用,计算思维大大拓展了人类认知世界和解决问题的能力和范围。计算机的出现强化了计算思维的意义和作用，表现在：理论可以实现的过程变成了实际可以实现的过程；实现了从想法到产品整个过程的自动化、精确化和可控化；实现了自然现象与人类社会行为的模拟；实现了海量信息的处理和分析、复杂装置与系统的设计、大型工程的组织等。,计算思维举例,1）七桥问题18世纪著名古典数学问题之一。在哥尼斯堡的公园，有七座桥将普雷格尔河中两个岛及河岸连接起来。问是否可能从四块陆地中任何一块出发，恰好通过每座桥一次，再回到起点?,计算思维举例,欧拉于1736年证明上述走法是不可能的。问题分析：抽象：用点表示岛和陆地，两点之间的连线表示连接它们的桥，把七桥问题化成判断连通图能否一笔画的问题。连通图可一笔画的充要条件：奇点(通过此点弧的条数是奇数)的个数为0或2。七桥问题中各点的度：A(5),B(3),C(3),D(3)。原因？,计算思维举例,结论：（1）凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。（2）凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。（3）其他情况的图都不能一笔画出。,计算思维举例,2）囚徒困境“囚徒困境”是1950年美国兰德公司提出的博弈论模型。两个共谋犯罪的人被关入监狱，不能互相沟通情况。如果两个人都不揭发对方，则由于证据不确定，每个人都坐牢一年；若一人揭发，而另一人沉默，则揭发者因为立功而立即获释，沉默者因不合作而入狱五年；若互相揭发，则因证据确实，二者都判刑两年。最优解是什么？能否实现？,计算思维举例,由于囚徒无法信任对方，因此倾向于互相揭发，而不是同守沉默。 问题分析：最符合个体利益的“理性”选择。以A为例：若B揭发A：A也揭发B，获刑2年；A保持沉默，获刑5年；若B保持沉默：A揭发B，免刑；A也保持沉默：获刑1年。对A来说，不管B作何选择，揭发对方都最有利。由囚徒困境可知，公共生活中，如果每个人都从眼前利益、个人利益出发，结果会对整体的利益（间接对个人的利益）造成伤害。虽然囚徒困境本身只属模型性质，但现实中的价格竞争、环境保护等方面，也会频繁出现类似情况。,计算思维举例,汉诺塔问题印度古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针A、B和C。印度教的主神梵天在创造世界时，在其中一根针上从下到上地穿好了由大到小的64片金片。不论白天黑夜，总有一个僧侣在按下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有金片移到另外一根针上时，世界将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。,计算思维举例,问题：怎样移？移动次数f(N)等于多少？若A塔上只有一个金片(N=1)，直接从A塔移动到C塔，f(N)=1。N1。f(N)=?定义算法Hanio(N，A，B，C)功能：借助于B塔，将N-1个金片从A塔移动到C塔。,计算思维举例,第一步：把N-1个金片从A塔经过移动，叠放到B塔上。方法：Hanio(N-1，A，C，B)。过程：借助于C塔，将(N-1)个金片从A塔移动到B塔，A是源塔，B是目标塔。移动次数：f(N-1)。 第二步：将剩下的第N个金片(也就是最底下的一个)直接从A塔叠放到空着的C塔上。 移动次数：1。第三步：用第一步的方法，再次将B塔上的所有金片叠放到C塔上。方法：Hanio(N-1，B，A，C)。过程：借助于A塔，将(N-1)个金片从B塔移动到C塔，B是源塔，C是目标塔。 移动次数：f(N-1)。总移动次数：f(N)=2f(N-1)+1。,计算思维举例,递归算法。将Hanio(N，A，B，C)转化为三个子问题： Hanio(N-1，A，C，B)，单次移动，Hanio(N-1，B，A，C)。f(N)=2f(N-1)+1。f(64)=264-1=18446744073709551615次。如果每秒钟移动一次，共需多长时间呢？一年有31536000秒，则18446744073709551615次/31536000次/年=5849亿年。,计算思维举例,旅行商问题一位商人去n个城市推销货物，所有城市走一遍后，再回到起点，问如何事先确定好一条最短路线，使其旅行的距离最少。例如：其中：A、B、C、D分别代表4个城市，连线上的数字代表是相邻城市之间的距离。,计算思维举例,问题分析：4个城市，6条路线组合。路径ABCDA的距离：4+2+4+2=12。路径ABDCA的距离：4+6+4+6=20。路径ACBDA的距离：6+2+6+2=16。路径ACDBA的距离：6+4+6+4=20。路径ADCBA的距离：2+4+2+4=12。路径ADBCA的距离：2+6+2+6=16。,计算思维举例,问题分析：城市数目为4时，组合路径数为6；城市数目为n时，组合路径数为(n-1)!。随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至到达无法计算的地步，这就是所谓的组合爆炸问题。假如城市的数目增为20个，组合路径数则为(20-1)！1.2161017。若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。,计算思维的应用,1）用在实验和理论思维无法解决的问题。比如大量复杂问题求解、宏大系统建立、大型工程组织都可通过计算模拟：核爆炸、蛋白质生成、大型飞机、舰艇设计等等。例如：波音777飞机完全是采用计算机模拟测试的，没有经过风洞测试。,大型飞机设计和核爆炸模拟,计算思维的应用,2）计算思维不仅渗透到每个人的生活里，而且影响到了其他学科的发展，创造和形成了一系列的学科分支。比如计算生物学，计算化学，计算经济学、计算艺术学等等。（1）计算生物学。计算机科学许多领域渗透到生物信息学中的应用研究，包括数据库、数据挖掘、人工智能、算法、图形学、软件工程、并行计算和网络技术等都被用于生物计算的研究。 （2）计算化学。计算机科学在化学中的应用包括：化学中的数值计算、化学模拟、化学中的模式识别、化学数据库及检索、化学专家系统等。,计算思维的应用,（3）计算经济学。比如计算博弈论正在改变人们的思维方式。囚徒困境是博弈论专家设计的典型示例，可以用来描述两家企业的价格大战等许多经济现象。（4）计算机艺术学。这是科学与艺术相结合的一门新兴的交叉学科，它包括绘画、音乐、舞蹈、影视、广告、书法模拟、服装设计、图案设计、产品和建筑造型设计以及电子出版物等众多领域。此外计算思维影响的学科领域还有工程、社会、地质学、天文学、数学、医学、法律、娱乐、体育等。,习题,一、选择题1、计算机主要元器件采用晶体管的计算机被称为（ ）。A、第一代计算机 B、第二代计算机 C、第三代计算机 D、第四代计算机2、按使用器件划分计算机发展史,当前使用的微型计算机是（ ）。 A、集成电路 B、晶体管 C、电子管 D、超大规模集成电路3、计算机最早的应用领域是（ ）。 A、科学计算 B、数据处理 C、过程控制 D、CADCAMCIMS,B,D,A,习题,4、计算机辅助制造的简称是（ ）。 A、CAD B、CAM C、CAE D、CBE5、将计算机CAD与CAM技术集成，称为（ ）系统。 A、计算机辅助设计 B、计算机辅助制造 C、计算机集成设计 D、计算机集成制造6、在计算机应用中，“OA”表示（ ）。 A、决策支持系统 B、管理信息系统 C、办公自动化 D、人工智能,B,D,C,习题,7、下列不属于人类三大科学思维的是（ ）。 A、理论思维 B、逻辑思维