计算学科中的基本概念

《计算学科中的基本概念》由会员分享，可在线阅读，更多相关《计算学科中的基本概念（234页珍藏版）》请在装配图网上搜索。

1、 b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql 计 算 结 果 是 10100011， 即 对 给 定 的 数 加 1。 b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql 以 上 命 令 计 算 的 是 这 样 一 个 函 数 ： S(x) x 1。当 没 有 输 入 时 ， 即 初 始 状 态 所 指 的 方 格 为 空 格（ b） 时 ， 不 改 变 空 格 符 ， 读 写 头 不 动 并 停 机 。 o第 一 ， 把

2、 图 灵 机 看 作 识 别 器 ， 即 判 断 带 子 上 最初 的 内 容 能 否 被 图 灵 机 所 接 受 。 假 定 图 灵 机 从左 向 右 扫 描 完 带 子 上 的 内 容 后 停 机 则 为 接 受 ，否 则 为 不 接 受 。o 例 2 一 台 图 灵 机 可 以 设 计 成 识 别 下 面 的 序 列 ： 1000110, 10011101, 010101011。 o第 二 ， 把 图 灵 机 看 作 生 成 器 ， 对 给 定 的 输 入 集合 ， 考 察 输 出 集 合 ， 并 研 究 输 入 输 出 集 合 性 质之 间 的 关 系 ， 这 就 研 究 了 图 灵

