计算机与计算思维.ppt

1 大学计算机基础 计算机学院 计算机与计算思维 第一章 2 联系方式 StaffRoom 计算机学院208室Telephone 82312196 2016 O EMAIL luxiaofeng 上机时间 第5 15周 周二第7 8节地点 教八楼6楼计算机学院机房 3 计算机的发展 算盘中国唐代第一种手动式计数器计算尺1622年 英国WilliamOughtred 奥特瑞德 手动式 减 乘 除 指数和三角函数运算加法器1942年 法国BlaisePascal 帕斯卡 机械式 只能做加法计算器1673年 德国GottfriedLeibniz 莱布尼茨 机械式 加 减 乘 除和开方差分机1812年 英国CharlesBabbage 巴贝奇 分析机1834年 英国CharlesBabbage计算机1946年 宾夕法尼亚大学ENIAC 4 查尔斯 巴贝奇1812年差分机1834年分析机 差分机和分析机 计算机的直系祖先 三部分组成 1 由许多轮子组成的保存数据的存储库 2 运算装置 3 能对操作顺序进行控制 并选择所需处理的数据以及输出结果的装置 5 计算机科学奠基人英国科学家阿兰 图灵 电子计算机之父 美籍匈牙利数学家冯 诺依曼 阿兰 图灵和冯 诺依曼 美国计算机学会 ACM 1966年设立图灵奖 主要贡献 建立图灵机模型 奠定了可计算理论的基础提出图灵测试 阐述了机器智能的概念 主要贡献 与同事研制人类第二台计算机EDVAC 存储程序 概念冯 诺依曼计算机奠定了现代计算机体系结构和工作原理 姚期智2000 A N Kolmogorov1H Poincare2D Hilbert3VonNeumann5陈省身31Alan Turing68华罗庚90 6 电子计算机的问世 1946年2月由宾州大学研制的ENIAC电子计算机时代的到来 ElectronicNumericalIntegratorAndCalculator 电子数字积分计算机 重达30吨占地250m2启动工耗150000瓦18000个电子管 每秒5千次加减运算没有存储器采用十进制 7 国际TOP500组织6月23日公布了最新的全球超级计算机500强排行榜 中国 天河二号 获全球超级计算机500强三连冠 Top1 天河二号 中国 运算速度为每秒33 86千万亿次 国防科大 Top2 泰坦 美国能源部下属橡树岭国家实验室 每秒17 59千万亿次 Top3 红杉 美国劳伦斯 利弗莫尔国家实验室 每秒17 17千万亿次 Top4 京 日本理化研究所 每秒10 51千万亿次 富士通 Top5 米拉 美国阿尔贡国家实验室 每秒8 59千万亿次 LINPACK是线性系统软件包测试 天河二号每秒5 49亿亿次双精度浮点运算峰值速度每秒3 39亿亿次Linpack测试性能系统存储总容量相当于600亿册每册10万字图书 计算机对我们产生了什么影响 无处不在工作助手生活伙伴 最直观的感受 深刻影响着人们的思维方式影响着很多学科的研究和发展 事实上 8 1 1计算与计算科学 1 1 1计算与数字化 计算不再只和计算机有关 它决定着我们的生存 尼葛洛庞帝 数字化生存 该书成为了二十世纪九十年代纽约时报排行榜中的畅销书 9 计算已经改变了科学家们的思考方式 计算生物学改变着生物学家的思考方式 计算博弈理论改变着经济学家的思考方式 纳米计算改变着化学家的思考方式 计算物理学改变着物理学家的思考方式 数学机械化改变数学家的思考方式 社会计算改变着社会学家的思考方式等等 10 什么是计算 计算的本质是基于规则的符号串变换 更广义的说 计算是基于规则的物理状态的变换 1 3 4这样的数学运算可以说是我们最容易认同的计算 而将一段中文文章翻译成英文也就是计算 因为其实质是在保持语义不变的前提下 将一串中文符号变换成对应的英文符号 任何给定一定的输入 经过处理和变换 得到期望的输出的过程都可以称为计算 11 计算可以和广阔的专业领域结合 通过学科交叉与融合 迸发出前景广阔的研究空间 计算生物学应用数据分析及理论的方法 数学建模和计算机仿真技术 来研究生物学 行为学和社会群体系统 计算经济学运用计算思想分析和综合经济问题 进行问题分析 模型研究及决策 统计数据表明 计算思想在诺贝尔奖获奖理论中占到70 以上的比例 12 计算物理学是一门新兴的边缘学科 利用计算机大存储量和快速计算的有利条件 将物理学 力学 天文学和工程中复杂的多因素相互作用过程 通过计算机来模拟 如原子弹的爆炸 火箭的发射 以及代替风洞进行高速飞行的模拟试验等 目前 实验物理学 理论物理学和计算物理学已经步入一个三强鼎立的时代 13 社会计算学科根据社会科学理论 以计算技术为工具 研究人类社会的组成 关系 结构 层次 行为 运动等问题 研究社会媒体 促进社会人群的交流与合作 计算也在改变着人们的工作方式 数字化会议为分布于世界各地的公司提供远程会议支持 创造出天涯若比邻的工作场景 数字化制造使得在设备在没有制造出来之前 既可以通过仿真系统进行分析 通过虚拟装配进行模拟设备的装配 在对于效果满意之后再进行实际投产 14 1 1 2计算科学 计算科学是研究计算技术的一门科学 它具有促进其他科学门类发展的重要作用 计算技术发展到当今 其特征日益体现出以下特点 计算手段的器械化 计算过程的形式化 计算执行的自动化 计算对象的泛在化 15 计算过程的形式化是计算自动执行的前提 人们首先需要对于计算问题进行抽象 对其实现形式化的表示 其次 对于计算过程往往需要设计算法 并完成程序设计 最后由计算机进行程序运行而得到期望的处理结果 16 应用计算科学处理问题时是可能有误差的 误差的来源 可能来自于模型也可能来自于计算工具 17 计算科学的研究内容 计算科学的研究内容 算法可计算性算法的实现问题 18 算法是对计算机上执行的计算过程的具体描述 确定求解问题的算法是求解问题的关键步骤 19 算法举例 若m和n是两个正整数 并且m n时 求m和n的最大公因子的欧几里得算法可表示为 E1 求余数 以n除m得余数r E2 余数为0吗 若r 0 计算结束 n即为答案 否则转到步骤E3 E3 互换 把m的值变为n n的值变为r 重复上述步骤 依照这三条规则指示的步骤 可计算出任何两个正整数的最大公因子 20 21 例 求两个正整数m和n的最大公约数及最小公倍数 C语言实现 include stdio h voidmain intm n r M N intintGreatComDiv intLeaseComMul intGreatComDiv为最 大公约数 intLeaseComMul最小公倍数printf 请输入m和n的值 scanf d d 22 while r 0 利用辗除法 直到r为0为止 m n n r r m n intGreatComDiv n intLeaseComMul M N intGreatComDiv printf m和n的最大公约数是 d n intGreatComDiv printf m和n的最小公倍数是 d n intLeaseComMul 可以把计算过程看成执行这些步骤的序列 我们发现 计算过程是有穷的 而且计算的每一步都是能够机械实现的 机械性 23 可计算性是指一个实际问题是否可以使用计算机来解决一个可以使用计算机解决的问题应该被定义为 可以在有限步骤内被解决的问题 故哥德巴赫猜想这样的问题是不属于 可计算问题 之列的 因为计算机没有办法给出数学意义上的证明 不能期待计算机能解决世界上所有的问题 24 1 2计算思维 计算思维是运用计算机科学的基础概念进行问题求解 系统设计 以及人类行为理解的涵盖计算机科学之广度的一系列思维活动 计算思维的本质是抽象和自动化 如同所有人都具备 读 写 算 简称3R 能力一样 计算思维已经成为必须具备的科学思维能力 25 1 2 1科学思维 人类思维模式 艺术思维 宗教思维 科学思维 逻辑思维 实证思维 计算思维 26 科学思维模式大体上可以分为三种 1 以观察和归纳自然 包括人类社会活动 规律为特征的实证思维 2 以推理和演绎为特征的逻辑思维 3 以抽象化和自动化为特征的计算思维 27 实证思维 实证思维起源于物理学的研究 集大成者的代表是伽利略 开普勒和牛顿 开普勒是现代科学中第一个有意识地将自然观察总结成规律 并把这种规律表示出来 伽利略建立了现代实证主义的科学体系 强调通过观察和实验 实验是把自然现象单纯化 以保证可以仔细研究其中的一个局部 获取自然规律的法则 牛顿把观察 归纳和推理完美地结合起来 形成了现代科学大厦的整体框架 28 实证思维要符合三点原则 第一是可以解释以往的实验现象 第二是逻辑上自洽 即不能自相矛盾 第三是能够预见新的现象 即思维结论必须经得起实验的验证 29 逻辑思维 逻辑思维的研究起源于希腊时期 集大成者是苏格拉底 柏拉图 亚里士多德 他们基本构建了现代逻辑学的体系 以后又经过众多逻辑学家的贡献 例如莱布尼茨 希尔伯特等 使得逻辑学成为人类科学思维的模式和工具 30 逻辑思维也要符合一些原则 第一是有作为推理基础的公理集合 第二是有一个可靠和协调的推演系统 推演规则 任何结论都要从公理集合出发 经过推演系统的合法推理 得出结论 31 计算思维 计算思维是人类科学思维中 以抽象化和自动化 或者说以形式化 程序化和机械化为特征的思维形式 计算思维也是与人类思维活动同步发展的思维模式 但是计算思维概念的明确和建立却经历了较长的时期 32 计算思维中的抽象化与数学 逻辑思维 的抽象化有不同的含义 计算思维的抽象化不仅表现为研究对象的形式化表示 也隐含这种表示应具备有限性 程序性和机械性 因此 可以说形式化 程序化和机械化作为计算思维的特征 33 1 2 2计算思维 计算思维的标志是有限性 确定性和机械性 计算思维表达结论的方式必须是一种有限的形式 回想一下 数学中表示一个极限 是用一个自变量趋向于无穷来定义一个代数式的值 这种方式在计算思维中是不允许的 语义必须是确定的 在理解上不会出现因人而异 因环境而异的歧义性 必须是一种机械的方式 可以通过机械的步骤来实现 这三种标志是计算思维区别于其他两种思维的关键 34 应用计算思维对问题的处理方法是 通过问题的形式化表示 算法的构造 对于算法的执行而得到所期望的处理结果 35 例1 在一个高考成绩列表s1 s2 sn中查找考号为10011087的学生的成绩 问题分析 如何利用计算机来完成这样一个任务 36 把一个班级的学生信息存在计算机的存储器中 要求完成 用户从键盘上输入要查找的学生学号10011087 屏幕显示该学生的成绩 设计一个算法完成这个查找过程 那么这个算法的思想和人工查找是基本一致的 即逐个对比s1 s2 sn 如果其中某一个的学号值与key 10011087匹配 则查找成功 结束查找过程 如果所有的学号都不与key匹配 则说明没有要找的这个学生 称为查找失败 结束查找过程 37 例2 在一个按照学号升序排列的班级花名册s1 s2 sn中查找学号为1001的学生 分析 如果设计一个算法 在一个按照学号有序序列中完成查找指定的学号1001 设待查找的学号为key 我们仍然可以利用例1中的算法实现 然而 如果利用学生信息存储的有序性这一特点 我们可以设计一个效率更高的查找方法 称为二分查找 38 描述如下 Step1 设定三个变量 i j m 其中 i 1 j n m i j 2Step2 当i j成立时 重复执行以下步骤Step2 1如果key s m no 结束查找过程 查找成功 Step2 2如果keys m no i m 1 Step3 结束查找过程 查找失败 即无此学号的学生 39 本例可以看出 算法和数据的存储是具有紧密关系的 对数据的组织方式不同 算法的设计就可能不同 40 计算思维方式对解决的问题 往往需要经过问题的抽象化 问题的符号化表示 问题的求解算法 算法的实现这几个步骤 应用问题的解决是需要构造一个如上的算法 该算法的特点是必须在有限的步骤内结束 可以看出 算法往往具有机械性 重复性 而算法的每个步骤都是具有确定性的 算法针对一定数据组织的执行就可以得到有益的结果 41 计算思维也可以叫做构造思维 只是由于计算机的发展极大促进了这种思维的研究和应用 并且在计算机科学的研究和工程应用中得到广泛的认同 所以人们习惯地叫做计算思维计算思维是一直存在的一种固有科学思维方式 只是计算机的出现极大地促进了计算思维的应用 42 1 2 3计算机的出现强化了计算思维的作用 计算机的出现 给计算思维的研究和发展带来了根本性的变化 计算机所具有的对信息和符号的快速处理能力 使得许多原本只是理论可以实现的处理过程变成了可以实现的过程 例如 海量数据的处理 复杂系统的模拟 大型工程的组织等 借助计算机可以实现从想法到产品整个过程的自动化 精确化和可控化 大大拓展了人类认知世界和解决问题的能力和范围 43 研究一个问题如何变换成为能够用计算机求解的方式以及如何利用计算机解决问题 这是目前众多的学科领域的研究者需要思考的问题 44 1 2 4计算思维对其他学科的影响 在很长一段时间里 计算思维的研究是作为数学思维的一部分进行的 对于计算思维本身的认识和研究进展缓慢 主要的原因是计算思维考虑的可构造性和可实现性 而相应的手段和工具的研究进展缓慢 45 使用计算思维考虑和陈述问题 已经成了越来越熟悉和普遍的事实 计算思维成为一个现代人所必须具备的素质 计算思维是21世纪每一个人都要用的基本工具 它将会像数学和物理那样成为人类学习知识和应用知识的基本组成和基本技能 46 智能交通控制 天气预报 疾病的流行趋势分析与控制 计算生物学等等众多领域的研究者都在其研究工作中运用着计算思维 47 1 3计算机科学 1 3 1计算机科学计算机是一种进行算术和逻辑运算的机器 其处理的对象都是信息 因而也可以说 计算机科学是研究信息处理的科学 计算机科学 ComputerScience 缩写为CS 是系统性研究信息与计算的理论基础 以及它们在计算机系统中如何实现与应用的学科 48 计算机科学包含很多分支领域 其中 计算机图形学强调特定结果的计算 计算复杂性理论是研究计算问题的性质 还有一些领域专注于挑战怎样实现计算 比如 程序设计语言理论描述计算的方法 而程序设计是应用特定的程序设计语言解决特定的计算问题 人机交互则是专注于怎样使计算机和计算变得有用 可用 以及随时随地为人所用 49 计算机科学的研究内容 主要包括理论计算机科学 计算机系统结构 软件工程和人工智能 50 理论计算机科学是研究计算机自身理论的科学 二十世纪40年代电子计算机出现后 关于现实计算机及其程序的数学模型性质的研究以及计算复杂性的研究迅速发展起来 形成自动机理论 形式语言理论 程序设计理论 算法设计与分析和计算复杂性理论几个领域 自从二十世纪50年代以来 计算机的性能在计算速度和编址空间方面已提高了几个数量级 但这些性能上的提高基本都是通过元件更新而获得的 在计算机的系统结构方面基本上仍是属于40年代后期形成的存储程序型 即所谓冯诺伊曼型机器 51 存储程序结构 冯诺伊曼型机器 的主要特点是它属于控制流型 在这种结构中 一项计算先做什么后做什么是事先确定了的 程序中指令的顺序是事先确定了的 为了在计算机的性能方面取得大的进展 需要突破这种旧的形式 然而 这种突破仍然在研究阶段 52 软件工程和程序设计方面的研究工作 在相当长的时间内 是一种类似 手艺 而不是类似现代工程的技术 二十世纪60年代以来 程序的规模越来越大 随着程序的复杂性增加 这些大程序的可靠性很难保证 到60年代后期 西方国家出现了 软件危机 软件危机指有些程序过于庞大 包含几十万条以至几百万条指令 软件开发成本过高 而可靠性则比较差 于是 在计算机科学领域一个重要的研究课题是软件工程问题 软件工程的思想是使软件开发遵守严格的规范 使用一套可靠的方法 从而保证软件质量 现代软件工程的重要方向是形式化和自动化 而形式化的目的在于自动化 53 1 3 2计算机科学与其他学科的交叉与融合 计算机科学的发展给其他学科的科学研究工作带来了巨大的变化 使得学科的交叉和融合对于人类的科学进步产生巨大的影响 我们以人工智能为例 说明计算机科学与其他学科的融合所迸发出的广阔研究兴趣 以及对相关学科产生的巨大推动力 54 什么是人工智能 如果机器能够完成这些任务的一部分 那么就可以认为机器已经具有某种程度的 人工智能 人工智能是用计算机模拟人的智能 特别是模拟思维活动的技术及其有关理论 图灵测试2014 55 人工智能应用系统已经成为计算机科学与众多研究领域交叉融合的产物 1 问题求解系统人工智能最早的尝试求解智力难题和下棋程序 后者又称博弈 另一种问题求解程序是将各种数学公式符号汇编在一起 搜索解答空间 寻求较优的解答 56 2 自然语言理解和处理系统语言处理一直是人工智能研究的热门方向之一 人们很早就在开始研制语言翻译系统 LanguageTranslationSystem 早期的自然语言理解多采用键盘输入自然语言 现在已经开发出文字识别和语言识别系统 能够配合进行书面语言和有声语言的识别与理解 现在已有智能翻译系统 你可对它说话 它能将你说的话打印出来 并且可以用另一种语言表示出来 57 演示 3 智能控制 智能系统和智能接口智能控制 IntelligentControl 是一类无需或者尽可能少的人工干预就能够独立的驱动智能机器实现其目标的自动控制 它采用AI ArtificalIntelligent 理论及技术与经典控制理论 频域法 现代控制理论 时域法 相结合 研制智能控制系统的方法和技术 它是AI与控制论以及工程控制论等科学相结合的产物 智能系统 IntelligentSystem 的含义非常广泛 通常它指配备有智能化软 硬件的计算机控制系统或计算机信息系统 在AI中 智能化的软 硬件计算机控制系统指具有问题求解和高层决策功能的一些学习控制系统 如拟人控制系统 自主机器人控制系统 人 机结合控制系统 58 上述领域里的典型系统有 1 监管系统 SupervisorySystem 现在大的办公楼和商业大厦变得愈来愈复杂 监管系统可以帮助控制能源 电梯 空调等 并进行安全监测 计费 顾客导购等 2 智能高速公路 这也是一种智能监控系统 它能优化已有高速公路的使用 通过广播交通的警告 将大量的车辆导向可代替的路线 控制车流的速度与空间 帮助选择出发点到目的地的最优路线 演示 3 银行监控系统 AmericanExpress是美国一家大的银行公司 用户信用卡的使用每年由于恶性透支和欺骗行为损失1亿美元 需要解决的问题是 如何在短时间内判断是否允许顾客使用他的信用卡 一般 需要一个系统在90秒内给出判断 59 4 智能调度和规划系统智能调度和规划系统能够确定最佳调度或组合方案 这类系统已被广泛应用于汽车运输调度 列车的编组与指挥 空中交通管制以及军事指挥等系统 例如 1 空中交通控制系统 随着航空事业的发展 一个大型机场每天控制 管理成千架飞机的起降 导航 人工控制很难 空中交通控制系统能够帮助安排飞机的起降 以最大限度保证安全和最小的延迟时间 60 2 军事指挥系统现代军事指挥离不开计算机科学的支持 如果没有基于先进计算机技术的军事指挥系统 那么军官就变成了瞎子 军事指挥也就变成了瞎指挥 61 5 模式识别系统模式识别 PatternRecognition 是AI最早和最重要的研究领域之一 模式是一个内涵极广的概念 广义地讲 一切可以观察其存在的事物形式都可称为模式 如图形 景物 语言 波形 文字和疾病等都可视为模式 62 模式识别的广义研究目标是指应用电子计算机及外部设备对某些复杂