《计算机概论》学习总结与预习

大家好，欢迎来到IT知识分享网。

《计算机科学概论》第1-3章总结

1. 数据存储

1.1位与位存储

1. 数字数据由不同层次的抽象表示。在最底层，所有数字数据都由位表示，在较高层，位被分组用于表示抽象，包括但不限于数、字符和颜色。在抽象的最底层，数字数据只用数字0和1的组合以二进制(基数2）表示。
2. 布尔运算用来处理真/假值，包括四个基本运算AND（与）,OR（或）,XOR（异或），NOT（非）。

布尔运算AND可用于计算，连接词AND和两个较小或较简单的语句组成的一条语句的真/假值。这种语句的一般形式如下：P AND Q

其中，P代表一条语句，Q代表另一条语句。

AND运算的输入是复合语句分句的真/假值，输出则是复合语句本身的真/假值。P AND Q形式的语句的值只有在其两个分句都是真时才为真。

OR运算是建立在如下形式的复合语句的基础之上的：P OR Q

其中，同样，P代表一条语句，Q代表另一条语句。在至少其中一条组成语句为真时，这种语句才为真。

XOR运算：当两个输入中的一个为1(真)、另一个为0(假)时，XOR运算的输出为1(真)。(简言之，当两个输入不同时，XOR运算的输出为1。)

NOT(非)运算是另一个布尔运算。它与AND、OR和XOR不同，因为它只有一个输入。它的输出值与输入是相反的；如果NOT运算的输入为真，那么它的输出值就为假，反之亦然。

1. 逻辑门是用布尔函数建模的硬件抽象。门通常是由称为晶体管的小型电子电路实现的，其中数字0和1由电压电平表示。
2. 触发器是计算机存储器的基本单元，它是一个可以产生0或1输出值的电路，它的值会一直保持不变，直到有另一个电路过来的脉冲(临时变成1之后再变为0)使其变换成其他值。换句话说，通过设置，可以让输出在外界刺激的控制下“记住”0或者1。
3. 计算机电路的设计就会呈现一种层次结构，其中每层都将较低层次的构件作为抽象工具使用。
4. 超大规模集成技术支持将数百万个电子元件构造在一个称为芯片的半导体晶片上，用于创建包含数百万个触发器及其控制电路的微型设备。
5. 二进制数据由计算硬件(包括门、芯片和元件)的物理层处理。
6. 硬件采用多层抽象构建，如晶体管、逻辑门、芯片、存储器、母板、专用卡和存储设备。
7. 用十六进制(基数16)表示数字数据是因为十六进制表示使用的数位比二进制的少。

1.2 主存储器

1.计算机的主存储器是由称为存储单元的可管理单元组成的。

2.通常假设存储单元的位是排成一行的，该行的左端称为高位端,右端称为低位端。高位端的最左边的一位称作高位或最高有效位。低位端类似地，低位端的最右边的一位称为低位或最

低有效位。

1. 为了区分计算机的主存储器中的各个存储单元，每个存储单元都被赋予了一个唯一的“名字”,称为地址。
2. 因为计算机的主存储器是由独立的、可编址的存储单元组成的，所以可以根据需要独立访问这些存储单元，因而计算机的主存储器常被称为随机存取存储器。
3. 许多技术将位存储为微小的快速消散的电荷。因此，这些设备需要附加电路(称为刷新电路),在一秒内反复补充电荷很多次。因为它的这种易失性，通过这种技术构造的计算机存储器常被称为动态存储器。
4. 术语千字节(kilobyte,符号表示为KB)被用于表示1024字节。

1.3 海量存储器

1.存储介质的选择对操纵它包含的数据的方法和成本都有影响。

2.有4个标准可以用来评估一个磁盘系统的性能：(1)寻道时间;(2)旋转延迟;(3)存取时间;(4)传输速率。其他用于评估海量存储器和更一般的通信系统的重要性能度量指标有：(1)带宽;(2)等待时间。

3.系统带宽是位速率的度量单位，位速率是一个固定时间内发送的数据量(用位度量)。系统等待时间是传输和收到请求之间所经过的时间。

4.微小晶格能够在没有外力的情况下保持截获的电子很多年，所以闪存技术非常适合存储便携、非易失的数据。

1.4 用位模式表示信息

1.数字基数包括2、10和16,被用于表示和研究数字数据。数字可以从任何一种基数转换为任何其他基数。

2.图像的一种表示方法是：将图像解释为一组点，每个点称为一个像素;然后，对每个像素的显示进行编码，整个图像就表示成了这些编码像素的集合，这个集合称为位图。

3.不太理解声音和图像的编码方式。

1.5 二进制系统

1.在二进制补码系统中，位模式最左边的二进制位指明了所表示的值的符号。因此，最左边的位常称为符号位。在二进制补码系统中，符号位为1的模式表示负值，符号位为0的模式表示非负值。

在二进制补码系统中，绝对值相同的正负值的表示模式之间有一种对应关系，从右向左

读时，直到第一个二进制1(包括那个1),它们都是相同的。然后，以这个1为分界线，左面的位模式互为补码。(要得到一个模式的补码,需要将所有的二进制0转换为1,并将所有的二进制1转换为0。)

1. 有限表示用于建模数的无限数学概念。在许多程序设计语言中，用于表示字符或整数的固定位数限制了整数值的范围和数学运算；这个限制会导致溢出或其他错误。整数可能会由于存储的局限性被限制在程序能表示的最大值和最小值之间。
2. 余码系统和二进制补码系统的一个区别就是符号位相反。

余8记数法，我们先用传统二进制系统的编码解释每个模式，然后将其与余码记数法表示的值进行比较，在每种情况下，二进制解释的值都比余码记数法解释的值大8。

1.7 分数的存储

1.实数是通过不一定有无限精度的浮点表示近似得到的。

2.在许多程序设计语言中，用于表示实数(像浮点数一样)的固定位数限制了浮点值的范围和数学运算，这个限制会导致舍入误差和其他误差。

1.8 数据与程序设计

1.定位和修正程序中的错误被称为调试程序。

1.9数据压缩

1.在使用有损压缩技术和无损压缩技术来存储和传输数据方面需要权衡。

2.对于被压缩数据由一长串相同的值组成的情况，流行使用称为行程长度编码的压缩技术，这是一种无损方法。它的过程是，将一组相同的数据成分替换成一个编码，指出重复的成分以及其在序列中出现的次数。

3.另外一种无损数据压缩技术是频率相关编码,在这个系统里，用于表示数据项的位模式的长度与这个项的使用频率是反相关的。例如：哈夫曼编码。

1. 字典编码技术，这里的术语字典指的是一组构建块，压缩的消息通过它们建造起来，而消息本身被编码成字典的一系列参照。
2. 虽然无损数据压缩会减少存储或传输的位数，但允许完整重构原始数据。有损数据压缩可以大大减少存储或传输的位数，但代价是只能重构原始数据的近似值。
3. GIF的系统是一个字典编码系统。它处理压缩问题的方法是，将赋予一个像素的颜色数量减少到只有256个。每种颜色的“红—绿—蓝”组合都用3字节编码，这256个编码被存储在一个称为调色板的表格(字典)里。图像中的每个像素都可以用一个字节表示，该字节的值指明了这个像素的颜色是由256个调色板条目中的哪一个表示的。

注意，在将GIF应用于任意图像时，它是一个有损压缩系统，因为调色板中的颜色可能与原始图像中的颜色不一致。

1. 音频压缩系统MP3,它是在MPEG标准中开发出来的。MP3利用人耳的特性，删除了人耳觉察不到的细节。其中一个特性称为时域掩蔽,指的是在一次巨大声响后，短时间内人耳觉察不到本可以听见的轻柔声音。另一个称为频域掩蔽,指的是某一频率的声音可能掩盖相近频率的轻柔声音。利用这些特性，可以通过MP3获得显著的音频压缩，而且保持接近CD的音质。

1.10 数据差错

1.在可用的编码系统中加一个奇偶校验位，可用于奇校验和偶校验。

2.模式有一组奇偶校验位构成的校验字节。校验字节中的每个位都是一个奇偶校验位，与散布在整个模式中的一组特殊位相联系。用这种方式，更容易检测到集中在原始模式某个区域中的一些差错，因为这些差错会在一些奇偶校验位的范围内。这个校验字节概念的演变出了称为校验和及循环冗余校验的差错检测方案。

1. 数据操控

2.1 计算机体系结构

1.CPU由3部分构成:算术/逻辑单元,它包含在数据上执行运算的电路；控制单元,它包含协调机器活动的电路；寄存器单元,它包含称为寄存器的数据存储单元(与主存储器存储单元相似),用于CPU内部的信息的临时存储。

2.位序列可表示指令或数据。

2.2机器语言

1. 一种是CPU只需要执行最小的机器指令集，在这种思想的作用下，产生了精简指令集计算机（RISC）。该体系结构的支持者认为，这种计算机效率高、速度快，制造成本低。另一种是另外一些人则认为CPU应该能够执行大量复杂的指令，尽管其中许多在技术上是多余的，在这种思想的作用下，产生了复杂指令集计算机(CISC)。CISC的支持者认为，CPU越复杂越容易应对现代软件日益增加的复杂性。
2. 不管是选择RISC还是选择CISC,机器指令都可以分为3类：(1)数据传输类；(2)算术/逻辑类；(3)控制类。
3. 需要讲解一下Vole。

2.3程序执行

1.CPU内部的两个专用寄存器：指令寄存器和程序计数器。指令寄存器用于存储正在执行的指令。程序计数器中包含的是要执行的下一条指令的地址，因此它用于以机器方式跟踪程序执行到了什么地方。

2.机器周期中的3步是取指、译码和执行。

2.4 算术/逻辑指令

1.按位运算:组合两个二进制位串，在各个列上应用基本运算，产生一个输出串。

2.一个字节二进制位的寄存器，将其内容向右移一位，最右端的位被移出边界，最左端出现一个空位。对于这个额外的位及留出的空位如何操作是区别各种移位运算的特征。一种技术是将右端移出的位放置在左端的空位上，这类运算称为循环移位。因此，如果我们对一个字节的位模式进行8次右循环移位，那么我们得到的位模式将与初始位模式相同。

另一种技术是丢弃移出边界的位，并用0填充空位，这类运算称为逻辑移位。这种向左的移位可以用于实现2乘以二进制补码的运算。因此,，二进制数字左移相当于乘以2,就像十进制数字左移就相当于乘以10。此外，被2除的运算可以通过二进制串右移来完成。无论哪种移位，在使用某些记数法系统时都必须注意保留符号位。

右移时留出的空位(在符号位的位置出现)总是用它原来的值来填。保留符号位不变的移位称为算术移位。

2.5与其他设备通信

1. 控制器（用于通信）都是通过电缆与计算机机箱里的外围设备，或者是与计算机背面称为端口的连接器相连接的。
2. 控制器存取主存储器的能力称为直接存储器存取,它是计算机性能的重大资本。
3. 需要讲解一下冯 诺依曼结构。
4. 两个计算设备之间的通信可通过两种途径来处理：并行和串行。
5. 并行通信是指若干信号同时传输，每个信号都在各自的“线路”上。这种技术传输数据的速度快，但是需要相对复杂的通信路径。
6. 串行通信是指信号在一条线路上一个接一个地传输。因此，相对于并行通信，串行通信只需一条相对简单的数据路径，这也是它很流行的原因。

2.6数据操控编程

1. 函数是程序设计指令的一个命名分组。函数是可复用的程序设计抽象。函数简化了编写和维护程序的复杂性。
2. 在程序中调用过程时，参数提供不同的值作为过程的输入。参数通过允许使用函数而不是复制代码来归纳解决方案。

1. 操作系统
   1. 操作系统的历史

1. 允许执行一个程序来通过远程终端与用户对话——这种特性称为交互式处理。
2. 计算机是强制在一个限期内执行任务的，这一过程就是实时处理，其中所完成的动作被称为是实时发生的。
3. 能同时给多个用户提供服务的操作系统，这一特性称为分时。实现分时的一种方式是应用称为多道程序设计的技术。

3.2操作系统的体系结构

1. 机器软件分为两大类：应用软件和系统软件。
2. 应用软件是由一些完成机器特定任务的程序组成的。有电子表格软件、数据库系统、桌面出版系统、记账系统、程序开发软件以及游戏等。
3. 系统软件又可分两类，一类是操作系统本身，另一类是统称为实用软件的软件单元。安装的大多数实用软件包括这样一些程序，它们实现的活动只是计算机安装的基础，但没有包含在操作系统中。
4. 实用软件是由一些能够扩充(或定制)操作系统功能的软件单元组成的。
5. 操作系统负责处理与用户通信的部分通常称为用户界面。老式的用户界面称为外壳,通过键盘和显示屏用文本信息与用户通信。更现代化的系统利用图形用户界面实现与用户的通信，其中操作的对象(如文件和程序)被表示为显示屏上的图标。这些系统允许用户使用某种常用的输入设备发出命令。
6. 窗口管理程序,该程序在屏幕上分配若干个称为窗口的块，跟踪与每个窗口相联系的应用程序。

1. 操作系统的内部部分称为内核。操作系统的内核包含一些完成计算机安装所需的极基本功能的软件组件。其中一个组件是文件管理程序,它的工作是协调机器海量存储器设施的使用。
2. 一条由目录内的目录组成的链称为目录路径。路径通常是这样表示的：列出沿该路径的目录，然后用斜杠分隔它们。
3. 内核的另一个组件是一组设备驱动程序,它们负责与控制器(有时直接与外围设备)通信，以操作连接到机器的外围设备的软件单元。
4. 在操作系统的内核中还有一个组件就是内存管理程序,它担负着协调机器使用主存储器的任务。
5. 当所需的总主存储器空间超过该计算机实际所能提供的可用内存空间时，内存管理程序的任务会更复杂。在这种情况下，内存管理程序会在主存储器与海量存储器之间来回切换程序和数据[这种技术称为页面调度],从而造成有额外内存空间的假象。这块由页面调度所产生的大的“虚构”内存空间被称作虚拟内存。
6. 存储器(这是CPU期望找到初始程序的地方)的一小部分是由特殊的非易失性存储单元构成的。由于这种存储器的内容可以读取，但不可以改变，因而被称为只读存储器(ROM)。
7. 在通用计算机中，引导装入程序被永久存储在机器的ROM中。

3.3协调机器的活动

1. 在操作系统的控制下执行某个程序的活动称为进程。与进程联系在一起的是活动的当前状态，称为进程状态。
2. 进程状态：一个进程在计算机中会有他的状态，也可以叫做进程的生命周期，按照时间顺序依次是创建、准备、运行和等待、退出，其中运行和等待会交替进行，直到程序退出。
3. 为了跟踪所有的进程，调度程序在主存储器中维护着一个称为进程表的信息块。每当要请求程序执行时，调度程序都在进程表中为该程序创建一个新的表项。这个表项包含分配给该进程的存储区域(从内存管理程序得到的)、进程的优先级以及该进程是处于就绪状态还是处于等待状态这样的信息。
4. 进程能够继续执行，那么该进程就处于就绪状态；如果进程因要等待某个外部事件(如完成海量存储操作、按下键盘上的一个键或者等待其他进程传来的消息)的发生而延迟，那么该进程就处于等待状态。
5. 分派程序是内核的一个组件，它监督被调度的进程能实际执行。在分时/多任务处理系统中，这个任务由多道程序设计来完成的；这种从一个进程变换到另一个进程的过程称为进程切换或上下文切换。
6. 每次分派程序给进程分配一个时间片时，都会初始化一个计时器电路，通过产生一个称为中断的信号来指示时间片的结束。当CPU收到中断信号时，它会完成当前的机器周期，保存它在当前进程中的位置，然后开始执行一个称为中断处理程序的程序。

3.4 处理进程间的竞争

1.坚持让测试任务和可能有的标志置位任务必须在没有中断的条件下完成。一种方法是使用大多数机器语言都提供的禁止中断指令和允许中断指令。

2.另一种方法是使用许多机器语言里都可用的测试并置位指令。这条指令要求CPU检索一个标志的值，记录接收到的值，然后置位该标志——所有这些工作都在一条机器指令内完成。它的优点是，因为CPU在识别中断之前必须完成当前的指令，所以测试和标志置位任务作为一条指令实现时无法被拆分。

3.一个正确实现的标志称为信号量。

4.一个指令序列称为临界区。这种一次只允许一个进程执行一个临界区的要求称为互斥。

3.5 安全性

1.操作系统在每个登录过程(一个事务序列，在这个过程中用户与计算机操作系统建立初步联系)中使用这个信息控制用户对系统的访问。

2.账户由一个称为超级用户或管理员的人创建。

3.设计审计软件的另一个目的是检测嗅探软件,这种软件在计算机上运行时能够记录活动并在稍后将之报告给潜在的入侵者。

《计算机科学概论》第4-6章预习

1. 组网及因特网

4.1网络基础

1. 计算机网络通常分为个人域网、局域网、城域网和广域网。区分主要是连接距离。
2. 另一种分类是用于公共还是个人，分为开放式网络和封闭式网络。
3. 无线网络中的通信是通过无线电广播和中央机器实现的，其中，中央机器被称为接入点,是协调所有通信的焦点。
4. 有时总线网络会通过链路将每台计算机连接到中央位置，在中央位置再连接到一种叫作集线器的设备上。集线器其实就是一条非常短的总线，其功能在于将接收到的信号(可能会经过一些放大)传回给与之相连的所有机器。
5. 网络的规则称为协议，在基于以太网标准的总线网络中，报文传输的许可是通过名为带冲突检测的载波监听多路访问的协议控制的。该协议规定每条报文都要广播给总线上的所有机器。
6. 通过将网络连接成一个相同“类型”的更大的网络。这可以通过中继器、网桥、交换机等不同的设备来完成，它们中最简单的是中继器，它只是在两个原始总线间简单地来回传送信号(通常有某种形式的放大)的设备，而不会考虑信号的含义。
7. 网桥类似于中继器，但比中继器更复杂。与中继器相似，它也是连接两条总线，但是不是在连接上传输所有的报文。相反，网桥要检查每条报文的目的地址，当报文的目的地是另一端的计算机时才在连接上转发这个报文。与中继器形成的系统相比，网桥形成的系统更高效。
8. 交换机本质上就是具有多个连接的网桥，可以连接若干条总线，不止两条。因此，交换机形成的网络包括若干从交换机延伸出来的总线，与网桥一样，交换机也要考虑所有报文的目的地址。
9. 连接的网络有时会有不兼容的特性。网络必须按建立一个网络的网络[称为互联网]的方式连接。在这个网络中，原始网络仍然保持其独立性，并且继续作为独立的网络运行。
10. 把网络连接起来形成互联网的设备是路由器,这是一种用来传送报文的专用计算机。
11. 进程间通信通常采用的是客户/服务器模式。这种模式规定了进程的基本角色，或者是向其他进程发出请求的客户机,或者是满足客户机请求的服务器。
12. 另一种进程间通信的方法是对等计算模式。为了随时准备为其客户机提供服务，对等计算模式中的进程通常都是临时执行的。
13. 在网络上不同计算机的组件组成分布式系统。
14. 集群计算指的是一种分布式系统，其中多个独立的计算机密切合作，提供的计算或服务堪比大得多的机器。其可靠性更高，维护成本更低。这样的分布式系统用于提供高可用性(因为即使集群中其他成员发生故障或不可用，更有可能保证集群中至少有一个成员能够响应请求)和负载平衡)(因为负载可以自动从集群中负载太大的成员转移到负载太小的成员)。
15. 网格计算是指耦合度没有集群高但是仍能共同完成大型任务的分布式系统。
16. 云计算可以使网络上大量计算机按需供客户使用。

