当前位置：首页 > news >正文

软件设计师笔记1

news 2025/8/28 1:47:54

分享一下学习软考时做的笔记，笔者太懒了，后续篇章都没咋记录，现在放出来水几篇文章

另外，本章内容都是结合教材，B站课堂记录。下一篇软考笔记知识点来自真题

软考笔记

第一章

1. 计算机的组成

1. 控制器

控制器由程序计数器（PC，Program Counter）、指令寄存器（IR，Instruction Register）、指令译码器（ID，Instruction Decoder）、时序产生器（Timing Generator）、操作控制器（Control Unit）组成。

控制器

功能：
控制CPU的工作，决定运算过程的自动化
指令控制逻辑、时序控制逻辑、总线控制逻辑、中断控制逻辑

执行过程
取指令
指令译码
指令执行
下一条指令地址

重要部件
- 指令寄存器IR：将内存中的指令读取到缓冲寄存器，然后送入IR暂存。指令译码器根据IR的内容产生各种微操作指令，控制其它部件完成功能
- 程序计算器PC：PC寄存信息，计数。PC存储下一个指令的所在地址。大多数指令都是顺序执行，因此PC++即可寻找到吓一跳指令的地址。如果遇到转移指令，CPU修改PC内容，获取地址。
- 地址寄存器AR：保存当前CPU访问的内存单元的地址。
- 寄存器组：专用寄存器和通用寄存器。

2. 主存

在这里插入图片描述

用于存储程序运行时的数据。

MAR：存储地址存储器

MDR：存储数据存储器

3. 运算器

在这里插入图片描述

运算器

功能：
执行所有算数运算。包括加减乘除以及附加运算
执行逻辑运算与逻辑测试：与或非、零值测试、两个值比较

运算器重要组件
- 算数逻辑单元ALU：实现数据运算与逻辑运算
- 累加寄存器ACC：在计算过程中，为ALU提供一个工作区，存储中间结果。
- 乘商寄存器MQ：乘商寄存器，在乘、除运算时，用于存放操作数或运算结果。
- 数据缓冲寄存器DR：对内存读写时，DR暂时存放存储器读写的一条指令，或者一个数据字段。
- 状态条件寄存器PSW：计算条件状态码。主要分为状态标志，控制标志
  - 进位标志（C）
  - 溢出标志（V）
  - 为0标志（Z）
  - 负结果标志（N）
  - 中断标志（I）
  - 方向标志（D）
  - 单步标志

计算机的各个功能部件按照下述形式，组合在一起。协调工作，实现计算机的复杂功能。

在这里插入图片描述

2. 数据表示

2.1 原码

1). 正数

短除法计算，看下图

$45]_{原} = 101101_{2}$

在这里插入图片描述

2). 负数

取其绝对值，计算原码。在其最高位上补1，用于表示符号位

将负数的绝对值转换为二进制数。
如果二进制数的位数不足，可以在左侧用零进行填充，使其达到所需的位数。
在最高位添加符号位，通常为 1（表示负数）。

举例来说，将十进制的 -5 转换为 4 位二进制原码：

将 5 转换为二进制：101
由于是 4 位原码，需要在左侧用零进行填充：0101
添加符号位 1（表示负数），最终的 4 位二进制原码为 1101。

3). 小数

整数部分正常转换，小数部分按照乘以 2 并记录整数部分的方式来完成

举例说明，将十进制的 5.625 转换为原码：

整数部分 5 转换为二进制：101
小数部分 0.625 转换为二进制：0.101
合并整数和小数部分：101.101
因为是正数，符号位为 0。

5.625 的二进制原码表示为 0101.101

所谓的x2记录法，是对小数做x2处理。每次取整数部分作为结果。留下小数部分作为下次x2处理。持续迭代，指导位数达到要求或者小数为0。

对于十进制的小数 0.61825，我们可以使用 “乘以2并记录” 的方法进行转换为二进制。以下是详细步骤：

