Ayy3

时间停止吧，你是多么的美丽

发表于 更新于 Disqus：

来自《数据库系统概论（第6版）》第二章

关系代数

假设关系 和 具有相同的目 ，且相应的属性取自同一个域， 是元组变量。

  • 并

关系 和 的并记作 其结果仍是 目关系，由属于 或 的元组组成。

  • 差

关系 和 的差记作 其结果仍是 目关系，由属于 而不属于 的元组组成。

  • 交

关系 和 的交记作 它不是基本运算，因为可以转化：。画个van图就知道怎么回事。

  • （广义）笛卡尔积

加上"广义"的原因是这里笛卡尔积的元素是元组。

两个分别为 目和 目的关系 和关系 的笛卡尔积是一个 列元组的集合： 这玩意就是个排列组合。

  • 选择

在关系 中选择满足给定条件的诸元组（选行）：

  • 投影

关系 上的投影是从 中选择若干属性列组成新的关系（选列）：

  • 连接

从两个关系的笛卡儿积中选取其属性间满足一定条件的元组： 等值连接：从关系 和 中选取广义笛卡儿积中A、B属性值相等的那些元组。

自然连接：特殊的等值连接，要求两个关系中进行比较的分量必须是同名的属性列，且在结果中将重复的属性列去掉。直接用 表示。

  • 除

设关系 除以关系 的结果为关系 ，则 包含所有在 但不在 中的属性及其值，且 的元组与 的元组的所有组合都在 中。 其中 为 在 中的象集。

象集：给定一个关系 。当 时， 在 中的象集为：

可以理解为对于一个给定的取值 ，其对应的在关系 中 的取值的集合。

然后除运算就是指所有满足其在关系 中 的取值的集合能够包含关系 中所有 取值集合所对应的关系 中的 。

一些例题

试用关系代数完成如下查询：

查询李勇同学选修的课程中考试及格的课程名。 李勇 查询既选修了2号课程又选修了3号课程的学生的学号和姓名。 查询只选修了1门课程的学生的学号和姓名。

关系演算

元组关系演算语言ALPHA

  • 检索操作

最难的操作

语句格式：GET 工作空间名【（定额）】 （表达式1）【：操作条件】【DOWN/UP 表达式2】

根本看不懂，这里举几个例子

还是这三张表

（1）简单检索

查询所有被选修的课程的课程号： 查询所有学生的数据： （2）限定的检索（带条件）

查询信息系（IS）中年龄小于20岁的学生的学号和年龄： （3）带排序的检索

查询计算机科学系（CS）学生的学号、年龄，结果按年龄降序排序： （4）带定额的检索

取出一个信息系学生的学号： 查询信息系年龄最大的三个学生的学号及其年龄，结果按年龄降序排序： （5）用元组变量的检索

元组变量：表示可以在某一关系范围内变化

用途：1、简化关系名；2、操作条件中使用量词()时必须用元组变量。

定义元组变量：关系名 变量名

一个关系可以设多个元组变量

（6）用存在量词的检索

查询选修2号课程的学生名字。 查询选修了这样课程的学生学号，其直接先行课是6号课程。 查询至少选修一门其先行课为6号课程的学生名字。 （前束范式形式）

（7）带有多个关系的表达式的检索

查询成绩为90分以上的学生名字与课程名字。 （8）用全称量词的检索

查询不选1号课程的学生名字。

是不是有点抽象，其实一般人应该会这么写：

可以从下式转换为上式（存在量词转化为全称量词）。但是可以理解上式的含义：选定Student表的一行，对于表SC中的每一个条目，要么学号不为Student表所对应的学号，要么等于对应的学号，但是都满足课程号不为1.

（9）用两种量词的检索

查询选修了全部课程的学生姓名。

有点抽象，这里我理一下。

首先，我们固定表Student的一个元组，然后对该元组进行判断：

1、对于表Course的所有项，都存在表SC的一项，满足二者的Cno相同

2、然后对于存在的表SC的这一项，都需要满足它和表Student所固定元组的Sno相同

所有题目的思路都应该是这样的：固定GET W里的变量，然后判断条件是否为真

（10）用蕴含的检索

查询最少选修了201215122学生所选课程的学生学号。

求解思路是这样的：首先固定Student.Sname

然后对Course的每一门课程，看它是否被201215122选，如果选了的话，再判断是否也被Student对应学生选。这是一个蕴含关系。

（11）聚集函数

函数名 功能
COUNT 对元组计数
TOTAL 求总和
MAX 求最大值
MIN 求最小值
AVG 求平均值

查询学生所在系的数目： 查询信息系学生的平均年龄：

一些例题

呃呃呃，还是这三个表：

试用元组关系演算语言ALPHA完成如下查询：

查询李勇同学选修的课程中考试及格的课程名。 李勇 查询既选修了2号课程又选修了3号课程的学生的学号和姓名。 查询所有选修课程均不及格的学生的学号和姓名。

这里要把一门课都没选的学生给排除掉

  • 修改操作

修改操作用UPDATE语句实现，其步骤是：

  1. 用HOLD语句将要修改的元组从数据库读到工作空间中
  2. 用宿主语言修改工作空间中元组的属性值
  3. 用UPDATE语句将修改后的元组送回数据库

把201215121学生从计算机科学系转到信息系。

  • 插入操作

插入操作用PUT语句实现，其步骤是：

  1. 用宿主语言在工作区间中建立新元组
  2. 用PUT语句把该元组插入指定的关系

学校新开设了一门2学分的课程“计算机组织与结构”，其课程号为8，直接先行课为6号课程。插入该课程元组 计算机组织与结构

  • 删除操作

删除操作用DELETE语句实现，其步骤是：

  1. 用HOLD语句把要删除的元组从数据库读到工作空间中
  2. 用DELETE语句删除该元组

201215125学生因故退学，删除该学生元组

补充一些关于关系数据库的小知识点

关系模型中三类完整性约束：

  • 实体完整性
  • 参照完整性
  • 用户定义的完整性

实体完整性：若属性A是基本关系R的主属性，则属性A不能取空值。

一个基本表通常对应现实世界的一个实体集或多对多联系。现实世界的实体和实体间的联系都是可区分的，即它们具有某种唯一的标识，而在关系模型中，这种唯一的标识即主码，它需要保证非空，来确保所对应的实体是完整的，独一无二的。

外码：设F是基本关系R的一个或一组属性，但不是关系R的码。是基本关系S的主码。如果F与基本关系S的主码 对应，则称F是基本关系R的外码。并称基本关系R为参照关系，S为被参照关系。（R与S可能是同一个关系）

参照完整性：若属性F是基本关系R的外码，它与基本关系S的主码 对应，则对于R中的每个元组在F上的取值必须为：

  • 空
  • S中某个元组的主码值

用户定义的完整性：略

下课了喵

发表于 更新于 Disqus：

计网——物理层复习