4.2 因特网

1.因特网连接着全世界的设备和网络。网络和基础设施得到了商业和政府举措的支持。

2.我们已经提到，因特网是相连网络的集合。这些网络的构建和维护是由称作因特网服务提供方的组织来完成的。

3.端到端体系结构方便连接因特网上的新设备和网络。

4.允许因特网为这么多种设备和技术提供通信服务的因特网设计的方方方面，使因特网成为端到端体系结构。

1. 互联网需要一个互联网范围的编址系统，为该系统中的每台计算机分配一个唯一的标识地址。在因特网中，这些地址称为IP地址。
2. IP地址是分层的。通过分配IP地址可以使设备连接到因特网上。
3. 送消息之前将助记地址转换成IP地址。这种转换是在许多称为名称服务器的服务器的帮助下完成的，这些名称服务器本质上是向客户机提供地址转换服务的目录,称为域名系统。使用域名系统进行转换的过程称为域名系统查找。

4.3 万维网

1.为了在万维网上定位及检索文档，每个文档都被赋予了一个唯一的称为统一资源定位地址(URL)的地址。

2.可扩展标记语言(XML)是一种标准化的风格(类似于上面乐谱的例子),用于设计将数据表示为文本文件的符号系统。

3.浏览器或万维网服务器付出额外的活动。如果这些活动由客户机(如浏览器)完成则称为客户端活动，如果这些活动由服务器(如万维网服务器)完成则称为服务器端活动。