0.61825 乘以 2 等于 1.2365，记录整数部分 1。
取新的小数部分 0.2365，再次乘以 2 等于 0.473，记录整数部分 0。
取新的小数部分 0.473，再次乘以 2 等于 0.946，记录整数部分 0。
取新的小数部分 0.946，再次乘以 2 等于 1.892，记录整数部分 1。
取新的小数部分 0.892，再次乘以 2 等于 1.784，记录整数部分 1。
取新的小数部分 0.784，再次乘以 2 等于 1.568，记录整数部分 1。

持续进行以上操作，直到小数部分为0或者达到了所需的二进制位数。在这个例子中，我们得到的二进制表示是 0.1010011001100101101

4). 负小数

取小数绝对值，得到原码。然后在最高位补1.表示符号

2.2 反码

负数的反码=负数的原码，除了符号位不变，其余位置全部取反。

小数的反码=整数部分取反【符号位不变】+ 小数部分取反

tip: 正数的原码=正数的反码

2.3 补码

正数：不变

负数：反码+1

负小数：小数反码的最后一位 + 1

3. 定点数和浮点数

定点数的补码和移码可以表示 $2^n$ 个数，原码和反码只能表示 $2^{n}-1$ 个数（0占用2个编码）。

在十进制中，83.125 可以写成 $10^{3}\times 0.083125$ ，那么二进制中；二进制数1011.10101可以写成 $2^{4}\times 0.101110101$ 。因此我们可以得知，一个二进制数N可以写为如下形式： $N=2^{E}\times F$

E称为阶码，F称为尾数。这种表示方式称为浮点表示法

浮点数的表示方式如下：

**|阶符| 阶码 | 数符 | 尾数| **

阶码决定数的范围，尾数决定精度

浮点数规格化，规定尾数范围落在[0.5, 1]之间

3.1 IEEE 754浮点数

浮点数的3中格式

在这里插入图片描述

浮点数可以表示为 $(-1)^s 2^E (b_0 b_1\dots b_{p-1})$

其中， $1)^s$ 为浮点数的数符，当S为0时表示正数，1时为负数。E为指数（阶码），用移码表示。偏移位数由浮点数精度决定。 $(b_0 b_1\dots b_{p-1})$ 为尾数，长度为P位，用原码表示

eg: 用IEEE 754 将176.0625写成单精度浮点数

将176.0625转换为二进制形式。整数部分和小数部分分别转换。

整数部分的二进制表示为：10110000
小数部分的二进制表示为：0001。

将整数部分和小数部分合并，得到176.0625的二进制表示为10110000.0001。

根据IEEE 754标准，确定符号位、指数位和尾数位的长度。

符号位：1位，表示正负号，0表示正数，1表示负数。
指数位：8位，用于存储指数部分的偏移量。
尾数位：23位，用于存储小数部分的有效位数。

确定符号位：

由于176.0625是正数，所以符号位为0。

规格化二进制数：

将10110000.0001规格化为1.01100000001 × 2^7。

计算偏移量：

指数偏移量为127（单精度浮点数的偏移量是2^(8-1)-1=127），所以偏移量为7 + 127 = 134，对应的二进制为10000110。

将指数和尾数合并：

指数为134的二进制表示为10000110，尾数部分只保留小数点后的23位有效位，即01100000001000000000000。

得到IEEE 754表示：

最后，将符号位、指数位和尾数位合并，得到单精度浮点数的IEEE 754表示为：

0 10000110 01100000001000000000000

因此，176.0625的IEEE 754表示为01000011001100000000100000000000。

浮点数+ -

对阶，移动尾数小数点，使得阶数E处于同一数量级。
尾数携带符号，进行±计算
对得到的结果重新规格化

浮点数x➗

阶数相±
尾数乘除
修改符号位
规格化

4. 校验码

4.1 奇偶校验

通过额外添加一个数位，来使原先编码所中1的个数为奇数或偶数。

4.2 海明码

设：数据有m（message）位，校验码有p（parity）位；

则：校验码一共有 $2^p$ 种取值；

若想通过检验码指出任意一位上出现错误，那么必须满足以下式子
$2^p - 1 \geq m + p$

