(教材资料)高二年级计算机讲义(一)

高二年级计算机讲义（一）高二年级计算机讲义（一） 一、信息的数字化 负数的表示负数的表示 （1）Signed Magnitude：如果用 n 个 bit 表示一个负数，用最左边的位表示符号，1 表示负 数，0 表示正数。 缺点：（1）有两个 0 的表示法；（2）不能直接做加法 10000001+00000010=10000011 （2）Ones complement （反码）：要表示一个负整数 k，先将其相反数-k 写成二进制形式， 然后对所有位都取反，就得到 k 的反码表示形式。例：00000010=210；11111101=-210 缺点：仍有两个 0。做加法的特点：加法需要将最高位的进位加到最低位 （3）Twos complement（补码）：将一个负数 k 先写成反码形式，然后加 1。例： 00000010=210；11111110=-210。 只有 1 个 0，可以直接相加。由于补码有这样的优势，因此使用较为广泛。 实验实验 1 （1）VB 中整型分配 2 个字节，最大是 011111(0 后面 15 个 1)，215-1=32767；最小是 10000(1 后面 15 个 0)，表示的是-215=-32768。 （补码表示） 将超过该范围的数值赋给整型变量，运行程序观察结果 *（2）改用 VC+，用 C 语言。C 中 int 型一般占据 4 个字节。也用补码表示，范围自然是 -231到 231-1（-2147483648 到 2147483647） 下面代码运行结果是什么 小数的表示小数的表示 定点表示法：固定小数点的位置，灵活性很差 浮点表示法：使用科学记数法；要记录三个数量：符号+位移量+尾数 例如：+1000111.0101=+1.0001110101226；总是将小数点移动到最左边的 1 右侧。于是我 们记录+；6；0001110101 一般采用两种标准 指数 尾数符号 单精度8 23 1 双精度11 52 1 在 VB 中，单精度浮点数对应的变量称为 Single；双精度浮点数对应的变量称为 Double 以单精度为例说明浮点数的表示： 最低 23 位为尾数（小数部分，整数部分约定总是 1） 然后 8 位为指数，存储为指数+127 最高位符号位，0 正 1 负 例子： 8.12510=1000.0012=1. 0000011011 尾数 000001 指数 3+127=130=100000102 符号 0 0 10000010 0000010 00000000 00000000 字符的表示字符的表示 ASCII 码：1 个字节表示一个字符，只能表示 256 种可能性（且最高位置为 0 不用） ，因此 只能表示英语和常见符号。 Unicode：2 个字节，能表示世界上所有的语言文字。 UTF-8：基于 Unicode 的一种编码，用一个字节表示英文字符，两个或三个字节表示其它 语言字符。变长编码的机制为了减少存储空间的浪费。 为了能让应用程序区分不同编码的文本文件，Unicode 文本文件开头多了两个字节 FFFE。 实验实验 2 *（1）使用下面的 C 代码能够观察一个 32 位单精度浮点数的表示情况 输入这段代码，运行并观察结果 （2）最大的单精度浮点数是什么？（3.40282339e38） 验证两个单精度数 33554431 和 33554434 被认为是相等的，为什么？ 33554431 和 33554435 呢？ （3）在记事本中输入 1 个英文字符和 1 个中文字符，保存成 Unicode, ANSI 和 UTF-8 格式， 分析其大小并验证。 创建一个空文本文件，保存成 Unicode, ANSI 和 UTF-8 格式，分析其大小并验证。 二、中央处理器和主存储器 计算机体系结构的一般理论： (1) 处理器在硬件层次上执行一个较小的功能集合，称为指令集 逻辑判断,算术运算 (2) 软件/程序是基本指令的组合，完成各种应用 (3) 程序(指令)和数据都被存储在存储设备中。程序运行时候，逐条指令从存储器中读入到 处理器内被执行。 （称为存储程序） CPU=ALU（运算和逻辑单元）+控制单元 当前即将被执行的指令和数据保存在处理器内部的存储器寄存器中；寄存器大小通常是 计算机字长的大小，字长决定了（1）计算机一次进行运算处理或传输的数据大小；（2） 支持的指令数量；（3）内存编址的空间。 主存储器： 随机存储器中随机的含义：表示可以根据内存地址在常数时间直接访问内存单元，而无需 顺序存取。内存中每个单元一般存储一个字节。 高速缓冲存储器（Cache） 包含主存储器中部分内容的副本 当 CPU 存取主存中内容时，先检查 Cache 如果不在 Cache 中，从主存中复制从需要读取的字开始的数据块到 Cache 中 提高效率的原因 局部化原理：（执行程序过程中，在特定阶段，只是执行局部的若干条指令。 ） 不同的体系结构： 复杂指令集计算机（CISC） 指令数较多，某些指令实现复杂的功能 精简指令集计算机（RISC） 指令数少，实现功能较简单 对复杂指令集计算机的批评：硬件实现复杂；复杂指令实现功能可以用简单指令的组合取 代；执行效率不理想；许多复杂指令使用频率不高。 流水线（Pipelining）的思想 计算机对于每条指令的执行需要经过取指，译码，执行和存储四个阶段。使用流水线技术 的处理器，在同一时间，可以执行不同指令的不同阶段，以此提高单位时间内完成的指令 数量。 实验所用软件可在 7/wwj 下载（用户名和密码为 shs） 实验实验 1：下载 latency.exe。运行该软件可以查看机器的 Cache 级别，大小，以及从各级 Cache 获取数据的时间。 （以 machine cycle 为单位） 实验实验 2：观察内存数据 下载 HeapMemView.exe 打开记事本，输入大段文本 在 HeapMemView 软件中选择进程“Notepad”，查看输入文本在内存中的位置 实验实验 3：使用 CPUZ 的 Registers Dump 功能，观察你的机器寄存器的大小 三、二级存储器 存储器分为两部分： 存储介质：用以保存数据的物理材料 存储设备：从存储介质上读取或写入信息的硬件设备。 按照存储介质可以将存储器分为：磁性存储技术；光学存储技术；固态存储技术 磁性存储介质：通过磁化存储介质表面的可磁化物质来存储数据；磁盘驱动器的读写头可 以磁化存储介质表面的可磁化物质使得它们朝向两个方向其中之一，用以表示 0 和 1，磁 性存储介质可以在断电情况下长期保存数据。 磁性存储介质包括硬盘、软盘、磁带。 硬盘的结构： 它包含若干盘片（Platters） ，它们以共同的速度绕一个主轴（Spindle）旋转，每个磁盘通 过磁臂末端的读写头来读写，每个盘片的两个面都有一个读写头和磁臂，它们可以靠近或 远离主轴，当读写头静止，盘片旋转时，读写头下方经过的的表面称为一个磁道。同时再 按照一定角度将磁道划分为扇区。 硬盘表面的结构：磁道；扇区 通常一个扇区包含 512 字节的数据。逻辑相邻的数据通常不存放在物理上相邻的扇区，这 是为了提高磁盘空间的利用率，但是会降低存取速度，因此需要对磁盘碎片进行整理 （defragment） 。 传统的硬盘结构划分的特点：外道的扇区面积大，内道扇区面积小，但存储数据量都是 512 字节，为了更有效利用磁盘，提出 Zone bit recording 技术，即外道划分出更多的扇区。 何为接口：磁盘或其它 I/O 设备不能直接连接到计算机的总线上，需要有接口来清除这种 障碍。常见的外存接口有 SCSI，SATA，IDE 等。 数据的备份： （1）磁带：顺序存取，存取速度慢 （2）廉价磁盘冗余阵列（RAID：Redundant Array of Inexpensive Disks） RAID 0：数据分块（并没有冗余，只是提高存取速度） RAID 1：数据镜像 光学存储器： 表面有 land 和 pit，具有不同的反射性质，用来表示 0 和 1。 光学存储器的存取速度 使用数据传输率（Kbps）为单位（千 bit/每秒） ； 原始的 CD-ROM 驱动器的传输率为 150Kbps； 2X, 9X,的含义：对 CD：1X=150Kbps，2X=2150Kbps=300Kbps， DVD 的情形，与 CD 有不同的数量级，1X=9150Kbps=1350Kbps 实验实验 1：使用 Windows XP 软件的磁盘碎片清理程序（Defragmenter） ，查看硬盘某个分区 的碎片数量。 实验实验 2：通过创建一个小的记事本文件，分析你使用的计算机的簇包含多少扇区。 实验实验 3：使用 Everest 软件观察你使用的计算机上的硬盘各参数（转速，盘片数量，扇区数 量） 四、软件一般理论和数据文件的组织 计算机系统的非硬件因素=软件+与软件相关联的文档和数据 对软件的分类： （1）根据功能分类 系统软件：面向计算机系统:管理计算机资源,控制硬件工作;不解决生活工作的实际问题 应用软件：面向实际问题:提高人们的工作效率,提供娱乐等 最重要的系统软件：操作系统 其它系统软件的例子： 文件压缩工具 磁盘碎片整理工具 设备驱动 杀毒软件 程序开发环境(编译程序) 控制面板中的工具 （2）根据获得途径的不同分类 免费软件 商业软件 共享软件(Shareware)：可以免费试用一段时间，之后需支付费用方能继续使用 开源软件(Open Source Software)：免费而且可以合法进行修改 开放源代码软件的例子：OpenO（办公软件） ；Firefox；Linux 现在许多开发商只提供开放源代码软件,他们通过提供服务和支持来获取利润. 共享软件的例子：WinRAR 软件许可协议(license)：软件如何被使用的法律约定。现在通常采取的形式是 EULA（End- User License Agreement；最终用户许可协议） ，在安装时候显示协议条文，用户同意后继续 安装。 包含的一些内容 使用者的限定 (单个用户) ,何种情况下可以备份软件 租借和赠予的约定 反向工程的约定 开发商免责声明（As is） 数据文件的分类 文本文件：只包含字符。 （例如：html 文件，txt 文件，程序源代码） 二进制文件 计算机内部格式存储的数据集合 数，图象等等 只有当被程序正确解释时才有意义 由数据记录集合构成的文件的组织形式 顺序文件：顺序地存取记录；按照顺序一个接一个地存放 随机存取文件：使用地址直接访问某条记录 有两种实现（1）索引文件，记录的标识（主键）与地址的对应关系维护在一个索引文件中 （2）散列方法，用函数对应的方法维护记录标识与地址的关系 实验实验 1: 通过阅读 Microsoft Office 的 EULA 找到下面问题的答案 对于你购买的 Microsoft Office,你是否能够安装多个软件副本,是否可以租借,转赠软件,是否 可以进行反向工程. 实验实验 2：下载并使用开放源代码的图像处理软件 GIMP，比较它与 Photoshop 在界面和功能 上的异同。 一部关于开放源代码软件的纪录片电影 /v_show/id_XNTcxODcxNDg=.html 五、操作系统 操作系统的必要性：应用软件不与硬件直接交互；否则，开发应用软件变得低效和困难 操作系统：统一管理计算机软硬件资源，充分发挥计算机系统效率的系统软件 操作系统对硬件资源的分配策略： 处理器的管理： 多道程序(Multiprogramming)：I/O 任务与计算任务同时被执行，一个进程在执行输入输出 任务时候，须将处理器使用权交给另一个进程。 分时系统(Time-sharing)：给每个程序或用户一个时间片，轮流执行 内存管理： 面临的问题：程序对于内存而言过大 如何解决，基于以下认识 在一个时间段内，并非程序的所有部分都被使用（程序的局部化原理） 将部分程序存储在硬盘上，将这部分硬盘看成 RAM 虚拟内存 与虚拟内存相关的是分页文件：将内存、虚拟内存和程序划分成为等长的分块，作为分配 内存和虚拟内存的基本单位，这样的分块称为页面（Page） 。 当内存中分配给一个进程的空间已满，又有新的页面需要调入时，需要将部分页面淘汰出 内存。简单的算法是先进先出（FIFO，First in first out） ，将在内存中驻留时间最长的页面 淘汰出内存。但这会造成 Belady 异常现象，即分配给一个进程的页面数增加时，缺页率反 而会增加。 红色表示缺页 内存分配 3 个页面 （缺页 9 次） ；内存分配 4 个页面（缺页 10 次） 文件管理 （1）Windows：文件分配表(FAT)；簇是分配辅存的基本单位（若干相邻扇区的组合） ；链 表结构维护文件占用的簇和空闲簇。 （2）Unix/Linux：索引节点表；文件分配以块为单位（某些系统上长度 1KB） ；索引节点 表记录一个文件的基本信息+块地址；文件的前 10 个块直接记录在它的索引节点表中；如 果文件大小超过 10 个块，用间接索引的方法；间接块（不包含文件内容，而是包含文件块 的地址） 两种不同的操作系统用户界面 命令行界面和图形界面 (Graphic User Interface) 命令行界面：用户与计算机系统的交互通过键入命令完成 图形用户界面：用户与计算机系统通过图形化的元素进行交互。 两者的比较：可参考 /issues/ch000619.htm 主流操作系统： （1）Linux 和 Unix Unix 是 1971 年 AT&T Bell 实验室研发的多任务多用户操作系统。 Linux 是 1990 年由芬兰学生 Linus Torvalds 开发的类 Unix 操作系统，是开放源代码软件。 Linux 的优势是稳定和免费，缺点是相对较少的应用软件选择和使用时较高的技术要求。 （2）Windows 早期 Windows 是 DOS 的图形化操作环境；直到 Windows 95 才成为独立的操作系统，2000 年以前 Windows 分为两个系列，服务器操作系统使用 NT 内核（包括 Windows NT 3.1, Windows NT 4.0, Windows 2000） ，个人版本仍使用 DOS 内核（包括 Windows 95, 98, Me） 。 Windows XP 开始所有的 Windows 版本（无论服务器版本还是个人使用的版本）都使用 NT 内核。 （3）Mac OS 苹果计算机上使用的操作系统，是第一个商业上取得成功的图形化界面操作系统。 六、软件工程 软件工程的目的：克服软件开发过程中的随意性，工程化地组织和开展软件开发，确保软 件的质量。具体的做法和原则（1）周密的分析和设计（2）严格的项目管理（3）详细的文 档支持（4）要对软件实施不断的测试 软件开发的瀑布模型：分析，设计，实现，验证，维护 软件测试的一些原则 详尽测试（测试每个可能的输入和流程图中每一条可能的路径）是不可行的 第三方测试（测试不宜由负责编码的开发人员本身进行） 单位，模块和系统测试 等价类的划分（将输入数据划分成等价类，例如对于保存文档的子模块进行测试，可 以将文件名划分为：合法的文件名；过长的文件名；过短的文件名；包含非法字符的 文件名等） 边界值的分析（输入区间的边界常常容易出错） 软件测试的一些类型： 黑盒测试：用户角度，测试产品的完整性 白盒测试：测试具体的逻辑细节，代码层面 alpha 测试：在公司内部，由用户在模拟实际操作环境下进行的受控测试 beta 测试：开发者无法控制的环境下进行的软件现场应用。在 Beta 测试中，由用户记下遇 到的所有问题，定期向开发者报告。 七、计算理论 计算理论要回答的问题：哪些问题是可求解的，哪些问题是不可求解的。对可求解的问题， 它的时间复杂度是怎样的。 算法的定义：良好定义的逐步解决问题或完成任务的方法。很多人认为 Euclid 算法是最早 的非平凡算法，它