4.4 因特网协议

1.因特网上的软件有4层，每层是由软件例程组成。这4层被称为应用层、传输层、网络层和链路层。

2.因特网是一个发送数字数据的分组交换系统，在发送数据时会将其分解成称为分组的位块，其中包含正在传输的数据和用于路由该数据的控制信息。

3.因特网上的路由选择是容错的、冗余的。

因特网上两点之间路由选择的冗余(即不止有一条通向路由数据的路)能提高因特网的可靠性，并帮它扩大到更多的设备和更多的人。

4.分组和路由选择的标准包括传输控制协议/因特网协议(TCP/IP)。

5.可以使用IP地址的设备的数量增长得特别快，以至于已经建立了新协议(IPv6)来处理更多设备的路由选择。

4.5 简单的客户机服务器

1.数据可以存储为许多种格式，具体取决于数据的特点(如大小和预期用途)。

4.6 网络安全

1.实现网络安全有软件、硬件和人3个部分。

2.当计算机连接到网络上时，它会成为未授权访问和恶意破坏的对象，未授权访问和恶意破坏是网络犯罪的两种形式。

3.病毒是一种软件，它先通过将自身嵌入计算机已有的程序中来感染计算机，与宿主程序一同启动。

4.蠕虫是一个自主程序，它可以通过网络传送自己，驻留在计算机中并将其自己的副本转发到其他计算机。