理解：p位校验码能够表示 $2^p$ 个数，其中有一种是表示正确的情况。因此，只有 $2^p - 1$ 个数能表示错误情况。而海明码的m + p 位都有可能出错，因此校验码最少能够表示m + p个错误。因此得出上述等式。

现在，我们要发送1010数据，数据长度m = 4，由上述式子得出 p >= 3，取最小值 p = 3。校验码一共有三位

现在，我们创建如下表格，将数据填入其中

校验码p1p2p3每一位填写在 $2^n(n=0、1、2\dots)$ 位置上，剩下位置添加数据码

在这里插入图片描述

现在，我们建立p和数据各位之间的关系
$p_1 \ \ \ m_3 \ \ \ m_5 \ \ \ m_7 \\ p_2 \ \ \ m_3 \ \ \ m_6 \ \ \ m_7 \\ p_3 \ \ \ m_5 \ \ \ m_6 \ \ \ m_7 \\$
p与m之间的关系，取决于二进制数的位置。例如** $p_1$ ，m对应下标的二进制数**，只要第一位是1，那么就需要和 $p_1$ 构建联系。同理，p2所寻找的m需要满足下标二进制的第二位是1。p3则是二进制第三位是1。

寻找到p与m的关系，就只需要按照奇偶检验码的规则确定p
$p_1 \ \ \ 0奇,1偶 \ \ \ 1 \ \ \ 0 \ \ \ 0 \\ p_2 \ \ \ 1奇,0偶 \ \ \ 1 \ \ \ 1 \ \ \ 0 \\ p_3 \ \ \ 0奇,1偶 \ \ \ 0 \ \ \ 1 \ \ \ 0 \\$
将数据填写回表格

在这里插入图片描述

现在，我们规定采用奇校验规则，发送方发送数据0110010，接收方收到的数据为0110011，现在接收方进行数据校验，具体校验规则如下
$e_1 \ \ \ p_1 \ \ \ m_3 \ \ \ m_5 \ \ \ m_7 \\ e_2 \ \ \ p_2 \ \ \ m_3 \ \ \ m_6 \ \ \ m_7 \\ e_3 \ \ \ p_3 \ \ \ m_5 \ \ \ m_6 \ \ \ m_7 \\$
将接受方接收到的数据上表
$e_1\ \ \ 0 \ \ \ 1 \ \ \ 0 \ \ \ 1 \\ e_2 \ \ \ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1 \\ e_3 \ \ \ 0 \ \ \ 0 \ \ \ 1 \ \ \ 1 \\$
根据奇校验规则，解得e1 = 1，e2 = 1，e3 = 1。组合得到e3e2e1 = 111，既m7错误。对比发送数据，发现雀氏是第7位出错。接收方自动将第7位置取0，完成自动纠错

tip: 由e1, e2, e3组合出错误位置时，需要记得顺时针旋转，得到e3e2e1，而不是e1e2e3

4.3 循环冗余校验码 CRC

核心是利用冗余的数据位，检验出错误的数据位。而检验的方式是：模2除法。

假设需要发送的数据是101001，协议规定的除数是1101，确定余数（冗余码）的方法如下：

余数长度 = 除数长度 - 1，本题中，余数长度 = 3
在发送数据后面添加4个0，得到101001 000
用除数循环除以101001 000，具体过程如下

在这里插入图片描述

最终计算结果，余数位1. 因为冗余码长度为3，所以最终结果需要在1左边补0.得到001

5. 指令流水

5.1 执行方式

一条指令的执行过程可以分为多个阶段，大部分计算机的指令都可以分为取指，分析，执行三个阶段

顺序执行

在这里插入图片描述

指令穿行执行，一条指令执行完后，才能执行下一条指令。

这种执行模式，对于硬件来说实现很容易，但硬件的利用率很低。一般来说，指令的三个阶段所用到的硬件是不同的，也就是说，取值k结束后可以立刻进行取值k+1，分析k和取指k+1用到不同的硬件，所以可以并行执行

总耗时 T = 3nt

一次重叠执行

在这里插入图片描述

总耗时 T = 2nt + t

总耗时减小1/3，但硬件布线复杂

二字重叠

类似，不再赘述

5.2 流水线的性能指标