3、机 的 生 成 能 力 。o 例 3 设 一 台 图 灵 机 的 输 入 集 合 为 In1n0nn N， 可 设 计 一 台 图 灵 机 ， 对 给 定 的输 入 集 合 In， 得 到 输 出 集 合 Out0n1nn N。 其 中 ， N是 全 体 自 然 数 的 集 合 。 o第 三 ， 把 图 灵 机 看 作 计 算 器 ， 相 当 于 一 个 函 数 。图 灵 机 的 输 入 是 函 数 的 自 变 量 的 值 ， 图 灵 机 的输 出 是 函 数 的 值 。 例 4 图 灵 机 可 以 计 算 下 列 函 数 ： (1) s(x) x 1； (2) o(x) 0； (3) A(0

4、， y) y 1， A(x 1， 0) A(x， 1)， A(x 1， y 1) A(x， A(x 1， y)。 o第 一 和 第 二 个 函 数 读 者 不 难 从 图 灵 机 的 定 义 出发 感 悟 到 它 们 是 图 灵 机 可 以 计 算 的 函 数 ， 而 第三 个 函 数 就 比 较 复 杂 ， 一 时 难 于 判 断 。 顺 便 提一 下 ， 第 三 个 函 数 叫 做 阿 克 曼 函 数 ， 它 是 阿 克曼 （ W.Ackermann） 在 研 究 原 始 递 归 函 数 和递 归 函 数 的 关 系 时 给 出 的 。 这 个 函 数 在 计 算 理论 中 具 有 重 要

5、 价 值 。o事 实 上 ， 图 灵 机 还 可 以 计 算 形 式 上 比 第 三 个 函数 更 复 杂 的 函 数 。 n n-1 1 0 -1-m+1 -m其 中 ， 10称 为 十 进 制 的 基 数 ,ki 0,1,2,3,4,5,6,7,8 9， m， n为 正 整 数 。 小 数 点 的 位 置 不 言 自 明 。 S knkn-1 k0. k-m kn 2n kn-1 2n-1 k0 20 k-m 2-m -m ki 2i i n 其 中 ， 2称 为 二 进 制 的 基 数 ， ki 0,1,m,n为 正 整 数 。 进 一 步 ， 读 者 可 从 十 进 制 数 和 二 进

6、 制 数 的 一 般 表 示公 式 得 到 启 发 ， 将 这 种 表 示 推 广 到 更 一 般 的 任 意 进 制 ，不 同 之 处 只 是 基 数 不 一 样 。 二 进 制 的 运 算 规 则 比 十 进 制 的 运 算 规 则 简单 得 多 。 只 要 建 立 两 种 进 制 的 数 据 之 间 的 转 换方 法 ， 那 么 ， 二 进 制 将 具 有 更 多 的 优 势 。 计 算机 的 理 论 基 础 是 逻 辑 和 代 数 。 当 二 进 制 与 同 样只 使 用 “ 真 ” 和 “ 假 ” 两 个 值 的 逻 辑 代 数 建 立了 联 系 后 ， 这 就 为 计 算 机 的

7、逻 辑 设 计 提 供 了 便利 的 工 具 。 图 灵 机 的 出 现 为 现 代 计 算 机 的 发 明 提 供 了重 要 的 思 想 。 图 灵 机 的 带 子 可 以 看 成 是 计 算 机的 存 储 设 备 ， 数 据 可 以 存 储 在 上 面 ， 也 可 以 根据 需 要 擦 去 。 图 灵 机 的 命 令 相 当 于 一 组 事 先 设计 、 存 储 好 了 的 程 序 ， 它 们 在 控 制 器 安 排 下 ，决 定 读 写 头 的 每 一 步 操 作 。 这 样 一 种 数 学 机 器 ，如 果 不 考 虑 它 的 实 用 性 ， 就 思 想 和 原 理 而 言 ，确 实

8、包 含 了 存 储 程 序 的 重 要 思 想 。 存 储 器 运 算 器 控 制 器 输 入 /输 出 设 备 命 令 寄 存 器 “ 与 ” 、 “ 或 ” 、 “ 非 ” 三 种 门 电 路 示 意 图 P P P A B C A B C A （ a） （ b） （ c） o 用 计 算 机 求 解 一 个 问 题 ， 必 须 事 先 编 制 好 程 序 。 程序 是 由 指 令 组 成 的 。 每 一 台 计 算 机 都 设 计 规 定 了 一组 指 令 集 合 ， 称 为 机 器 指 令 系 统 。o 机 器 指 令 的 格 式 一 般 分 为 两 部 分 ， 如 下 所 示 ： 指

9、 令 格 式 ： 操 作 码 地 址 部 分 其 中 ， 操 作 码 指 出 运 算 的 种 类 ， 如 ， ， ， ， 跳 转 等 ， 地 址 部 分 用 来 指 示 参 与 运 算 的 数 据 保存 在 什 么 地 方 ， 如 存 储 器 的 某 个 地 址 或 某 个 寄 存 器等 。 操 作 码 和 地 址 部 分 都 用 二 进 制 代 码 表 示 。 o机 器 指 令 一 般 可 根 据 其 功 能 划 分 为 以 下 几 类 ： (1)控 制 指 令 ； (2)算 术 运 算 指 令 ； (3)逻 辑运 算 指 令 ； (4)移 位 操 作 指 令 ； (5)传 送 操 作指 令

10、 ； (6)输 入 /输 出 指 令 。o应 当 注 意 的 是 ， 不 同 的 机 器 ， 其 指 令 系 统 是不 同 的 。o指 令 系 统 的 日 渐 增 大 虽 然 给 用 户 的 程 序 设 计带 来 了 方 便 ， 但 也 带 来 了 硬 件 设 计 复 杂 性 的增 加 和 因 译 码 、 存 储 、 寻 址 等 开 销 的 增 大 而使 运 算 速 度 下 降 。 研 究 发 现 ， 指 令 系 统 存 在着 改 进 的 必 要 和 可 能 。 RISCo思 路 主 要 是 通 过 减 少 指 令 总 数 和 简 化 指 令 的功 能 来 降 低 硬 件 设 计 的 复 杂

11、度 ， 从 而 提 高 指令 的 执 行 速 度 。o优 点 :与 CISC技 术 相 比n 简 化 了 指 令 系 统 ， 适 合 超 大 规 模 集 成 电 路的 实 现 ；n 提 高 了 机 器 执 行 的 速 度 和 效 率 ；n 降 低 了 设 计 成 本 ， 提 高 了 系 统 的 可 靠 性 ；n 提 供 了 直 接 支 持 高 级 语 言 的 能 力 ， 简 化 了编 译 程 序 的 设 计 。 机 器 指 令o机 器 指 令 系 统 每 台 数 字 电 子 计 算 机 在 设计 中 ， 都 规 定 了 一 组 指 令 。o机 器 语 言 用 机 器 指 令 形 式 编 写 的

12、 程 序 。o在 裸 机 级 ， 计 算 机 语 言 关 于 算 法 的 描 述 采 用的 是 实 际 机 器 的 机 器 指 令 ， 它 的 符 号 集 是 0，1，n 支 撑 实 际 机 器 的 理 论 是 图 灵 机 等 计 算 模 型 ；n 在 图 灵 机 等 计 算 模 型 理 论 的 指 导 下 ， 有 关设 计 形 态 的 主 要 成 果 有 冯 诺 依 曼 型 计 算 机等 具 体 实 现 思 想 和 技 术 ， 以 及 各 类 数 字 电子 计 算 机 产 品 。 计算机语言抽象理论设计裸 机级 的主 要内 容和 成果 语 言 的 符号 集 为 ：0， 1；用 机 器 指令

13、对 算 法进 行 描 述 图 灵 机 （ 过 程 语言 的 基 础 ） 、 波斯 特 系 统 （ 字 符串 处 理 语 言 的 基础 ） 、 -演 算（ 函 数 式 语 言 的基 础 ） 等 计 算 模型 冯 诺 依曼 型 计 算机 等 实 现技 术 ；数 字 电 子计 算 机 产品 汇 编 语 言o汇 编 语 言 实 际 上 是 由 一 组 汇 编 指 令 构 成 的 语言 。 每 一 条 汇 编 指 令 用 某 个 西 文 字 符 串 的 缩写 来 表 示 其 所 代 表 的 操 作 ， 用 符 号 来 代 表 数据 的 二 进 制 、 八 进 制 和 十 进 制 数 字 序 列 。 大多

14、 数 情 况 下 ， 一 条 汇 编 指 令 对 应 一 条 机 器 指令 ， 少 数 对 应 几 条 机 器 指 令 。 例 如 ， 下 面 是几 条 汇 编 指 令 的 操 作 符 ， 右 边 中 文 是 名 称 。 add 加 法 idiv 有 符 号 除 法 mul 无 符号 乘 法 neg 求 补 xchg 交 换 test 逻 辑 比 较 jmp 无 条 件 转 移 汇 编 语 言o当 然 ， 汇 编 语 言 在 可 读 性 和 编 写 程 序 时 仍 然是 不 能 令 人 满 意 的 ， 这 导 致 进 一 步 发 展 了 高级 程 序 设 计 语 言 。 不 过 ， 由 于 高

15、 级 语 言 在 使用 时 通 常 还 是 要 通 过 编 译 程 序 逐 步 将 高 级 语言 写 的 程 序 翻 译 成 机 器 指 令 的 程 序 ， 而 这 种翻 译 的 结 果 往 往 不 如 机 器 指 令 或 汇 编 语 言 写的 程 序 效 率 高 ， 所 以 ， 直 到 今 天 ， 不 少 工 程师 在 系 统 软 件 的 开 发 中 还 在 使 用 机 器 指 令 和汇 编 语 言 。 求 解 一 个 给 定 的 问 题 ， 不 同 的 人 常 编 写出 不 同 的 然 而 都 是 正 确 的 程 序 ， 这 是 为 什 么呢 ？ 这 里 存 在 两 个 层 面 的 问 题

16、 ， 一 个 是 与 计算 方 法 密 切 相 关 的 算 法 问 题 ， 另 一 个 是 程 序设 计 的 技 术 问 题 。 o不 难 想 象 ， 不 同 的 求 解 方 法 将 产 生 出 不 同 的算 法 ， 不 同 的 算 法 将 使 我 们 设 计 出 不 同 的 程序 ， 而 决 定 这 个 程 序 功 能 的 本 质 是 计 算 方 法及 其 算 法 。 一 般 地 说 ， 对 不 同 计 算 方 法 过 程的 抽 象 描 述 就 产 生 了 相 应 的 不 同 算 法 ， 但 同一 算 法 由 不 同 的 人 来 写 程 序 则 完 全 可 能 设 计出 差 别 很 大 的

17、程 序 。o凭 直 觉 想 象 给 出 的 算 法 往 往 不 是 最 好 的 算 法 。 算 法 被 认 为 是 计 算 科 学 的 核 心 问 题 之 一 。 o 定 风 1： 给 定 问 题 和 设 备 ， 一 个 算 法 是 用 该 设 备 可理 解 的 语 言 表 示 的 ， 解 决 这 个 问 题 的 一 种 方 法 的 精确 刻 划 。 特 别 ， 算 法 具 有 下 列 特 征 属 性 ： (1) 算 法 应 用 于 一 个 具 体 的 输 入 集 合 或 问 题 描 述将 在 有 穷 步 动 作 序 列 之 后 得 到 结 果 ； (2) 该 序 列 有 一 个 唯 一 的

18、初 始 动 作 ； (3) 该 序 列 中 的 每 一 个 动 作 有 一 个 唯 一 的 后 继 动作 ； (4) 该 序 列 终 止 时 或 者 得 到 这 个 问 题 的 解 ， 或 者因 该 问 题 不 可 解 而 获 得 不 可 解 说 明 。 o 定 风 1： 给 定 问 题 和 设 备 ， 一 个 算 法 是 用 该 设 备 可理 解 的 语 言 表 示 的 ， 解 决 这 个 问 题 的 一 种 方 法 的 精确 刻 划 。 特 别 ， 算 法 具 有 下 列 特 征 属 性 ： (1) 算 法 应 用 于 一 个 具 体 的 输 入 集 合 或 问 题 描 述将 在 有 穷

19、步 动 作 序 列 之 后 得 到 结 果 ； (2) 该 序 列 有 一 个 唯 一 的 初 始 动 作 ； (3) 该 序 列 中 的 每 一 个 动 作 有 一 个 唯 一 的 后 继 动作 ； (4) 该 序 列 终 止 时 或 者 得 到 这 个 问 题 的 解 ， 或 者因 该 问 题 不 可 解 而 获 得 不 可 解 说 明 。 定 义 2（ Knuth算 法 定 义 ） 一 个 算 法 ， 就 是 一 个 有 穷 规 则 的 集 合 ， 其 中 之 规 则确 定 了 一 个 解 决 某 一 特 定 类 型 问 题 的 运 算 序 列 。 此 外 ，算 法 的 规 则 序 列

20、须 满 足 如 下 五 个 重 要 条 件 （ 特 性 ） ： (1) 有 穷 性 。 算 法 必 须 总 是 在 执 行 有 穷 步 之 后 结 束 ； (2) 确 定 性 。 算 法 的 每 一 个 步 骤 必 须 是 确 切 地 定 义的 ； (3) 输 入 。 算 法 有 零 个 或 多 个 输 入 ； (4) 输 出 。 算 法 有 一 个 或 多 个 输 出 ， 即 与 输 入 有 某个 特 定 关 系 的 量 ； (5) 能 行 性 。 算 法 中 有 待 执 行 的 运 算 和 操 作 必 须 是相 当 基 本 的 ， 即 是 说 ， 它 们 原 则 上 都 是 能 够 精 确

21、 地 进 行的 ， 而 且 用 笔 和 纸 做 有 穷 次 就 可 以 完 成 。 nH n 1312111 X=1 Y=2 X=X+Y Y=Y+1 Y100 结 束 开 始 Y N 开 始 X=0 I=1 X=X+1/I I=I+1 I=N 结 束 N Y 开 始 n = 0 X =0， Y =1 Print X ， Y I=1 In-1 Z =X +Y X =Y Y =Z Print Y I=I+1 结 束 Y =0 Print Y Y N Y N 在 梵 天 塔 问 题 中 ， 需 要 移 动 的 盘 子 次 数 为h(n)=2n-1， 则 该 问 题 的 算 法 时 间 复 杂 度 表

22、 示为 (2n)； 例 4.4的 算 法 时 间 复 杂 度 表 示 为 (1)；例 4.5的 算 法 时 间 复 杂 度 表 示 为 (n)； 例 4.6的算 法 时 间 复 杂 度 表 示 为 (n)等 等 。 一 般 而 言 ， 对 于 较 复 杂 的 算 法 ， 应 将 它 分成 容 易 估 算 的 几 个 部 分 ， 然 后 用 的 求 解 原 则计 算 整 个 算 法 的 时 间 复 杂 度 ， 最 好 不 要 采 用指 数 级 和 阶 乘 级 的 算 法 ， 而 应 尽 可 能 选 用 多项 式 级 或 线 性 级 等 时 间 复 杂 度 较 小 的 算 法 。另 外 ， 还 要

23、 在 算 法 最 好 、 平 均 和 最 坏 的 情 况下 区 别 执 行 效 率 的 不 同 。 在 阶 乘 级 的 算 法 中 ， 如 果 问 题 规 模 n为 10，则 算 法 时 间 复 杂 度 为 10！ （ 3， 628， 800） 。若 要 检 验 10！ 种 情 况 ， 设 每 种 情 况 需 要 1毫 秒的 计 算 时 间 ， 则 整 个 计 算 将 需 1小 时 左 右 。 一般 来 说 ， 如 果 选 用 了 阶 乘 级 的 算 法 ， 则 当 问题 规 模 等 于 或 者 大 于 10时 ， 就 要 认 真 考 虑 算法 的 适 用 性 问 题 。 C A B D E

24、F G H I J K L C A B D 一 个 程 序 具 有 一 个 单 一 的 、 不 可 分 的 结 构 ，它 规 定 了 某 个 数 据 结 构 上 的 一 个 算 法 。 瑞 士著 名 计 算 机 科 学 家 尼 可 莱 沃 思 （ Nikiklaus Wirth） 在 1976年 曾 提 出 这 样 一 个 公 式 ： 算 法 +数 据 结 构 =程 序 这 一 公 式 仅 可 以 作 为 一 种 参 考 ， 不 能 作为 教 学 中 的 定 义 。 由 此 看 来 ， 我 们 前 面 提 到 的 算 法 和 数 据 结 构是 计 算 机 程 序 的 两 个 最 基 本 的 概

25、 念 。 算 法 是程 序 的 核 心 ， 它 在 程 序 编 制 、 软 件 开 发 ， 乃至 在 整 个 计 算 机 科 学 中 都 占 据 重 要 地 位 。 数据 结 构 是 加 工 的 对 象 ， 一 个 程 序 要 进 行 计 算或 处 理 总 是 以 某 些 数 据 为 对 象 的 ， 而 要 设 计一 个 好 的 程 序 就 需 将 这 些 松 散 的 数 据 按 某 种要 求 组 成 一 种 数 据 结 构 。 然 而 ， 随 着 计 算 机科 学 的 发 展 ， 人 们 现 在 已 经 意 识 到 程 序 除 了以 上 两 个 主 要 要 素 外 ， 还 应 包 括 程 序

26、 的 设 计方 法 以 及 相 应 的 语 言 工 具 和 计 算 环 境 。 抽象理论设计常 用 的 符 号 ： 数 字 (09)，大 小 写 字 母 (AZ、 az)，括 号 ， 运 算 符 (+， ， *， /)等 ;用 高 级 语 言 对 算 法 进 行 的描 述 ；语 言 的 分 类 方 法 ；各 种 数 据 类 型 的 抽 象 实 现模 型 ；词 法 分 析 、 编 译 、 解 释 和代 码 优 化 的 方 法 ；词 法 分 析 器 、 扫 描 器 、 编译 器 组 件 和 编 译 器 的 自 动生 成 方 法 形 式 语 言和 自 动 机理 论 ；形 式 语 义学 ： 操 作、

27、指 称 、公 理 、 代数 、 并 发和 分 布 式程 序 的 形式 语 义 特 定 语 言 ： 过 程 式 的 COBOL，FORTURN， ALGOL，Pascal， Ada， C） ， 函 数 式的 （ LISP） ， 数 据 流 的（ SISAL， VAL） ， 面 向 对象 的 （ Smalltalk， C+） ，逻 辑 的 （ Prolog） ， 字 符 串（ SNOBOL） ， 和 并 发（ Concurrent Pascal， Modula 2） 等 语 言 ；词 法 分 析 器 和 扫 描 器 的 产 生器 （ 如 YACC， LEX） ， 编译 器 产 生 器 ；语 法 和

28、 语 义 检 查 ， 成 型 、 调 试 和 追 踪 程 序 o 对 程 序 结 构 本 质 的 深 入 研 究 促 进 了 对 程 序 质量 的 认 识o开 发 程 序 的 效 率 和 质 量 取 决 于 程 序 设 计 方 法和 技 术o多 年 的 研 究 发 展 了 许 多 程 序 设 计 方 法 和 技 术 。如 自 顶 向 下 逐 步 求 精 的 程 序 设 计 方 法 、 自 底向 上 的 程 序 设 计 方 法 、 程 序 推 导 的 设 计 方 法 、程 序 变 换 的 设 计 方 法 、 函 数 式 程 序 设 计 技 术 、逻 辑 程 序 设 计 技 术 、 面 向 对 象

29、 的 程 序 设 计 技术 、 程 序 验 证 技 术 、 约 束 程 序 设 计 技 术 、 并发 程 序 设 计 技 术 等 。 o例 如 ， 对 于 许 多 问 题 的 计 算 ， 可 以 用 类 似 于计 算 函 数 的 方 法 来 进 行 ， 也 可 以 用 表 （ 一 种数 据 结 构 ） 处 理 的 方 法 进 行 ， 甚 至 还 可 以 用逻 辑 公 式 演 绎 推 导 的 方 法 进 行 ， 在 实 现 技 术上 ， 既 可 以 用 递 归 技 术 计 算 ， 也 可 以 用 迭 代技 术 或 其 它 技 术 进 行 计 算 。 o作 为 一 门 科 学 ， 高 级 语 言

30、和 程 序 设 计 确 实 对学 科 的 发 展 产 生 了 巨 大 的 影 响 。 程 序 设 计 方法 和 技 术 在 各 个 时 期 的 发 展 不 仅 直 接 导 致 了一 大 批 风 格 各 异 的 高 级 语 言 的 诞 生 ， 而 且 许多 新 思 想 、 新 概 念 、 新 方 法 和 新 技 术 不 仅 在语 言 中 得 到 体 现 ， 同 时 渗 透 到 了 计 算 机 科 学的 各 个 方 向 ， 从 理 论 、 硬 件 、 软 件 到 应 用 等多 方 面 深 刻 影 响 了 学 科 的 发 展 。o对 高 级 语 言 和 程 序 设 计 的 掌 握 是 计 算 机 科

31、 学专 业 的 基 本 功 之 一 。 o从 计 算 机 （ 硬 件 裸 机 ） 到 计 算 机 系 统o从 计 算 机 系 统 到 计 算 机 体 系 结 构 o软 件 是 一 个 发 展 的 概 念 ， 早 期 软 件 和 程 序 几乎 是 同 义 词 。 后 来 ， 软 件 的 概 念 在 程 序 的 基础 上 得 到 了 延 伸 。 1983年 ， IEEE对 软 件 给 出了 一 个 较 为 新 颖 的 定 义 ， 指 出 ： 软 件 是 计 算机 程 序 、 方 法 、 规 范 及 其 相 应 的 文 稿 以 及 在计 算 机 上 运 行 时 所 必 须 的 数 据 。 o系 统

32、软 件 和 应 用 软 件 迄 今 并 没 有 严 格 的 定义 。 图 像 处 理计算机图形学 模式识别图 像计 算 几 何特 征 数 据几 何 模 型 CAD/CAM计 算 机 艺 术计 算 机 动 画计 算 机 视 觉 o 随 着 计 算 科 学 及 其 应 用 的 高 速 发 展 ， 用 户 对 软 硬 件 和信 息 资 源 共 享 的 需 求 和 一 大 类 问 题 本 身 具 有 地 域 上 分布 的 特 点 ， 促 进 了 计 算 机 网 络 的 发 展 。o 所 谓 计 算 机 网 络 是 使 用 通 信 设 备 和 通 信 线 路 将 一 组 地理 上 分 布 的 相 同 （

33、 称 为 同 质 ） 或 不 同 （ 称 为 异 质 ） 的计 算 机 、 终 端 及 其 附 属 设 备 按 照 某 种 方 式 互 联 起 来 得到 的 一 个 计 算 机 硬 件 系 统 ， 也 叫 网 络 计 算 机 。 在 这 种计 算 机 硬 件 系 统 的 基 础 上 ， 通 过 开 发 能 协 调 各 台 计 算机 系 统 工 作 的 通 信 系 统 或 更 进 一 步 的 网 络 操 作 系 统 ，就 能 使 一 组 计 算 机 实 现 软 硬 件 资 源 共 享 、 协 同 计 算 ，合 作 求 解 一 个 问 题 。 由 这 种 通 信 系 统 或 网 络 操 作 系 统

34、连 同 网 络 计 算 机 一 起 ， 就 形 成 了 网 络 计 算 机 系 统 。 o 按 照 数 据 传 输 范 围 和 实 现 技 术 的 不 同 ， 计 算 机 网络 存 在 局 域 计 算 机 网 络 和 广 域 计 算 机 网 络 之 分 。局 域 计 算 机 网 络 是 一 个 数 据 通 信 系 统 ， 其 传 输 范围 在 中 等 地 理 区 域 ， 使 用 中 等 或 高 速 数 据 传 输 速率 ， 使 用 专 用 数 据 通 信 线 或 总 线 进 行 通 信 ， 可 联接 大 量 独 立 设 备 ， 在 物 理 通 信 通 道 上 互 相 通 信 。o 广 域 计

35、算 机 网 络 把 不 同 城 市 、 不 同 国 家 中 的 计 算机 或 计 算 机 网 络 通 过 分 级 互 联 技 术 联 接 起 来 ， 其传 输 范 围 可 达 到 相 当 远 的 距 离 。 目 前 最 常 见 的 是使 用 公 用 或 专 用 电 话 线 通 信 ， 主 干 网 和 一 些 局 域网 使 用 可 进 行 数 字 通 信 的 光 纤 光 缆 数 据 通 信 专 用线 。 o 网 络 互 联 的 拓 扑 结 构 是 计 算 机 网 络 的 重 要 特 性 。网 络 的 拓 扑 结 构 是 一 种 抽 象 的 由 点 和 线 组 成 的 图 。网 络 上 的 每 台

36、 计 算 机 用 一 个 结 点 表 示 ， 机 器 与 机器 之 间 的 链 路 用 线 和 路 径 表 示 ， 于 是 ， 图 论 构 成了 网 络 计 算 机 体 系 结 构 中 一 些 基 本 算 法 研 究 中 数学 描 述 的 理 论 基 础 。o 网 络 的 结 构 一 般 有 ： 主 从 型 、 环 型 、 星 型 、 等 o 支 持 计 算 机 网 络 的 重 要 技 术 是 通 信 ， 即 实 现 计 算机 之 间 信 息 传 输 的 一 种 技 术 方 式 。 网 络 通 信 的 核心 内 容 是 通 信 协 议 。 所 谓 通 信 协 议 是 网 络 通 信 中一 组

37、约 定 的 集 合 ， 由 它 确 定 了 经 由 通 信 网 络 传 输的 信 息 或 存 储 在 报 文 和 数 据 库 中 的 信 息 的 格 式 和控 制 方 式 。 研 究 通 信 协 议 主 要 是 为 了 在 网 络 计 算机 系 统 中 实 现 可 靠 的 、 高 效 的 数 据 交 换 ， 差 错 控制 ， 信 息 编 码 ， 线 路 利 用 ， 同 步 ， 使 通 信 数 据 具有 透 明 性 。 网 络 上 连 接 着 大 量 的 计 算 机 系 统 ， 每 台 计 算 机 系统 上 可 能 有 多 个 用 户 在 同 时 使 用 计 算 机 与 其 它 网 上 用户 进

38、 行 通 信 ， 而 网 络 通 信 线 路 通 常 设 计 成 公 用 资 源 ，这 样 ， 网 络 通 信 为 了 实 现 可 靠 的 数 据 交 换 ， 因 需 要 做许 多 具 体 的 操 作 运 算 而 变 得 十 分 复 杂 。 由 于 从 用 户 发送 或 接 收 可 以 识 别 的 符 号 信 息 到 实 际 在 正 确 的 通 信 线路 上 传 递 物 理 信 息 之 间 存 在 转 换 、 线 路 利 用 、 分 组 交换 、 差 错 纠 正 等 一 系 列 的 操 作 ， 为 了 便 于 协 议 的 有 效实 现 和 对 不 同 的 用 户 开 放 ， 最 大 限 度 地

39、 实 现 线 路 的 有效 利 用 ， 有 必 要 对 网 络 计 算 机 系 统 进 行 通 信 结 构 分 层 。于 是 产 生 了 网 络 协 议 层 。 每 一 层 包 含 一 组 通 信 功 能 和相 应 的 层 间 通 信 协 议 ， 支 持 通 信 双 方 在 不 同 的 层 间 进行 通 信 ， 并 提 供 了 实 现 通 信 的 具 体 思 想 和 方 法 。 按 照 ISO的 建 议 ， 网 络 结 构 模 型 是 开 放 系 统 互 连 模 型OSI（ 七 层 协 议 ） ， 包 括 物 理 层 ， 数 据 链 路 层 ， 网 络 层 ，传 输 层 ， 会 话 层 ， 表

40、 示 层 ， 应 用 层 共 七 层 ， 产 生 了 七层 协 议 。 开 放 系 统 A 开 放 系 统 B 应 用 层 协 议 应 用 层 应 用 层 表 示 层 协 议 表 示 层 表 示 层 会 话 层 协 议 会 话 层 会 话 层 传 输 层 协 议 传 输 层 传 输 层 网 络 层 协 议 网 络 层 网 络 层 数 据 链 路 层 协 议 数 据 链 路 层 数 据 链 路 层 物 理 层 协 议 物 理 层 物 理 层 物 理 传 输 介 质 o 物 理 层 协 议 实 现 物 理 上 互 连 系 统 间 位 流 信 息 的 透明 传 输 ， 即 实 现 了 一 位 （ 组

41、 ） 数 据 在 两 个 通 信 实体 之 间 的 可 靠 传 送 通 信 ， 它 描 述 了 经 通 信 介 质 在数 据 链 路 实 体 之 间 建 立 、 维 护 和 拆 除 物 理 连 接 。o 数 据 链 路 层 协 议 主 要 是 对 高 层 屏 蔽 传 输 介 质 的 特性 ， 为 网 络 通 信 实 体 之 间 提 供 建 立 、 维 护 和 释 放数 据 链 路 连 接 的 功 能 和 手 段 ， 实 现 无 差 错 的 数 据以 帧 为 单 位 的 可 靠 传 送 。o 网 络 层 协 议 主 要 是 为 通 信 子 网 与 高 层 结 构 之 间 提供 界 面 连 接 ，

42、 其 主 要 任 务 是 对 通 信 子 网 实 现 路 径选 择 ， 实 现 通 信 实 体 之 间 端 -端 的 透 明 的 数 据 传 送 ，对 高 层 屏 蔽 了 数 据 传 送 经 过 的 路 径 。 o传 输 层 协 议 也 称 为 主 机 -主 机 层 协 议 ， 它 为 会话 层 的 通 信 实 体 之 间 提 供 透 明 的 数 据 传 送 ， 其主 要 任 务 是 接 收 会 话 实 体 送 来 的 数 据 ， 根 据 需要 把 它 们 分 成 若 干 比 较 小 的 单 元 ， 保 证 所 有 数据 单 元 经 下 面 三 层 正 确 地 到 达 另 一 个 会 话 实

43、体 。o会 话 层 协 议 也 称 进 程 -进 程 层 协 议 ， 它 通 过 协议 提 供 的 一 组 命 令 为 网 上 两 个 进 程 之 间 的 通 信建 立 会 话 连 接 和 释 放 会 话 连 接 ， 并 管 理 它 们 在该 连 接 上 的 对 话 。 o表 示 层 协 议 以 对 应 用 实 体 有 意 义 的 形 式 提 供 有关 信 息 表 示 的 服 务 。 这 些 服 务 有 文 本 压 缩 、 代码 转 换 、 数 据 加 密 与 解 密 、 文 件 格 式 变 换 、 信息 格 式 变 换 、 终 端 属 性 的 转 换 等 。o应 用 层 协 议 是 用 户

44、访 问 网 络 的 接 口 层 ， 直 接 为正 在 通 信 的 端 点 用 户 的 应 用 进 程 服 务 ， 如 电 子邮 件 、 远 程 操 作 访 问 、 虚 拟 终 端 等 。o关 于 协 议 详 细 的 实 现 技 术 ， 其 主 要 的 基 础 是 分布 式 算 法 ， 今 后 ， 同 学 们 有 可 能 学 习 这 些 内 容 。o网 络 信 息 安 全 、 加 密 、 病 毒 、 高 性 能 计 算 与 通信 、 信 息 高 速 公 路 、 数 字 地 球 （ Binding） （ Complexity of Large Problems） （ Conceptual and Format Models） （ Consistency and Completeness） （ Efficiency） （ Evolution） （ Levels of Abstraction） （ Ordering in Space） （ Ordering in Time） （ Reuse） （ Security） （ Tradeoff and Consequences）