5.特洛伊木马是一种伪装成吸引人的程序(如游戏或有用的实用程序包)进入计算机系统的程序，它们被受害者自愿引入。然而，一旦特洛伊木马程序进入计算机，它就会实施可能有不良影响的额外活动。

6.恶意软件的另一种形式是间谍软件,有时称为嗅探软件，这类软件收集它所在计算机的活动信息，并把这些信息报告给攻击的发起者。

1. 分布式拒绝服务攻击通过使用来自多个系统的请求淹没目标来危害目标。
2. 网络仿冒、病毒和其他攻击都有人和软件两部分。
3. 防病毒软件和防火墙可以帮助避免对私人数据进行未授权访问。
4. 密码学是许多网络安全模型必不可少的。
5. 万维网上的浏览器和服务器之间共享信息和进行通信的标准包括HTTP和安全套接层/传输层安全(SSL/TLS)。
6. 密码学有数学基础。对称加密是一种涉及一个密钥的加密和解密的加密方法。
7. 开放标准有助于确保密码学是安全的。公钥加密不是对称的，因为它能增强安全性，所以它是一种广泛使用的加密方法。
8. 认证机构(CA)颁发用于验证安全通信中使用的加密密钥的所有权的、基于信任模型的数字证书。
9. 隐私和安全问题出现在计算系统和制品的开发和使用中。