1.吞吐率

吞吐率：吞吐率是指在单位时间内，流水线完成的任务总数

设任务数为n：处理完成n个任务所用的时间为 $T_k$

则计算流水线吞吐率（TP）的最基本公式为 $\frac{n}{T_k}$

在这里插入图片描述

一条指令的执行分为k个阶段，每个阶段耗时Δt，一般取Δt=一个时钟周期，执行n条指令耗时(k + n - 1)Δt，所以吞吐率为
$\frac{n}{(k + n - 1)\Delta t} \\ 当n -> \infty时，取得最大吞吐率 TP_{max} = \frac{1}{\Delta t}$
一般来说，0->I1称为装入时间， I2->In称为排空时间

TP意度量处理任务速度

2.加速比

加速比：完成同一批任务，不适用流水线所用时间与使用流水线的时间之比

设 $T_0$ 为不适用流水线所需时间， $T_k$ 为使用流水线所需时间，那么可以得到 $\frac{T_0}{T_k}$

以上图为例，得到等式如下
$\frac{nk\Delta t}{(k + n - 1)\Delta t} = \frac{nk}{k + n - 1} \\ 当n-> \infty ，S_{max} = k$
理想情况下，引入流水线后，cpu加速了k倍

3.效率

效率：流水线利用率称为流水线效率

在时空图中，意思为完成n个任务占用的时空区有效面积 与 n个任务所用的时间与k个流水段所围成的时空区总面积之比

在这里插入图片描述

以上图为例，可得公式
$\frac{kn\Delta t}{k(k + n - 1)\Delta t} = \frac{n}{k + n - 1} \\ 当n->\infty时，E_{max} = 1$
E趋近于1意味着引入流水线，硬件几乎都在忙碌

5.3 缓存

为了缓解CPU处理数据速度和内存存取数据速度严重不符的问题，在CPU和内存之间添加新的层次结构，也就是缓存。缓存的处理数据的速度，介于CPU和内存之间。能够有效的提高系统整体的工作效率

1. 缓存-内存系统取值时间

在这里插入图片描述

如上图所示，CPU存在两种取值方案

方案一：先去Cache中取值，如果命中则终止取值行为，否则再去内存中取值

方案二：同时去Cache，内存中取值，如果Cache命中，终止内存取值行为，否则等待内存取值完成

现在，假设 $t_c$ 为访问Cache所需时间， $T_m$ 为内存所需时间。 $H$ 为CPU在Cache中找到所需数据的概率（命中率）

如果采取方案一，则系统平均访问时间为
$t = Ht_c + (1 - H)(t_c + t_m)$
如果是方案二，则平均时间为
$t = Ht_c + (1-H)t_m$

2. 缓存-内存系统，数据交换单位

Cache 存储内存的数据，是以块为单位。我们将主存进行分块，块的大小为1KB。以此为数据交换的单位

在这里插入图片描述

CPU访问Cache，如果数据没有命中，CPU会访问内存。在内存中找到的数据会以数据块的形式缓存到Cache中

3. 缓存-内存系统，数据映射

全相连映射

在这里插入图片描述

这种映射允许内存块中的任意一块数据，存储在Cache中的任意一行。在将内存数据缓存Cache时，需要在缓存中额外记录当前存储的数据是来自主存的那个区块。

例如，主存为 64MB，Cache 为 32KB，块的大小为4KB(块内地址需要 12 位)，因此主存分为 16384 块，块号从 0~16383，表示块号需要 14 位，Cache 分为8块，块号为 0~7，表示块号需3位。

存放主存块号的相联存储器需要有 Cache 块个数相同数目的单元(该例中为 8)相联存储器中每个单元记录所存储的主存块的块号，该例中相联存储器每个单元应为 14 位，共8个单元。

主存地址包含主存块号，块内地址。本例中，主存为64MB，64MB = $2^{26}$ ，主存块号需要14位，那么块内地址需要 26 - 14 = 12位。

在这里插入图片描述

CPU在访问主存地址 1101 1011 1011 101101 1111 1011，主存地址的前14位存放的是主存块号信息。取前14位和标记位进行比对