物理层考虑的是怎样才能在连接各种计算机的媒体上传输数据比特流。它为数据链路层屏蔽了传输媒体的差异。

最ex的一层，我的评价是看了就忘

物理层的主要任务

  • 机械特性：指明接口所用接线器的形状和尺寸、引脚数目和排列、固定和锁定装置
  • 电气特性：指明在接口电缆的各条线上出现的电压的范围
  • 功能特性：指明某条线上出现的某一电平的电压表示何种意义
  • 过程特性：指明对于不同功能的各种可能事件的出现顺序

传输媒体

分为导引型传输媒体和非导引型传输媒体。

导引型：

  • 同轴电缆
  • 双绞线
  • 光纤
  • 电力线

非导引型传输媒体是指自由空间：

  • 无线电波
  • 微波
  • 红外线
  • 可见光，LIFI

传输方式

串行传输：数据是一个比特一个比特发送的，因此在发送端和接收端之间，只需要一条传输线路即可。

并行传输：一次发送n个比特，需要有n条传输线路。然而在计网上一般采用串行传输。

同步传输：

  • 数据块以稳定的比特流的形式传输。字节之间没有间隔。
  • 接收端在每个比特信号的中间时刻进行检测，来判断是比特0还是比特1。
  • 由于不同设备的时钟频率存在一定差异，因此需要使收发双方的时钟同步。

异步传输：

  • 以字节为独立的传输单位，字节之间的时间间隔不是固定的。
  • 接收端仅在每个字节的起始处对字节内的比特实现同步。
  • 通常在每个字节前后分别加上起始位和结束位。

通信方式

在许多情况下，我们要使用"信道"这一名词。信道和电路不等同，它一般用来表示向某一个方向发送信息的媒体。因此，一条传输电路往往包含一条发送信道和一条接收信道。

单向通信（单工通信）

只能有一个方向的通信，而没有反方向的交互。例：无线电广播

双向交替通信（半双工通信）

通信的双方可以发送信息，但是不能双方同时发送（同时接收）信息。

双向同时通信（全双工通信）

通信的双方可以同时发送和接收信息。

编码与调制

重点。

常用术语：

  • 数据——运送消息的实体
  • 信号——数据的电气或电磁的表现
  • 模拟信号——代表消息的参数的取值是连续的（？？？
  • 数字信号——代表消息的参数的取值是离散的
  • 码元——在使用时间域（时域）的波形表示数字信号时，代表不同离散数值的基本波形
  • 基带信号—— 来自信源的信号。像计算机输出的代表各种文字或图像文件的数据信号都属于基带信号。
  • 基带信号往往包含有较多的低频成分，甚至有直流成分，而许多信道并不能传输这种低频分量或直流分量。因此必须对基带信号进行调制 (modulation)。（？？？

不归零编码

所谓不归零编码，就是指在整个码元时间内，电平不会出现零电平

  • 正电平表示比特1/0
  • 负电平表示比特0/1

从上图可以看出，不归零编码存在同步问题，因此计算机网络的数据传输不采用这种编码。

归零编码

每个码元传输结束后信号都要“归零”，其虽然自同步，但编码效率低。

曼切斯特编码

在每个码元的中间时刻，信号都会发生跳变。

  • 负跳变表示比特1/0
  • 正跳变表示比特0/1
  • 码元中间时刻的跳变既表示时钟，又表示数据

传统以太网就是使用曼切斯特编码

差分曼切斯特编码

在每个码元的中间时刻，信号都会发生跳变，但与曼切斯特编码不同

  • 跳变仅表示时钟
  • 码元开始处电平表示是否变换表示数据，变化表示1/0，不变化表示0/1

调制

调幅AM：所调制的信号由两种不同振幅的基本波形构成，每个基本波形只能表示1bit

调频FM：所调制的信号由两种不同频率的基本波形构成，每个基本波形只能表示1bit

调相PM：所调制的信号由两种不同初相位的基本波形构成，每个基本波形只能表示1bit

混合调制

将上述三种调制方法进行结合

由于频率和相位是相关的（？？？喵），即频率是相位随时间的变化率，所以一次只能调制频率和相位两个中的一个。

通常情况下，相位和振幅可以结合起来一起调制，称为正交振幅调制QAM。

设波特率（即码元传输速率，单位时间内数字通信系统所传输的码元数）为B，采用m个相位，每个相位有n种振幅，则该QAM的数据传输速率 \(R=B\log_2(mn)\)。

信道的极限容量

奈氏准则

若用V表示每个码元的离散电平数目，则极限数据率为 \(2W\log_2V\)。

香农定理

这会考我吃

发表于 更新于 Disqus：

计网——网络层复习

网络层的主要任务是实现网络互联，进而实现数据报在各网络之间的传输。

网络层需要解决以下三个问题：

  1. 网络层向运输层提供怎样的服务（“可靠传输”还是“不可靠传输”）
  2. 网络层寻址问题
  3. 路由选择问题

因特网使用TCP/IP协议栈，使用网际协议IP

两种服务

面向连接的虚电路服务

通信之前先建立虚电路，以保证通信双方所需的一切网络资源。虚电路只是一条逻辑上的连接

发送方发送给接收方的所有分组都沿着同一条虚电路传送

无连接的数据报服务

只向上层提供无连接的、尽最大努力交付的数据报服务

发送前无需建立连接。每一个分组（即ip数据报）独立发送

IPv4

IPv4地址是给因特网（Internet）上的每一台主机（或路由器）的每一个接口分配一个在全世界范围内是唯一的32比特的标识符。

IPv4编址方法的三个历史阶段：分类编址->划分子网->无分类编址

IPv4：点分十进制表示方法

1. 分类编址

A类地址，最小网络号为0，但是保留，不指派。

第一个可指派的网络号是1，网络地址是1.0.0.0。

最大网络号127，但是作为本地环回测试地址，不指派。

最后一个可指派的网络号是126，网络地址是126.0.0.0。

可指派的网络数量为126。

每个网络中可分配的IP地址数量为 \(2^{24}-2=16777214\) （除去主机号全0的网络地址和全1的广播地址）

B类地址，最小网络号也是第一个可指派的网络号是128.0，网络地址是128.0.0.0。

最大网络号也是最后一个可指派的网络号是191.255，网络地址是191.255.0.0。

可指派的网络数量为 \(2^{16-2}=16384\)

每个网络中可分配的IP地址数量为 \(2^{16}-2=65534\)。

C类地址，最小网络号也是第一个可指派的网络号是192.0.0，网络地址是192.0.0.0。

最大网络号也是最后一个可指派的网络号是223.255.255，网络地址是223.255.255.0。

可指派的网络数量为 \(2^{24-3}=2097152\)

每个网络中可分配的IP地址数量为 \(2^{8}-2=254\)。

2. 划分子网

将原有的两级IP地址变为三级的IP地址