第5章算法

5.1 算法的概念

1.算法是定义一个可终止过程的一组无歧义的、可执行的步骤的有序集合。

2.定序是按给定语句的顺序应用每个算法步骤。

5.2 算法的表示

1.计算机科学解决一些问题的途径是建立一组定义明确的构建块，利用它们来构造和执行算法的表示。这种构建块称作原语。原语的集合以及说明如何组合这些原语来表示比较复杂的想法的规则集合就构成了程序设计语言。

2.用自然语言和伪代码描述算法是为了让人可以理解它们。

3.选择使用布尔条件来确定使用算法的两个部分中的哪一个。

4.迭代是算法一部分的重复，一直重复到满足条件或者达到指定次数为止。

5.定序、选择和迭代是算法的构建块。每个算法都可以只使用定序、选择和迭代来构造。

6.算法可以组合形成新算法。

5.3 算法的发现

1.创建计算制品用迭代和经常性的探索过程将想法变成有形的形式。

2.逐步精化是一种自顶向下方法,这种方法从一般发展到特殊。相反，自底向上方法是从特殊发展到一般。

5.4 迭代结构

1.按照条目在列表中出现的顺序进行查找的，这个算法称作顺序搜索算法，有时称作线性搜索。

5.5 递归结构

1.把每一阶段的重复当作前一阶段的子任务，就叫做递归。