如果标记位匹配并且有效位有效，那么Cache命中，访问块内1101 1111 1011号地址的数据。

如果没有匹配或标记位为0，那么取主存中寻址，获取数据。同时将数据缓存在Cache中，更改有效位，存储标记位。

直接映射

在这里插入图片描述

主存块在Cache中的 $\ \ \% \ \ Cacahe总块数$

通过取余的方式，我们可以将主存块划分为若干个区间。区间内的块数据依次映射到Cache中

这种方式有个很大的缺陷，每个区间相同位置的数据会映射到同一个Cache块上。比如0区间的第一块数据，和1区间第一块数据映射在Cache的同一个位置。后者需要缓存时，必须覆盖前者数据

组相连映射

组相联映像。这种方式是前面两种方式的折中。具体方法是将 Cache 中的块再分成组。例如，假定 Cache 有 16 块，再将每两块分为1组，则 Cache 就分为8组。主存同样分区，每区 16 块，再将每两块分为1组，则每区就分为8组。

组相联映像就是规定组采用直接映像方式而块采用全相联映像方式。也就是说，主存任何区的0组只能存到 Cache 的0组中，1组只能存到 Cache 的1组中，依此类推。组内的块则采用全相联映像方式，即一组内的块可以任意存放。也就是说，主存一组中的任一块可以存入Cache 相应组的任一块中。

在这种方式下,通过直接映像方式来决定组号,在一组内再用全相联映像方式来决定 Cache中的块号。由主存地址高位决定的主存区号与 Cache 中区号比较可决定是否命中。主存后面的地址即为组号。

4. 缓存-内存系统，替换算法

替换算法的目标就是使 Cache 获得尽可能高的命中率。常用算法有如下几种。

随机替换算法（RANDOM）。就是用随机数发生器产生一个要替换的块号，将该块替换出去。
先进先出算法（FIFO）。就是将最先进入 Cache 的信息块替换出去。
近期最少使用算法（LRU，Least Recently Used）。这种方法是将近期最少使用的 Cache 中的信息块替换出去。
最不经常使用算法（LFU）。这种方法必须先执行一次程序，统计 Cache 的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。

替换算法只在使用全相联映射，组相连映射时才有用，直接映射不存在替换算法。

直接映射，主存中的每一块存放的位置都是固定的，主存如果要缓存新的数据块，必须覆盖Cache中原有的数据块

6. 数据传输控制

数据传输是由cpu控制，数据从内存流向外存。内存的速度要快于外存，二者之间存在速率差异，因此需要进行控制，以保证数据正确传输

1. 程序控制

无条件传送
在此情况下，外设总是准备好的，它可以无条件地随时接收 CPU发来的输出数据，也能够无条件地随时向 CPU 提供需要输入的数据。
程序查询方式
在这种方式下，利用查询方式进行输入/输出，就是通过 CPU 执行程序来查询外设的状态判断外设是否准备好接收数据或准备好了向 CPU 输入的数据。根据这种状态，CPU 有针对性地为外设的输入/输出服务。

为了更好的理解，我们可以把CPU比作老师，老师为了检查学生是否学懂知识，不断地询问班上每一位同学。CPU为了感知外存是否接收完毕数据，需要轮询外存

2. 程序中断

中断的意思是：I/O系统进行数据传输时，不需要CPU轮询。当I/O设备准备好时，发出中断通知CPU。CPU保存当前工作状态，处理I/O数据传输。完成I/O传输后，恢复本来的工作。

我们可以理解为：学生举手告诉老师，这样就不需要老师轮询

3. 直接存储器存取

直接内存存取(Direct Memory Access，DMA)是指数据在内存与 IO 设备间的直接成块传送，即在内存与 IO 设备间传送一个数据块的过程中，不需要 CPU 的任何干涉，只需要 CPU在过程开始启动(即向设备发出“传送一块数据”的命令)与过程结束(CPU 通过轮询或中断得知过程是否结束和下次操作是否准备就绪)时的处理，实际操作由 DMA 硬件直接执行完成,CPU 在此传送过程中可做别的事情

在这里插入图片描述

