《计算机软件技术基础》
第一章 算法
1.1算法的基本概念
算法：指解题方案的准确而完整的描述
算法的基本特征：
能行性（算法中的每一个步骤必须能够实现；算法执行的结果要能够达到预期的目的）
确定性（算法中的每一个步骤都必须是有明确定义的，不能摸棱两可，也不能有多义性）
有穷性（算法必须能在执行有限个步骤之后终止）
拥有足够的情报（算法执行的结果总是与输入的初始数据有关。不同输入对应不同输出）
算法：是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的、明确的，此顺序将在有限的次数下终止。
算法的基本要素：
1.算法中对数据的运算和操作（算术运算、逻辑运算、关系运算、数据传输【赋值、输入、输出】）
2.算法的控制结构（算法中各操作之间的执行顺序）
1.2算法描述语言
C语言描述和简单的算法描述语言
（1）符号与表达式：符号主要用以表述变量名、数组名等
（2）赋值语句
计算机软件的组成（3）控制转移语句：
无条件转移语句形式：GOTO 标号
条件转移语句形式 IF C THEN S
IF C THEN S1
ELSE S2
（4）循环语句
WHILE语句：WHILE C DO S
FOR语句：FOR i=init TO limit BY step DO S
（5）其他语句
EXIT语句：退出某个循环，使控制转到包含EXIT语句的最内层的WHILE或FOR循环后面的一个语句去执行
RETURN语句：结束算法的执行（允许使用用引号括起来的注释信息）
READ(INPUT)和WRITE(PRINT/OUTPUT)语句：用于输入输出
（6）算法中的注释总是用一对方括号【】括起来；复合语句用一对花括号{}括起来
1.3算法设计基本方法
1.列举法【例1.1】
特点：算法比较简单，但列举情况较多时，工作量将很大
寻路径、查、搜索等问题采用列举法有效
2.归纳法
基本思想：通过列举少量的特殊情况，经过分析，最后出一般的关系
3.递推法（数学例题）
指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（本质属于归纳法）
4.递归
自己调用自己的过程称为递归调用过程
递归分为
直接递归：一个算法P显式地调用自己
间接递归：算法P调用另一个算法Q，而算法Q又调用算法P
5.减半递推技术（分治法）
减半：将问题的规模减半，而问题的性质不变
递推：重复“减半”的过程【例1.4】
6.回溯法
通过对问题的分析，出一个解决问题的线索；然后沿着这个线索逐步试探。对于每一步
的试探，如果成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探。（处理复杂数据结构方面有广泛应用）【例1.5】
1.4算法的复杂度分析
算法的复杂度主要包括时间复杂度和空间复杂度
算法的时间复杂度：指执行算法所需要的计算工作量
可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量，同时还需对问题的规模进行度量
综上，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
算法的工作量=f(n)
其中，n是问题的规模
在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量
（1）平均性态：用各种特定输入下的基本运算次数的带权平均数来度量算法分工作量A(n)）
（2）最坏情况复杂性：在规模为n时，算法所执行的基本运算的最大次数W(n)
【例1.6】
算法的空间复杂度：指执行这个算法所需要的内存空间
一个算法所占用的存储空间包括：算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
其中额外空间包括：算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间
如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的
实际问题中，为减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间
第4章 资源管理技术
1、计算机系统主要包括硬件（即物理设备）和软件（即程序及其文档的总称）两大部分；计算机系统中所有的硬件和软件统称为计算机资源。
2、操作系统是最基本和核心的系统软件，是用以控制和管理系统资源、方便用户使用计算机的程序的集合。操作系统的功能和任务主要有处理机管理、存储器管理、设备管理、文件管理、作业管理。
3、操作系统发展过程：手工操作阶段（手编程序）、成批处理系统（脱机技术）、执行程序系统（主机与通道并行工作）、多道程序系统（并行性、共享性）。
4、为使主机和输入输出设备并行工作，人们使用以通道技术、中断技术和多道程序设计技术为基础的假脱机技术。
5、多道程序技术是指在计算机内存中同时存放多道相互独立的程序，他们在操作系统的控制下，共享系统的硬件和软件资源。
6、操作系统的分类（按使用环境及访问方式）：
（1）多道批处理操作系统
（2）分时操作系统，特点：同时性、独立性、及时性、交互性；分时是指若干个并发程序对CPU的分时，其中每个程序对CPU的时间分享单位称为时间片；第一个分时操作系统是UNIX操作系统。
（3）实时操作系统
（4）通用操作系统
（5）多窗口系统，特点：灵活、方便的窗口操作，弹出式菜单、命令对话框；代表：Microsoft Windows系统。
7、顺序程序的特点：顺序性（按顺序执行）、封闭性（一旦执行其结果不受外界因素影响）
、可再现性（结果与运行速度无关）。
8、在单处理机的情况下，所谓并发执行是指多个程序的运行在时间上是重叠的，一个程序的运行尚未结束，另一个程序的运行已经开始，而并不是说这些程序在某一时刻同时占用处理机在运行。
9、并发程序特点：并发程序没有封闭性（结果与各程序执行的相对速度有关，结果的不确定性）；程序与其执行过程不是一一对应的关系（共享）；程序并发执行可以相互制约。
10、所谓进程，是指一个具有一定独立能力的程序关于某个数据集合的一次运行活动，简单地说，进程可以是并发执行的程序的执行过程，是控制程序管理下的基本的多道程序单位。
11、进程与程序的区别：
（1）进程是程序在处理机上的一次执行过程，是动态的概念；而程序只是一组指令的有序集合，是一个静态的概念。
（2）进程是程序的执行过程，是一次运行活动，具有一定的生命期；而程序是可以作为一种软件资源长期保存的。
（3）进程的组成包括程序、数据以及进程控制块（PCB）。
（4）一个程序可能对应多个进程。
（5）一个进程可以包含多个程序。
12、进程三种基本状态：运行状态（进程只能在运行状态下结束）、就绪状态、等待状态（又叫阻塞状态或封锁状态），三种基本状态之间在一定条件下可相互转换。
13、对进程的物理组织方式通常有线性表和链接表两种。
14、由于各进程互相独立地动态获得，不断申请和释放系统中的软硬件资源，这就有可能使系统出现这样一种状态：其中若干个进程均因互相“无知地”等待对方所占有的资源而无限地等待。这种状态称为死锁。
15、发生死锁的四个必要条件：资源的独占使用、资源的非抢占分配、资源的部分分配、
对资源的循环等待。当其中某一条件满足时，有可能发生死锁，但也并不是一定会发生死锁。
16、当多个进程共享数据块或其他排他性使用资源时，不能同时进入存取或使用，但进入的次序可以任意，这些进程之间的这种相互制约关系称为互斥（多个操作决不能在同一时刻执行）。进程之间为了合作完成一个任务，而需要互相等待和互相交换信息的相互制约关系称为同步。
17、一次只允许一个进程使用的资源称为临界资源，访问临界资源的程序段称为临界区或临界段。
18、进程通信可分为互斥与同步两类，互斥是一种特殊的同步关系。根据通信情况的不同，可把进程之间的同步分为信号同步（低级通信原语用于信号同步，如P/V操作）与信件同步（高级通信原语用于信件同步，消息缓冲是一种高级通信工具）。
19、处理机调度一般分为两级：作业调度（又称为高级调度或宏调度）与进程调度（又称为低级调度或微调度）
20、在进行地址变换时（又称地址映射，当用户程序进入内存执行时，必须要把用户程序中所有相对地址转换为内存中的实际地址，否则用户程序就无法进行），必须修改程序中所有与地址有关的项，也就是说，要对程序中的指令地址以及指令中的有关地址的部分（称为有效地址）进行调整，这个调整的过程称为地址重定位。
21、存储管理的功能：地址变换、内存分配、存储共享与保护、存储器扩充。
22、基本的存储管理技术：界地址存储管理、分页存储管理、分段存储管理、段页式存储管理。
23、分页存储管理与分段存储管理的优缺点：
（1）分页存储管理的优点：a.用户地址空间不再受内存大小的限制；b.更有利地利用了内存；c.动态分页管理提供了虚拟存储器（受外存容量的限制），更有利于多道程序的运行。
（2）分页存储管理带来的问题：a.不利于程序的动态连接装配；b.不利于程序与数据的共享。
（3）分段存储管理正好解决了这两个问题。
24、文件的物理组织形式主要有连续文件、链接文件和索引文件（建议看看P263多级索引结构）；文件系统对磁盘空闲空间的管理方式有空闲文件项和空闲区表、空闲块链、位示图、空闲块成组链接法。
第6章 编译技术概述
25、编译程序是将用高级语言编写的源程序翻译成机器语言程序的实用程序。
26、编译程序的基本组成：（1）词法分析程序（读词程序）；（2）语法分析程序：编译程序的主要组成成分；（3）加工程序：直接影响翻译质量的关键一步，包括大量的造表和查表的过程；（4）优化修饰部分；（5）装配程序或链接程序：将分块编译得到的半目标程序（包括库程序）进行总装配。
27、状态矩阵法的核心是一张状态表（也称状态矩阵）。所谓状态，是表示过去已经扫描了什么语法成分，以便当遇到新的语法符号时，在不同的状态下对该语法符号作出不同的处理。（关于状态矩阵的具体编译过程建议看书299-307）
28、状态矩阵是稀疏矩阵，为节省存储空间，通常对状态矩阵进行压缩。
29、通过词法分析，可将一个常数用V×10m表示，其中V为正整数，m=ep-n，e为阶码符号（+、-），p为阶码绝对值，n为小数位数。如FROTRAN常数0.032E-1中，e= -，p=1，n=3，经词法分析，其结果为32×10-1-3=32×10-4 （V=32，m=-4）。
发布评论