划分子网纯属是一个单位内部的事情，对外仍然表现为没有划分子网的网络。它的idea是从主机号中借用若干个bit作为子网号（subnet-id）。

子网掩码：连续的1对应网络号和子网号，0对应主机号。即（IP地址）AND（子网掩码）= 网络地址

3. 无分类编址

无分类域间路由选择CIDR：消除了传统的A、B、C类地址以及划分子网的概念，使用各种长度的网络前缀来代替网络号和子网号。

CIDR使用斜线记法，即在IPv4地址后面加上斜线“/”，写上网络前缀所占比特数量。例如 128.14.25.7/20

CIDR实际上是将网络前缀都相同的连续IP地址组成一个“CIDR地址块”。我们只要知道一个CIDR地址块中的任何一个地址，就可以知道该地址块的全部细节：

  • 地址块的最小、最大地址
  • 地址块的地址数量
  • 地址块聚合某类网络（A、B、C类）的数量
  • 地址掩码（也可继续称为子网掩码）

有点抽象，这里偷个例子看看

路由聚合：将路由器中路由表的多个CIDR记录找最大公共前缀（这不是Trie吗，ACMer特有的感知），合并成一个记录

IPv4地址的应用规划

王道p146

给定一个IPv4地址块，将其划分成几个更小的地址块，分配给不同的网络

定长的子网掩码FLSM

就是划分子网的方式，从主机号部分借用 \(n\) 位作为子网号，可以划分出大小相等的 \(2^n\) 个不同的网络。

变长的子网掩码VLSM

就是无分类编址的方式。这里给出一个例子

划分方案不唯一，建议从大的子网（主机号多的）开始划分。

地址解析协议ARP

从IP地址找出其对应的MAC地址

每台主机都设有一个ARP高速缓存，用于存放本局域网上各主机和路由器的IP地址到MAC地址的映射表，即ARP表。

若未查到目的主机的MAC地址，则通过使用目的MAC地址为FF-FF-FF-FF-FF-FF的帧来封装并广播ARP请求分组。目的主机收到ARP请求后，向源主机发送ARP响应（单播MAC帧，包含目的主机的IP地址和MAC地址）。源主机收到ARP相应后，记录到ARP表中。

ARP表中的IP地址与MAC地址的对应关系记录，是会定期自动删除的，因为IP地址与MAC地址的对应关系不是永久性的

IP数据报的发送和转发

忽略ARP过程和交换机自学习流程

获取目的网络地址：将目的地址IP和源地址的子网掩码进行逻辑与运算

  • 如果目的网络地址和源网络地址相同，则属于同一个网络，直接交付
  • 否则属于间接交付，需要将IP数据报传输给主机所在网络的默认网关（路由器）

默认网关：为了让本网络中的主机能和其它网络中的主机进行通信，就必须指定本网络的一个路由器的接口，由该路由器帮忙转发

路由器收到IP数据报后如何转发？

  • 检查IP数据报首部是否出错：
    • 若出错，则直接丢弃该IP数据报并通告源主机
    • 若没有出错，则进行转发
  • 根据IP数据报的目的地址在路由表中查找匹配的条目：
    • 若找到匹配的条目，则转发给条目中指示的下一跳
    • 若找不到，则丢弃该数据报并通告源主机

检查路由条目：将目的地址与路由条目中的地址掩码进行逻辑与运算得到目的网络地址，并和路由条目中的目的网络进行比较，如果相同，则该条目就是匹配的条目。根据该条目的下一跳指示，进行转发。（补充，按前缀长度的顺序进行检查）

路由器是隔离广播域的。

路由算法与路由协议

静态路由配置

由网络管理员手工配置每一条路由。

默认路由0.0.0.0/0，与所有IP匹配，但是优先级也是最低的。

特定主机路由，例如192.168.2.1/32，优先级是最高的。

黑洞路由，匹配后分组就没了

路由选择协议

因特网采用分层次的路由选择协议

  • 自治系统AS：在单一的技术管理下的一组路由器，这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS中的路由，同时还使用一种AS之间的路由选择协议来确定AS之间的路由。

路由信息协议RIP

这个玩意运行在传输层的UDP协议之上。疑问：路由器不是只实现了网络层吗？

RIP要求自治系统AS内的每一个路由器都要维护它自己到AS内其它每一个网络的距离记录。这是一组距离，称为“距离向量D-V”

RIP使用跳数作为距离的度量。

  • 路由器到直连网络的距离定义为1
  • 到非直连网络的距离定义为经过的路由器数加1
  • 允许一条路径最多只能包含15个路由器。“距离”为16时相当于不可达。

RIP认为距离短的路由就是好的路由。当到达同一网络有多条距离相等的路由时，可以进行“等价负载均衡”。

RIP包含以下三个要点：

  • 仅和相邻路由器交换信息
  • 交换信息为自己的路由表
  • 周期性交换信息

RIP工作举例：

  • 相同下一跳，更新
  • 新网络，添加
  • 不同下一跳但是有路由优势（距离短），更新
  • 不同下一跳且距离相同，等价负载均衡，添加
  • 不同下一跳且劣势，不更新

RIP存在“坏消息传播慢”的问题，又称路由环路或距离无穷问题，这是距离向量算法的一个固有问题。假设某网络N1故障，其直连路由器开始传播N1不可达的RIP更新信息，但是发的慢了，会被其余认为N1可达的信息误导，这会导致路由环路，使路由收敛减慢：

开放最短路径优先OSPF

OSPF是基于链路状态的路由算法协议，采用SPF最短路算法计算路由，因此在算法上保证了不会产生路由环路。

链路状态：指本路由器都和哪些路由器相邻，以及相应链路的“代价”

嗯？这不是每个点的邻接表吗（雾

问候分组Hello：OSPF相邻路由器通过交互问候分组，建立和维护邻居关系。

在IP数据报的首部字段的协议号中标注为89，表明数据载荷为OSPF分组

链路状态通告LSA：包含以下内容

  • 直连网络的链路状态信息
  • 邻居路由器的链路状态信息

LSA被封装在链路状态更新分组LSU中，用洪泛法发送

链路状态数据库LSDB：存储各路由器的LSA

通过LSDB构造带权有向图，就可以使用SPF算法计算各自路由器到达其它路由器的最短路径：

OSPF共有以下五种分组类型：

  1. 问候分组，Hello
  2. 数据库描述分组，向邻站给出自己的LSDB中所有链路状态项目的摘要信息
  3. 链路状态请求分组，向对方请求发送某些链路状态项目的详细信息
  4. 链路状态更新分组，LSU，它是OSPF最核心的部分
  5. 链路状态确认分组

为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统AS再划分为若干更小的范围，称为区域。这样做的目的是将LSU的广播仅限于每一个区域内，减少网络上的通信量。

边界网关协议BGP

BGP是不同AS的路由器之间交换路由信息的协议。