在此期间，CPU不会干预DMA数据传输，由DMA

7. 计算机系统可靠性（可用性）与可靠性模型

1. 可靠性（可用性）

计算机可靠性：计算机开始运行到一段时间内，正常运行的概率，一般用 $R (t)$ 表示

失效率：单位时间内，失效的元件数与原件总数的比例，用 $\lambda$ 表示。当 $\lambda$ 为常熟时，可靠性与失效率的关系为
$e^{-\lambda t}$
如下是典型的失效率与时间的关系图

在这里插入图片描述

平均修复时间（MTRF）：故障需要修复的平均时间，参数用于表示计算机的可维修性，即维修效率

无故障时间（MTBF）：两次故障间，系统正常工作的平均时间，即 $1/\lambda$

计算机的可用性：指计算机的使用效率，用系统在任意时刻，正常工作的概率A表示，即
$\frac{MTBF}{MTBF + MTRF}$
计算机的可靠性：MTBF/(1+MTBF)

2. 可靠性模型

计算机系统非常复杂。我们可以拆解为若干个子系统，简化分析计算机的可靠性

1.串联系统

假设一个系统有N个子系统，只有所有子系统都正常运行，系统才能正常运行。这样的系统称为串联系统。

在这里插入图片描述

假设每个子系统的可靠性用 $R_1,R_2\dots R_N$ 表示，那么系统的可靠性 $R=R_1R_2\dots R_N$

2.并联系统

假设一个系统的某个功能有多个子系统实现，当一个子系统崩溃时，存在其它子系统代替崩溃的子系统工作，那么这样的系统称为并联系统
在这里插入图片描述

系统的可靠性 $1-(1-R_1)(1-R_2)\dots(1-R_N)$

如果要让并联系统崩溃，则需要所有子系统全部崩溃。单个子系统崩溃的概率为 $1-R_n$ 。所有子系统同时崩溃的概率为 $(1-R_1)(1-R_2)\dots(1-R_N)$ ，那么整体系统不崩溃的概率即为 $1 - 子系统同时崩溃的概率$ ，也即 $1-(1-R_1)(1-R_2)\dots(1-R_N)$

3. 计算机性能指标

主频：表示计算机1s内有多少次脉冲。（2.4GHZ表示1s内有2.4G次脉冲）

时钟周期：表示计算机1次脉冲有多少秒，一个时钟周期C包含多少秒。（1s/2.4GHZ）

时钟周期（C） = 1/主频。时钟周期将1s分配给脉冲

CPI：CPI代表着 C/I，C表示时钟周期，I表示指令。CPI表示1条指令所包含的时钟周期个数

P代表着每，也就是 /

IPC：I/C，意味着单位时钟周期包含的指令数

IPC = 1/CPI

MIPS：百万条指令 / 1s，即 $\times 10^6)=主频/CPI = 主频 \times IPC$

M = 百万（million）

MFLOPS : 浮点数操作次数，即 $\times 10^6)$

吞吐量：一定时间内，完成的任务量（请求） Task/Time

吞吐率：单位时间内，完成的任务量（请求）Task/1s

响应时间（RT）：提交请求到完成请求的时间

例如在文本编辑器中打字，从按下键盘到显示字母的时间就是RT

完成时间（TAT）：指令执行完成的时间

tip:

在时间的范围内，存在如下的单位转换形式
$1KHZ = 10^3HZ，1MHZ = 10^3KHZ，1GHZ = 10^3MHZ$
在存储的范围内，存在如下的单位转换形式
$1B(字节) = 8b(比特bit)，1KB=2^{10}B，1MB=2^{10}KB，1GB=2^{10}MB$

第二章

1.编译过程概述

2.文法和语言的描述形式

3. 词法分析

1. 正规表达式和正规集

2. 有限自动机

确定的有限自动机（DFA），确定的有限自动机是五元组 $(S,\sum,f,s_0,Z)$
- S是一个有限集，其每个元素称为一个状态。
- ∑是一个有穷字母表，其每个元素称为一个输入字符。
- f是 SxΣ→S 上的单值部分映像。f(A,a)=Ω 表示当前状态为 A、输入为a时，将转换到下一状态 Ω，称 Ω为A的一个后继状态。
- $s_0\in S$ ，是唯一的一个开始状态。
- Z是非空终止状态集合， $Z\subseteq S$