2.执行递归函数产生的错觉是这个函数存在多个副本,每个副本称作这数的一次激活。

3.递归函数会在请求进一步激活之前测试终止条件[通常称作基本条件或者退化条件]。

5.6 效率和正确性

1.找到问题的高效算法可以帮助解决问题的更大实例。

确定算法的效率是通过对算法的形式化或数学推理来完成的。同一个问题的不同的正确算法可能会有不同的效率。

2.算法的正确性是通过对算法的形式化或数学推理来确定的，而不是通过测试算法的实现来确定的。

第6章 程序设计应用

6.1 历史回顾

1.第一代程序是使用机器语言编写的。所谓机器语言，即内置在计算机电路中的指令，使用起来非常复杂而困难，所以第一代程序员都是数学家或工程师。

2.由于机器语言使用的困难，有些程序员就开发了一些工具来辅助程序设计，于是第一代人工程序设计语言出现了，被成为汇编语言。因为最终机器上执行的是机器语言，所以程序员还创建了一种翻译程序，来把汇编语言变成机器语言，称为汇编器。

1. 从二代开始，出现了高级语言。高级语言无法直接被计算机理解，但是可以通过“编译”这一操作来转换成机器语言供计算机使用。每种高级语言都有相应的编译器。
2. 在高级语言之外出现了应用程序包，这是一种多用途的应用程序，便于普通的用户使用简单的编程语言也能实现很多功能。
3. 高级程序设计语言为程序员提供了更多的抽象，使人们读写程序更容易。
4. 不同的程序设计语言提供不同层次的抽象。
5. 用于算法的语言包括自然语言、伪代码，以及可视和文本程序设计语言。不同的语言更适合表达不同的算法。
6. 一些程序设计语言是为特定领域设计的，更适合表达那些领域中的算法。
7. 用于表达算法的语言可能会影响清晰度或可读性之类的特性，但不会影响算法解决方案是否存在。
8. 几乎所有的程序设计语言都能够表达任何算法。在用语言表达算法时，清晰度和可读性是重要的考虑因素。
9. 命令式范型,也叫过程范型,代表了程序设计过程的传统方法。
10. 说明性范型,它要求程序员描述的是要解决的问题，而不是要遵循的算法。
11. 函数式范型，在这种范型下，程序被看作接受输入和产生输出的实体。
12. 另一种程序设计范型(当今软件开发领域中最著名的一个)是面向对象范型,它是与称为面向对象程序设计(O0P)的程序设计过程相关联的。