不同AS之间必然没有统一的路由评价标准。因此BGP只能是寻求一条能够到达目的网络且比较好的路由，而非找到最佳路由。

BGP运行在传输层的TCP之上

BGP的主要idea是，每个AS的管理员需要在配置BGP的时候选择至少一个路由器，作为该AS的“BGP发言人”（往往就是边界路由器）

一个BGP代言人要和其它AS的代言人交换信息，需要先建立TCP连接，然后在此基础上交换BGP报文以建立BGP会话，来交换路由信息。当BGP各代言人互相交换网络可达性的信息后，就根据各自所用的策略，各自找出到达各AS的较好的路由。

这会形成一个树形结构

BGP-4共使用4种报文：

  1. 打开（Open）报文。用来和相邻的另一个BGP代言人建立关系，使通信初始化
  2. 更新（Update）报文。用来通知某一路由的信息，以及列出要撤销的多条路由
  3. 保活（Keepalive）报文。用来周期性地证实邻站的连通性
  4. 通知（Notification）报文。用来发送检测到的差错。

IPv4数据报格式

直接上图

  • 一个IP数据报由首部和数据两部分组成
  • 首部的前一部分是固定长度，为20字节
  • 首部后面部分是可选字段，其长度可变
  • 首部长度一定是4字节的整数倍，填充部分用于确保这一条件

每一行由32个比特组成，每个小格子称为字段或者域，用来表达IP协议的相关功能：

  • 版本：4比特，表示ip协议的版本
  • 首部长度：4比特，表示ip数据报首部的长度，以4字节为单位
  • 可选字段：1字节到40字节不等，用来支持其它功能
  • 填充字段：确保首部长度为4字节的整数倍，用全0填充
  • 区分服务：利用该字段的数值可提供不同等级的服务质量，不过一般情况不使用该字段
  • 总长度：16比特，以字节为单位
  • 标识：占16比特，属于同一个数据报的各分片数据报应该具有相同的标识
  • 标志：3比特，DF位（1表示不允许分片，0表示允许分片），MF位（1表示后面还有分片，0表示这是最后一个分片），保留位（必须为0）
  • 片偏移：13比特，以8个字节为单位，指出分片数据报的数据载荷部分偏移其原数据报的数据载荷位置多少个单位

这要求分片的数据载荷部分，除了最后一个分片，都要保证其大小为8个字节的整数倍？

  • 生存时间TTL：占8比特，现在以跳数为单位，路由器转发IP数据报时，将IP数据报首部中的该字段的值减1，若不为0则转发，否则丢弃

  • 协议：占8比特，指明IP数据报部分是何种协议数据单元：

协议名称 ICMP IGMP TCP UDP IPv6 OSPF
协议字段值 1 2 6 17 41 89

这里不仅有网络层协议，还有传输层协议捏。咦，传输层和网络层之间是有关联的吗，为什么要把传输层的信息封装在IP首部中？这不是违背了分层的idea了吗？

  • 首部检验和：占16比特，用来检测首部在传输过程中是否存在差错。比CRC简单。IP数据报每经过一个路由器，都要重新计算该字段，因为某些字段（TTL、标志、片偏移等）可能发生变化
  • 源/目的IP地址：各占32比特

网际控制报文协议ICMP

ICMP的作用是让主机或者路由器报告差错和异常情况，提高IP数据报交付的机会。

ICMP报文有两种：ICMP差错报告报文和ICMP询问报文。

ICMP差错报告报文用于目标主机或目标路径上的路由器，向源主机报告差错和异常情况。共5种常用类型：

  1. 终点不可达。当路由器或主机不能交付数据报时，发送该报文
  2. 源点抑制。当路由器或主机由于拥塞，而丢弃数据报时，发送该报文，使源点知道应该把数据报的发送速率降低
  3. 时间超过。当路由器收到TTL为零的数据报时，除丢弃数据报外，还需要向源点发送时间超过报文。另外一种情况是终点在规定时间内不能收到一个数据报的全部数据报片时，就把已有数据报丢弃，也会向源点发送该报文。
  4. 参数问题。当路由器或目标主机收到的数据报的首部中，有的字段值不正确时，丢弃该数据报，发送参数问题报文
  5. 改变路由（重定向）。路由器把该报文发送给主机，让主机知道下次应将数据报发送另外的路由器。

以下情况不应发送ICMP差错报告报文：

  • 对ICMP差错报告报文，不发送ICMP差错报告报文（不然就套娃了不是吗
  • 对第一个分片的数据报片的所有后续数据报片，不发送ICMP差错报告报文（不然就太多了？
  • 对具有多播地址的数据报，不发送
  • 对具有特殊地址（如环回地址127.0.0.0或者0.0.0.0），不发送

ICMP询问报文，常见的有2种：

  1. 回送请求和回答。向特定的目的主机发出询问，目的主机收到该报文后必须给源主机或发送ICMP回送回答报文。一般用于测试目的站是否可达。
  2. 时间戳请求或回答。请求某个主机或路由器当前的日期和时间，通常用于进行时钟同步和测量时间。

ICMP应用：

  1. PING，用来测试主机或路由器间的连通性。应用层直接使用网际层的ICMP回送请求和回答报文，来检测目的主机是否可达。
  2. traceroute，用来测试ip数据报从源主机到达目的主机要经过哪些路由器。原理是发送TTL设定值的ICMP回送请求报文，这样TTL为0时，路由器会返回时间超过的ICMP差错报告报文。

虚拟专用网VPN

由于IP地址紧缺，一个机构能申请到的ip地址数往往远小于本机构所拥有的主机数。VPN的idea是在同一个机构中，分配本机构可自由分配的专用地址。

专用（私有）地址是规定的：

  • 10.0.0.0 - 10.255.255.255（10/8地址块）
  • 172.16.0.0 - 172.31.255.255 （172.16/12地址块）
  • 192.168.0.0 - 192.168.255.255（192.168/16地址块，是不是很熟悉？）

私有地址只能用于同一机构内的通信，不能和因特网上其它主机通信。因此路由器对所有目的地址是专用地址的ip数据报一律不转发。

各部门都至少需要一个路由器具有全球合法的ip地址，这样各自的专用网才能利用公用的因特网进行通信。

有两个首部：内部IP数据报首部，和真正的IP数据报首部。

网络地址转换NAT

NAT的主要思想是将大量使用内部专用地址的用户共享少量的全球合法地址。

假设，使用私有地址的主机要给因特网上使用全球ip地址的另一台主机发送数据报，这时候需要用安装了NAT软件的专用网的路由器进行ip地址转换：

若多台主机同时采用NAT，路由器内部需要维护一个私有地址到全球IP地址的映射关系：

如果NAT路由器具有n个全球ip地址，这样的话只能有n个内网主机能够同时和因特网上的主机通信。

解决方法是使用传输层中TCP和UDP协议的端口号，利用运输层的端口号和IP地址一起转换，这种技术叫做NAPT：