一个DFA可以由两种图示表示：状态转换图，状态转移矩阵

例：
$已知有 DFA \ \ M_1=(\{s_0,s_1,s_2,s_3\},\ \ \{a,b\}, \ \ f, \ \ s_0, \ \ \{s_3\})，其中f为: f(s_0,a)=s_1,\\f(s_0,b)=s_2,,f(s_1,a)=s_3,f(s_1,b)=s_2,f(s_2,a)=s_1,f(s_2,b)=s_3,f(s_3,a)=s_3;$
则状态转换图，转移矩阵如下

对于上例， $\sum$ 中的任意字符串 $\Omega$ ，存在一条路径使得从初始状态走向终止状态，那么称DFA M1能够识别 $\Omega$ 。

DFA 所能识别的语言$ L(M) = {\Omega | \Omega 是从M的初态到终态的路径上的弧上标记形成的串 }$

不确定有限自动机（NFA）

NFA和DFA的区别如下

当前状态的后继状态并不唯一
有向弧的标记可以是 $\varepsilon$

3. NFA -> DFA

NFA转化到DFA算法步骤
在这里插入图片描述

4. DFA最小化

采用Hopcroft算法，算法的计算方式如下

在这里插入图片描述

将非终止点和终止点划分为两类，分别取名S，q2。q2无法继续划分，无需考察划分情况。

对于S，我们考察边b。q0-b->q1(S)，q1-b->q3(S)，q3-b->q3(S)，S中的所有节点在b的作用下都指向S集合，因此b无法划分S集合

我们考察边a。q0-a->q1(S)，q1-a->q2(q2)，q3-a->q2(q2)。S中的节点在边a的作用下划分为两类，一类指向S本身(q0)，另一类指向q2（q1, q3），因此S可以继续划分，划分结果如下图

在这里插入图片描述

考察集合q0，已经无法划分

考察集合S1，边b使得q1, q3都指向S1，因此b无法划分S1；边a使得q1, q3都指向q2，因此无法划分。所以S1无法划分。

最终得到如下的最小DFA

在这里插入图片描述

5. 正规式与有限自动机之间的转换

1. 有限自动机转换正规式

在这里插入图片描述

2. 正规式到有限自动机

在这里插入图片描述

6. 语法分析

1. LL（1）分析算法

从左（L）向右读入程序，最左（L）推导，采用一个（1）前看符号。算法基本思想是表驱动的分析算法

第三章

3.4. 树

3.4.3 生成树及最小生成树

1.基础概念

连通图：存在一条路径使得从任意一个节点开始，都能到达连通图其它的所有节点。

极小连通子图：在连通图的基础上，需要保证边数是最少的。这意味着如果移除任意一条边，图将不在连通。

生成树：连通的无向图中的一个子图，需要满足以下特性。1. 连通性：生成树包含原图的所有顶点；2.无环性：不存在回路；3. 最小行：去除任何边都会导致不连通，满足边数量=顶点数 - 1

在这里插入图片描述

2.生成最小树

（1）普里姆（Prim）算法