6.2 传统的程序设计概念

1.通常，程序由一组语句组成，这些语句一般可以分成3类：声明语句、命令语句和注释。

2.软件是用多层次抽象(如常量、表达式、语句、过程和库)开发的。

3.程序指令可能涉及初始化、更新、读取和写入的变量。

4.程序中的变量通常与数据结构有关，数据结构是数据在概念上的形态或排列。

5.无论单独工作还是在协作程序设计环境中工作，文档都有助于开发和维护程序。

6.关于程序组件(如段和过程)的文档有助于开发和维护程序。

6.3 过程单元

1.函数就是完成一个任务的一组指令，它能够用作其他程序单元的抽象工具。

2.在函数中声明的变量称为局部变量,意思是它只能在这个函数的内部引用。局部变量能够消除由于两个独立的函数碰巧使用同一名称的变量所产生的混淆。

3.开发抽象的过程涉及去除细节和归纳功能。为了归纳概念，抽象从具体示例中提取共同特征。

4.参数化可以归纳一个特定的解决方案。

5.抽象用允许软件复用的输入参数来概括功能。

6.使用现有的正确算法作为构建块来构造新算法有助于确保新算法是正确的。

6.4 语言实现

1.将程序从一种语言转换为另一种语言的过程称为翻译,原始形式的程序称作源程序,翻译后的版本称作目标程序。