NAPT路由器就是我们常用的家用路由器

如果外网需要主动与内网某主机进行通信，这会有问题（根本就不知道ip地址呀），这需要网络应用自己使用一些特殊的NAT穿越技术来解决问题。

发表于 更新于 Disqus：

前面几章就是文科啦，应该不是重点

第一章 软件工程基础

软件工程的定义：

  1. 应用系统的、规范的、可量化的方法来开发、运行和维护软件，即将工程应用到软件
  2. 对1中各种方法的研究

第二章 软件工程的发展

1950s-2000s软件工程的特点

1950s：科学计算；以机器为中心进行编程；像生产硬件一样生产软件

1960s：业务应用（批量数据处理和事务计算）；软件不同于硬件；用软件工艺的方式生产软件

1970s：结构化方法；瀑布模型；强调规则和纪律

1980s：追求生产力最大化；现代结构化方法/面向对象编程广泛应用；重视过程的作用

1990s：企业为中心的大规模软件系统开发；追求快速开发、可变更性和用户价值；Web应用出现

2000s：大规模Web应用；大量面向大众的Web产品；追求快速开发、可变更性和用户价值和创新

  • 瀑布模型：

将软件生命周期中的各个活动规定为线性连接的模型，包括需求分析、设计、编码、测试、维护等，相邻的步骤之间相互衔接，强调一个阶段结束后对其制品进行验证和检验。优点：容易理解，管理成本低，强调开放的阶段性早期计划和产品测试 缺点：客户必须能够完整、正确和清晰地描述他的需要，开始阶段难以评估项目进度，项目结束后会出现大量集成和测试工作，需求或设计中的错误往往只有到了项目后期才被发现（对风险的控制能力较弱）

  • 演化模型：迭代的过程，适用于软件需求缺乏准确认识的情况

    • 原型模型：

    是预期系统的一个可执行版本，反映的是系统性的一个选定子集，一个原型不必满足目标软件的所有约束。

    原型模型开始于沟通，其目的是定义软件的总体目标，标识需求，然后快速制定原型开发的计划，确定原型的目标和范围，采用快速设计的方式对其进行建模，并构建原型。

    可将原型分为三种：1、探索性原型：目的是弄清目标的需求，确定所希望的特性，并探讨多种方案的可能性；2、实验性原型：目的是验证方案或算法的合理性，是在大规模开发前，用于考察方案是否可靠的方法；3、演化性原型：将原型作为目标系统的一部分，通过多次改进，逐步演化为最终的目标系统。

    • 螺旋模型：将瀑布模型和演化模型相结合。螺旋模型将开发过程分为几个螺旋周期，每个螺旋周期大致和瀑布模型相符合：

    螺旋模型强调风险分析，使得开发人员和用户对每个演化层出现的风险有所了解。

  • 敏捷开发：应对快速变化的需求的一种软件开发方法，更强调程序员团队和专家之间的紧密协作、面对面沟通、频繁地交互新的软件版本、紧凑而自我组织型的团队、能够很好地适应需求变化的代码编写和团队组织方法。适用于团队规模较小的队伍。

第四章 项目管理基础

团队结构

（1）主程序员团队

特点：主程序员负责领导团队，效率较高，最大限度地保证产品不同元素的一致性

局限：主程序员的能力是瓶颈；团队成员无法发挥主动性，积极程度不高

（2）民主团队

特点：每个成员都可以发挥自己的能动性，所有人都可以在自己擅长的领域工作

局限：花费在交流，统一思想上的时间成本太大，效率较低

（3）开放团队

特点：使用黑箱管理方式，团队内部的交流路径是不可见的，所有成员按照自己的方式进行自我管理，最大发挥团队成员的创新能力

局限：项目进展没有可视度

团队的建设措施

  • 建立团队章程
  • 持续成功（项目的整体成功，项目的阶段性成功，也可以是无关的团队活动的成功）
  • 和谐沟通
  • 避免团队杀手

质量保障活动

  • 需求评审
  • 体系结构评审
  • 详细设计评审
  • 代码评审
  • 需求度量
  • 设计度量
  • 代码度量
  • 测试度量
  • 集成测试

题目：结合实验，说明一个项目的质量保障包括哪些活动？

配置管理活动

  • 标识配置项
    • 首先要确定有哪些配置项需要被保存和管理，其次要给配置项确定标识，设置唯一的ID，最后要说明配置项的特征，包括生产者、基线建立时间、使用者等
  • 版本管理
    • 为每一个刚纳入配置管理的配置项赋予一个初始的版本号，并在发生变更的时候更新版本号
  • 变更控制
    • 已经纳入配置管理中的配置项发生变化时，需要根据变更控制过程进行处理
  • 配置审计
    • 目标是确定一个项目满足需求的功能和物理特征的程度，确保软件开发工作按照需求和设计特征进行，验证配置项的完整性、正确性、一致性和可跟踪性
  • 状态报告
    • 标识、收集和维持演化中的配置状态信息，也就是对在动态演化着的配置项信息及其度量取快照
  • 软件发布管理
    • 将软件配置项发布到开发活动之外，例如发布给客户

第五章 软件需求基础

需求

（1）用户为了解决问题或达到某种目标所需要的条件和能力

（2）系统或系统部件为了满足合同、标准、规范或其它正式文档所规定的要求而需要具备的条件或能力

（3）对（1）或（2）中的一个条件或一种能力的一种文档化表述

需求的层次性

  • 业务需求：描述了组织为什么要开发系统（目标）
  • 用户需求：描述了系统能够帮用户做些什么（任务）
  • 系统级需求：描述了开发人员需要实现什么（系统行为）

需求分类

  • 功能需求：和系统主要工作相关的需求，即不考虑物理约束的情况下，用户希望系统所能执行的活动
  • 性能需求：定义了系统必须多快、多好地去完成专门的功能
  • 质量属性：可靠性、可用性、安全性、可维护性、可移植性、易用性
  • 对外接口：系统和环境中其它系统之间需要建立的接口（用户界面、硬件接口、软件接口、网络通信接口等）
  • 约束：进行系统构造时，需要遵守的约定（编程语言、硬件设施）
  • 数据需求（不是标准的需求类别，是功能需求的补充）：通常描述数据库等存储介质

第六章 需求分析方法

怎么画用例图、概念类图

结构化方法

数据流图（DFD）

  • 外部实体：待构建软件系统之外的实体，它们不受系统的控制。它们作为软件系统的数据源或数据目的地。
  • 过程：指施加于数据的动作或者行为，它们使得数据发生变化，必须有输入和输出，且二者应存在差异。
  • 数据流：指数据的运动。DFD的数据流必须要和过程产生关联。
  • 数据存储：软件系统需要在内部保存供以后使用的数据集合。

练习（谢谢blackbird宝宝！）：

面向对象分析方法

