《《计算模型与计算机》课件》由会员分享，可在线阅读，更多相关《《计算模型与计算机》课件（67页珍藏版）》请在金锄头文库上搜索。
1、 大学计算机大学计算机 计算、构造与设计计算、构造与设计 西安交通大学西安交通大学 2 自底向上进行系统构造的基本思路和方法自底向上进行系统构造的基本思路和方法 自顶向下利用计算机求解问题的基本思路和方法自顶向下利用计算机求解问题的基本思路和方法 课程的主要教学目标： 何为会何为会 用计算用计算 机？机？ 3 我在小学就已经会用计算机了我在小学就已经会用计算机了，为什么为什么现在现在还要学呢还要学呢？ 这门课能教我些什么这门课能教我些什么？我基础比较弱我基础比较弱，能学懂吗能学懂吗？ 这这门课程门课程和我要学的其它计算机课程有什么关系和我要学的其它计算机课程有什么关系？ 为什么要学习“大学计算
2、机” 为什么学习“大学计算机” 你你或许或许已经能够：已经能够： 4 5 计算机为什么既能做数值计算计算机为什么既能做数值计算，还能处理各种各样像文字还能处理各种各样像文字、声音声音、图像图像 这样的信息这样的信息？ 为什么学习“大学计算机” 计算机为什么能计算机为什么能认识各种信息认识各种信息？它们在计算机它们在计算机中是怎么中是怎么表示和存放表示和存放的的？ 要用计算机解决问题需要做哪写工作要用计算机解决问题需要做哪写工作？怎样做怎样做？ 为什么会有计算机为什么会有计算机？它到底有多大能耐它到底有多大能耐？ 中小学中小学信息技术课程与大学计算机课程的区别信息技术课程与大学计算机课程的区别
3、中中、小学课程小学课程 讲是讲是什么什么？讲技能讲技能 大学课程大学课程 讲为什么讲为什么？讲思路讲思路、设计方法设计方法 6 为什么学习“大学计算机” 7 计算机的理论基础是什么计算机的理论基础是什么？怎样的构成怎样的构成？如何工作的如何工作的？ 引论引论 系统构造系统构造 计算机为什么能够认识各种信息计算机为什么能够认识各种信息，它们是如何表示的它们是如何表示的？ 信息表示信息表示 与编码与编码 “大学计算机”课程将带给你： 网络是怎么回事网络是怎么回事？网络上的信息是如何传送的网络上的信息是如何传送的？ 网络技术网络技术 及应用及应用 如何编写实现一些简单功能的程序如何编写实现一些简单功
4、能的程序？ 程序程序 设计设计 8 “大学计算机”课程将带给你： 什么样的问题是计算机不可做的什么样的问题是计算机不可做的？ 枚举法枚举法 枚举法的运算量枚举法的运算量是（是（n n- -1 1）！ 例：例：一个快递公司，要将一个快递公司，要将N N个客户的个客户的订货全部订货全部送到。如何确定送到。如何确定哪哪 条条路线最短？（路线最短？（旅行商问题）旅行商问题） 解决问题首先需要：解决问题首先需要： 建立解决问题的思路建立解决问题的思路、确定解决问题的方法确定解决问题的方法 确定确定 算法算法 课程教学内容组织 模块模块1 1 引言引言 模块模块2 2 信息表示与编码信息表示与编码 模块模
5、块3 3 系统软硬件构造系统软硬件构造 模块模块4 4 网络技术及应用网络技术及应用 模块模块5 5 C C语言程序设计语言程序设计 模块模块6 6 算法分析与设计算法分析与设计 9 本课程重点讲授：本课程重点讲授： 系统构造与基本原理系统构造与基本原理 程序设计程序设计 算法分析与实现算法分析与实现 大学计算机大学计算机 10 计算机程序设计计算机程序设计 微机原理与微机原理与 接口技术接口技术 计算机软件计算机软件 技术基础技术基础 网络技术及应用网络技术及应用 数据库技术数据库技术 计算机应用类课程计算机应用类课程 计算机系统组成 Personal Computer 12 计算机系统组成
6、计算机系统组成 计算机系统组成 计算机系统计算机系统 硬件系统硬件系统 软件系统软件系统 微型计算机主机板微型计算机主机板 15 主机板 芯片芯片 扩展插槽扩展插槽 对外接口对外接口 17 芯片芯片 CPUCPU，BIOSBIOS，控制芯片组等控制芯片组等 扩展槽扩展槽 内存插槽内存插槽，总线扩展槽等总线扩展槽等 接口接口 主机板 控制和协调计控制和协调计 算机系统各部算机系统各部 件的运行件的运行 基本输入输出基本输入输出 系统。功能：系统。功能： 自检，初始化，自检，初始化， 系统设置系统设置 图灵机与计算图灵机与计算问题问题 第第3 3讲讲 19 计算机是一种计算装置计算机是一种计算装置
7、 为什么能够发明出计算机？为什么能够发明出计算机？ 计算机的理论基础是什么？计算机的理论基础是什么？ 虽然虽然这里这里的的 “计算”“计算” 可可 能是广义的能是广义的 Alan Mathison Turing 英国英国著名数学家著名数学家和和逻辑学家逻辑学家 设计理论计算机设计理论计算机 计算与自动进行的机械操作联系在计算与自动进行的机械操作联系在一起一起 计算机计算机理论理论之父之父 20 ？ 图灵机模型 论文论文: :“论数字计算在决断难题中的应用论数字计算在决断难题中的应用” 给出给出“可计算性可计算性”的严格的数学定义的严格的数学定义 图灵机图灵机（TuringTuring Mach
8、ineMachine，TMTM） 用机器来模拟人们用笔和纸用机器来模拟人们用笔和纸进行运算进行运算的过程的过程 21 将计算与自动进行的机械操作联系在一起将计算与自动进行的机械操作联系在一起 图灵机模型 组成：组成： 一条无限长的纸带一条无限长的纸带TypeType 一个读写头一个读写头HeadHead 内部状态内部状态 一套控制规则一套控制规则TableTable。 22 BBX1X2XiXnBB读写头 （状态qi）图灵机模型 23 纸带纸带 单元格单元格 带符带符 3 3个动作：个动作： 改写当前格改写当前格 左移左移1 1格格 或右移或右移1 1格格。 包含一组固定的状包含一组固定的状
9、态和规则（程序）态和规则（程序） 图灵机工作条件图灵机工作条件： 输入输入带符的集合带符的集合 内部状态的集合内部状态的集合 一组控制规则一组控制规则 24 图灵机模型 工作状态取决于规则和内部状态工作状态取决于规则和内部状态 图灵机模型 图灵机的工作过程：图灵机的工作过程： 读写头从纸带上读出一个方格中的信息；读写头从纸带上读出一个方格中的信息； 根据内部状态查规则表根据内部状态查规则表TableTable（程序程序）； 确定输出动作确定输出动作选择以下三个动作之一：选择以下三个动作之一： 向纸带上写信息；向纸带上写信息； 使读写头向前移动一个方格；使读写头向前移动一个方格； 使读写头向后移
10、动一个方格使读写头向后移动一个方格。 说明下一时刻内部状态的变化说明下一时刻内部状态的变化。 25 图灵机模型 规则表：规则表： 26 当前内部状态当前内部状态S 输入数值输入数值i 输出动作输出动作O 下一时刻的内部状态下一时刻的内部状态S B 1 前移前移 C A 0 往纸带上写往纸带上写1 B C 0 后移后移 A 图灵机示例 设计计算设计计算“X+X+1 1”的图灵机的图灵机，要求计算结束后读写头回到要求计算结束后读写头回到 原位原位 题目分析：题目分析： TMTM的工作条件是：输入带符集合的工作条件是：输入带符集合，内部状态集合内部状态集合，一组控制规则一组控制规则 设：设：X=X=
11、5 5，采用采用0 0和和1 1表示表示。 设计：设计： 输入符号集合输入符号集合 =0，1，* 状态集合状态集合Q Q Start，add，carry，noncarry，overflow，return，halt 27 图灵机示例 ：控制器规则的集合：控制器规则的集合 28 输入输入 响应响应 当前状态当前状态 当前符号当前符号 新符合新符合 读写头移动读写头移动 新状态新状态 Start * * Left Add Add 0 1 Left Noncarry Add 1 0 Left Carry Add * * Right Halt Carry 0 1 Left Noncarry Carry
12、1 0 Left Carry Carry * 1 Left Overflow Noncarry 0 0 Left Noncarry Noncarry 1 1 Left Noncarry Noncarry * * Right Return overflow 0或1 * Right Return Return 0 0 Right Return Return 1 1 Right Return Return * * stay Halt 图灵机示例 设置读写头的起始位置在最右侧设置读写头的起始位置在最右侧，纸带上存储的内容为纸带上存储的内容为5 5 29 * 1 0 * 1 Start 图灵机示例 30
13、 * 1 0 * 1 Add 按照规则表，读写头按照规则表，读写头向左移动一格，状态变为“加”向左移动一格，状态变为“加” 输入输入 响应响应 当前状态当前状态 当当前前带带符号符号 新符号新符号 读写头移动读写头移动 新状态新状态 Start * * Left Add * 1 0 * 1 Start 图灵机示例 31 * 0 0 * 1 Carry 做加法，若当前方格中为内容为“做加法，若当前方格中为内容为“1 1”，则使其变为“”，则使其变为“0 0”，”， 然后读写头然后读写头向左移动一位，并有进位向左移动一位，并有进位。 输输 入入 响响 应应 当前状态当前状态 当当前前带带符号符号
14、新符号新符号 读写头移动读写头移动 新状态新状态 Start * * Left Add Add 1 0 Left Carry * 1 0 * 1 Add 图灵机示例 32 * 0 1 * 1 Noncarry 若当前状态为“若当前状态为“Carry”、方格中符号为“”、方格中符号为“0”，则使其变为”，则使其变为 “1”，然后读写头”，然后读写头向左移动一位，变为“无进位”状态向左移动一位，变为“无进位”状态。 输输 入入 响响 应应 当前状态当前状态 当当前前带带符号符号 新符号新符号 读写头移动读写头移动 新状态新状态 Start * * Left Add Add 1 0 Left Car
15、ry Carry 0 1 Left Noncarry * 0 0 * 1 Carry 图灵机示例 33 * 0 1 * 1 Noncarry 若当前状态为“若当前状态为“NoncarryNoncarry”、方格中符号为“”、方格中符号为“1 1”，则使其保”，则使其保 持“持“1 1”，读写头向左移动一位，状态不变”，读写头向左移动一位，状态不变。 输输 入入 响响 应应 当前状态当前状态 当当前前带带符号符号 新符号新符号 读写头移动读写头移动 新状态新状态 Start * * Left Add Add 1 0 Left Carry Carry 0 1 Left Noncarry Noncarry 1 1 Left Noncarry * 0 1 * 1 Noncarry 图灵机示例 34 * 0 1 * 1 Return 按规则表操作：按规则表操作： 输输 入入 响响 应应 当前状态当前状态 当当前前带带符号符号 新符号新符号 读写头移动读写头移动 新状态新状态 Start * * Left