2.翻译过程包括3个活动，它们分别是词法分析、语法分析和代码生成，翻译器中完成这3个活动的相应单元分别称为词法分析器、语法分析器和代码生成器。

3.为了简化语法分析过程，早期程序设计语言坚持将每条程序语句以一种特定的方式定位在打印页上，这种语言称为固定格式语言。

4.许多程序设计语言都是自由格式语言,这意味着不再苛求语句的位置安排了。

5.用程序设计语言编写的代码经常会被翻译成另一种(较低级的)语言的代码，以便在计算机上执行。

6.5 面向对象程序设计

1.需要讲解。

6.6 程序设计并发活动

1.这种多个激活的同时执行称为并行处理或并发处理。

《计算机科学概论》第7-10章泛读

1. 软件工程

7.3 软件工程方法学

1.给正确的工作程序逐渐增加测试程序段，有助于创建正确的大型程序。

2.程序开发的迭代过程有助于开发解决问题的正确程序。

3.增量模型和迭代模型有时会利用软件开发朝着原型开发发展的趋势。原型开发是构建并评估预期系统的非完整版本(称为原型)的过程。

4.在增量模型中，将这些原型发展为一个最终的完整系统的过程称为演化式原型开发。在迭代性更强的情况下，可能会丢弃原型，以使最后设计有全新的实现，这种方法称为抛弃式原型开发。

5.由瀑布模型转化而来的变化最显著的方法是称为敏捷方法的方法学集合。

1. 数据抽象

8.1 基本数据结构

1.数组是一种“矩形的”数据块，其项具有相同的类型。

2.聚合类型是一个由数据项组成的块，其中的各个数据项可能具有不同的类型和大小。

3.另一种基本数据结构是列表,它是一个集合，其表项按顺序排列。列表的开头称为表头,列表的结尾称为表尾。

4.列表和列表操作(如添加、移除和搜索)在许多程序中很常见。集合的基本操作包括添加元素、移除元素、迭代所有元素以及确定元素是否在集合中。

5.树是一种集合，其项具有层次化的组织形式，树中的每一个位置称为一个节点。树顶部的那个节点称为根节点。另一端点处的节点称为终端节点(terminal node),有时称为叶节点。我们常将从根到叶子的最长路径上的节点数称为树的深度。换句话说，一棵树的深度就是该树所包含的水平层数。

第9章数据库系统

9.6 数据挖掘

1.模式会出现在使用计算工具转换数据的时候。数据挖掘已经使医学、商业和科学领域的创新成为可能。

2.数据挖掘的两种常见形式是类描述和类辨别。

3.另一种数据挖掘的形式是聚类分析,它用来发现类。

4.还有一种数据挖掘的形式，称为关联分析,它的工作是寻找两个数据组之间的联系。

5.孤立点分析是数据挖掘的另一种形式。它试图识别不符合规则的数据项。

第10章

10.1 计算机图形学范围

1.数字图像可以通过生成像素模式、处理现有数字图像或者组合图像来创建。

2.数字特效和动画可以用现有软件创造，也可以用包含实现特效和动画功能的软件来修改。

3.计算能够对现实和虚拟现象进行创造性探索。

4.数字特效、图像、音频、视频和动画的创造已经改变了相关产业。计算方面的发展已经产生和提高了其他领域的创造力。