主要采用统一建模语言（UML）技术。

用例图（P94）

  • 用例：用例模型中最重要的元素，使用一个水平的椭圆表示。
  • 参与者：一个小人，代表同系统进行交互的角色。

概念类图（P98）

  • 对象：对具体问题域事物的抽象。
    • 标识符：使用对象的引用作为标识符，用以唯一地标识和识别对象。
    • 状态：对对象的特征描述，包括对象的属性和属性的取值。
    • 行为：对象在其状态改变或者接收到外界消息时所采取的行动。
  • 类：对对象分类思想的结果，是共享相同属性和行为的对象的集合，为属于该类的对象提供统一的描述。
  • 链接：对象之间互相合作的关系
  • 关联：类之间的关系
    • UML使用类（对象）之间的直线来表示关联（链接），它可以是单向的和双向的。
    • 聚合：表示部分与整体之间的关系（如商品列表与商品），在“整体”的关联端使用空心菱形来表示。
    • 组合：更强的聚合，部分相对于其整体无法单独存在，整体对该部分有完全的管理职责。
  • 继承：用三角形箭头的实线表示，子类->父类。

建立概念类图：

  • 对每个用例文本描述，建立局部的概念类图
    • 识别候选类
    • 确定概念类
    • 识别关联
    • 识别重要属性
  • 合并局部概念类图，建立软件系统的整体概念类图
  • 识别关联
  • 识别重要属性

练习：P100-104 //不是哥们，这玩意太难了

有空的话可以画一画课后习题

题目：给一段材料，要求建立用例模型，画出各种图

第七章 需求文档化与验证

为什么要进行需求规格说明

需求规格说明文档是项目交流的最重要内容，众多开发人员都需要以其为基础进行工作。如果软件需求规格说明文档存在错误，那么会给后续开发工作带来很多问题，再修复的代价就会很高。

对给定的需求示例，判定并修正其错误

  • 使用用户术语
    • 对用户易读，不要使用计算机术语
  • 可验性
    • 描述模糊或过于抽象的需求都是不可验证的（如：用户查询的界面应该友好，不可验证；用户完成查询时鼠标点击不超过五次，可验证）
  • 可行性
    • 系统必须每周7天，每天24小时可用（显然不可行）

对给定的需求示例，设计功能测试用例

看书

写输入，写出预期输出，中间再做一些说明

第八章 软件设计基础

软件设计

是关于整个软件对象的设计。软件设计既指软件对象实现的规格说明，也指产生这个规格说明的过程。

软件设计的核心思想

抽象和分解

抽象是在纵向上聚焦各子系统的接口。这里的接口和实现相对，是各子系统之间交流的契约，是整个系统的关键所在。抽象可以分离接口和实现，让人更好地关注系统本身，从而降低复杂度

分解是在横向上将系统分割为几个相对简单的子系统以及各子系统之间的关系。分解之后每次只需要关注经过抽象的相对简单的子系统及其相互间的关系，从而降低复杂度

软件设计的分层

高层：基于反映软件高层抽象的构建层次，描述系统的高层结构、关注点和设计决策

中层：更加关注组成构建的模块的划分、导入/导出、过程之间的调用关系或者类之间的协作

低层：深入模块和类的内部，关注具体的数据结构、算法、类型、语句和控制结构等

第九章 软件体系结构基础

体系结构的概念

软件体系结构 = {部件、连接件、配置}

  • 部件是软件体系结构的基本组成单位之一，承载系统的主要功能，包括处理与数据
  • 连接件是软件体系结构的另一个基本组成单位，定义了部件的交互，是连接的抽象表示
  • 配置是对形式的发展，定义了部件以及连接件之间的关联方式，将它们组织成系统的总体结构

体系风格的优缺点

主程序/子程序：

  • 优点：
    • 流程清晰，易于理解（符合分解和分治的思想）
    • 强控制性（很容易保证正确性）
  • 缺点：
    • 程序调用是一种强耦合的连接方式，非常依赖交互方的接口规格，这会使系统难以修改和复用
    • 程序调用的连接方式限制了各部件之间的数据交互，可能会使不同部件使用隐含的共享数据交流，产生不必要的公共耦合，进而破坏它的“正确性”控制能力

面向对象式：

  • 优点：
    • 内部实现的可修改性（隐藏内部实现）
    • 易开发、易理解、易复用的结构组织（契合模块化思想）
  • 缺点：
    • 接口的耦合性（由于方法调用机制，接口的耦合性无法消除）
    • 标识的耦合性（一个对象要和其它对象交互，必须知道标识）
    • 副作用（难以实现程序的“正确性”）

分层：

  • 优点：
    • 设计机制清晰，易于理解（抽象层次分离，隔离复杂度）
    • 支持并行开发（层次之间遵守成熟稳定的接口）
    • 更好的可复用性和可修改性（接口的稳定性，不同层次的部件能够相互替换）
  • 缺点：
    • 交互协议难以修改（可能需要改变所有的层次，接口具有强耦合性）
    • 性能损失（禁止跨层调用）
    • 难以确定层次数量和粒度

MVC：

  • 优点：
    • 易开发性（分别抽象了业务逻辑，表现和控制机制清晰，易于开发）
    • 视图和控制的可修改性（一个模型可以同时建立并支持多个视图）
    • 适宜于网络系统开发的特征
  • 缺点：
    • 复杂性（不利于理解任务实现）
    • 模型修改困难（视图和控制均依赖于模型）

第十章 软件体系结构设计与构建

体系结构的设计过程

（1）分析关键需求和项目约束

（2）选择体系结构风格

（3）进行软件体系结构逻辑（抽象）设计

（4）依赖逻辑设计进行软件体系结构物理（实现）设计

（5）完善软件体系结构设计

（6）定义构件接口

（7）迭代过程（3）到（6）

包设计原则

  • 共同封闭原则（CCP）：一起改的类应该在一起
  • 共同重用原则（CRP）：一起重用的包应该放在一起
  • 重用发布等价原则（REP）：重用的单元就是发布的单元
  • 无环依赖原则（ADP）：包的依赖结构是一个有向无环
  • 稳定依赖原则（SDP）：依赖关系应该随着稳定的方向
  • 稳定抽象原则（SAP）：稳定包应该是抽象包，不稳定包是具体包

体系结构构件之间接口的定义

书P174

能够根据用例写出某层的接口，需求分配的过程

体系结构开发集成测试用例

书P177

桩：在软件测试里用来替换某些模块的，模仿下层模块，测试上层

驱动：模仿上层模块，测试下层

第十一章 人机交互设计

可用性

书上叫易用性（usability）

可用性分为五个维度：

  • 易学性：新手用户容易学习，能够很快使用系统
  • 易记性：以前使用该软件的用户，能够有效记忆或者快速重新学会使用
  • 效率：熟练用户能够高效地完成任务
  • 出错率：用户使用系统时，会犯多少错，错误有多严重，以及能够从错误中很容易地恢复
  • 主观满意度：让用户有良好的体验