普里姆算法构造最小生成树的过程是以一个顶点集合 [-{g}作为初态,不断寻找与 U中顶点相邻且代价最小的边的另一个顶点，扩充 U集合直到 UV时为止。

如下是Prim算法生成最小树的过程

在这里插入图片描述

（2）克鲁斯卡尔（Kruskal）算法

克鲁斯卡尔求最小生成树的算法思想为:假设连通网 $N = (V . E)$ ，令最小生成树的初始状态为只有 n个顶点而无边的非连通图$ T=(V,{}) $，图中每个顶点自成一个连通分量。在$ E $中选择代价最小的边，若该边依附的顶点落在$ T$中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依此类推，直到T中所有顶点都在同一连通分量上为止。

在这里插入图片描述

3.4.3 拓扑排序和关键路径

1. AOV网

AOV网是一种图论模型，用于表示一个工程或项目的活动及其执行顺序关系

顶点：每一个顶点表示一个独立的活动或任务

有向边：用于表示活动之间的优先关系或依赖关系。比如A->B。表示B的开始依赖于A的结束

无环性质：AOV网络是有向无环图（DAG）

2.拓扑排序极其算法

拓扑排序就是将AOV网拍布成一个线性序列的过程。此过程保证满足AOV网对所有任务依赖的要求，保证能够按照顺序解决工程问题。

一个可行的算法如下：

(1)在 AOV 网中选择一个**入度为0(没有前驱)**的顶点且输出它

(2)从网中删除该顶点及与该顶点有关的所有弧。

(3)重复上述两步，直到网中不存在入度为0的顶点为止。

以AOV网（a）为例，按照上述计算步骤，得到如下有序序列：6 1 4 3 2 5

在这里插入图片描述

3. AOE网

若在带权有向图G中以顶点表示事件，以有向边表示活动，以边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网(Activity On Edge network，AOE 网)。

通常在 AOE 网中列出了完成预定工程计划所需进行的活动、每项活动的计划完成时间、活动开始或结束的事件以及这些事件和活动间的关系，从而可以分析该项工程是否实际可行并估计工程完成的最短时间，以及影响工程进度的关键活动;进一步可以进行人力、物力的调度和分配，以达到缩短工期的目的。

4. 关键路径和关键活动

关键路径

AOE网中最长的路径称为关键路径，关键路径上的所有活动都是关键活动。

第四章

4.2 进程管理

4.2.1 基本概念

3. 进程的状态及其状态间的切换

三态模型

运行：进程在cpu上运行时，称为运行状态
就绪：一个进程得到了除cpu外的一切资源，只要有cpu即可运行
阻塞：进程在等待这某一个事件的发生，因而将cpu让出。即使这时将cpu分配给进程也不会让他运行。

在这里插入图片描述

五态模型

在这里插入图片描述

有挂起的状态转换

活跃就绪：进程在主存并且处于可调度状态
静止就绪：就绪进程被交换到辅存时的状态，他是不能被直接调度的状态
活跃阻塞：进程在主存，一旦等待的事件产生便进入活跃就绪状态
静止阻塞：阻塞进程交换到辅存，一旦发生事件就进入到静止就绪状态

在这里插入图片描述

软考笔记

第一章

1. 计算机的组成

1. 控制器

2. 主存

3. 运算器

2. 数据表示

2.1 原码

1). 正数

2). 负数

3). 小数

4). 负小数

2.2 反码

2.3 补码

3. 定点数和浮点数

3.1 IEEE 754浮点数

4. 校验码

4.1 奇偶校验

4.2 海明码

4.3 循环冗余校验码 CRC

5. 指令流水

5.1 执行方式

5.2 流水线的性能指标

1.吞吐率

2.加速比

3.效率

5.3 缓存

1. 缓存-内存系统取值时间

2. 缓存-内存系统，数据交换单位

3. 缓存-内存系统，数据映射

4. 缓存-内存系统，替换算法

6. 数据传输控制

1. 程序控制

2. 程序中断

3. 直接存储器存取

7. 计算机系统可靠性（可用性）与可靠性模型

1. 可靠性（可用性）

2. 可靠性模型

3. 计算机性能指标

第二章

1.编译过程概述

2.文法和语言的描述形式

3. 词法分析

1. 正规表达式和正规集

2. 有限自动机

3. NFA -> DFA

4. DFA最小化

5. 正规式与有限自动机之间的转换

1. 有限自动机转换正规式

2. 正规式到有限自动机

6. 语法分析

1. LL（1）分析算法

第三章

3.4. 树

3.4.3 生成树及最小生成树

1.基础概念

2.生成最小树

3.4.3 拓扑排序和关键路径

1. AOV网

2.拓扑排序极其算法

3. AOE网

4. 关键路径和关键活动

第四章

4.2 进程管理

4.2.1 基本概念

3. 进程的状态及其状态间的切换

三态模型

4.2.3 进程间通讯

相关文章：