计算概论：计算机文化、程序设计.pdf

计 算 概 论-计 算 机 文 化、程 序 设 计 Introduction to Computing:Computer Culture,and Programming闫 宏 飞 陈 狮 编 著 by Hongfei Yan and Chong Chen2010/9/23内 容 简 介 本 书 主 要 是 汇 编 各 书 和 参 考 资 料 而 成，比 较 系 统 地 介 绍 了 计 算 机 文 化，和 程 序 设 计。通 过 这 两 部 分 有 机 的 结 合（前 者 占 1/3,后 者 占 2/3）,即 理 论 与 实 践 结 合，使 学 生 理 解 和 掌 握 有 关 计 算 机 和 信 息 技 术 的 基 本 概 念 和 基 本 原 理，对 计 算 机 学 科 有 全 局 性 的 认 识；学 会 使 用 计 算 机 进 行 信 息 处 理，熟 练 掌 握 C+语 言 编 程 技 术，为 后 续 相 关 课 程 的 学 习 打 好 基 础。本 书 层 次 分 明，山 浅 入 深，具 有 学 习 和 实 用 双 重 意 义。本 书 可 作 为 高 等 院 校 各 专 业 一、二 年 级 学 生 的 教 学 参 考 书 和 技 术 资 料，对 广 大 从 事 计 算 机 相 关 研 究 和 应 用 开 发 的 科 技 人 员 也 有 很 大 的 参 考 价 值。,*,-a-刖 H 计 算 概 论 是 普 通 高 校 面 向 理 工 科 低 年 级 学 生 开 设 的 计 算 机 基 础 教 育 课。课 程 前 1/3部 分 为 计 算 机 文 化，后 2/3部 分 为 程 序 设 计。任 教 此 课 两 年 来，发 现 没 有 合 适 的 教 材，因 此 根 据 授 课 经 验，汇 编 各 书 和 参 考 资 料，编 成 此 书。编 者 2009年 1月 于 北 大 燕 园目 录 计 算 概 论-I第 1章 弓 I论._ 11.1 计 算 机 科 学.21.2 摩 尔 定 律.313 SCOPE OF PROBLEMS.5计 新 文 化.9第 2 章 统.102.1 COMPUTER INTRODUCTION.102.1.1 TURING MODEL.102.1.2 VON NEUMANN MODEL.162.1.3 Computer components.182.1.5 Practice set.272.2 计 算 机 系 统 漫 游.282.2.1 Information is Bits+Context.302.2.2 Programs Are Translated by Other Programs into Different Forms.322.2.3 It Pays to Understand How Compilation Systems Work.342.2.4 Processors Read and Interpret Instructions Stored in Memory.352.2.5 Caches Matter.412.2.6 Storage Devices Form a Hierarchy.422.2.7 The Operating System Manages the Hardware.432.2.8 Systems Communicate With Other Systems Using Networks.502.2.9 The Next Step.52第 3 章 糠 和 数 的 新.543.1 数 据 的 新.543.1.1 黜 的 类 型.543.1.2 计 孰 内 部 的 螂.553.1.3 表 示 数 据.563.1.4 十 六 进 制 表 示 法.633.1.5/U 4制 表 示 法.643.1.6 Practice set.643.2数 的 表 示.683.2.1 H dS制 和 二 进 制.683.2.9 Practice set.69第 4 章 麟 设 腌 言 和 开 发 环 境.724.1 粉 设 演 言.724.1.8 Practice set.794.2 开 发 环 境.82下 篇 出 设 计.88第 5 章 础.895.1 C+无 萨 结 构(STRUCTUREOF A PROGRAM).895.2 变 量 和 类 型(VARIABLES AND DATATYPES).935.3 常 量(C ONSTANTS).1025.4 操 作 符/运 算 符(O PERATORS).1075.4 基 本 输 入 输 出(BASIC INPUT/OUTPUT).118第 6 章 控 制 辘 和 函 数.1256.1 控 缶(J结 构(CONTROLSTRUCTURES).1256.2 函 数 I(FUNCnONSl).13663 函 数 H(FUNCTIONSI I).142第 7 章 组 合 蟠 频.1557.1 数 组.1557.2 字 符 序 列(CHARACTER SEQUENCES).1667.3 指 针(POINTERS).1747.4 动 态 内 存 分 配(DYNAMICMEMORY).1897.5 数 据 结 构.1947.6 其 他 数 据 类 型.202第 8 章 标 僻.2078.1 C LANGUAGE LIBRARY.2088.2 INPUT/OUTPUT STREAM LIBRARY.2098.3 STRING LIBRARY.210iii8.4 STL：STANDARD TEMPLATE LIBRARY.210第 9 章 端 和 引 用.2149.1 POINTERS.2149.1.1 Reference operator(&).2149.1.2 Dereference operator(*).2169.1.3 Declaring variables of pointer types.2179.1.4 Pointers and arrays.2209.1.5 Pointer initialization.2229.1.6 Pointer arithmetics.2239.1.7 Pointers to pointers.2259.1.8 void pointers.2269.1.9 Null pointer.2279.1.10 Pointers to functions.2289.2 DYNAMIC MOMORY.2299.2.1 Operators new and new.2299.2.2 Operators delete and delete口.2319.2.3 Dynamic memory inANSI-C.233第 10 章 VARIABLES:A DEEPER LOOK.23410.1 MEMORY ORGANIZATION.23410.2 VARIABLE SCOPE.23610.3 UNDERSTANDING POINTERS.237第 11章 算 法-24011.1 THE ROLE OF ALGORITHMS IN COMPUTING.24111.1.1 Algorithms.24111.1.2 Algorithms as a technology.24611.2 算 法 的 概 念.24911.3 算 法 的 三 种 基 本 结 构.24911.4 算 法 的 标.25011.5 介 绍 几 种 基 本 算 法.25011.6 迭 代 与 递 归.250第 12章 班 设 计.25112.1 简 单 计 算 题.25112.2 模 拟.251iv12.3 可 模 型 化 的 问 题.25212.4 动 态 殿 ij.252Introduction(Beginner).253Elementary.256Intermediate.257Upper-Intermediate.259Advanced.260的 翅.264第 1章 引 论 第 1章 引 论 计 算 机 文 化 这 个 词 的 出 现 到 被 广 泛 认 可 的 时 间 并 无 确 切 的 考 证，但 基 本 上 是 在 2 0世 纪 8 0年 代 后 期。计 算 机 开 始 是 一 种 装 置，进 而 到 一 门 学 科，再 发 展 成 为 一 种“文 化”，它 对 人 类 的 影 响 力 之 大 的 确 令 人 惊 叹。计 算 机 文 化 是 指 能 够 理 解 计 算 机 是 什 么，以 及 它 如 何 被 作 为 资 源 使 用 的。简 单 地 说，计 算 机 文 化 不 但 是 知 道 如 何 使 用 计 算 机，更 重 要 的 是 知 道 什 么 时 候 使 用 计 算 机。在 当 今 世 界，几 乎 所 有 专 业 都 与 计 算 机 息 息 相 关。但 是，只 有 某 些 特 定 职 业 和 学 科 才 会 深 入 研 究 计 算 机 本 身 的 制 造、编 程 和 使 用 技 术。用 来 诠 释 计 算 机 学 科 内 不 同 研 究 领 域 的 各 个 学 术 名 词 的 涵 义 不 断 发 生 变 化，同 时 新 学 科 也 层 出 不 穷。五 个 主 要 的 计 算 机 学 科(disipline of com puting)包 括 计 算 机 工 程 学(Computer Engineering),是 电 子 工 程 的 一 个 分 支，主 要 研 究 计 算 机 软 硬 件 和 二 者 间 的 彼 此 联 系。计 算 机 科 学(Computer S c ie n c e),是 对 计 算 机 进 行 学 术 研 究 的 传 统 称 谓。主 要 研 究 计 算 技 术 和 执 行 特 定 任 务 的 高 效 算 法。该 门 学 科 为 我 们 解 决 确 定 一 个 问 题 在 计 算 机 领 域 内 是 否 可 解，如 可 解 其 效 率 如 何，以 及 如 何 作 成 更 加 高 效 率 的 程 序。时 至 今 日，在 计 算 机 科 学 内 已 经 派 生 了 许 多 分 支，每 个 分 支 都 针 对 不 同 类 别 的 问 题 进 行 深 入 研 究。软 件 工 程 学(Software E ngineering),着 重 于 研 究 开 发 高 质 量 软 件 系 统 的 方 法 学 和 实 践 方 式，并 试 图 压 缩 并 预 测 开 发 成 本 及 开 发 周 期。信 息 系 统(Infbrmation S y stem s),研 究 计 算 机 在 一 个 广 泛 的 有 组 织 环 境(商 业 为 主)中 的 计 算 机 应 用。信 息 技 术(Infbrmation T echnology),指 计 算 机 相 关 的 管 理 和 维 护。计 算 概 论 课 程 关 注 的 是 计 算 机 学 科。较 大 规 模 的 致 力 于 计 算 机 科 学 的 组 织 有：美 国 计 算 机 协 会(Association of Computing M achinery,简 称 ACM)；美 国 电 气 电 子 工 程 师 协 会(Institute of Electrical and Electronics Engineers,简 称 为 IEEE)1 Computing Curricula 2005:The Overview Report,http:/www.acm.org/education/curric vols/CC2005-March06Final.pdf i 第 1章 引 论 1.1 计 算 机 科 学 计 算 机 科 学 是-门 包 含 各 种 各 样 与 计 算 和 信 息 处 理 相 关 主 题 的 系 统 学 科，从 抽 象 的 算 法 分 析、形 式 化 语 法 等 等，到 更 具 体 的 主 题 如 编 程 语 言、程 序 设 计、软 件 和 硬 件 等。作 为 一 门 学 科，它 与 数 学、计 算 机 程 序 设 计、软 件 工 程 和 计 算 机 工 程 有 显 著 的 不 同，却 通 常 被 混 淆，尽 管 这 些 学 科 之 间 存 在 不 同 程 度 的 交 叉 和 覆 盖。2计 算 机 科 学 研 究 的 课 题 是：计 算 机 程 序 能 做 什 么 和 不 能 做 什 么（可 计 算 性）；如 何 使 程 序 更 高 效 的 执 行 特 定 任 务（算 法 和 复 杂 性 理 论）；程 序 如 何 存 取 不 同 类 型 的 数 据（数 据 结 构 和 数 据 库）；程 序 如 何 显 得 更 具 有 智 能（人 工 智 能）；人 类 如 何 与 程 序 沟 通（人 机 互 动 和 人 机 界 面）。计 算 机 科 学 的 大 部 分 研 究 是 基 于“冯 诺 依 曼 计 算 机”和“图 灵 机”的，它 们 是 绝 大 多 数 实 际 机 器 的 计 算 模 型。作 为 此 模 型 的 开 山 鼻 祖，邱 奇-图 灵 论 题（Church-Turing Thesis）表 明，尽 管 在 计 算 的 时 间，空 间 效 率 上 可 能 有 所 差 异，现 有 的 各 种 计 算 设 备 在 计 算 的 能 力 上 是 等 同 的。尽 管 这 个 理 论 通 常 被 认 为 是 计 算 机 科 学 的 基 础，可 是 科 学 家 也 研 究 其 它 种 类 的 机 器，如 在 实 际 层 面 上 的 并 行 计 算 机 和 在 理 论 层 面 上 概 率 计 算 机、o racle计 算 机 和 量 子 计 算 机。在 这 个 意 义 上 来 讲,计 算 机 只 是 一 种 计 算 的 工 具：著 名 的 计 算 机 科 学 家 D ijkstra有 句 名 言“计 算 机 科 学 之 关 注 于 计 算 机 并 不 甚 于 天 文 学 之 关 注 于 望 远 镜。计 算 机 科 学 根 植 于 电 子 工 程、数 学 和 语 言 学，是 科 学、工 程 和 艺 术 的 结 晶。它 在 2 0世 纪 最 后 的 三 十 年 间 兴 起 成 为 一 门 独 立 的 学 科,并 发 展 出 自 己 的 方 法 与 术 语。早 期，虽 然 英 国 的 剑 桥 大 学 和 其 他 大 学 已 经 开 始 教 授 计 算 机 科 学 课 程，但 它 只 被 视 为 数 学 或 工 程 学 的 一 个 分 支，并 非 独 立 的 学 科。剑 桥 大 学 声 称 有 世 界 上 第 一 个 传 授 计 算 的 资 格。世 界 上 第 一 个 计 算 机 科 学 系 是 由 美 国 的 普 渡 大 学 在 1962年 设 立，第 一 个 计 算 机 学 院 于 1980年 由 美 国 的 东 北 大 学 设 立。现 在，多 数 大 学 都 把 计 算 机 科 学 系 列 为 独 立 的 部 门，部 分 将 它 与 工 程 系、应 用 数 学 系 或 其 他 学 科 联 合。计 算 机 科 学 领 域 的 最 高 荣 誉 是 A C M设 立 的 图 灵 奖，被 誉 为 是 计 算 机 科 学 的 诺 贝 尔 奖。它 的 获 得 者 都 是 本 领 域 最 为 出 色 的 科 学 家 和 先 驱。华 人 中 首 获 图 灵 奖 的 是 姚 期 智 博 士。他 于 2000年 以 其 对 计 算 理 论 做 出 的 诸 多“根 本 性 的、意 义 重 大 的”贡 献 而 获 得 这 一 崇 高 荣 誉。2 http:/zh.wikiDedia.org/wiki/计 算 机 科 学 2 第 1章 引 论 1.2摩 尔 定 律 http:en.wikipedia.org/wiki/Moore%27s LawMoores law describes a long-term trend in the history of computing hardware.Sincethe invention of the integrated circuit in 1958,the number of transistors that can beplaced inexpensively on an integrated circuit has increased exponentially,doublingapproximately every two years.The trend was first observed by Intel co-fbunderGordon E.Moore in a 1965 pape匚 It has continued for almost half of a century and isnot expected to stop for another decade at least and perhaps much os-2,000,000,0001,000,000,000 10,000,0001,000,000 100,000 10,0002,300 JOual-Corn narnum 2 POWER.Ittrtu E 2 9MB cache Core?QuadHnrMUn 2 100,000,0001980 1990 2000 2008Curve shows Moores Law：transistor count doublingevery two years*IUnli*n TIA W H A GT200 RV770Date of introduction图 I-I CPU Transistor Counts 1971-2008&Moores Law,Growth of transistor countsfor Intel processors(dots)and Moores Law(logarithmic vertical scale)Almost every measure of the capabilities of digital electronic devices is linked toMoore*s law:processing speed,memory capacity,even the number and size of pixels indigital cameras.All of these are improving at(roughly)exponential rates as well.Thishas dramatically increased the usefulness of digital electronics in nearly every segmentof the world economy.Moores law describes this driving force of technological and3 第 1章 引 论 social change in the late 20th and early 21st centuries.http:/算 机 第 一 定 律 摩 尔 定 律 M oore定 律。归 纳 起 来，主 要 有 以 下 三 种“版 本”：集 成 电 路 芯 片 上 所 集 成 的 电 路 的 数 目，每 隔 18个 月 就 翻 一 番。微 处 理 器 的 性 能 每 隔 18个 月 提 高 一 倍，而 价 格 下 降 一 倍。用 一 个 美 元 所 能 买 到 的 电 脑 性 能，每 隔 18个 月 翻 两 番。图 1-2 Computer SpeedupMoores Law:The density o f transistors on a chip doubles every 18 months,for thesame cos/(1965)半 导 体 集 成 电 路 的 密 度 或 容 量 每 18个 月 翻 一 番 Moores Law is still valid.His law has nothing to do with the speed of theproccesor.It has to do with the number of transitotrs which is still doubleing everycouple of years.Case in point there is now multiple cores in the same space instead ofone core.4-第 1章 引 论 戈 登 摩 尔(Gordon Moore),C PU生 产 商 Intel公 司 的 创 始 人 之 一。1965年 提 出“摩 尔 定 律”，1968年 创 办 Intel公 司。摩 尔 1929年 出 生 在 美 国 加 州 的 旧 金 山。曾 获 得 加 州 大 学 伯 克 利 分 校 的 化 学 学 士 学 位，并 且 在 加 州 理 工 大 学(CIT)获 得 物 理 和 化 学 两 个 博 士 学 位。5 0年 代 中 期 他 和 集 成 电 路 的 发 明 者 罗 伯 特 诺 伊 斯(Robert Noyce)-起，在 威 廉 肖 克 利 半 导 体 公 司 工 作。后 来，诺 伊 斯 和 摩 尔 等 8 人 集 体 辞 职 创 办 了 半 导 体 工 业 史 上 有 名 的 仙 童 半 导 体 公 司(FairchildSemiconductor).,仙 童 成 为 现 在 的 Intel和 AM D之 父。1968年，摩 尔 和 诺 伊 斯 一 起 退 出 仙 童 公 司，创 办 了 Intel。Intel初 期 致 力 于 开 发 当 时 计 算 机 工 业 尚 未 开 发 的 数 据 存 储 领 域，后 来，Intel进 行 战 略 转 移，专 攻 微 型 计 算 机 的“心 脏”部 件-C P U。1.3 Scope of ProblemsWhat can you do with 1 computer?What can you do with 100 computers?What can you do with an entire data center?http:en.wikiDedia.org/wiki/Distributcd comDuting#ProiectsProjects:A variety of distributed computing projects have grown up in recent years.Manyare run on a volunteer basis,and involve users donating their unused computationalpower to work on interesting computational problems.Examples of such projectsinclude the Stanford University Chemistry Department Foldinghome project,whichis focused on simulations of protein folding to find disease cures and to understandbiophysical systems;World Community Grid,an effort to create the world*s largestpublic computing grid to tackle scientific research projects that benefit humanity,runand funded by IBM;SETIhome,which is focused on analyzing radio-telescope datato find evidence of intelligent signals from space,hosted by the Space SciencesLaboratory at the University of California,Berkeley(the Berkeley Open Infrastructurefbr Network Computing(BOINC),was originally developed to support this project);LHChome,which is used to help design and tune the Large Hadron Collider,hostedby CERN in Geneva;and,which is focused on finding optimal Golombrulers and breaking various cryptographic ciphers.http:folding.stanford.edu/English/Mainhttp:zh.wikiDcdia.org/wiki/Foldinghomchttp:www.stanford.edu/grouD/pandegrouD/images/FAH-May2008.png 5第 1章 引 论 http:如 何 工 作 的 呢？Folding home是 一 个 研 究 研 究 蛋 白 质 折 叠，误 折，聚 合 及 山 此 引 起 的 相 关 疾 病 的 分 布 式 计 算 工 程。使 用 联 网 式 的 计 算 方 式 和 大 量 的 分 布 式 计 算 能 力 来 模 拟 蛋 白 质 折 叠 的 过 程，并 指 引 我 们 近 期 对 由 折 叠 引 起 的 疾 病 的 一 系 列 研 究。图 1-3 Foldinghome 6 第 1章 引 论 图 1-4 Shrek Dreamworks Animation,rendering multiple frames of high-qualityanimationHappy Feet Kingdom Feature Productions;Lord of the Rings New Line Cinema图 1-5 Simulating several hundred or thousand charactersIndexing the web(Google)Google()是 一 个 搜 索 引 擎，由 两 个 斯 坦 福 大 学 博 士 生 LarryPage 与 Sergey Brin 于 1998 年 9 月 发 明，Google I n c.于 1999 年 创 立 Google 网 页 搜 索 技 术 是 来 源 于 信 息 检 索 技 术。G oogle的“网 页 快 照”功 能，能 从 G oogle服 务 器 里 直 接 取 出 缓 存 的 网 页。Simulating an Internet-sized network for networking experiments(PlanetLab)http:wwwwlanet-lab.org/PlanetLab is a global research network that supports the development of newnetwork services.Since the beginning of 2003,more than 1,000 researchers at topacademic institutions and industrial research labs have used PlanetLab to develop newtechnologies for distributed storage,network mapping,peer-to-peer systems,distributed hash tables,and query processing.PlanetLab currently consists of 1128nodes at 511 sites.Speeding up content delivery(Akamai)美 国 A kam ai是 国 际 上 最 大 的 C D N服 务 商，它 巨 大 的 网 络 分 发 能 力 在 峰 值 时 可 达 到 15Gbps A kam ai公 司 是 为 数 不 多 的 旨 在 消 除 Internet瓶 颈 和 提 高 下 载 速 度 的 儿 家 新 公 司 之，是 一 个 致 力 于 网 络 交 通 提 速 的“内 容 发 布”公 司，是 波 士 顿 高 技 术 区 最 卓 越 的 新 兴 企 业 之 一。A kam ai公 司 向 全 球 企 业 提 供 发 送 互 联 网 内 容，汇 流 媒 体 和 应 用 程 序 的 服 务(目 前，该 公 司 为 15个 国 家 的 企 业 管 理 着 8000多 台 服 7 第 1章 引 论 务 器）。1998年，丹 尼 尔.L和 麻 省 理 工 学 院 的 一 些 研 究 人 员 起 创 立 了 这 家 公 司,他 在 麻 省 理 工 学 院 的 硕 士 论 文 构 成 了 Akamai公 司 最 初 的“自 由 流”（Freeflow）技 术 的 核 心。根 据 美 国 航 空 公 司 的 消 息，丹 尼 尔.L31岁，在 2001年 9 月 1 1日 撞 击 纽 约 世 界 贸 易 中 心 的 被 劫 持 飞 机 上 遇 难。上 篇 计 算 机 文 化 上 篇 的 主 要 目 的 是 向 读 者 介 绍 有 关 计 算 机 和 信 息 技 术 的 基 本 概 念 和 基 本 原 理，使 读 者 能 够 对 计 算 机 学 科 有 全 局 性 的 认 识。9第 2 章 计 算 机 系 统 第 2章 计 算 机 系 统 2.1 Computer Introduction本 节 大 部 分 内 容 取 自 下 面 这 本 书 的 第 一 章。等 号 线 之 间 内 容 是 编 者 加 的。Foundations of Computer Science,2e,by Behrouz Forouzan and Firouz MosharrafCengagc Learning Business Press,December 5,2007http:www.cengage.ca.uk/forouzan/The phrase computer science has a very broad meaning today.However,in this book,we define the phrase as issues related to the computer”.This introductory chapter firsttries to find out what a computer is,and then investigates other issues directly relatedto computers.We look first at the Turing model as a mathematical and philosophicaldefinition of computation.We then show how today*s computers are based on the vonNeumann model.The chapter ends with a brief history of this culture-changingdevice.the computer.ObjectivesAfter studying this chapter,the students should be able to:Define the Turing model of a computer.Define the von Neumann model of a computer.Describe the three components of a computer:hardware,data,and software.List topics related to computer hardware.List topics related to data.List topics related to software.Discuss some social and ethical issues related to the use of computers.Give a short history of computers.2.1.1 TURING MODELThe idea of a universal computational device was first described by Alan Turing in io-第 2 章 计 算 机 系 统 1937.He proposed that all computation could be performed by a special kind ofmachine,now called a Turing machine.Although Turing presented a mathematicaldescription of such a machine,he was more interested in the philosophical definiton ofcomputation than in building the actual machine.He based the model on the actionsthat people perfonn when involved in computation.He abstracted these actions into amodel for a computational machine that has really changed the world.Perceptual knowledge（感 性 认 识）计 算 机 组 成 部 分 http:n 101/2008/video/computer components.flvIntroduction to Computer Hardwarehttp:net.D 101/2008/video/intro2comDuter hardware.flvInstall http:net.D 101/2008/vidco/flvplaycr sctup.cxe,if yourcomputer can not show videos.图 2-1 Motherboard（主 板：集 成 多 个 部 件、适 配 器，提 供 它 们 之 间 的 互 联）主 板（Main Board）又 名 主 机 板、系 统 板、母 板，是 P C机 的 核 心 部 件。P C机 的 主 板 包 括 CPU、芯 片 组（Chipset）、高 速 缓 存（Cache）、ROM BIOS芯 片-、CMOS芯 片、内 存 RAM、总 线 通 道、软 硬 磁 盘 接 口、串 行 和 并 行 接 口、U S B接 口、扩 11第 2 章 计 算 机 系 统 展 槽(Slots)直 流 电 源 插 座、可 充 电 电 池 以 及 各 种 条 线。图 中 从 上 到 下，左 到 右：内 存 条，磁 盘、光 驱 等 的 数 据 线 接 口；C PU风 扇(一 般 下 面 是 散 热 器，和 CPU)；棕 色 A G P槽：只 能 接 显 卡；白 色 PCI槽：能 接 显 卡、网 卡、声 卡 等.图 2-2 CPU=运 算 器+控 制 器 图 2-3