人机交互设计原则

  • 简洁设计：图片比描述文字更清晰
  • 一致性设计：相似的任务，一致的交互机制
  • 低出错率：帮助用户避免犯错
  • 易记性设计：历史记录

题目：给你几张图，分析体现或违反了哪些人机交互原则，详细解释

精神模型、差异性

书P185-186

精神模型：用户在进行人机交互时头脑中的人物模型

差异性：不同的用户群体，差异化的交互机制

导航、反馈、协作式设计

导航：目的是为用户提供一个很好的完成任务的入口

反馈：让用户意识到行为的结果（声音、效果）

协作式设计：调整计算机因素以便更好地适应并帮助用户的设计方式

第十二章 详细设计的基础

详细设计的出发点

以需求开发的结果（需求规格说明和需求分析模型）和软件体系结构的结果（软件体系结构设计方案与原型）为出发点

书P197、建造桥梁

协作

抽象对象之间的协作

  • 从小到大，将对象的小职责聚合成大职责
  • 从大到小，将大职责分配给小对象

上面两种方法一般同时运用，共同来完成对协作的抽象。

控制风格

选择合适的控制风格：

  • 为了完成某一个大的职责，需要对职责的分配做很多决策，控制风格决定了决策由谁来做和怎么做
  • 逻辑层的接口依据需求来创建
  • 分散式
  • 集中式
  • 委托式（授权式）

建立设计类图

P203，注意表12-2

建立详细顺序图

P206，表12-3

题目：给出用例描述，用集中控制的方式画出设计类图和顺序图

协作的测试

Mock Project：类间协作的桩程序

第十三章 详细设计中的模块化与信息隐藏

重点

结构化设计中的耦合

耦合：描述两个模块间关系的复杂程度

分类（耦合性从高到底）：

  • 内容管理：一个模块直接修改或者依赖于另一个模块的内容（goto）
  • 公共耦合：模块间共享全局的数据（全局变量）
  • 重复耦合：模块间有同样逻辑的代码
  • 控制耦合：一个模块给另一个模块传递控制信息
  • 印记耦合：共享了一个数据结构，但是却只用了其中一部分（传了整个记录，只需要一个字段）
  • 数据耦合：两个模块的所有参数是同类型的数据项（传一个整数给一个计算平方根的函数）

前三个耦合是不可接受的。

结构化设计中的内聚

内聚：一个模块内部的联系的紧密性

分类（从低到高）：

  • 偶然内聚：模块执行多个完全不相关的操作
    • 修车、烤面包、遛狗、看电影
  • 逻辑内聚：模块执行一系列相关操作，每个操作的调用由其它模块决定
    • 开车去上撤硕，坐火车上厕所
  • 时间内聚：模块执行一系列有关时间的操作
    • 起床刷牙洗脸吃南航
  • 过程内聚：模块执行一系列与步骤顺序有关的操作
    • 返校：院系经办人审核、院系领导审核、校职能部审核
  • 通信内聚：模块执行一系列与步骤顺序有关的操作，并且这些操作在相同的数据上进行
    • 查书的名字、查书的作者、查书的出版商
  • 功能内聚：模块只执行一个操作或达到单一目的
    • 只计算平方根
  • 信息内聚：模块进行许多操作，各有各的入口点，每个操作的代码相对独立，所有操作都是在相同的数据结构上完成
    • 栈（push pop等）

信息隐藏的基本思想

每个模块都隐藏着一个重要的设计决策，每个模块都承担一定的职责。对外表现为一份契约，并且在这份契约之下隐藏着只有这个模块知道的设计决策或者秘密，决策实现的细节（特别是容易改变的细节）只有模块自己知道。

两种常见的信息隐藏决策

  • 根据需求分配的职责
  • 内部实现机制

第十四章 详细设计中面向对象方法下的模块化

模块化设计原则

  1. 不要用全局变量
  2. 显式（explicit），显示的清楚一点，内容明确（代码写清楚点？？？）
  3. 不要有代码重复
  4. 针对接口编程
  5. 迪米特法则
  6. 接口分离原则（ISP）
  7. 里氏替换原则
  8. 使用组合代替继承
  9. 单一职责原则（SRP）

题目：给个例子，找出其违反的原则并进行修正。

访问耦合

类A拥有对类B的引用，则A可以访问B，存在耦合

分类（从高到低）：

  • 隐式访问：B既没有在A的规格中出现，也没有在实现中出现（连续的方法调用，方法套娃）
  • 实现中访问：B的引用是A方法中的局部变量
  • 成员变量访问：B的引用是A的成员变量
  • 参数变量访问：B的引用是A的方法的参数变量
  • 无访问：理论最优，无关联耦合，维护时不需要对方任何信息

降低访问耦合的方法：

  • 针对接口编程
  • 接口最小化/接口分离原则
  • 访问耦合的合理范围/迪米特法则

继承耦合

继承里，父类和子类之间存在耦合

类型（从高到低）

  • 修改
    • 规格：子类修改继承回来的方法的接口
    • 实现：子类修改继承回来的方法的实现
  • 精化：
    • 规格：子类根据定义好的规则来修改父类的方法，且至少有一个方法的接口被改动
    • 实现：子类根据定义好的规则来修改父类的方法，但是只改动了方法的实现
  • 扩展：子类只增加新的方法和成员变量，不对从父类继承回来的成员做任何修改
  • 无：两个类之间没有继承关系

降低继承耦合的方法：

  • 里氏替换原则
  • 使用组合代替继承

内聚

分类

  • 方法内聚：和结构化中的函数内聚一致，体现方法实现时语句之间的内聚性
  • 类的内聚：衡量类的成员变量和方法之间的内聚
  • 继承内聚：继承树中类之间的内聚

提高内聚的方法：

  • 集中信息与行为
  • 单一职责原则

第十五章 详细设计中面向对象方法下的信息隐藏

信息隐藏的含义

  • 封装类的职责，隐藏职责的实现
  • 预计将会发生的变更，抽象它的接口，隐藏内部实现机制

封装

分离接口和实现

含义：

  • 将数据和行为同时包含在类中
  • 分离对外接口与内部实现

实现细节：

  • 封装数据与行为
  • 封装内部结构
  • 封装其它对象的引用
  • 封装类型信息
  • 封装潜在变更

开闭原则（OCP）

是面向对象设计的一个指导性、方阵性原则

具体内容：

  • 好的设计应该对扩展开放
  • 好的设计应该对修改关闭

简单来说，发生变更时，好的设计只需要添加新的代码，而不需要修改原有的代码

依赖倒置原则（DIP）

内容：

  • 抽象不应该依赖于细节，细节应该依赖于抽象。因为抽象是稳定的，细节是不稳定的。
  • 高层模块不应该依赖于低层模块，而是双方都依赖于抽象。因为抽象是稳定的，而高层模块和低层模块都可能是不稳定的。

