《计算机科学导论》是一本由[美]贝赫鲁兹·佛罗赞著作，机械工业出版社出版的平装图书，本书定价：69.00元，页数：421，特精心从网络上整理的一些读者的读后感，希望对大家能有帮助。
●还有一本书，深入理解计算机系统，这两本书同样特别经典难得。相比较而言，CS APP文本更厚，需要一定的时间和耐心读下去，而这本书可以认为是CS APP的简化版。最新版的CS APPA中文版是双色印刷，有决心的同学可以尝试下，如果觉得困难，这本书可以作为先导书读一遍。
●以前看的是布鲁克希尔德《计算机科学概论》，看了不久，觉得烦。老头子功力虽然深厚，但讲东西比较深入复杂。尤其是划分“计算机科学”这门课的脉络不分明。容易迷失，直到学C在知乎上看到有人推荐这本书，下来看。绪论就让我折服。入门绝佳书籍！
●这是一本介绍计算机各个领域的书。本书只是让你了解一些知识，拓宽你在计算机各方面的认识，并未做太多的深入，适合对计算机感兴趣的新人阅读。
●读一本书最重要的是想要了解什么知识，而不是书中的内容。合适才是关键。我读过很书中，大部分都是看到比人推荐才去买。看过后发现 并不是不好，而是不适合当时的我读。
《计算机科学导论》读后感(一)：是“导论”，也能查漏补缺
如书名，这是一本“导论”级别的书。豆瓣上原书第二版看过的读者比较多，第三版没有太多评论。首先，这本书兼顾了CS各个方面的广度。从计算机硬件结构到操作系统，从网络传输协议、网络安全到数据结构、数据结构、程序语言、算法⋯⋯因此对于新手来说，是一本比较不错的入门书籍，足够一览CS的各个领域基础知识，对于老手也能查漏补缺。当然也因为广度损失了一部分深度。这不能不说是一个遗憾，当然本书本就是“导论”。如果想在某方面深入，可以按图索骥去找经典书籍阅读。最后，吐槽一下机械工业出版社草纸一般的质量。这本书的纸张实在无法匹配这本经典书籍。
这本书的定位从名字中的”导论“就可以看出，是一本计算机科学方面的入门教材。这本书从二进制原理，到计算机软硬件的构成、最基础的算法知识，再到最后的计算机科学前沿概念。为初识计算机的入门者们徐徐描绘了一幅计算机世界的“地形图”。 说来惭愧，作为一名计算机相关专业的学生，我在即将进入研究生阶段的时候还需要阅读这本“计算机入门读物”。主要是因为本科阶段的底子打得太差，一方面是因为这四年盲目追求GPA，在学习的路途上太过功利。另外一方面也有本科教学体系的问题，我个人认为，国内现在的本科专业设置太细，太专了，以计算机专业来举例，一个计算机在本科阶段就分出来计算机、软件工程、网络与信息安全、智能科学与技术等等方向，虽然加速了专业人才的培养，但也可能导致学生的基础不牢，不利于后续的发展。总之，作为一本入门教材，这本书是十分成功的。非常适合计算机专业的大一同学，以及想对计算机科学有全面认识的其他专业的同学。即使其中有一些不是特别清晰的地方，直接上网百度相关名词即可。在我的阅读过程中，发现的问题主要集中在机械工业出版社印刷的纸质版纸质不是特别好，这也是这套黑皮书的通病，同时在里面也有一定数量的错别字，较为影响阅读体验。
《计算机科学导论》读后感(三)：部分笔记
学习相关知识前再复习一遍十分有益
第7章 操作系统
软件分为操作系统和应用程序
操作系统控制对硬件和软件资源的访问
自举-自举程序存在ROM内存中 可将操作系统装入RAM内存
多道程序-将多个程序同时装入内存 资源可用时将它分给需要它的程序
分时-资源可被不同程序分享
调度-给不同程序分配资源并决定哪个程序什么时候用哪一种资源
并行系统-同一计算机安装多个CPU
操作系统包括内存管理器 进程管理器 设备管理器 文件管理器和用户界面
1⃣️用户界面-负责操作系统与外界通信
2⃣️内存管理-分单道和多道程序 多道程序分交换和非交换
非交换:程序在运行期间始终在内存中
①分区调度:内存被分为不同大小的区来保存各个程序 一个程序执行结束后再执行下一个程序
②分页调度:内存被等分为若干帧 程序等分为若干页 帧和页大小相等 程序在内存中不必连续
交换:运行期间程序可以在内存和硬盘之间多次交换数据
①请求分页调度:程序被分为页后不必整体载入内存运行
②请求分段调度:程序按模块分为主程序和子程序
③请求分页和分段调度:结合①② 一个模块可以分页 内存可以分成帧
虚拟内存 请求分页调度和请求分段调度时 程序一部分(a)在内存 一部分在硬盘(b) 即只有a大小的内存却有a+b大小的虚拟内存
3⃣️进程管理
程序:一组编写好的指令
作业:一个程序从被选中执行 到运行结束并再次成为一个程序的过程中被称为作业 处于保持/ 终止状态
进程:内存中(运行着)的作业 处于就绪/运行/等待状态
调度器:改变作业或进程的状态
①作业调度器:创建/终止一个进程 即保持➡️就绪 或 运行➡️终止
②进程调度器:一个进程的状态转换
运行➡️等待:等待某事件发生
等待➡️就绪:事件发生
就绪➡️运行:CPU准备执行这个进程
运行➡️就绪:进程所分配的时间片耗尽
队列:存储含有作业/进程信息的作业/进程控制块 一个操作系统有多个队列 进程管理器可用多种策略从队列中选择下一作业/进程
两种有问题的状态-死锁和饿死
⒈死锁:⑴⑵⑶⑷同时出现时可能发生
⑴互斥:一个资源只能被一个进程占有
⑵资源占有:一个进程只能占有一个资源
⑶抢先:操作系统不能临时对资源重新分配
⑷循环等待:所有进程和资源保含在一个循环里
⒉饿死:操作系统对进程分配资源有太多限制
4⃣️设备管理-访问输入/输出设备(比CPU 内存速度慢很多)
5⃣️文件管理-
①控制文件的访问:控制哪些应用程序可以访问文件及其访问发生
②管理文件的创建 修改 删除 命名
③管理文件存储方式和位置
④对文件归档和备份
主流操作系统-UNIX Linux Windows
《计算机科学导论》读后感(四)：《计算机科学导论》读书笔记
evernote版本：点这里
第一章：图灵模型：计算机被程序所控制，将输入数据进行处理，成为输出数据 冯诺伊曼模型：储存器、算数逻辑单元、控制单元和输入/输出单元；程序和数据存储在储存器中 计算机硬件：冯诺伊曼原型的四个部分计算机数据：储存数据和结构数据计算机软件：程序：包括指令的序列、算法、语言以及软件工程的设计以及编写原则、操作系统 第二章：小数的转换：连续乘2，并记录结果的整数和消暑部分，小数部分留下继续乘，整数部分放到结果中。 第三章：数据的存储类型： 存储整数
无符号表示法符号加绝对值表示法二进制补码表示法（从右边复制位，然后一直到有一被复制，然后反转其余的位）（作逆运算后加一）存储实数
浮点表示法：符号、位移量和定点数余码系统：将一个正整数统一加到每个数字中，将它们统一移到非负的一边IEEE标准：S：符号E：指数M：尾数（1.xxxxx小数点后面的数字）第四章： 算数移位运算：右移：对整数除以2左移：对整数乘以2 算数减法：减数作补码表示，然后和被减数相加
第五章： 计算机组成 计算机子系统：
中央处理单元 CPU/中央处理单元的作用：进行数据的运算算数逻辑单元 逻辑运算 移位运算 算数运算 寄存器：用于临时存放住距的高速独立的存储单元 控制单元：控制子系统的操作 计算机指令周期：每条计算机指令都使用一个指令周期（85），步骤为：获取指令、译码、执行主储存器 主存：主存（ 内存？ ）是存储单元的集合（65） 地址空间：所有在存储器中标示的独立的地址单元的总数称为地址空间 缓存：缓存含有一部分主存内容的副本，当CPU要获取主存的内容的时候先判断缓存中有没有相同内容，如果有则从缓存中获取 输入/输出子系统：让计算机和外界通信，并在断电的情况下存储程序和数据 非储存设备 键盘和监视器 打印机 储存设备 磁的：角速度、寻道时间、传送时间 光的 ：CD-ROM ，CD-R ，CD-RW ，DVD子系统之间的互相连接，列出不同总线系统：
CPU和储存器互联 数据总线 地址总线 控制总线 IO设备互联 SCSI 火线 USB输入输出寻址的不同方法 (76)
IO独立寻址IO储存器映射寻址：指令集较小，但是占用存储地址同步CPU和内存的方法：
程序控制输入输出 中断控制输入输出 直接存储器存取计算机体系结构的趋势
复杂指令 - CISC 精简指令 - RISC改善吞吐量
流水线：在相同时间内执行不同指令的多个阶段 并行处理：计算机拥有多个控制单元、算数单元和内存单元6th计算机网络 达成双向通信的协议分层的首要原则：
保证每一个写一层可以进行两个对立且方向相反的工作两个站点中每一层的两个对象必须相同TCP/IP协议族：应用层（100 - 110）
客户机 - 服务器模式：通过名称进行区分，数据被打包为“消息”（99）WWW：万维网（具有连接分布在世界各地的文档中信息的储存库）客户端服务器统一资源定位器HTTP：超文本传输协议电子邮件的体系结构UA：用户代理MTA：信息传送代理MAA：信息访问代理TELNET：终端网络（远程登录协议）；SSH：安全外壳域名系统客户机 - 客户机模式集中网络分散网络传输层：通过端口号区分，数据被打包为“分段数据报”
UDP协议TCP协议网络层：通过逻辑地址进行区分，数据被打包为“数据报”
使用了IP协议数据链路层：通过链路层地址进行区分，数据被打包为“帧”
节点对节点的通信（117）节点：两个端主机和路由器看作节点，它们之间的网络看成链接（118）物理层
模拟信号：连续的值数字信号：离散的值7操作系统 操作系统是计算机硬件和用户之间的一个接口，让其他程序更加方便有效的运行，并且能够方便的对计算机硬件和软件资源进行访问。 自举过程：CPU调用自举程序，自举程序将操作系统掉入内存 组成部分
内存管理 内存的调度意味着当程序运行时，一部分程序会停留在内存中，一部分放在硬盘上（136） 分区调度：内存进行分区，CPU在各个分区内交替服务 分页调度：内存进行大小相等的分区，同一个程序被拆开，分到了不同的区上，程序的载入不用进行等待连续区域的出现。 进程管理 程序=>作业（被选中只想倒运行结束）=>进程（运行中的程序） 作业调度器： 进程调度器 队列：作业队列，就绪队列，IO队列 死锁：B需要A的资源，A需要B的资源（操作系统没有对进程的资源进行限制：可以占有这个资源，即使在获取另外资源之前一直不回动它，占着茅坑不拉屎） 饿死：A同时需要两个资源，但是这两个资源先后被其他的进程占用（操作系统对进程的资源限制过大） 设备管理 维护设备用 文件管理第八章：算法 递归 第九章：程序设计语言（program language） 程序语言的翻译（168）- 编译：将整个源程序翻译成目标程序- 解释：一行一行的翻译；翻译成字节代码然后再次翻译 过程式模式（强制性模式）：程序不定义过程，它只是触发或调用过程（170）面向对象模式：对象通过外部刺激来执行过程（172），相同类型的对象使用一组方法，为了创建这些方法，语言使用了称为“类”的单元。函数式模式：程序被看成一个数学函数说明式：根据逻辑推理的原则响应查询 程序可以通过下列两种方式之一来给子程序传递参数：- 传值- 传引用 10th软件工程
分析阶段：面向过程分析数据流图实体关系图状态图面向对象分析用例图类图状态图设计阶段面向过程：结构图、 模块化面向对象：详细描述类的细节，定义对象的方法实现阶段：可操作、可维护、可迁移测试阶段：目的是发现错误11th数据结构 数组：节点有特定的名字（索引）；索引直接定义了元素在实际存储上的相对位置； 记录：增加了域（属性） 链表：节点没有特定的名字；节点（域）：数据 + 下一个节点的地址第一个节点：定义头指针并且指向第一个节点最后一个节点： 节点的数据 + 一个无地址的指针 12th抽象数据类型 抽象概念意味着：一个数据类型能做什么是已知的；如何去做是隐藏的 线性表：创建、入列、出列、检索、遍历、空 限制线性表a) 栈：倒转数据、配对数据项b) 队列：“操作系统和网络中都有队列的身影” 广义线性表：用于元素的存储1. 元素具有相同的类型2. 元素顺序排列，有第一个元素和最后一个元素3. 除第一个元素外每个元素有唯一的前驱，除最后一个元素外每一个元素有唯一的后驱4. 每个元素是一个带有关键（不重复）字段的记录5. 每个元素的（这个记录）按照关键值排序 树：包括一组有限的元素，称为节点，同时包括一组有限的有向线段，用来连接节点，称为弧。如果树是非空的，其中有一个节点没有进入的弧，该节点为根。树中的其他节点都可以沿着从根开始的唯一路径到达。 二叉树：赫夫曼编码、表达式树递归定义：是一棵空树或由一个根节点和两颗子树构成，而每棵子树也是二叉树。 遍历原则1）深度优先pre：根在子树之前被处理in：根在子树之间被处理post：根在子树之后被处理2）广度优先：先处理节点的子节点，然后进行下一层。 二叉搜索树：方便查找定义：每个节点的值大于左子树所有节点的关键值，小于右子树所有节点的关键值特质：1）使用中序遍历的时候创建了一个升序列表2）可使用折半查找 图：由一组节点和一组节点间的连线构成的 13th 文件结构 顺序文件其更新，需要涉及以下文件：
新主文件：结果旧主文件：历史内容事务文件：修改的操作错误报告文件：报告的错误随机存储文件
索引文件：由数据文件组成，数据文件由key值和其对应的磁盘地址组成 （238）倒排文件：同一个磁盘地址有多个key相对应散列文件：key值代入某个函数得到文件的磁盘地址散列方法直接散列法求模法数字析取法如果出现冲突开放寻址链表桶散列法目录：绝对目录和相对目录；在大多数操作系统中的目录被表示成为一个包含关于其他文件的信息的特殊文件类型 14th 数据库 数据库：组织内被应用程序使用的逻辑相一致的相关数据的集合 数据库管理系统的必要组成部分：硬件、软件、用户、规章、数据 数据库模型：层次模型、网状模型和关系模型 关系的操作：
一元操作插入删除更新选择投影二元操作连接并交差数据库的建立：
通过ER图建立实体，属性和关系建立实体表和关系表规范化：减少数据修改的时候对于数据库重建的需要；第一范式，第二范式数据库模型：
关系型数据库（⬆️）：SQL语言允许使用这些关系操作，从关系型数据库中抽取更加复杂的信息分布式数据库（备份）面向对象数据库：XML语言用于从面相对象数据库中查询信息15th 数据压缩
无损压缩有损压缩后续略 16th 安全 信息：完整、可用、机密 后续略 17th 计算理论 三种基本语句：递增+递减+循环 => 能做高级语言所有的事情，但是效率要低 图灵机和简单语言的关系：图灵机模拟简单语言 图灵机的组成：读写头 控制器 磁带 斯德哥尔数：一个无符号数，其能被分配给任何用特定语言编写的程序 用格德哥尔数证明停机问题不可解决：停机问题：我们能编写一个程序来测试任何可以用格德尔数表示的程序是否会终止？证明过程：假设有一个程序（TEST），如果输入程序终止，则输入1，不终止，则输出0在test后增加一个判断，如何为1则无限循环，如果为0则不无限循环，记录为程序STRANGE将STRANGE自己调用自己，发现矛盾，说明TEST不存在。 多项式可解问题的复杂度要远远小于非多项式可解问题的复杂度，这导致了后者的输入数如果很大的话，计算机需要很长时间才能解决。
《计算机科学导论》读后感(五)：和《计算机科学概论》综合读更好
这本书的框架体系可以和《计算机科学概论》（就是内尔·黛尔和约翰·路易斯那本，2016·3,机械工业出版社）结合，知识点取长补短最好。但是，《计算机科学导论》有些地方过深，我认为就没有必要读下去了。
下面是我的读书笔记——结合了这两本书。有问题欢迎指出！
计算机系统 组成 硬件 构成机器及其附件之物理元件的集合 软件 提供计算机执行的指令的程序的集合 早期的编程 存储器既存储数据又存储程序 程序 有序的指令集；计算机可使用不同的指令集，公用的、不同（多样）的指令集为程序的编制提供了方便 算法 研究问题的解决方法/步骤的分析、设计、优化 语言 计算机语言源于自然语言，用于编写程序 软件工程 程序设计的原理，原则集合体与框架 操作系统 常用、公共指令集的集中，程序—计算机部件互动的接口 由软件、硬件管理的数据 分层 通信层 操作计算机的基础层 应用程序层 解决真实世界问题的能力 操作系统层 管理资源、设备—程序—数据交互 程序设计层 处理软件、实现计算指令、管理数据 硬件层 含门与电路，控制电流运行计算机 信息层 计算机表示处理、存储信息方式 抽象：心理模型，删除隐藏复杂细节，仅存实现目标所需信息（体现于六大分层之中） 计算工具与计算学科 计算机科学 科学学科 理解系统动作原理（计算机科学是科学学科） 理论 基本概念与符号，用于理解某学科内的对象的关系 实验 对模型进行研究判断，看是否可进行准确预测 设计 构造不同用途的计算机系统 系统领域 应用程序领域 计算工具：计算机 理论模型：图灵机 原理 输入数据→数量处理（程序→计算机）→输出数据 特点 可执行任何种类的计算 仅需要编写用于执行不同任务的程序 计算机 定义 通用的数据处理器 程序 定义 输出数据=输入数据+程序 特点 仅在输入数据与程序相同时，输出数据才会相同 基于图灵模型的冯一诺伊曼模型 基础：程序的可存储性 程序也是数据，也可以存储 内容 输入数据→I/O输入/输出（算术逻辑单元→存储器→控制单元）→输出数据 特点 存储程序 程序必须放在存储器中方可执行 按顺序执行指令 在内在中（提取→解释→执行） 指令本身也可以跳转，但计算机仍按顺序执行指令 意义 现代（1946—）的计算机（I代~V代）均构建于冯一诺伊曼模型 二进制与计算机的联系 信息存储形式 计算机各存储位反高电平与低电平两种信号，故它使用二进制存储信息（必须是0/1，不可为空） 用电子信号出现/消失的特定方式存储数据 对其他非电子信号的数据：进行编码 信息组织形式 将数据组织为许多小单元，而后将小单元组织为大单元 位与字 一个位，一个储存单元（放一个0或1），为一个比特（Bit），其中，8位=1字节（Byte） 字：数字字节的集合，字的总位数=计算机的字长（例如：32位CPU，64位CPU） 计算机发展历史 计算机种类 机械计算机 电子计算机 非冯氏结构计算机 冯氏结构计算机 计算机发展的三个阶段 机械计算机器 17世纪，Pascsline 首台机械计算器（加减运算）——布莱斯·帕斯卡 17世纪后期，莱布尼茨之轮 加减乘除均可——莱布尼茨 19世纪初期 ，雅卡尔提花织机 首台利用存储与编程概念，约瑟夫—玛丽·雅卡尔 1823年，差分机1号 数学运算能力强，与冯氏体系相似——查尔斯·巴比奇 1890年，人口普查机 赫尔曼·何勒里斯设计、制造出具有编程能力的机器用于人口普查 非冯氏结构的电子计算机 原因：程序不在存储器中，在外部进行编程 20世纪30年代 ABC 首台完成特定任务的计算机 Z1 康拉德·朱斯研制，欧洲唯一的一台电子计算机 Mark I 完全机电式计算机 20世纪40年代 巨人 阿兰·图灵，用于破译“恩格尼玛” ENIAC 首台通用的、完全电子的计算机 冯氏结构的计算机 1950年——EDVAC、EDSAC的诞生 1950-1959：第I代——电子管计算机 出现商用计算机；大机构使用 1959-1965：第II代——晶体管计算机 中小企业可负担，高级语言出现 1965-1975：第III代——集成电路计算机 出现小型计算机，软件包与软件工程 1975-1985：第IV代——出现微机 出现计算机网络 1985-现在：第VI代 出现掌上电脑、台式电脑，太多了，略 计算机科学的社会/道德问题 社会问题 人们对电脑的依赖程度↑ 社会分裂/矛盾 计算机消费及应用仅针对一部分人 道德问题 隐私保证 数据的版权 病毒及恶意软件的破坏 盗取金钱 记数系统 什么是数字系统 使用有限的数字符号（数码），定义了表示一个数字的方法 数码需重复使用，只表示了一个数，不改变它的值 基本概念 数字 可运算的一个值 自然数 0、0+n×1（n=1,2,……） 负数 小于0的数 整数 自然数+负数 有理数 整数+两整数之商 记数系统（位置记数法） 基本概念：基数 概念 记数系统的基本数字 作用 规定使用的数字个数，与遇到X进位的情况 组成 整数部分+小数部分 内容 数位按顺序排列，其中一个数位上有一个值 该法表示数字位上，第n位与第n数位之值乘积的和 多项式记数法：将上述乘积展开 常见进制及其转化 常见进制 十进制 0，1，2，3，4，5，6，7，8，9 二进制（计算机科学中常用） 0，1 八进制 0，1，2，3，4，5，6，7 十六进制 0,1,2,3,4,5,6,7,8,9,A(10),B(11),C(12),D(13),E(14),F(15) 相互转化 二进制→十六进制 关键：从右到左4个一组→替换 二进制→八进制 就是将上面的“4”换为“3” 八进制→十六进制 八进制→二进制，是二进制→八进制的逆向操作；而后二进制→十六进制 十进制→其他进制 短除法除以其他进制的基数，倒着求出结果的顺序写出各数字 其他进制→十进制 规律 求出其多项式记数法的和即可 任何记数系统，最右边数字均为“1”数位 运算 加法 A+B>R（基数）时，进位 减法 “较小数－较大数”时，向前借一个基数 验证 全部转化为十进制计算 非位置化数字系统 关键 一个并列表示的符号仅在共内部进行运算后，才有大小意义 典型：罗马数字系统 数据存储 数据与信息 数据与信息的关系 数据（基本值/事实）→按某种统一的数据表示法组织/处理XX格式→（输出）还原为信息 计算机中的数据均以二进制存储（成本低，更可靠） 数据压缩 减少数据存储所占的空间，用于在有带宽（某时间段内两点传输的最大位/字节数）限制的数据传输中。 无损压缩 压缩时不丢失任何信息 有损压缩 压缩时丢失一些信息 二进制的特点 1个位仅能表示0/1两种状态，若有n位，则可表示2的n次方种状态（一个位组合=一种状态） 2的n次方种状态下，仍会有一部分位组合无对应意义（浪费）（任何类型的数据之最小存储量均为k×2的n次方，k为正整数） 模拟数据与数字数据 计算机的问题 用有限的机器表示无限的世界（前者离散有限，后者连续无限） 模拟数据 连续形式表示信息 数字数据 离散形式表示信息（将信息数字化，即分割信息为离散片段） 降级、PCM（脉冲编码调制）、重新计时： PCM的特点 电信号在两极端之间进行跳跃变化 电信号会由于环境影响波动（降级），周期性地重新计时数字信号不会让电信号降级太多丢失信息 数字数据存储法 两个问题：正负号存储、小数点显示 溢出问题：分配给结果的位数存不下计算出的值。此时多出的部分将被舍去。 正整数与0表示法 常规方法 转换为二进制即可 应用 计数 从1开始 寻址 一个存储单元中有另一个单元的地址（地址：0开始→整个存储器总字节数） 储存其他数据类型 负整数表示法 符号数值表示法 形式 ±数字（±表示正负类别，数字表示大小） 切割二进制数g切为两部分：0开头→正数；1开头→负数 数据运算 A+B<=>A向右移动B个单位；A-B<=>向左移动B个单位（在数轴上） 使用步骤 输入→转化为二进制数，加位补全，加符号位→按n位下二进制数据的本存储模式存储 缺陷 ±0的存在 有正溢出与负溢出（原因：首位用于定正负，则仅三位表示数据处） 应用 一定范围的正整数及负整数 存储部分实数与采样模拟信号 十进制补码（定长量数） 原理 设定X（X>0），用0—X的一半数字表示负数，另一半表示正负（无“±”） 数据运算 按十进制运算规则，但舍弃进位，且-B=>+(-B)(-B与B表示不同) 数轴上：将十进制补码中的负数=>符号数值表示，然后执行。 n位数字中，负数X表示为10的n次方+X 二进制补码 原理 首位1=负数/0=正数；而后位才表示数字大小（绝对值，用二进制表示） 计算 求出该十进制数之二进制码1→0，0→1（即反码）；而后该数加1 或者从目标负数右端复制位，直到有1被复制；而后其他的位全部取反码 特点 仅有一个0；有正溢出与负溢出 应用 用于存储整数的标准表示法 实数表示法：浮点表示法 实值：非整数的值；实数=整数部分、小数部分 形式 符号×尾数×b^exp（exp调整原数至不含小数点为止，空位补0上去;b=10时为科学计数法，此时尾数只能有1位整数） 优点 仅存储上述三个部分，符号，尾数，exp(仅R=2时) 转换 十进制→其它进制（小数部分） 正向 确定目标进制基数R 原数×R，将结果中“.”前一位作1°位（左→右，后同） 将结果小数部分×R，得到之数的整数部分作2°位 循环直至小数部分=0 反向 知道了，不写，略 文本表示法 着重点 将文章中的各字符分别表示并存储——建立字符集 字符集 概念：字符与对应表示它们代码的清单 思想 每个字符对应一个二进制字符串，存储后者 两种典例 ASCII字符 各字符有相对顺序（排序） 仅能表示英语；部分字符不作输出 Unicode字符 ASCII字符集的超集，可表示任何语言 文本压缩 关键字编码 原理 常用单词→单个字符 局限 无法出现于原件；大小写版本分开编码；压缩率取决于文档主题 扩展 用特殊字符替换文本中特定的部分（前/后缀）（压缩率不高） 行程长度编码（迭代编码） 原理 重复的字符序列→标志字符+重复字符+重复次数 特点 长度为2/3的序列不予以编码 赫夫曼编码 原理 每个字符在字符集中由定长的二进制位串表示——较少位表示常用字符，较长位表示不常用者 特征 一个编码<=>一个字符（左→右，可用于还原） 音频数据表示法 声音的传播：声波 原理：PCM（脉冲编码调制）与采样 1.采样：同期性测量，记录信号电压——数字化信号电压 2.采样是有损的，但较高采样率足以完成音频表示 步骤 1°在模拟信号上采集一定数量的样本（值） ①每秒钟采集的样本数量称为采样率（S） ②样本率与信号平坦程度负相关 2°对样本执行量化（取为最接近整数值） 3°将每个样本→二进制数（每个样本位的数量=位深度，B） （位率R=BS，MP3标准的R=705.6KB/S，采用有损压缩法） 示例 塑胶唱片、CD（唱针上下伸缩/唱盘表示凹痕激光反射的强度=>信号电压） 音频格式 种类 mp3、mp4、wav、flac、…… MP3格式压缩原理： 展开分析频率→与人类心理声学模型比较→舍弃不可听见信息→用赫夫曼编码压缩 图像与图形表示法 颜色表示法 原理 颜色是人类视网膜对不同频率光的感觉，所有颜色均由红色（R）、绿（G）、蓝（B）组成 表示与特点 RGB值（R值，G值，B值） ①三种值各自范围均为0~255（与参与度/份额正相关） ②增强彩色：三种值各自占5位，色深度16位 真彩色：三种值各自占8位，色深度24位 由于人眼与显示器限制，实际可见颜色数<真彩色颜色数 图形与图像数字化 光栅图/位图 （缺点：文件体积太大，不便重新调整图像大小） 1°对模拟数据组成的照片进行采样（扫描） ①样本称为像素，每个样本有单独密度值 ②每秒钟扫描到的像素数称为解析度 2°每个像素都是一定位数的二进制数，一种颜色对应一个一定位数的二进制数 ①真彩色：用24位编码一种颜色；一种颜色=3个三原色，一个8位（224种颜色） ②索引色：用8位编码一种颜色（选256种颜色建立索引，各赋于0-225的一个值） ③像素数×一种颜色的位数=存储照片的位的数量 ④JPEG：真彩色（压缩图像）减少位数量；GIF：索引色 矢量图：几何模型/面向对象图形 ①将图像分解为几何图形的组合 ②每个几何图形由数学公式表达，系统在显示/打印图像时设计大小和重新用公式画出图像 ③用途：Flash创建字体、CAD 视频表示法 本质 一帧一帧的图像连续播放（帧=幅） 视频压缩技术 原理 视频编译码器：专门进行对视频的压缩/解压缩器，使视频可以在计算机或者网络上播放 特点 基本上采用有损压缩 类别 时间压缩 查找连续帧之间的区别——只保存改变的部分（增量帧） 针对于连续的图像：帧与帧之间变化不大的视频片段 空间压缩 删除单个帧中的冗余信息 常将颜色相同的像素聚集在帧的某一个区域中，将只存储此区域的颜色与坐标 门与电路 计算机电学概念 电平 计算机以电平区分信号值 低电平（0） 0-2V 高电平（1） 2-5V 门、电路及其表示法 门 1个/多个信号→一个信号（一个门<=>一种门函数） 电路 由门相互关联组合而成，以逻辑控制其电流 表示方法 布尔表达式 以布尔代数的运算与属性来用表达式定义与操作逻辑电路 逻辑框图 用图形表示电路及其元件。 真值表 列表法表示门函数（△！可完全表示门函数） 门 本质 门的输入+门（对应的）函数=门的输出 也存在有三个输入/更多输入的门 六种主要的门 非（Not） 1→0，0→1（对输入者求逆） 与（AND） 仅均输入1时输出1，否则输出0 与非（NAND） 仅均输入1时输出0，否则输出1 或（OR） 仅均输入0时输出0，否则输出1 或非（NOR） 仅均输入0时输出1，否则输出0 异或（XDR） 输入相同输出0，否则输出1 构造 晶体管运行原理 晶体管常有三个极：发射极（常接地）、基极与源极（上面常接输出极） 基极信号为高电平，源极信号被接地，晶体管关闭；若为低电平，则源极信号仍为高电平，晶体管打开 非/与非/或非门构造原理 非门 输入极（Vin）<=>基极，输出极（Vout）<=>输出 与非门 V1、V2处同时输入高电平，源极接地，晶体管关闭（输出低电平） 或非门 V1/V2处任意一个输入高电平，源极均会接地 电路 仍可用描述门的三种方式描述电路 分类 组合电路 输出由输入决定 数个门的组合，其研究方法用“结果→输入”作出真值表并求出电路对应的布尔代数表达式。其设计与等价性体现出布尔代数的分配律 时序电路 输出=f（输入，电路现有状态） 加法器 由两个半加器组成的全加器：一个半加器管求和，一个半加器管进位 多路复用器 可以决定用某入输入作为输出（采用选择信号/选择控制线），有多个输入但仅有一个输出 多路分配器 仅有一个输入，但有多个输出 存储器电器 本质 存储值 S=R=1，X（当前状态）与Y值相瓜，S+Y（与非门）→X，X值不变。反过来，R+X（与非门）→Y，Y值不变，则X不改变。 存入值 S/R中一值为0.X（当前状态）设定好后，若0→1，则X（当前状态）继续保持 集成电路（IC） 嵌入了多个门的硅片，封装于塑料或者陶瓷中，边缘有引脚，可以焊接在电路板上或插入合适的插座中 按照包含的门数分类，可以分为小/中/大/超大规模集成四类；芯片具有很高的门-引脚比，使得其引脚数目减少 最常见的集成电路是CPU 计算机组成 CPU 组成 算术逻辑单元（ALU） 执行数据运算：逻辑运算、移位运算、算术运算 寄存器 数据寄存器 存储输入数据与运算（中间）结果 指令寄存器 存储大小内存中取出的指令 程序计数器 保存正在执行的指令；完成指令后自动加1指向下一条指令地址 控制单元 控制各个子系统的操作 补充概念 核 单个芯片中集成的CPU 时针 在计算机内部集中生成电脑冲来保证各部分动作协调，脉冲次数即为CUP处理速度（单位Hz） 总线 连接计算机内各元件的电线，其中前端总线（FSB）负责CPU与外界（内在和I/O设备） 携带地址（决定数据的流动方向）、数据与控制信息（控制地址与数据的流动） 总线宽度 同时传输的比特数 处理器位数 中央处理器一般寄存器中的位数 缓存 集成在CPU内部的小型、快速的储存介质，CPU会先从缓存中读取数据，仅缓存中无所需内容时使用FSB 性能折中 CPU与耗电、FSB与成本、缓存与速度的平衡 （性能↑耗电↓）（速度↑制作成本↑）（空间↑速度↓） 主板 个人计算机中，冯·诺伊曼体系结构的计算机的部件均安装在一个印刷电路板上，即为主板 主存储器 定义 存储单元的集合 存储单位 字节（B） 8位=1字节 KB 2的10次方字节=1KB MB 2的20次方字节=2的10次方KB=1MB GB 2的30次方字节=2的20次方KB=2的10次方MB=1GB TB 2的40次方字节=2的30次方字节KB=2的20次方MB=2的10次方GB=1TB 地址 每一个存储单元唯一的标识（以位形式存储） 存储单元中的数据以字形式传输于内存中，一个地址对应一个字的存储器 字与字节的区别 字 更长的位模式，每个字均用地址标识 字节 字长度的单位，用字节衡量字的大小 内存地址空间（内存总字节数） 字长×字的数量（N），是独立地址单元之总数N个字，用N以2为底的对数位无符号整数标识 存储器类型 RAM类（随机存取存储器） 主存主要组成部分 特点 每个字节均可访问（读写）：易失性（断电后失去信息） 技术类别 SRAM 快，昂贵（传统触发器门电路） DRAM 慢，便宜（电容器） ROM类（只读存储器） 特点 只能读不能写；非易失性（断电后不丢失） 技术类别 PROM 只能存储一次程序，而后只读不能写 EPROM 可用特殊仪器擦写 EEPROM 可用特殊电子脉冲擦写（CIH病毒感染原理） 存储器层次结构 高速存储器 较少，针对速度要求较高 常见于CPU的寄存器 中速存储器 数量居中，存储经常需要访问的数据 典例：高速缓冲存储器 速度：寄存器/CPU>高速缓冲存储器>主存 位置：CPU与主存之间 优势所在：提升处理速度 低速储存器 数量较多，存储不经常访问的数据 I/O子系统 非存储I/O设备 键盘（输入） 监视器（显示并响应输入） 屏幕尺寸（11.6''，12.5''……） 显示区域对角线长 分辨率 显示器显示元素的水平行数，m×n指屏幕水平方向有m个像素，垂直方向有n个像素的像素分辨率。（但垂直方向像素≤n个像素，水平方向亦同） GPU（图形处理器） 负责处理图像的显示与计算 触摸屏 概念：同时担任I/O功能的显示屏 电阻式 接触的竖直线与水平线说明了触摸屏幕的位置 电容式 依靠比较来自每个角的电流强弱确定触摸屏幕的位置 红外式 依靠用户打断红外光束的位置来确定触摸点的位置 表面声波式 类似于红外触摸屏，依靠用户打断声波的位置来确定触摸点的位置 打印机（产生永久性记录的输出设备） 鼠标 操纵杆及其他 存储I/O设备 磁介质存储设备 磁盘 结构 由磁片堆叠而成，由薄磁膜封装起来 每个盘面都被划分为一些磁道（同心圆），每一个磁道又被分为若干个扇区（弓状线） 磁道间与扇区间均存在间隔 工作原理 通过每一个磁片的读/写磁头读写磁介质表面，进行读取与存储 读写头按I/O指令寻找磁道，待找到正确位置后等待目标扇区抵达读写头下。 性能指标 角速度 旋转速度 寻道时间 磁头寻找磁道 传送时间 数据从磁盘→CPU/内存 分类 HDD（Hard Disc Drive） SSD（固态硬盘） 软盘（基本上停止使用） 磁带 结构 以读写头、磁带、带盘、收带盘组成 工作原理 顺序读取 特点 速度慢于磁盘，但便宜 光存储设备 制造原理 把坑弄出来 光盘原理结构与磁盘类似，但是，划分成的是里→外盘旋的螺旋磁道 速度 从1x（单倍速，约150KB/s）到40x（40倍速，约6MB/s） 指光驱读写的最大速度而非平均速度 光盘分类 CD CD缺点：容量小；光盘缺点：容量过小 CD-ROM只读光盘 优点：①成本可调控；②适用于量产 缺点：仅适用于光盘量产；不能写 CD-R可刻录光盘 优点：①适用于用户自行备份数据；②只写一次，读多次 缺点：仅能写一次 CD-RW可擦写光盘 优点：可以擦写，多次写入数据 缺点：①价格比CD-R贵；②内容可以被改变 DVD 优点：①容量更大（4.7G、8.5G、9.4G、17G）；②采用MPEG压缩，视频可存储更多内容，更长时间 缺点：最大容量仅17G（双面双层DVD） DVD+R DVD-R DVD+RW DVD-RW 光盘驱动器类别 光盘驱动器：读取光盘的设备 ROM：只读；R：可记录的；RW：可重写的；DL：双层。这些术语同样适用于光盘 出现了蓝光格式，容量更大——光盘驱动器使用了蓝色激光 CD-ROM CD-RW DVD-ROM DVD-RW 闪存 概念：含USB端口的非易失性计算机存储器 用途 制作SSD（比HDD更调整、更低功耗） 计算机子系统的互连 CPU—存储器（使用三种总线） 数量总线 1位数据1根线 地址总线 用于访问存储器中的字；1根线传输1位地址数据 控制总线 用于CPU内存间传递信息；m根线传输2m条指令 I/O设备之间 每一个I/O设备都有一个特定的控制器（接口）接至总线；减少了不同种类设备之间的差异 按照串/并行分类 串行控制器 仅一线连接至设备 并行控制器 多线连接至设备 控制器种类 SCSI（小型计算机系统接口） 并行接口 每个设备都必须要有唯一的地址 连接线两端均有终结器 火线（IEEE标准1394规定） 快速传输（高清摄像机/高性能磁盘驱动器） 串行接口 连接线无需终结器 设备可以连接至火线控制器，再从火线控制器以火线和其他设备连接 USB（通行串行总线） 串行接口 多个设备可以连接至USB控制器（集线器）上 一种常用的接口，分3个标准：USB1.0、USB2.0、USB3.0 HDMI （高清晰度多媒体接口） 适用于计算机显示器、视频投影仪、数字电视或数字音像设备的多媒体播放、信号接收 可以用于以太网络数据连接 VGA端口 用于连接笔记本—外部显示器/投影仪 Express Card槽 允许计算机外接电路板，实现一些计算机的特殊功能 I/O设备寻址（I/O设备—CPU） I/O独立寻找 读/写内存（指令集）不同于读写I/O设备（指令集） I/O设备各有不同地址 内存地址可与I/O地址重叠 I/O存储器映射寻址 仅一份指令集 I/O的寄存器占用一部分内存地址，作为内存中存储的字 程序运行流程 本质 冯·诺伊曼体系：计算机通过执行程序，将输入数据转换成输出数据；而程序与数据都放在内存中 机器周期 读取下一条指令 由控制单元进行 算术逻辑单元中，程序计数器存放下一条指令之地址，指令寄存器存放即将执行的指令（在完成机器周期后，程序计数器内容改变） 译解指令 由控制单元进行，译解为控制信号（二进制） 从内存中获取数据 控制单元从内存中获取内容装入寄存器 执行指令 控制单元将译解出的控制信号交付算术逻辑单元 执行结果可能在内存/寄存器中 CPU与I/O同步的方法 CPU等待I/O设备（浪费时间） 数据均在内存中转 中断控制I/O 等到I/O设备准备好后，I/O设备通知CPU而不必让CPU等待I/O设备（仅监视） 数据均在内存中转 DMA DMA控制器承担了一部分CPU的功能，DMA控制器工作时CPU空闲 计算机体系结构 冯·诺依曼体系结构 CISC（复杂指令集计算机） 特点：指令集复杂；微程序设计；成本略高 示例：Intel—奔腾系统CPU RISC（精简指令计算机） 特点：指令集简单；复杂指令用简单指令模拟 与CISC比较：程序设计难，但更为便宜 流水线 控制单元同时执行机器周期的2个/3个阶段 并行体系结构 定义：CPU中多控制单元，多算术逻辑单元，多内存单元，抑或多处理器计算机 大规模并行处理器、处理器可联网通过专用网络相连，提高运行效率 类别 （S=单，M=多，I=指令流，D=数据流） SISD 比特级：增加计算机的字长 SIMD 数据级：同组指令处理不同数据集（一个CPU一个数据集） MISD MIMD 任务级：流水线多CPU完成一个任务 用途 科学团体及科学任务 嵌入式系统 概念 为完成小范围功能而专门设计的计算机 架构 程序写入ROM中，其整体位于单个微型处理芯片上 应用 各种数码的电子设备中（程序常用汇编语言） 低级程序设计语言与伪代码 计算机操作 计算机：对数据进行存储、检索、处理的可编程电子设备（可编程：改变指令就可改变对计算机对数据的处理） 机器语言 概念 因处理器不同而不同、固定在处理器内部且处理器唯一能够识别的计算机指令集。 组成 由一定数量的指令组成。一条指令只能执行一个操作。 与其他计算机编程语言的关系 高级语言/汇编语言—（翻译）—>机器语言 缺点 程序员只能更专注于硬件；指令繁琐；过程枯燥 组成与使用 操作数：要处理的数据 在学习此部分时，我们需要明白：我们必须搭建一台电脑，通过这台电脑我们可以对机器语言有一个大体的理解与体会。当然，这台电脑是被从实体机中大大简化的理想模型! 1.执行指令时，使用的寄存器：程序计数器、指令寄存器、累加器（保存操作的数据与结果） 2.指令格式：指令说明符+操作说明符 （1）指令说明符：操作码（说明指令的含义）+寄存器说明符（说明使用的寄存器）+寻址模式。分为两种模式： ①立即寻址——操作说明符存储操作数， ②直接寻址——操作说明符存储操作数存储的内存地址 （2）操作说明符：以寻址模式决定其存储内容。 一元指令：无操作数之指令。 程序执行的步骤 读取—执行周期 汇编语言 组成 数个助记指令码，每一个都只能执行一种特定的操作（代表了一条特定的机器语言指令）。 执行过程： 1.汇编语言程序输入汇编器 2.汇编器读取助记码，使用汇编器指令，输出机器代码程序 3.CPU执行机器代码程序。 注释 解释某段代码目的文字。（不能太多但是不能没有） 优势 接近底层 缺陷 效率低且太过面向硬件，有硬件方面的特异性，不能够跨平台。 具有分支/循环的程序 具有分支的程序 提出问题，得到答案后根据答案采取行动。 具有循环的程序 重复执行一个过程（操作一样但是每一次结果可能不同） 其中，在每一次重复循环时更新一次散列标记（又名计数器。初始值为0,在每一次循环时加1），用该散列标记与要求的循环次数做比较以确定是否结束循环。 算法的表达 算法的概念 解决问题的方案，使用伪代码表达。 伪代码的相关概念 伪代码必须翻译成程序设计语言才能在计算机上运行 变量 内存中存储值的位置，其命名应该反映出其存储值在算法中的作用。 赋值 （清除变量中原有的值）将另外的单个值或者表达式（变量和操作符）放入变量中。 表达形式 Set 变量名 to 单个值/表达式，或者变量名←单个值/表达式。 在直接使用变量名而不是使用“”括起来时，直接访问变量的值。 输入/输出 从外部世界向计算机中输入数据。 表达 输入—Read/Get/Input，输出—Write/Display/Print 输出+“xx”，显示xx；输出+变量名，显示变量的值。 布尔表达式： 形式 while（……）或if（……），括号内部即是。 作用 判断是否执行while/if结构内的代码。如果满足布尔表达式，则执行；否则不执行，跳到下一行不缩进的代码。 循环结构和重复结构中，if、else、while结构下的代码都会缩进 选择结构： 作用：①选择性地执行或跳过某个操作。②选择两项操作之一。 if—then—else 如果满足if（判断式）中判断式的条件，就选择执行then下面缩进的代码；如果不满足，就选择执行else下面缩进的代码。 if—else（后者不写） 如果满足if（判断式）中判断式的条件，就执行if下方缩进的代码；如果不满足，直接跳过该循环结构，执行下一行没有缩进的代码。 重复结构 作用：重复执行一段指令直到满足要求。 while（判断式） 满足判断式时，重复执行这段代码；不满足判断式时，跳出该循环，执行下一行不缩进的代码。 编写、翻译与执行伪代码算法 编写伪代码算法 策略 ①提出问题②写出大致思路③细化与补充细节④对伪代码进行桌面检查（用纸和笔，把自己想象成一台计算机，按照代码走一遍，跟踪变量内容，确定是否满足要求。又名走查。） 细化与补充细节的方式 提出问题，应用伪代码的相关概念解决。 翻译伪代码算法 按照使用的编程语言的规则规范转换即可。 执行伪代码算法 列表（关于变量名、常量名及其每一次循环结束后的内容），走查算法。 问题求解与算法设计 如何解决问题 数学家、计算机科学的先驱之一G.Polya在自己的著作《How To Solve It：A New Aspect of Mathematical Method》中提出了一个经典的解决问题的思路。 提出问题 必须要问的问题 （1）我对问题了解多少？（2）解决方案是怎样的？（3）是否存在特例？（4）我如何得知问题已经被解决？ G.Polya的“如何解决它”列表的核心内容（扩展版本） Step 1 理解问题——需要知晓： 问题是……；已知信息是……；条件是……（内容、被满足的可能性、对问题的影响程度和矛盾程度）；分割问题 Step 2 设计方案——找到解决方案与已知信息的联系，其中思考的方式可如下： （1）以前见过相同问题或者其变形 （2）相关的问题 a.可能适用的定理 b.引用其解决方法或者解决结果（可能会要求添加辅助元素） c.描述方式的变换或等价转换d.寻找一个更简单、更普适、更专用的问题 （3）相似的问题 （4）解决部分问题 （5）当条件或已知信息发生了变化（增加、减少和修改）时，问题的变化情况；从已知信息中获取的相关情况 （6）是否涉及了所有的已知信息、条件与相关概念 Step 3 执行解决方案——检查与证明每一个步骤的正确性 Step 4 回顾——检查结果与已知信息，结果因问题不同而不同的差异性、重复性与可迁移性 借鉴 寻找熟悉的或相似的情况，使用已经存在的、成功的解决方案，不要重复造轮子 分治法 将一个问题划分为数个小问题，小问题再继续划分，如此进行，直至可以解决每一个小问题为止。 算法 有限的时间内，用有限的已知信息解决问题/子问题的指令集。（就是G.Polay所提到的解决方案） 注意：有求和、求积与求数组中最值这3种基本算法，但太过简单，略；后面介绍几种常见而略难的基本算法 特点 处理已知信息的极限、解决方案中的条件描述必须明确；逐步解决问题与完成任务；各步骤（指令）必须清楚明白、有序组织；在一定时间内终止。 计算机问题求解过程 流程：分析与说明阶段→算法开发阶段→实现阶段→维护阶段 遵循G.Polya的“如何解决它”列表的思想。 注意：和后面的软件过程相关联 分析与说明阶段 理解/定义问题，说明程序要解决的问题。输出：清楚的问题描述。 算法开发阶段 开发算法与测试算法。输出：问题通用的解决方案。 实现阶段 编码（将算法翻译为程序设计语言）、测试与完善程序 维护阶段 使用程序并完善它 自顶向下的方法 即G.Polya的“如何解决它”列表的思想的计算机科学体现 分析问题 理解问题→列出处理的对象、个人对问题或信息的假设→思考手动解决问题的方案→明确采用的方案，开发一个全面的解决方案（算法） 列出主要任务 用伪代码/自然语言在主模块中重新描述问题，用含义明确的标识符标明由主模块分割而来的各任务模块。 同时，可以：引入控制结构、推迟细节、逻辑重组。 编写其余的模块 在保证上层模块完整性的前提下，不断细化每一个模块，直至每一个模块的每一条语句均为可执行的具体步骤为止。 根据需要进行重组与改写 按照需求修改或重写代码。这是正常的、必要的∩ω∩ 测试算法 测试的目标是验证这个过程能够求出准确的、预期的答案。 测试应当在算法开发较早的阶段进行。 嵌套结构 一个控制结构嵌入另一个控制结构。 抽象步骤 需要进一步扩展的步骤；具体步骤：不需要扩展的步骤。 算法的设计本身就是将所有的抽象步骤扩展延伸为抽象步骤的过程。 算法的表述形式 UML 就是流程图，体现结构与思路 伪代码 模拟真实代码，UML的文字版 有简单参数的算法 简单变量（原子变量）：存储在一个地方的一个值，存储的内容不可以分割和独立访问。 带有选择（判断）的算法 就是if……else结构（判断→选择结构）的应用。如果满足某个条件就会触发某个操作，否则会触发另外一个操作。 带有循环（重复）的算法 分为两种：计数控制循环、事件控制循环。 计数控制循环 运行过程：初始化（将循环控制变量，即计数器设定为为某个值）→测试（检测计数器的值是否已经达到特定值）→更新（此处又名递增，如果没有达到，继续循环，然后计数器的值加1)或停止循环（如果达到） 事件测试循环 运行过程：与计数控制循环类似，有初始化、测试与更新三个部分。但有以下区别： ①计数器并非只进行增量，而有可能参与算法之中；计数器的值仍然会更新，但不一定是增量，而是由循环本身进行的运算的结果所决定，因此可能无法直接由代码得知循环进行的次数。 ②测试与更新的顺序可能没有明确的先后顺序。 ③循环的终止由循环本身、计数器的值和特定值的关系共同决定。这是因为，在计数控制循环中，计数控制器是独立的，只会在循环完成后执行加量,其值加1：而在事件测试循环中，计数控制器会参与循环体本身，其值将由循环本身决定。 顺序结构 运行过程：逐步执行指令即可，没有选择与循环！ 复杂变量 什么是复杂变量？就是集合数据并存储，可以分割和独立访问的存储内容 数组 1.概念：可以通过单个项目在集合中的位置（即索引，一般从0开始）访问该项目的项目集合。 2.复杂变量使用的时候必须说明其结构（声明），简单变量使用时不必 3.有关数组的算法：搜索（寻找特定项）、排序（将元素按照顺序放入数组中）与处理（对元素进行预算）。 记录 概念 可以通过项目名字访问该项目的项目集合。 特点 ①集合可以包含任意类型的数据。②一个对象可以同时含有多个项目。 记录中一个位置在算法中的表示：变量+点+字段名（项目的名字） 类 在第九章中详细介绍。 搜索算法 顺序搜索 一个一个元素拿来和目标元素比对。当二者匹配或所有的元素寻找完毕但是没有找到匹配项时，循环中止。 有序数组中的顺序搜索 因为数组有序，直接设置在目标可能出现的地方停止搜索即可。 二分检索 1.此方法从数组的中间开始比对，与数学中的二分法类似。 2.优势：有序数组且元素不超过20个时较快。但是因为计算索引，比较操作花费时间更长。 排序算法 选择排序 1.原理 ①将数组分为两个部分——无序部分和有序部分。②在无序部分中寻找最小者，排至有序部分第一个。③在剩下的无序部分中继续寻找最小者，排至有序部分的第二位。而后重复③的前面步骤，排列第三个、……直至最后一个。 2.算法编写时，除了要造两份列表外，还要准备三个变量用于互换算法。 冒泡排序 1.原理：从数组的最后一个元素开始，这个元素与它的前一个元素比对，如果前者大于后者，则二者交换位置；否则，不交换位置。然后如果之前发生了位置交换，倒数第二个元素和倒数第三个元素重复这个操作；否则，才换完位置的较大元素和它的前面一个重复这个操作。 2.特点：大量的交换操作，而且速度较慢。 3.对有序数组的冒泡算法定义：若各个元素的所有迭代都没有发生元素的位置交换，则该数组有序。 插入排序 1.原理：先排好第一个元素和第二个元素的位置；然后将二者作为一个整体，与第三个元素确定好位置关系，又作为整体与第四个元素确定位置关系……其中，整体内部的位置可能因为顺序会插入新的元素，整体内部元素的相对位置并非不变。 2.特点：元素的位置顺序是相对于其他元素有序的，但在整体上，各元素还不完全有序——因为没有排列完全。 递归算法 概念 在执行时某种程度上会调用它自己本身（又名递归）的算法。 本质 使用选择语句来确定是调用算法本身（重复一遍算法）还是停止执行算法的循环控制结构。 适用的情况 问题陈述逻辑上分为基本情况（答案已知的情况）与一般情况（调用自身来解决问题的更小版本的解决方案）。必须在设计递归解决方案前设定尺寸系数（衡量问题规模） 子程序结构 概念 一个控制结构，是各程序下执行某一小任务（小模板任务）的算法 运行机理 ①程序的一部分代码被对应地给予一个名称（这段代码叫做调用单元）。②而后另一部分代码使用这个调用单元，则这个调用单元将会被执行 ，同时其他的代码将停止执行。③当调用单元行完成后，可能会返回一个值给调用它的代码。其他停止执行的代码恢复执行 优势 一种有效的抽象工具，易于理解；可以调用，无需重写。 递归阶乘 N的阶乘=N*（N-1）的阶乘，（N-1)的阶乘=（N-1）*（N-2）的阶乘，……这就是递归思想的典例——调用自己。阶乘你已经学过，略。 递归二分检索：与二分检索相似，都是调用了“二分”这个思想和方式，递归思想的体现。 分裂算法 概念 首先将数组分裂成两半，然后对这两部分各自又执行分裂操作，对分裂出来的部分又继续执行这个操作……直至分裂出来的部分易于排序。各部分排好序后组合到一起即形成有序数组。 优势 对于无序数组排序快速。 几个重要思想 信息隐蔽 概念 设计每个特定的模块时，只考虑与之相关的细节，而隐蔽其本身的细节，以控制对模块本身的细节的访问。这样可以避免模块本身细节发生变化，让模块大幅度修改甚至重写的问题。 结果 抽象——只观察到与模块相关的细节而非模块本身的细节。 （处理复杂事务的有效工具 ） 几种典型的抽象 数据抽象 分离数据的逻辑视图与数据逻辑视图的实现。 过程抽象 分离动作的逻辑视图与动作逻辑视图的实现。 控制抽象 分离控制结构的逻辑视图与控制结构逻辑视图的实现。 事务命名 概念 给数据或过程一个有实际意义的名字——标识符 特异性 不同的计算机程序设计语言有着不同的标识符构成与使用规则。 抽象数据类型（ADT）与子程序 抽象数据类型 抽象数据类型与观察数据的层次 抽象数据类型 数据和操作明确地与其特定实现分离的容器。 Note：容器就是用来存放其他对象的。 观察数据的三个层次 应用层（用户层） 与特定问题有关的数据 逻辑层（抽象层） 数据值、处理数据的操作抽象 实现层 存放数据项的结构、数据处理操作在特定的程序设计语言中的编码。 数据结构 一种抽象数据类型中复合数据域的实现。 几种线性抽象复合结构 栈 特点 项目只能从一端访问栈中的元素；遵循“后进先出”原则 可执行运算 这两种操作均针对栈内在栈中时间最短的项目，体现“后进先出”原则 推进 插入元素，栈内不能满 弹出 删除元素，栈内不能空 队列 特点 项目从一端入，另外一端出；遵循“先进先出”原则。 可执行运算 插入 在队列尾部（rear）插入元素，针对在队列里面时间最短的项目。 删除 在队列头部（front）删除元素，针对在队列里面时间最长的项目。 广义线性表 特点 常规操作可以在任何地方进行的表（表中间、表头与表尾）；元素按照关键字值排列 操作 建表 建立一个空表 插入 查找元素插入位置，将元素插在可以保持关键字顺序的地方 删除 查找被删除者在表中的位置，而后进行删除操作 检索 查找对象，再存取单个对象 遍历 逐一处理表中的元素 空 检查表是否是空的 列表 特点 项目同构（项目的类型相同）、项目线性化（除第一项与最后一项外，各项均有前一项与后一项）、列表是变长的。 列表可以表述数组，但是数组不是列表。 可执行运算 插入（Insert） 插入一个项目 删除（Delete） 删除一个项目 检索（Isthere） 搜索并确认一个项目是否存在。 返回项目个数（GetLength） 报告列表中的项目数量。 比较 比较列表中的数个项目。 链表 由节点组成，一个节点＝用户数据+指针（指向列表的下一个节点）。最后一个节点的指针是null（空）。它可以乱序排列，因为各个节点的指针可以确保列表的读取顺序是有序的。 几种非线性抽象复合结构 二叉树 组成 一个由节点相互连接成为树形结构的抽象结构。 特点 ①1个节点下面最多只能有2个节点。前者为父母，后者为子女（左边的——左子女；右边的——右子女）没有子女的节点被称为叶子。隔了几代的节点存在长晚辈关系，与家族关系类似。 ②每个节点只能有一个父母（总二叉树的根节点无父母），且每个节点均可为子二叉树的根节点。 与二叉树有关的运算 二叉检索树的构造 ①关键：将第一个插入的元素确定为根节点，然后再插入两个元素，小于根者作为左子女，大于根者作为右子女。每一个子女又作为子二叉树的的根节点，重复上面的操作。 ②注意：属于递归算法；而且在子女节点进行插入元素的操作时，未插入元素已经按照和根的大小关系分成了两部分。左/右要插入元素，会将小于、大于根节点的两堆元素分别分给左子女和右子女。 二叉检索树的搜索 关键：先确定目标，然后从根节点开始比对（小于者左边，大于者右边）；然后和根结点的左/右子女开始比对，重复上面的操作。直到找到目标或者目标不存在。 输出二叉检索树的数据 原则是：先输出比根的值小的值，再输出比根的值大的值 图 概念 本质上是去掉“1个节点只能有2个子女”“1个节点只能有1个父母“限制的树。 特点 ①节点被称为顶点，节点之间的连接线被称为边（弧)且均有权值。被边相连接的一组顶点称为邻顶点 ②边可以有方向，有方向者可以称为有向图，否则成为无向图。 与图有关的运算 创建图 图有什么元素就加什么。 搜索图 分为深度优先搜索（用栈描述）、广度优先搜索（用队列描述）与单源最短路径搜索（路径的总权值最短）三种。 子程序 子程序相对于总程序而言——模块：总程序在执行时，可以直接调用子程序来执行任务。 参数传递 参数列表 子程序使用的标识符/值的列表。 形参与实参 子程序调用某一个变量时，形式为：子程序名（形参——说明变量名及其种类）+实参（真正的变量内容/子程序行为）。先读取形参然后执行子程序时调用其对应的实参。 注意：二者数目必须相同。 3.形参的类别——值参：实参内容为变量的内容；引用参数：实参的内容为变量存储的地址。 面向对象设计与高级程序设计语言 面向对象设计方法概论 概念 针对对象（问题背景中具有意义的事物或实体）生成解决方案的问题求解方法。 与自顶向下方法的区别 前者只需收集与对象有关的信息，后者对问题进行了分层分为几个任务，每个任务独立处理输入的数据并输出。 相关概念： 对象 略 (对象)类 一组具有相似属性或行为的对象。 域 说明了类中的属性或行为，包含数据值或者子程序（即方法）。 方法 处理对象中的数据值的制定算法。 应用过程 Step1 集体讨论阶段——大致确定问题中的类 Step2 过滤阶段——对类进行增减、修改。查漏补缺。 Step3 场景阶段——确定每一个类的责任（类的行为以及需要的数据）并封装（将数据和动作集中在一起，使结果和实现细节分离以达到抽象的目的） Step4 责任算法——为责任编写算法 高级程序设计语言 使用编译器的高级语言的翻译过程 例：FORTRAN、COBOL、ALGOL 1.向编译器中输入高级语言代码 2.编译器输出机器语言代码 3.CPU执行机器语言代码 使用解释器的高级语言的翻译过程 例：Lisp、SNOBOL4、APL、Java 1.向解释器（Java中称为JVM，即Java虚拟机）中输入高级语言代码（Java中称为字节码程序） 2.解释器直接翻译并执行高级语言代码。 相对于第一种来说，其优点是可移植性好（任何机器只要具备解释器均可执行该类代码，最典型例子是Java）。第一种达到可移植性好，要求编译器可以执行的机器语言代码是相对于高级编程语言是特定的，没有通用之说。 注意： ①Ada语言的编译器起到的作用是将代码翻译成字节码。②源文件是某些用高级程序编写、存储为文本文件的程序。 程序设计语言的范型 范型的概念 范型是语言反应现实的不同方面的方式。 命令式范型 语言示例 FORTRAN、Basic、Pascal、C、C++（后两种其实两种范型均有） 特点 顺序执行指令；变量的使用代表内存地址；赋值语句的使用代表改变变量的值。 类别： 面向过程的范型 语句分组为数个子程序，每一个子程序通过处理输入的数据来完成其功能。数据是被动地被程序所操作。 面向对象的范型 对象和操作对象的代码绑定在一起，每一个对象负责控制自己的操作。数据是活跃地和对象一同活动。 声明式范型 语言示例 Lisp、PROLOG（人工智能常用的编程语言） 概念 描述结果而不描述完成得到结果的过程。 类别 函数式模型 直接调用数学中的函数来对数据进行运算并输出结果。 逻辑编程式模型 包含一系列关于对象的事实以及一系列对象之间的关系。程序包括两个部分：①询问对象和对象之间的关系。②通过使用这些关系和逻辑规则来推演出问题的答案。 高级程序设计语言的功能性 布尔表达式 标识符之间由运算符号分隔，运算的结构为True或False 概念 包含数个标识符的标识符序列。 用途 判断是否满足一个条件以执行某一段代码。 组成 布尔操作符：AND（表达式均为真时返回值为真）、OR（表达式均为假时返回FASLE）、NOT（改变表达式的值），其逻辑就是布尔代数的逻辑。 数据归类 强类型化 只能在变量中存储合适的类型的内容。强类型化的语言包括C++、Java和Visual Basic.NET 数据类型 一组特定类型的数值和一组可以应用在这种类型的数值上的基本操作。常见的有如下几个： 整数 有的高级程序设计语言会提供数种范围不同的整数数据类型。其可以应用的操作是：算术运算符、关系运算符、模运算符。 实数 表示特定精度的数的范围（范围由表示的实数所占的字节数决定）。有的高级程序设计语言会提供两种大小不同的实数。其可以应用的操作与整数数据类型相同，但是精度可能下降。 字符 Unicode字符集中的所有单个字符均可作为字符数据类型中的内容。 其可以应用的操作是：比较操作（比较字符与字符在字符集中的相对位置的先后。） 布尔型 布尔表达式的产物。只有True和False两者。布尔型数据类型的变量可以为之指定一个布尔表达式。 字符串 一个字符序列，通常由单引号或双引号圈起来。 一般常见操作为：连接、比较操作。因语言不同而不同。 声明 将变量、动作或语言中的其他实体与标识符关联起来的语句。作用是可以通过标识符引用这些语句。必须进行变量声明的语言有：Visual Basic.NET、C++、Java。 变量初始化 在程序开始执行时，向变量中存储一个值。 保留字 某些程序设计语言中具有特殊意义，从而不可以作为标识符的字。例如Visual Basic.NET中的Dim、Python中的long、int、float和bool。 区分大小写 大小写不同的同一个标识符会被认为是不同的标识符。例如C++、Java、Python和Visual Basic.NET。 注释符号 用于标明注释开始（或结束）的符合 字面值 程序中使用的预先定义好的值。大多数语言要求使用单引号括起来，与双引号括起来的字符串区别。 常量 存储固定值，值无法不改变，用于替代字面值而使用。 标识符 程序中对象的名称 输入/输出结构 输入 程序从外部环境中获取一个值，并将其存储到程序内的变量。 强类型语言 输入内容前，必须声明输入内容所使用的变量的数据类型。而后在接受到输入时，按照已经确定的数据类型接受输入的字符（串），并且存储到变量中去（以位模式）。 输入变量的类型决定了如何解释输入的字符，计算机将按变量的数据类型去理解变量中存储的字符（串）。 非强类型语言 输入内容的格式决定了输入内容的数据类型。引号圈起来的存储为字符串，数字存储为数字。 输出 将变量中以位模式形式存储的内容按照变量的数据类型进行解释转换，而后作为字符流输出。 控制结构 类别 重复、选择与子程序。 使用原则 程序的每一个逻辑单元只能有一个入口、一个出口,不可以随便跳入、跳出逻辑单元。（一个控制结构=一个逻辑单元)。 嵌套逻辑 控制结构中还嵌套着控制结构。 异步处理 又名事件驱动处理——程序指令代码以外的事件控制着程序中的某一部分代码执行与否。程序中的所有代码并不都是同时执行的。 表达式 由一系列操作数和运算符简化后的一个单一数值 运算符 算术运算符 +（加）、-（减）、*（乘）、/（除）、%（取模运算）、++（递增，变量值加1）、--（递减，变量值减1） 关系运算符 <（小于）、<=（小于等于）、>（大于）、>=（大于等于）、==（等于）、!=（不等于） 逻辑运算符 ！（非）、&&（与）、||（或） 操作数 运算符涉及的运算对象 语句 赋值语句 给变量赋值 复合语句（块） 包含数个语句的代码单元，使一组语句成为一个整体 控制语句 用于改变语句的执行顺序 选择 单路选择（2个选择）、多路选择（2个以上的选择） 重复 预先检查循环（符合条件再循环一次）、计数器控制循环（计数器未达到要求，不停止循环）、后测试循环（循环一次再检查是否符合条件） 顺序 按顺序执行。 返回值 子程序执行完成后向主程序返回1个/数个值 实现 子程序具体变成不同语言中的不同程序代码。 面向对象语言的功能性 封装 概念 已经在前面说过了，说一说它的作用：它是实施信息隐蔽的语言特性——它的结果是抽象，即使用某个类正式定义的接口的独立模块隐藏了类实现的细节。（此处类是用于提供封装的结构，决定了对象的特点） 类 已经在前面说过了，略。（实例化——创建类中的一个具体对象） 默认情况下，类中的域是私有的——如果一个类中的域没有被标记为公有，那么其他类的对象将无法访问这个域！ 继承 概念 一个类可以继承另外一个类的数据和方法（即域）。前者称为派生类，后者称为超类。 特点 下级的类将会继承其父类的所有行为和数据；继承所发生的类的层次越低，对象越专门化。 多态概念 不同的类中存在相同名称与相同作用的方法。 面向过程设计与面向对象设计的区别 前者会操作数据结构与子程序，不会将实现细节隐藏；而后者会使用封装的办法向用户隐藏实现细节。 软件工程 软件生命周期 开发→使用，如果出了问题就修改/维护，然后接着用；如果软件过时、低效或者用户需求变化，软件停止修改/维护，继续进行新的开发 软件开发周期 阶段 分析 设计 实现 测试 两类模型 瀑布模型 特点 开发过程只有一个方向的流动——前一个阶段没有完成，后一个阶段无法开始 优点与缺点 下一个阶段开始前，每个阶段已经完成；但是整个开发过程有问题，所有阶段都必须进行检查。 增量模型 整个软件工程被分割为数个小的系统，每一个系统均包含了4个这样的阶段。当现有的系统工作正常后，才会在原有的基础上增加更多细节，形成下一个系统。下一个系统依然重复前面叙述的过程，直至工程目标完成。 分析阶段 生成规格说明文档——说明了软件的功能而非实现软件功能的细节 两种分类 面向过程分析 使用面向过程语言实现 面向对象分析 使用面向对象语言分析 设计阶段 概念:完成实现软件功能的细节 面向过程设计 任务 设计过程，也设计数据 特点 整个系统被分解为一组过程或者模块 面向对象设计 设计实现类的细节的方法 实现阶段 完成设计阶段设计出来的东西 语言的选择 常用纯过程语言：C、Java 软件质量 高质量软件系统的特点 可以满足用户需求、符合组织操作标准、可以高效运行 质量因素 可操作性、可维护性、可迁移性 测试阶段 目标 发现错误 无论如何测试，只能保证程序对测试用例运行正确，不能保证对所有的数据运行正确。 分类 白盒测试（玻璃盒测试） 特点 知道软件内部结构 目标 检查是否将软件的所有部分都设计出来 标准 每个模块中的所有独立路径至少被测试过一次；所有判断结构的分支、所有循环与数据结构均被测试 分类 基本路径测试 使用一组测试用例，将软件中的每条语句至少测试一次 控制结构测试 包含基本路径测试。 条件测试 针对模块中的条件表达式 数据流测试 基于通过模块中的数据流 循环测试 使用测试用例检查循环的正确性 黑盒测试（暗箱测试） 概念：不知道程序内部结构与运行原理的情况下测试程序 分类 穷尽测试 用输入域中的所有可能的值去测试软件（不可能实现） 随机测试 随机选择输入域的值的子集（随机生成）进行测试 边界值测试 选择边界值进行测试 文档 特点 在软件生命周期中持续 分类 用户文档（用户手册） 软件使用说明书，可以提升软件的易用性与友好性，有助于软件销售 系统文档 记录软件开发周期的具体过程与细节，便于其他人（非原始开发人员）维护软件 技术文档 描述软件安装与维护、更新的方式 计算机网络和因特网 基本概念 网络 为了通信或共享资源（文件/打印机），可通信设备（主机/端系统或连接设备）用媒介（有线/无线）相互连接构成的设备组。 节点（主机） 网络中的所有设备（计算机、打印机、网络信息传输设备） 连接设备 路由器：连接网络——网络 包在网络之间的传输时，接收并发送包。特点：每一个路由器只知道包传输的下一个目的地的最佳路径，而包将沿着这条路径传输。 交换机：连接不同设备 调制解调器：改变数据形式 补充 中继器：在传输线路过长时，防止数字信号过分减弱的装置。 4种网络 局域网（LAN） 私有的，有一定范围限制；仅一定数量的主机或其他设备（通过交换机连接） 拓扑 管理LAN的各种配置。 环形拓扑 所有的节点→闭合的环，消息在环内传播。 星形拓扑 一个节点为中心，其他节点连接中心节点。中心一完蛋，网络必完蛋。 总线拓扑 所有的节点均连接在一根通信线上，消息在线上可以双向传播，各节点检查消息目标是否为本节点。常用的技术是以太网。 广域网（WAN） 连接两个或更多的局域网，范围更大；连接交换设备（为通信公司创建并出租） 最大的广域网：Internet（因特网） 网关 局域网之间的节点。 网际互联 网络之间的通信。 城域网（MAN） 通过无线/光纤连接的、适用于特定城市、学校或组织的大型局域网（LAN） 互联网 多个网络之间连接；最大互联网：Internet Internet 结构 《计算机科学导论》95：图6-4 Internet连接 Internet是由多个较小规模的广域网连接而成的，是全世界所拥有的。 Internet骨干网 承载Internet通信的一组高速网络。特点：数据传输速率高、冗余大。 Internet服务提供商（ISP） 给其他公司或个人提供Internet访问，其之间连接到更大的ISP或者Internet骨干网。 接入Internet网络的方法： 电话调制解调器 由ISP付费提供，计算机数据→二进制模拟音频信号，在电话线中传输。达到目的地后逆向操作。 经过路径 Internet骨干网——ISP——计算机。 速率较慢（max：64KB/s） 数字用户线路（DSL） 在电话调制解调器的基础上，将计算机数据转换为了数字数据而非模拟信号。 同样使用电话线，但与电话信号频率不同。电话公司就是ISP。 经过路径 相同 速率：更快 线缆调制解调器 使用的线缆换成了有限电视信号的线缆。 注意：后两种又被称为宽带，其具体速率均由位置与传输介质所决定。 下载 从Internet上将数据传到家用计算机上 上载 与下载相反 二者的速度大小：前者大于后者。原因是用户主要下载数据居多（浏览、接收数据……） 协议分层 本质 各部分分工合作，负责网络通信不同的任务 协议 说明格式化和处理传输的数据的方法，即计算机之间交流时，都必须遵守的通信规则。 定义 主机中自上而下相互关联的数个模块 特点 ①各模块完成不同层次的任务 ②模块化：相互独立工作，共同完成网络通信任务 ③无论是该协议分层的哪一层，它们的物理基础均为物理层；物理层上面是逻辑连接，物理层是实际连接 优势 ①各层对高低均有对应层次服务，只需执行任务 ②简化了网络通信进程 劣势 单一协议层增加安全与维护风险 原则 ①双向通信，各协议层工作相反对应。 ②同种层处理对象相同 常用协议分层：TCP（传输控制协议）/IP（网际协议）族 又名开放系统互联（OSI）模型 本质 协议与底层网络通信工具程序的组合。 TCP/IP结构 应用层-传输层-网络层-数据链路层-物理层 工作原理 《计算机科学导论》99页—图6-8 地址：源地址与目标地址 A应用层：名称 B传输层：端口号 C网络层：逻辑地址 D数据链路层：链路层地址 数据包：即数据 A应用层：消息 B传输层：分段/用户数据报 C网络层：数据报 D数据链路层：帧 E物理层：位 作用 网络体系结构的通用模型。将不同类型的网络连接到一起，使得网络相互之间可以通信。网络技术开发的核心与基础 TCP/IP协议分层结构 应用层 作用：提供服务；本层的协议可移除、添加或变更以满足用户。 交互方式 客户机—服务器模式 特点 客户端自由运行，服务器只能一直开启 结构 客户向服务器发送请求，服务器响应客户请求 劣势 服务器易过载；使用成本必须以足够的收入来补偿 典例 万维网（WWW）与超文本传输协议（HTTP） WWW文档的交换协议 HTTP中，客户机使用临时端口号，服务器用80号端口 结构 ①世界上有无数的Web（万维网）服务器（站点），每一个服务器都存储着一定的具有（文档）名称与可删减、改变、增加文档。文档的名字是网页（可多种数据形式）地址 ②这些服务器相互连接，构成Web（万维网）—一