《《大学计算机基础》课件+第1章――自学完整版(2014_10_9)【OK】》由会员分享，可在线阅读，更多相关《《大学计算机基础》课件+第1章――自学完整版(2014_10_9)【OK】（278页珍藏版）》请在金锄头文库上搜索。
1、大学计算机基础 第1章自学版 北京航空航天大学计算机学院 2 课程目录 求解显示 交互 2学时 问题的抽象与建模 4学时 3 第1章计算机与计算思维 1 3为什么计算机能够计算 1 6计算机模型与计算思维 自学 1 2理论思维 实验思维和计算思维 1 1从图灵测试看思维 1 4计算机的理论模型与物理实现 1 5计算思维主要思维方法的案例 4 本课件说明 说明 本课件为 大学计算机基础 第1章中关于计算机基础知识的详细课件供同学们自学和参考 5 1 6计算机模型与计算思维 1 6 1图灵机模型1 6 2现代计算机模型1 6 3计算机之逻辑基础1 6 4信息在计算机中的表示1 6 5现代计算机系统
2、 6 1 6 1图灵机模型 计算机之所以能够计算 或者具备智能 其思维类比于人脑 语言单元 神经元单元 数字及其编码语言的关系 神经元的链接 数据结构 数据关系思维 神经元网络的自动链接 数据的模型和算法感知和动作 肢体和器官 计算机的输入和输出 我们如果能有一台机器 可以存储 可以运算 可以输入输出 那么 就可以具备计算的能力 我们来看看这个抽象的过程 图灵机模型 7 图灵其人 图灵其人阿兰 麦席森 图灵 AlanMathisonTuring 1912 1954 出生于英国伦敦 19岁入剑桥皇家学院 22岁当选为皇家学会会员英国数学家 逻辑学家 密码学家 计算机逻辑的奠基者 提出了 图灵机
3、TuringMachine 和 图灵测试 等重要概念1937年 提出了图灵机模型 这是图灵对人类的最大贡献1950年 发表了划时代的文章 机器能思考吗 成为了人工智能的开山之作被誉为 计算机科学之父 和 人工智能之父 计算机界于1966年设立了最高荣誉奖 ACM图灵奖 8 图灵机缘起 什么是计算 一个问题 1900年 德国数学家希尔伯特提出 23个数学难题 中 逻辑的完备性问题 即是否所有数学问题原则上都可解一篇文章 1937年 图灵发表 论可计算数及其在判定问题中的应用 OnComputableNumbersWithanApplicationtotheEntscheidungsProblem
4、 图灵给 可计算性 下了一个严格的数学定义 并提出著名的 图灵机 的设想 可解的问题是能够用 图灵机 的自动机理论模型表达的问题一个大神 图灵 1912 1954一个模型 可计算模型 9 图灵机模型 图灵的基本思想是用机器来模拟人们用纸笔进行数学计算的过程 根据计算需求在纸上写下相应的公式或符号 2 根据眼睛看到的符号 在脑中思考相应的计算方法 3 在纸上写上或擦除某个符号 4 把视线从纸的一个位置移动到另一个位置 5 转到第 2 步 重复以上步骤 直到认为计算停止为止在每个阶段 人要决定下一步的动作 依赖于 a 人当前所关注的纸上某个位置的符号 b 人当前思维的状态为了模拟人的这种数学计算过
5、程 图灵构造出一台假想的机器 图灵机 10 图灵机模型的组成 图灵机模型由3个部件组成无穷纸带 符号集合 两端可无限延长 纸带被分为一系列均匀的方格 每个方格中可填写一个来自有限字母表的符号读写头 读 改写 左移 右移 有穷控制器 有限状态机 拥有预定的有限个互不相同的状态 并能根据输入改变自身的状态 可控制读写头工作 11 图灵机模型是如何抽象的 图灵机模型是如何抽象的 将所有具体的输入 输出 转换细节抛弃 定义一个五元组图灵机是一个五元组 K s H 其中 K是有穷 有限 个状态的集合 是字母表 即符号的集合 s K 是初始状态 H K 是停机状态的集合 当控制器内部状态为停机状态时图灵机
6、结束计算 是转移函数 即控制器的规则集合 12 图灵机的工作原理 计算 x 1 的图灵机 图灵机的工作原理图灵机的计算 由控制器控制执行的一系列动作图灵机从纸带上的某个起始点出发 动作完全由初始状态和指令组决定其计算结果是从图灵机停止时纸带上的信息得到的 例1 计算 x 1 的图灵机目标 利用二进制设计一个专门计算 x 1 的图灵机 要求计算完成时 读写头回归原位x由0 1串组成 为x的分隔符 界定符 当纸带上有多个数时 用 将它们隔开 13 计算 x 1 的图灵机 首先进行抽象 确定图灵机五元组的内容状态集合K start add carry noncarry overflow return
7、 halt 字母表 0 1 初始状态s start停机状态集合H halt 规则集合 规则 如果A那么B 形式化表示为 A B 图灵机控制器的规则 控制器当前状态 读写头当前位置的符号 读写头写入新符号 读写头移动动作指示 控制器新状态 14 规则集合 1 2 3 4 5 6 7 8 9 步骤 15 5 1 的计算过程 1 初始状态 第1步完成后状态 第1步 16 5 1 的计算过程 2 第3步完成后状态 第2步 加1 新符号变成0 第2步完成后状态 加上进位 新符号变成1 第3步 17 5 1 的计算过程 3 第5步完成后状态 第4步完成后状态 第4步 第5步 18 5 1 的计算过程 4
8、第9步 停机 停止计算 运算结果 第8步完成后状态 停机状态 19 课后练习 给出计算 7 1 的图灵机运算过程 列出每一步的指令和指令完成后的状态 20 通用图灵机 图灵机本质是进行字符串的处理图灵机输入是一个字符串图灵机输出也是一个字符串如果将图灵机的有限个内部状态与读写头的有限个动作用字符串表示那么每条转换规则也可以用一个字符串表示 当前状态 当前符号 新符号 动作 新状态 图灵机可以由一个较长字符串完全表示 通用图灵机 满足这样一个有穷规则有限状态的可以对字符串处理的机器 就是计算机 而可描述成这样的科学问题 就是可以计算的 而其具体实现 则是冯 诺伊曼机 21 通用图灵机实现 5 1
9、 计算 1 例2 通用图灵机实现 5 1 计算 编码方案 22 通用图灵机实现 5 1 计算 2 3带通用图灵机M 图灵机输入字符串 00100001000000010010 对应 101 图灵机的所有规则 每个规则20位字符 当前状态 当前符号 新符号 动作 新状态 当前状态 0101对应start状态 利用编码描述的规则 01010010001000110110 23 通用图灵机实现计算的过程 发现了什么 计算过程与具体的编码方案和规则都不相关 意味着什么 程序可以重复执行 24 图灵机的思想 图灵机的思想图灵机不是具体的机器 而是一种思想模型 可制造一种十分简单但运算能力极强的计算装置
10、用来计算所有能想象得到的可计算函数 基本思想是用机器来模拟人们用纸笔进行数学运算的过程 10001110110 0110101 10001 0110101 由 程序 控制输入 转换 为输出 输入 输出 程序 通用机器 所谓计算就是计算者 人或机器 对一条两端可无限延长的纸带上的一串0或1 执行指令一步一步地改变纸带上的0或1 经过有限步骤 最后得到一个满足预先规定的符号串的变换过程 图灵机的计算 由控制器控制执行的一系列动作 25 图灵机的思想 Cont 图灵机的思想是数据 指令 程序及程序 指令自动执行的基本思想 输入被制成一串0和1的纸带 送入机器中 数据 如00010000100011
11、机器可对输入纸带执行的基本动作包括 翻转0为1 或 翻转1为0 左移一位 右移一位 停止 对基本动作的控制 指令 机器是按照指令的控制选择执行哪一个动作 指令也可以用0和1来表示 01表示 翻转0为1 当输入为1时不变 10表示 翻转1为0 当输入0时不变 11表示 前移一位 00表示 停止 输入如何变为输出的控制可以用指令编写一个程序来完成 如 011110110111011100 机器能够读取程序 按程序中的指令顺序读取指令 读一条指令执行一条指令 由此实现自动计算 26 图灵机引出的计算理论问题 图灵机引出的计算理论问题计算理论是研究使用计算机解决计算问题的数学理论有三个核心领域 自动机
12、理论 可计算性理论和计算的复杂性理论自动机是将离散数学系统的构造 作用和关系作为研究对象的数学理论 描述通用计算机计算能力的图灵机模型 可计算性理论的中心问题是建立计算的数学模型 进而研究哪些是可计算的 哪些是不可计算的计算的复杂性理论研究算法的时间复杂性和空间复杂性 27 图灵机引出的计算方法论问题 图灵机引出的计算方法论问题计算机学科的方法论有三个过程 抽象 理论和自动化设计及实现最根本的问题在于 问题如何进行描述 哪些部分能够被自动化 如何进行自动化描述 建立物理符号系统并对其实施等价变换是计算机学科进行问题描述和求解的重要手段 可行性 所要求的 形式化 及其 离散特征 使得数学成为重要
13、的工具而计算模型无论从方法还是工具等方面 都表现出它在计算机上科学中的重要作用 28 图灵机蕴含的计算思想 图灵机蕴含的计算思想 1 程序也是数据 x 1 图灵机功能是固定的 相当于一个程序通用图灵机的功能根据编码方案 主要是规则集合 的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上 M就按程序一步一步运行直到给出结果 结果也保存在存储带上 2 通用图灵机的所有规则构成指令集指令指示了操作的对象 当前符号 指令指示了待实施的操作 改写符号 移动读写头 29 图灵机蕴含的计算思想 Cont 3 通用图灵机模型是计算机的计算能力的极限因为 根据丘奇 图灵论题 Ch
14、urch Turingthesis 不能用图灵机完成的计算任务是不可计算的邱奇 图灵论题认为 如果某种方法 算法 可进行运算 那么该运算也可被图灵机执行 也可被递归定义的函数或 函数执行 4 计算机系统应该有 存储器 相当于存储带 中央处理器 控制器及其状态 并且其字母表可以仅有0和1两个符号为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户 计算机系统还应该有输入设备和输出设备如键盘 鼠标 显示器和打印机等 30 冯 诺依曼机对图灵机的实现 1944年 冯 诺依曼参与ENIAC研究小组1945年 在ENIAC基础上 冯 诺依曼等人提出了EDVAC设计方案 计算机的组成包括 运算器
15、控制器 存储器 输入和输出设备 31 1 6 2现代计算机模型 1 6 2 1冯 诺伊曼计算机的基本思想1 6 2 2冯 诺伊曼计算机的组成及其特点1 6 2 3冯 诺伊曼计算机的局限性1 6 2 4冯 诺伊曼计算机的改进 探索新的计算模型 自学 重点 32 需要思考的若干问题 请带着以下问题学习本节内容 1 冯 诺依曼机的基本思想是什么 冯 诺依曼机有哪些特点 2 冯 诺依曼机包括哪五大部件 其作用分别是什么 为什么计算机能够像人一样进行加减乘除各种算术运算 甚至能够进行各种逻辑运算 为什么计算机能够自动工作 3 以存储器为中心的结构与以运算器为中心的结构有何不同 4 冯 诺伊曼计算机的局限
16、性表现在哪几个方面 这几十年以来 人们是如何努力改进冯 诺伊曼计算机 探索新的计算模型的 33 1 6 2 1冯 诺伊曼计算机的基本思想 冯 诺伊曼其人约翰 冯 诺依曼 JohnVonNeuman 1903 1957 美藉匈牙利人 20世纪最重要的数学家之一 在现代计算机 博弈论和核武器等诸多领域内有杰出建树的最伟大的科学全才之一 电子计算机之父 博弈论之父 布达佩斯数学博士 先后执教于柏林大学和汉堡大学 历任普林斯顿大学 普林斯顿高级研究所教授 美国数学会主席 美国原子能委员会会员 美国全国科学院院士 34 冯 诺伊曼思想的提出 关于ENIAC1946年2月14日 世界第二台电子计算机ENIAC ElectronicNumericalIntegratorAndCalculator 电子数字积分计算机 音译埃尼阿克 在美国宾夕法尼亚大学诞生研制小组 埃克特 约翰 莫克利 赫尔曼 戈尔斯坦 亚瑟 博克斯17468只电子管 每秒5000次加法运算或400次乘法运算 运算速度是继电器计算机的1000倍并具有按事先编好的程序自动执行算术运算 逻辑运算和存储数据的功能体重30吨 占地170M2