题目：给张类图，问运用了或违反了哪条面向对象设计原则？问某个类是什么内聚？

第十六章 详细设计的设计模式

如何实现可修改性、可扩展性、灵活性

实现接口和实现分离

  • 通过接口和实现该接口的类完成分离
  • 通过子类继承父类，将父类的接口与子类的实现分离

代码

策略模式

减少耦合、依赖倒置

抽象工厂模式

职责抽象、接口和重用

单例模式

职责抽象

迭代器模式

减少耦合、依赖倒置

题目：给定场景，应用设计模式并写出代码；给出代码，要求用设计模式改写

第十七章 软件构造

构造包含的活动

详细设计、编程、测试、调试、代码评审、集成与构建、构造与管理

名词解释

重构、测试驱动开发、结对编程

第十八章 代码设计

给定代码段示例，对其进行改进或者发现其中的问题

  • 简洁性/可维护性
  • 使用数据结构消减复杂判定
  • 控制结构
  • 变量的使用
  • 语句处理
  • 如何写不可维护的代码
  • 防御和错误处理

单元测试用例的设计

  • 基于规格的测试技术开发测试用例，等价类划分和边界值分析
  • 基于代码的测试技术开发测试用例，关键复杂代码：路径覆盖；复杂代码：分支覆盖；简单代码：语句覆盖

表驱动编程

if-else —> 一张表

契约式设计

断言式设计

基本思想：如果一个函数和方法，在前置条件满足的情况下开始执行，完成后能够满足后置条件，那么这个函数或方法就是正确、可靠的

常见方式：异常和断言（assert）

检查很多外来信息的有效性：

  • 输入参数，是否合法
  • 用户输入，是否有效
  • 外部文件，是否存在
  • ...

防御式编程

基本思想：在一个地方与其它方法、操作系统、硬件等外界环境交互时，不能确保外界都是正确的，所以要在外界发生错误时，保护内部方法不受损害

第十九章 软件测试

单元测试、集成测试、系统测试

黑盒测试

基于规格的技术，把测试对象看作一个黑盒子，完全基于输入和输出来判定测试对象的正确性。测试使用测试对象的规格说明来设计输入和输出数据

常见方法：

  • 等价类划分（把输入按照等价类划分，包括有效和无效）
  • 边界值分析
  • 决策表（表驱动）
  • 状态转换

白盒测试

基于代码的技术，将测试对象看成透明的，不关心测试对象的规格，而是按照测试对象内部的程序结构来设计测试用例进行测试工作

方法：

  • 语句覆盖：确保被测试对象的每一行程序代码都至少执行一次
  • 条件覆盖：确保程序中每个判断的每个结果都至少满足一次
  • 路径覆盖：确保程序中每条独立的执行路径都至少执行一次

题目：

白盒测试和黑盒测试的常见方法，并比较优缺点

能解释并区别白盒测试的三种不同的方法

给出一个场景，判断应该使用哪种测试方法，如何去写

  • 给出功能需求——写功能测试用例
  • 给出设计图——写集成测试用例、Stub和Driver
  • 给出方法描述——写单元测试用例、Mock Project
  • JUnit的使用

第二十章 软件交付

用户文档和系统文档

第二十一章 软件维护与演化

如何理解软件维护的重要性

修改代价

开发可维护软件的方法

  • 考虑软件的可变更性
    • 分析需求的易变性
    • 为变更进行设计
  • 为降低维护困难而开发
    • 编写详细的技术文档并保持及时更新
    • 保证代码的可读性
    • 维护需求跟踪链
    • 维护回归测试基线

软件演化生命周期模型

初步开发、演化、服务、逐步淘汰、停止

逆向工程、再工程

第二十二章 软件开发过程模型

软件生命周期模型

  1. 需求工程
  2. 软件设计
  3. 软件实现
  4. 软件测试
  5. 软件交付
  6. 软件维护

对给定场景，判断适用的开发过程模型（要求、特征描述、优缺点）

补充？

瀑布模型

对于软件开发活动有明确阶段划分，每个阶段的结果都必须验证，使得该模型是“文档驱动”

优点：对于软件开发活动有明确的阶段划分，有利于开发者以关注点分离的方式更好地进行复杂软件项目的开发

缺点：

  • 对文档期望过高
  • 对开发活动的线性顺序假设具有局限性
  • 客户、用户参与度具有局限性
  • 里程碑力度过粗（软件复杂使得每个阶段时间长，无法尽早发现缺陷）

适用性：

  • 需求非常成熟、稳定，没有不确定的内容，也不会发生变化
  • 所需的技术成熟，可靠，没有不确定的技术难点，也没有开发人员不熟悉的技术问题
  • 复杂度适中，不至于产生太大的文档负担和过粗的里程碑

螺旋模型

风险驱动

风险：指因为不确定性（对未来知识了解有限）而可能给项目带来损失的情况

基本思想：尽早解决比较高的风险，如果有些问题实在无法解决，那么早发现比项目结束时再发现要更好，至少损失会小很多

优点：降低风险，减少因风险而造成的损失

缺点：

  • 使用原型方法，为自身带来风险
  • 模型过于复杂，不利于管理者依据其组织软件开发活动

适用性：高风险的大规模软件系统开发

发表于 Disqus：

kmp

kmp算法的核心是它可以求出一个字符串的部分匹配表数组（PMT）

代表 的最长公共前缀后缀的长度

例如字符串ababab，它的最长公共前缀后缀是abab，因此

kmp一个最常用的场景是字符串匹配，我们来看看PMT是怎么加速匹配的。

当匹配到模式串的第i位时，发现不匹配了，这时候我们可以令 i = PMT[i-1]继续匹配。可以证明这样跳是最优的，且不会遗漏情况。

为了方便编程，一般将PMT表向右移动一位，得到nxt数组。这样以后失配了就可以直接令i = nxt[i]就行了。

特别地，令nxt[0]=-1，这是为了编程方便：

1
2
3
4
5
6
7
8
9
void kmp(string &s, string &t){
	int i = 0, j = 0;
	while(i < s.length()){
		if(j == -1 || s[i] == t[j]){
			++i; ++j;
			if(j == t.length()) printf("%d\n", i-j+1);
		}else j = nxt[j];
	}
}

j=-1的时候，++j就为0，代表最长前缀后缀为0

然后对于求nxt数组，可以认为是自己和自己作匹配。

只不过得从第一位开始匹配：

1
2
3
4
5
6
7
8
9
10
void getNext(string &str){
	nxt[0] = -1;
	int i = 0, j = -1;
	while(i < str.length()){
		if(j == -1 || str[i] == str[j]){
			++i; ++j;
			nxt[i] = j;
		}else j = nxt[j];
	}
}

例题：https://www.luogu.com.cn/problem/P3375

0%