软件设计师知识点
2021-09-26 10:13:45 2 举报AI智能生成
软件设计师知识点，软考的时候做的笔记，之后应该还有网络工程师和数据库设计师也要考，自己整理的笔记，已经考过了
作者其他创作
大纲/内容
https://blog.csdn.net/weixin_43488671/article/details/103433440
模块结构图
记录
任意一种编码都由许多码字构成，任意两个码距之间最少变化的二进制数就成为数据校验码的码距：如现有编码A，仅有三个码字0001、0010、1100，则其码距为2
码距
奇校验有奇数个1，偶校验有偶数个1，不足在末尾补1，否则补0，传输后发现数据有偶数个1（对于奇校验），则判断为发生错误，只能检查一位的错误
奇偶校验
让需要校验的数据除以某个二进制数，在尾部补上余数，传输之后，在除以除数，若能除断，则没有错，否则有误（还要一种情况是传输的时候错了，但是依旧可以除断，概率较小），能校验，但不能纠错
循环校验码CRC
设r为校验位的个数，m为数据位个数，则有(2^r)-1>=m+r;可用此求其校验位个数r
即可纠错，也可校验
海明码校验
校验码
只要有一个系统失效，就全都失效
串联系统
计算：可靠性R=1-(1-R1)*(1-R2)...(1-Rn)
有一个生效，就都生效
并联系统
串联并联都有
N模混合系统
串联系统与并联系统（有点像是计算电阻）
一条总线同一时刻仅允许一个设备发送，但允许多个设备接收
并行，多位同时传输，串行：只有一根线（一位），只能一位一位的传输
并行总线与串行总线
单总线的优点是控制简单方便、扩充方便，在一根总线上适应多种设备，但是数据传输的效率和速度受到限制
宽度根字长一样
在CPU与RAM之间来回传送需要处理或是需要存储的数据
数据总线（Data Bus）
则宽度也为32（实际上就是在32根线上传输0或1（无电信号，有电信号））
理论上能寻址2^32
如果字长位32
用来指定在RAM之中存储的数据的地址
地址总线（Address Bus）
将微处理器控制单元（Control Unit）的信号，传送到周边设备，一般常见的为USB Bus和1394 Bus
控制总线（Control Bus）
总线分类
同一时间中cpu处理二进制数的位数
字长
总线
时钟周期也称为振荡周期，定义为时钟频率的倒数。时钟周期是计算机中最基本的、最小的时间单位。在一个时钟周期内，CPU仅完成一个最基本的动作。时钟周期是一个时间的量。时钟周期表示了SDRAM所能运行的最高频率。更小的时钟周期就意味着更高的工作频率。
一个最基本的操作需要多少秒
时钟周期
1秒2.8*1024*1024*1024次最基本操作
2.8GHz
一秒能做多少次最基本的操作
主频
这里的执行指令，包括取指，分析，执行等一系列操作
CPI(Clock cycle Per Instruction)表示每条计算机指令执行所需的时钟周期
CPI
每秒执行几百万条指令数
等于主频除以CPI
MIPS(Million Instructions Per Second)：单字长定点指令平均执行速度 Million Instructions Per Second的缩写，每秒处理的百万级的机器语言指令数，也成运算速度
MIPS
cpu
存储单元
存储体的存储单元是字存储单元，即最小寻址单位是一个字（位，bit）
按字编址
存储体的存储单元是字节存储单元，即最小寻址单位是一个字节（byte）（1byte=8bit）
按字节编址
1.根据存储器所要求的的容量和选定的存储芯片的容量，就可以计算出所需芯片的总是，即 总片数=总容量/每片的容量2.若内存地址区间为4000H~43FFH（H表示HEX，十六进制），每个存储单元可存储16位二级制数，该内存区域用4片存储器芯片构成，则构成该内存所用的存储器芯片的容量是多少？总地址数=43FF-4000+1=2^10(10进制)；总容量=总地址数*16bit=2^10*16bit/4=512B(byte)
计算
编址与计算
主存
h代表对Cache的访问命中率，t1表示Cache的周期时间，t2表示主存储器的周期时间，以读操作为例，使用“Cache+主存储器”的系统平均周期为t3，则t3=h*t1+（1-h）*t2，其中（1-h）又称为失效率（未命中率）
在计算机的存储系统体系中，Cache是访问速度最快的层次（若有寄存器，则寄存器最快）使用Cache改善系统性能的依据是程序的局部性原理（时间局部性：最近访问过的地址区域不会回收，因为它再次被访问的概率要高；空间局部性：被访问的地址区域附近都会被加载，也是因为被访问的概率高。可以防抖动，即加载耗时太长的话会有停顿）
概念
计算机系统结构中，将主存与Cache的映像分成三种方式，直接映像，全相联映像，组相联映像。所谓映像就是将内存地址与Cache地址间的相互转换，我们知道Cache的容量相对于主存来说很小，为了能将两者有效的对应该起来，便产生了上面提到的映像方式。详细见《计算机组成与原理》 王爱英 p243
硬件电路较简单，但冲突率很高
直接相联映像
电路难于设计和实现，时尚用语小容量的Cache，冲突率较低
全相联映像
直接相联与全相联的折中
组相联映像
映像
Cache
寄存器，速度快，容量小，成本高
按内容存取
分两类：随机存储器（RAM）random access memory，只读存储器（ROM）Read Only Memory
内存（主存）
硬盘、光盘、U盘等
外存（辅存）
层次化存储结构
流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术，它把重复的顺序处理过程分解为若干子过程，每个子过程能在专用的独立模块上有效的地并发工作
流水线周期为执行时间最长的一段记为T
流水线计算公式
流水线计算
如两条的时候：执行10条指令，取指的时候可以二条并行，分析的时候也是，执行的时候也是，所以跟单条流水线相比，相当于执行5条指令的时间
多条流水线
超标量流水线
TP=指令条数/流水线执行时间
是指在单位时间内流水线所完成的任务数量或输出结果的数量
n指执行n条流水线
即n趋向无穷，或者流水线每段执行时间一样
TP（max）= 1/T
流水线最大吞吐率
流水线吞吐率（Though Put rate，TP）计算
使用顺序处理方式处理一批任务所用的时间与按流水处理方式处理同一 批任务所用的时间之比
加速比
即流水线设备的利用率，指流水线中的设备实际使用时间与整个运行时间的比值
效率
流水线
CISC(复杂)
https://blog.csdn.net/hovan/article/details/43761859
RISC(精简)
CISC(Complex Instruction Set Computers，复杂指令集计算集)和RISC(Reduced Instruction Set Computers)是两大类主流的CPU指令集类型，其中CISC以Intel，AMD的X86 CPU为代表，而RISC以ARM，IBM Power为代表。RISC的设计初衷针对CISC CPU复杂的弊端，选择一些可以在单个CPU周期完成的指令，以降低CPU的复杂度，将复杂性交给编译器。举一个例子，CISC提供的乘法指令，调用时可完成内存a和内存b中的两个数相乘，结果存入内存a，需要多个CPU周期才可以完成；而RISC不提供“一站式”的乘法指令，需调用四条单CPU周期指令完成两数相乘：内存a加载到寄存器，内存b加载到寄存器，两个寄存器中数相乘，寄存器结果存入内存a。按照此思路，早期的设计出的RISC指令集，指令数是比CISC少些，单后来，很多RISC的指令集中指令数反超了CISC，因此，引用指令的复杂度而非数量来区分两种指令集。 当然，CISC也是要通过操作内存、寄存器、运算器来完成复杂指令的。它在实现时，是将复杂指令转换成了一个微程序，微程序在制造CPU时就已存储于微服务存储器。一个微程序包含若干条微指令（也称微码），执行复杂指令时，实际上是在执行一个微程序。这也带来两种指令集的一个差别，微程序的执行是不可被打断的，而RISC指令之间可以被打断，所以理论上RISC可更快响应中断。 在此，总结一下CISC和RISC的主要区别：CISC的指令能力强，单多数指令使用率低却增加了CPU的复杂度，指令是可变长格式；RISC的指令大部分为单周期指令，指令长度固定，操作寄存器，只有Load/Store操作内存CISC支持多种寻址方式；RISC支持方式少CISC通过微程序控制技术实现；RISC增加了通用寄存器，硬布线逻辑控制为主，是和采用流水线CISC的研制周期长RISC优化编译，有效支持高级语言
指令系统类型
立即寻址
指令中存放的是操作数的地址
直接寻址
间接寻址
寄存器存放操作数
寄存器寻址
寄存器内存放的是操作数的地址
寄存器间接寻址
寻址方式
操作码|地址码
基本格式
a=b+c
op|A1|A2|A3
三地址指令
a+=b
op|A1|A2
二地址指令
如a++
op|A1
一地址指令
操作码指出了计算机要执行什么性质的操作
指令的基本概念
数据的算术运算和逻辑运算
算术逻辑单元ALU
通用寄存器，为ALU提供一个工作区，用在暂存数据
累加寄存器AC
读写内存时，暂存指令或者数据
数据缓冲寄存器DR
存状态标志与控制标志
状态条件寄存器PSW
运算器
主存储器（内存）
辅助存储器（硬盘）
是一种不根据地址而是根据存储内容来进行存取的存储器，可以实现快速地查找块表。既可以按照地址寻址也可以按照内容寻址（通常是某些字段），为了与传统寄存器作区别，称为按内容寻址的存储器
相联存储器
在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。
虚拟存储器
动态随机存取存储器，最为常见的系统内存，即DRAM（Dynamic Random Access Memory）。DRAM 只能将数据保持很短的时间。为了保持数据，DRAM使用电容存储，所以必须隔一段时间刷新（refresh）一次，如果存储单元没有被刷新，存储的信息就会丢失。 关机就会丢失数据。
动态随机存储器(dynamic random access memory)
所谓的“静态”，是指这种存储器只要保持通电，里面储存的数据就可以恒常保持。相对之下，动态随机存取存储器（DRAM）里面所储存的数据就需要周期性地更新。然而，当电力供应停止时，SRAM储存的数据还是会消失（被称为volatile memory），这与在断电后还能储存资料的ROM或闪存是不同的。
静态随机存取存储器（Static Random-Access Memory，SRAM）
EEPROM，或写作E2PROM，全称电可擦除可编程只读存储器
Flash Memory 的主要特性与传统的硬盘存储器相比，Flash Memory 具有质量轻、能耗低、体积小、抗震能力强等的优点，但也有不少局限性，主要如下：需要先擦除再写入Flash Memory 写入数据时有一定的限制。它只能将当前为 1 的比特改写为 0，而无法将已经为 0 的比特改写为 1，只有在擦除的操作中，才能把整块的比特改写为 1。块擦除次数有限Flash Memory 的每个数据块都有擦除次数的限制（十万到百万次不等），擦写超过一定次数后，该数据块将无法可靠存储数据，成为坏块。为了最大化的延长 Flash Memory 的寿命，在软件上需要做擦写均衡（Wear Leveling），通过分散写入、动态映射等手段均衡使用各个数据块。同时，软件还需要进行坏块管理（Bad Block Management，BBM），标识坏块，不让坏块参与数据存储。（注：除了擦写导致的坏块外，Flash Memory 在生产过程也会产生坏块，即固有坏块。）读写干扰由于硬件实现上的物理特性，Flash Memory 在进行读写操作时，有可能会导致邻近的其他比特发生位翻转，导致数据异常。这种异常可以通过重新擦除来恢复。Flash Memory 应用中通常会使用 ECC 等算法进行错误检测和数据修正。电荷泄漏存储在 Flash Memory 存储单元的电荷，如果长期没有使用，会发生电荷泄漏，导致数据错误。不过这个时间比较长，一般十年左右。此种异常是非永久性的，重新擦除可以恢复。
闪存（flash memory）
存储器
输入设备
输出设备
为了保证程序(在操作系统中理解为进程)能够连续地执行下去，CPU必须具有某些手段来确定下一条指令的地址。而程序计数器正是起到这种作用，所以通常又称为指令计数器。在程序开始执行前，必须将它的起始地址，即程序的一条指令所在的内存单元地址送入PC，因此程序计数器（PC）的内容即是从内存提取的第一条指令的地址。当执行指令时，CPU将自动修改PC的内容，即每执行一条指令PC增加一个量，这个量等于指令所含的字节数，以便使其保持的总是将要执行的下一条指令的地址。由于大多数指令都是按顺序来执行的，所以修改的过程通常只是简单的对PC加1
程序计数器PC
用来保存当前正在执行的一条指令。当执行一条指令时，先把它从内存取到数据寄存器（DR）中，然后再传送至IR。指令划分为操作码和地址码字段，由二进制数字组成。为了执行任何给定的指令，必须对操作码进行测试，以便识别所要求的操作。指令译码器就是做这项工作的。指令寄存器中操作码字段的输出就是指令译码器的输入。操作码一经译码后，即可向操作控制器发出具体操作的特定信号
指令寄存器IR
用来保存当前CPU所访问的内存单元的地址。由于在内存和CPU之间存在着操作速度上的差别，所以必须使用地址寄存器来保持地址信息，直到内存的读/写操作完成为止
地址寄存器
对指令中的操作码字段进行分析解释
指令译码器
提供时序控制信号
时序部件
控制器（与运算器共同组成cpu）
计算机结构
单指令流单数据流(SISD)
单指令流多数据流(SIMD)
多指令流单数据流(MISD)
多指令流多数据流(MIMD)
备注(单-single;指令-instruction;流-stream;数据-data;Multi-多)
flynn分类法-2
运算器与控制器-5
R进制转十进制按权展开法
十进制转R进制短除法
二进制转八进制与十六进制
原码
反码
补码
移码
码制
数值的表示范围
N=尾数*基数^指数
浮点数的表示
对阶>尾数计算>格式化
运算
特点
子主题
工业标准IEEE754
共32位，符号位1位，阶码8位，尾数23位
单精度
共64位，符号位1位，阶码11位，尾数52位
多精度
单精度与多精度
浮点的运算
数据的表示-5
冗余是指在正常系统运行所需的基础上加上一定数量的资源，包括信息、时间、硬件、和软件。冗余是容错技术的基础，通过冗余资源的加入，可以使系统的可靠性得到较大的提高。主要的冗余技术有结构冗余（硬件冗余和软件冗余）、信息冗余、时间冗余和冗余附加四种。
https://blog.csdn.net/lishanleilixin/article/details/90291744
冗余技术
计算机组成与体系结构
进程是程序在一个数据集合上运行的过程，她是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCV）和数据块三部分组成
进程与程序的区别：进程是程序的一次执行过程，没有程序就没有进程。进程是完成某个特定功能的一系列程序语句的集合，只要不被破坏，它就永远存在。程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是
进程的概念
时间片：时间片即CPU分配给各个程序的时间，每个线程被分配一个时间段，称作它的时间片，即该进程允许运行的时间，使各个程序从表面上看是同时进行的。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。而不会造成CPU资源浪费。在宏观上：我们可以同时打开多个应用程序，每个程序并行不悖，同时运行。但在微观上：由于只有一个CPU，一次只能处理程序要求的一部分，如何处理公平，一种方法就是引入时间片，每个程序轮流执行。
（主要掌握三态模型就行，还有五态，七态、九态等）就绪->运行：cpu此时处于空闲状态，并调度，程序即可进入运行状态运行->等待（阻塞）：程序此时要等待某个事件发生，如数据传输，则程序进入等待状态，cpu此时可先执行其他进程等待->就绪：程序需要等待的任务已经完成，则进入就绪状态运行->就绪：时间片到了，或者来了一个优先级更高的进程
进程的状态
同步：进程A完成后，再进行进程B
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。
直接制约关系
互斥：进程A、B可异步执行，没有先后关系，但是都要取某个数据资源
间接制约关系
虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。
临界资源
进程的同步和互斥
诸进程间需要互斥方式对其进行共享的资源，如打印机，磁带机等
每个进程中访问临界资源的那段代码称为临界区
临界区
物理意义：S≥0表示某资源的可用数，S＜0，则其绝对值表示阻塞队列中等待该资源的进程数
整型变量
信号量S
p是荷兰语的passeren，v是verhoog
生产者，消费者模型
某书店有一个收银员，该书店最多允许n个购书者进入。将收银员和购书者看做不同的进程，其工作流程如图6-3所示。利用PV操作实现该过程，设置信号量S1、S2和Sn，初值分别为0，0，n。则图6-3中a1、a2、b1和b2应分别填入（）
前趋图
pv操作应用
P操作表示申请一个资源，V操作表示释放一个资源
P操作定义：S=S-1，判断S，若S≥0，则执行P操作的进程继续执行，若S＜0，则置该进程为阻塞状态，并将其插入阻塞队列
V操作定义：S=S+1，判断S，若S>0，则执行V操作进程继续执行；若S≤0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续
PV操作
当有优先级更高的进程到来时，强行将正在运行的进程cpu分配给优先级高的进程
可剥夺
当优先级高的进程到来，等待正在运行的进程自动释放占用的CPU，然后将CPU分配给优先级高的进程
不可剥夺
进程调度方式是指当有优先级更高的进程到来时如何分配CPU
特点有利于长作业，不利于短作业；有利于CPU繁忙的作业而不利于I/O繁忙的作业
先来先服务（FCFS）。FCFS按照作业提交或进程成为就绪状态的先后次序分配CPU
分配每个进程相等的时间片
固定时间片
根据进程不同的要求对时间片的大小实时修改，可以更好地提高效率
可变时间片
特点：主要用于微观调度，提高并发性和时间响应特性
时间片轮转
进程的优先级在创建时确定，直到进程终止都不会变
静态优先级
在创建进程时赋予一个优先级，在进程运行中还可以改变
动态优先级
优先级调度
时间片轮转算法与优先级算法的总和与发展
多级反馈调度
进程调度算法
进程调度
进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事情，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁
环路等待：指进程资源有向图中构成环路
互斥，保持和等待，不剥夺，环路等待
死锁的必要条件
取足够多的资源，使其不可能发生死锁
有序资源分配法
当一个进程对资源的最大需求量不超过系统总的资源数时可以接纳该进程进程可以分期请求资源，但请求的总数不能超过最大需求量当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源
银行家算法
死锁的避免
打破四大条件
死锁的预防
死锁问题
进程如同一个工厂（计算机）中的一个车间（cpu），而线程即是车间（如汽车流水线）里的工作人员，有搬运模具的工人，有拧螺丝的工人，共同作业，完成一辆车（进程）的制造
线程
作业状态与作业管理
作业调度算法
作业管理
一般索引编号从0开始
索引文件结构
树形目录结构
位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配。有的系统把\"0\"作为盘块已分配的标记，把“1”作为空闲标志。(它们的本质上是相同的，都是用一位的两种状态标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。以上意思是每个二进制位标志一个盘块是否分配，0代表空闲，1代表已分配
假设计算机字长是32位的，位示图用每1位表示1个磁盘块的使用情况，1个字是32位，所以1个字可以表示32块物理块使用情况
位示图法
空闲存储空间的管理
文件查找的效率跟查找层级有关，如同目录下的文件，用相对路径查找比绝对路径要快
文件管理
程序控制（查询）方式
https://blog.csdn.net/weixin_30838873/article/details/98868273
中断向量是中断服务程序的入口地址，在计算机中中断向量的地址存放一条跳转到中断服务程序的跳转指令。中断地址是存储中断向量的内存单元。中断向量表：用来存放中断向量（共256个），它的地址范围是0~3FFH
https://blog.csdn.net/qq_39642794/article/details/84111379
中断处理过程，中断向量，中断保护现场，中断嵌套，中断返回
程序中断方式
直接存储器存储
DMA方式
通道方式
I/O方式
https://blog.csdn.net/baidu_37973494/article/details/82389577
https://blog.csdn.net/weixin_30951231/article/details/97476292
数据传输控制方式
SPOOLing是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”，SPOOLing技术通过磁盘实现
虚设备与SPOOLING技术
设备管理
寄存器-缓存-主存-存储组织的功能外存
寄存器-主存-外存
虚拟地址
源程序被编译后再经过链接编辑程序加工形成程序的装配模块，即转换为相对地址编址的模块，它是以0为基址的顺序进行编址的，相对地址也称为逻辑地址或虚地址，先对地址空间通过地址再定位机构转换到绝对地址空间，绝对地址空间称为物理地址空间
地址空间
逻辑地址空间（地址空间）是逻辑地址的集合，物理地址空间（简称存储空间）是物理地址的集合
存储空间
存储器的结构
地址重定位是将逻辑地址变换成主存物理地址的过程
程序装入主存时已经完成了逻辑地址到物理地址的变换在程序的执行期间将不会再发生变化
静态重定位
在程序运行期间完成逻辑地址到物理地址的变换
动态重定位
地址重定位
基本概念
将程序与内存划分为同样大小的块，以页为单位将程序调入内存
页表：提供程序与内存之间的映射关系
页号+页内地址
逻辑地址
块号（页帧号）+页内地址
物理地址
利用率高，碎片小，分配及管理简单
优点
增加了系统开销，可能产生抖动现象
缺点
页式存储组织
把主存的用户区划分成若干个连续区域，每个区域分配给一个用户作业使用，并限定它们只能在自己的区域中运行
固定分区
可变分区
可重定位分区
缺点：用户程序必须装入连续的地址空间，若无法满足用户要求的连续空间，需要进行分区靠拢操作，耗费系统时间
分区存储管理
按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样
段号+段长+基址
段表
多道程序共享内存，各段程序修改互不影响
内存利用率低，内存碎片浪费大
合法段，非法段
段式存储组织
段式与页式的综合体，线分段，再分页，1个程序有若干段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同，起始地址存在段表寄存器，与段号，页号共同算出物理地址
空间浪费小，存储共享容易，存储保护容易，能动态连接
由于管理软件的增加，复杂性和开销页随之增加，需要的硬件以及暂用的内容也有所增加，使得执行速度大大下降
段的长度取决于程序，用户将程序分段，后按页存储，所以不是段内所有页都会存
段页式存储组织
如果一个作业只部分装入主存便可以开始启动运行，其余部分暂时留在磁盘上，在需要时再装入主存，这样可以有效的利用主存空间，这样的存储器称为虚拟存储器
在段页式管理系统中加入请求掉段（页）、分段（页面）置换功能
虚拟存储管理
系统算出不再使用的程序去掉（过于理想化的算法）
最优（Optimal，OPT）算法
随机去掉程序
随机（RAND）算法
有可能产生抖动：如先调入的程序需要反复使用，会出现调入，调出，反复。导致抖动
先进先出（FIFO）算法
理论依据是“局部性原理”
最近最少使用（LRU）算法
刚被访问的内容，立即又被访问
时间局部性
刚被访问的内容，临近的空间很快被访问
空间局部性
页面置换算法
可变分区分配方式下，当收回主存时，应检查是否有与归还区相邻的空闲区，若有，则应合并成一个空闲区。相邻可能有上邻空闲区、下邻空闲区、既上邻又下邻空闲区、既无上邻又无下邻空闲区。 若有上邻空闲区，只修改上邻空闲区长度（为收回的空闲区长度与原上邻区长度之和）即可； 若有下邻空闲区，改记录这个下邻空闲区记录的地址为收回空闲区的地址，长度为下邻空闲区的长度和收回空闲区的长度即可； 若既有上邻又有下邻空闲区，改记录上邻区记录的长度（为上邻区长度、下邻区长度和收回区长度之和），再把下邻区记录的标志位改为空即可； 若既无上邻区又无下邻区，那么找一个标志位为空的记录，记下该回收区的起始地址和长度，且改写相应的标志位为未分配，表明该登记栏中指示了一个空闲区。
可变式分区分配方案
存储管理方案
存储管理
寻道时间是值磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间
存取时间=寻到时间+等待时间
中心和边缘存储大小相同，因为密度不同
先来先服务（FCFS）
读完一个后优先选取离它最近的一个
最短寻道时间优先（SSTF）
柱面相同，磁头号由小到大，扇区由小到大
由圆心到边缘，再由边缘到圆心
扫描算法（SCAN）
由圆心到边缘（做处理），回到圆心（不做处理），再由圆心到边缘（做处理）
循环扫描（CSCAN）算法
磁盘调度算法
读取磁盘数据时间计算
磁盘内部由磁头、盘面
磁盘工作原理
磁盘管理
SPOOLing是Simultaneous Peripheral Operation On-Line （即外部设备联机并行操作）的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。
实际上就是中间建一个缓冲区，cpu把数据发送到缓冲区，之后缓冲区与外设建立信息交流，所以可以做到“虚拟”，即便没有外设，或是只有一个外设，也可以做到多进程同时使用
spooling技术
一个作业通常包括几个进程，几个进程共同完成一个任务，即作业。用户提交作业以后，当作业被调度，系统会为作业创建进程，一个进程无法完成时，系统会为这个进程创建子进程
作业与进程的区别
进程管理
https://blog.csdn.net/luoyir1997/article/details/81673529
嵌入式系统的初始化
嵌入式系统
实时操作系统
分类
操作系统（6~8）
（视图级）外模式-（表级）概念模式映像
概念模式-（文件级）内模式映像
两级映像
视图
外模式
表
模式
索引
存储用顺序存储，还是树
加密还是明文
物理文件
内模式
三级模式
https://blog.csdn.net/lanadeus/article/details/80432823
https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E6%B5%81%E5%9B%BE/4136477?fr=aladdin
数据流图
https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%AD%97%E5%85%B8/1270246?fr=aladdin
数据字典
需求说明书
需求分析
概念模型
E-R模型
概念结构设计
关系模式
逻辑设计结构
物理设计
https://blog.csdn.net/bieleyang/article/details/77149954
数据库设计过程
属性（如员工名，部门名）
可以只建两个表，关联关系（外键）放在任何一个实体中都可
1:1联系
可以只建两个表，关联关系放在n对应的实体
1:n联系
需要建三个表
m:n联系
一种隶属关系，如员工属于某个部门
联系
实体（如员工，部门）
某种特殊的实体（如经理）
特殊化（弱实体）
属性冲突
结构冲突
命名冲突
https://blog.csdn.net/qq_38712932/article/details/83899790
冲突
并集
并
交集
交
s1-s2等于s1中s2中没有的那些记录
差
并，交，差（是对各集合元组的重新组合；要求：参加集合操作的各结果表的列数必须相同，对应项的数据类型也必须相同）
R除以S的结果集为在R的非公共属性组上取值相同的元组在公共属性组上的分量集合，包含S在公共属性组上的投影集合时，取R中元组在非公共属性组上的分量作为结果集中的元组
找S上于R上相同的分量（属性），去掉重复的值，取出作为S1（可能有多个元组），在R中相同的分量中比较，找到相同的（S1多元组的话，需要满足每条元组），然后看S和S1上不同的分量，如果此分量的值是一样的，即取出来作为结果
除法
第一列编号为1
做乘法
笛卡尔积
只选属性为xx，xx的字段
投影
选择某属性等于某值的记录
选择
做笛卡尔积，保留两表分量相同，值相同(多个分量的话要都相同)的元组
自然连接
做笛卡尔积，按给定的条件选取元组，左联的话即便左边表有一条记录不符合条件，也要保留，其余值取null；右连接：保留右边的；全连接：左右两边即便都有不符合的也都要保留
外连接
做笛卡尔积，按给定条件选择元组，去掉所有不符合的
内连接
https://blog.csdn.net/qq_41063141/article/details/89507876
关系代数
唯一标识元组，且无冗余
候选键
候选键上任选一个都行
主键
其他关系的主键
外键
键
1.将关系的函数依赖关系，用“有向图”的方式表示；2.找出入度为零的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有节点，则该属性即为关系模式的候选键。3.若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点（既有入度，也有出度的结点）并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键
求候选键
组成候选码的属性就是主属性，其他的就是非主属性
主属性与非主属性
设R（U）是属性U上的一个关系模式，X和Y是U的子集，r为R的任一关系，如果对于r中的任意两个元组u，v只要有u[X]=v[X]，就有u[Y]=v[Y]则称X函数决定Y，或称Y函数依赖于X，记为X->Y
属性值都是不可分的原子值
第一范式（1FN）：在关系模式R中，当且仅当所有域只包含原子值，即每个属性都是不可再分的数据项，则称关系模式R是第一范式
一个表只描述一个对象
非键字段必须依赖于键字段
主键A，非主属性B，A无法推出B
消除非主属性对候选键的部分依赖
第二范式（2FN）：当且仅当关系模式R是第一范式（1FN），且每个非主属性完全依赖候选键（没有不完全依赖）时，则称关系模式R是第二范式
在所有的非键字段中，不能有传递依赖
消除非主属性对候选键的传递依赖
消除主属性对候选键的部分和传递依赖
BC范式（BCNF）：设R是一个关系模式，F是它的依赖集，R属于CBNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码
范式
有损，无损
模式分解
系与学生的信息放在同一张表会造成1）数据冗余：浪费大量的存储空间，每一个系主任的姓名重复出现2）更新异常（Update Anomalies）：更新数据时，维护代价大：某系更换系主任后，须修改有关的每一个元组3）插入异常（Insertion Anomalies）：如果一个系刚成立，尚无学生，则无法把这个系及其系主任存入数据库4）删除异常（Deletion Anomalies）：如果某个系的学生全部毕业了， 则在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了
不满足范式时的问题
派生属性：“学生”实体中有“生日”和“年龄”等属性，从“生日”可以计算出“年龄”属性的值，“年龄”属性就是派生属性多值属性：一个人都多个亲属，亲属就是多值属性。一个人有多种爱好。一个人可能有多个电话号码单值属性：学生表中的学号就只有一个，所以叫单值属性。复合属性：”姓名“由 姓+中间名+名 构成简单属性：与复合相对的，就是简单属性。
数据的单值、多值、派生、简单、复合属性
https://blog.csdn.net/qq_43974000/article/details/105600550
规范化理论
它是按用户的观点来对数据和信息建模，用于数据库设计
概念数据模型（信息模型）
概念数据模型是对现实世界的数据描述，这种数据模型最终要转换成计算机能够实现的数据模型。现实世界的第二层抽象是直接面向数据库的逻辑结构，称为结构数据模型，这类数据模型涉及到计算机系统和数据库管理系统。结构数据模型的三个组成部分是： 数据结构：实体和实体间联系的表示和实现。 数据操作：数据库的查询和更新操作的实现。 数据完整性约束：数据及其联系应具有的制约和依赖规则。
如学生（学号，名字，年龄）老师（教师号，名字，年龄）
https://blog.csdn.net/nailuoch/article/details/96277877
关系模式需要满足多种约束
关系模型
逻辑模型主要包括层次模型、网状模型、关系模型、面向对象数据模型、对象关系数据模型、半结构化数据模型等
结构数据模型（逻辑模型）
按计算机系统的观点对数据建模，用于DBMS实现，物理模型是对数据最底层的抽象。 描述数据在系统内（磁盘上）的表示方式和存取方法
物理模型
数据模型
数据库系统（6~8）
实现具体的应用功能
应用层
数据的格式与表达，加密，压缩
表示层
建立，管理和终止会话
会话层
tcp和udp协议
端到端的连接
传输层
三层交换机，路由器，ARR，RARP，IP
分组传输和路由选择
网络层
网桥，交换机，PPTP，L2TP
传送以帧为单位的信息
数据链路层
中继器，集线器
二进制传输
物理层
OSI/RM七层模型
CSMA/CD
TokingRing
网络接口层（对应物理层与数据链路层）
IP
因特网控制协议，PING命令来自该协议
ICMP
组播协议
IGMP
地址解析协议，IP地址转换为MAC地址
ARP
反向地址解析协议，MAC地址转IP地址
RARP
网际层（对应网络层）
可靠的传输层协议
TCP
不可靠的传输层协议
UDP
传输层（对应传输层）
110端口，邮件收取
POP3
File Transfer Protocol，文件传输协议
20数据端口/21控制端口，文件传输协议
FTP
80端口，超文本传输协议，网页传输
HTTP
Telnet
Simple Mail Transfer Protocol，简单邮件传输协议
25端口，邮件发送
SMTP
基于TCP
67端口，IP地址自动分配
DHCP
TFTP
Simple Network Management Protocol
161端口，简单网络管理协议
SNMP
53端口，域名解析协议，记录域名与IP的映射关系
DNS
基于UDP
NFS
应用层（对应剩下三层）
TCP/IP模型
TCP/IP协议族
网络号0~7位，第一位为0
A类
网络号0~15位，前两位位10
B类
网络号0~23，前三位为110
C类
组播地址，前四位为1110
D类
保留今后使用
E类
目前使用的是ipv4，32位组成，由两部分组成，网络号和主机号
说明
是把一组路由汇聚为一个单个的路由广播。路由汇聚的最终结果和最明显的好处是缩小网络上的路由表的尺寸。
将各子网地址的网段以二进制写出。比较，从第1位比特开始进行比较，将从开始不相同的比特到末尾位填充为0。由此得到的地址为汇总后的网段的网络地址，其网络位为连续的相同的比特的位数。
路由汇聚
IP地址
子网划分
网络功能要求
网络的性能要求
网络运行环境的要求
网络的可扩充性和可维护性要求
实用性原则
开放性原则
先进性原则
网络规划原则
可靠性原则
安全性原则
高效性原则
可扩展性原则
网络设计与实施原则
核心层
汇聚层
接入层
层次化网络设计
网络规划与设计
局域网
城域网
广域网
因特网
按分布范围分
总线型
星型
环型
按拓扑结构分
计算机网络划分
公用交换电话网络PSTN
数字数据网DDN
综合业务数字网ISDN
非对称数字用户线路ADSL
同轴光纤技术HFC
有线接入
IEEE 802.11（WIFI）
IEEE 802.15(蓝牙Bluetooth)
红外（IrDA）
WAPI
AP:为AccessPoint简称，一般翻译为“无线访问节点”，它是用于无线网络的无线交换机，也是无线网络的核心。无线AP是移动计算机用户进入有线网络的接入点，主要用于宽带家庭、大楼内部以及园区内部，典型距离覆盖几十米至上百米，目前主要技术为802.11系列。大多数无线AP还带有接入点客户端模式（APclient），可以和其它AP进行无线连接，延展网络的覆盖范围。
AC：它是指无线接入控制服务器(AC)，接入控制器(AC)无线局域网接入控制设备，负责把来自不同AP的数据进行汇聚并接入Internet，同时完成AP设备的配置管理、无线用户的认证、管理及宽带访问、安全等控制功能
WLAN系统一般由 AC(接入控制器) 和 AP(Access Point无线接入点）组成。
https://baike.baidu.com/item/%E7%AA%84%E5%B8%A6%E6%97%A0%E7%BA%BF%E6%8E%A5%E5%85%A5/16271840?fr=aladdin
窄带微波
https://baike.baidu.com/item/%E7%A0%81%E5%88%86%E5%A4%9A%E5%9D%80/2503754?fromtitle=CDMA&fromid=185961&fr=aladdin
CDMA
https://baike.baidu.com/item/%E8%9C%82%E7%AA%9D%E7%A7%BB%E5%8A%A8%E9%80%9A%E4%BF%A1/106306?fr=aladdin
蜂窝通信
无线接入
网络接入技术
HTML
加密强度不高，但效率高
秘钥分发困难
加解密使用同一套秘钥
Data Encryption Standard，数据加密标准
DES
三个秘钥，加密->解密->加密，已兼容DES
3DES（即Triple DES）是DES向AES过渡的加密算法，它使用3条56位的密钥对数据进行三次加密。是DES的一个更安全的变形。它以DES为基本模块，通过组合分组方法设计出分组加密算法。比起最初的DES，3DES更为安全。该方法使用两个密钥，执行三次DES算法，加密的过程是加密-解密-加密，解密的过程是解密-加密-解密。3DES加密过程为：C=Ek3(Dk2(Ek1(P)))3DES解密过程为：P=Dk1(EK2(Dk3(C)))采用两个密钥进行三重加密的好处有：①两个密钥合起来有效密钥长度有112bit，可以满足商业应用的需要，若采用总长为168bit的三个密钥，会产生不必要的开销。②加密时采用加密-解密-加密，而不是加密-加密-加密的形式，这样有效的实现了与现有DES系统的向后兼容问题。因为当K1=K2时，三重DES的效果就和原来的DES一样，有助于逐渐推广三重DES。③三重DES具有足够的安全性，还没有关于攻破3DES的报道。
3DES（三重DES）
RC-5
IDEA算法
常见对称秘钥加密算法
对称加密技术（共享秘钥）
秘钥必须成对使用（公钥与私钥）
疑问，为什么速度慢
加密速度慢，但强度高
RSA、ECC
常见非对称加密算法
非对称加密技术（公开秘钥）
是非对称加密技术的一种应用，发送者用私钥加密（签名），接受者用公钥解密（验证签名的可靠性）
数字签名
由单向散列函数加密成固定长度的散列值，不可逆（实际上是需要花费很长时间，大概一千多年）
数字摘要
MD5，SHA；MD5算法的散列值为128位，SHA为160位，使用MD5加解密的时间更短，安全性低
常用算法
发送报文时，发送方用一个哈希函数从报文文本中生成报文摘要，然后用发送方的私钥对这个摘要进行加密，这个加密后的摘要将作为报文的数字签名和报文一起发送给接收方，接收方首先用与发送方一样的哈希函数从接收到的原始报文中计算出报文摘要，接着再公钥来对报文附加的数字签名进行解密，如果这两个摘要相同、那么接收方就能确认该报文是发送方的。
签名过程
信息摘要
管理公钥的机构
CA中心
①A生成对称秘钥；②A向CA申请证书，CA用自己的私钥用数字签名的方式加密A的公钥，生成证书③B获取到证书（A直接发给B的，或者其他方式），B通过CA的公钥验证数字签名，确认A的公钥的合法性④B用A的公钥加密信息发送给A⑤A用自己的秘钥解密B发送的消息
PKI公钥体系
隔离
屏蔽
链路加密、PPTP、L2TP
防火墙、IPSec
TLS、SET
全称：Pretty Good Privacy ，优良保密协议，是一套用于信息加密、验证的应用程序，可用于嘉敏电子邮件内容
PGP
MIME(Multipurpose Internet Mail Extensions)多用途互联网邮件扩展类型。是设定某种扩展名的文件用一种应用程序来打开的方式类型，当该扩展名文件被访问的时候，浏览器会自动使用指定应用程序来打开。多用于指定一些客户端自定义的文件名，以及一些媒体文件打开方式。它是一个互联网标准，扩展了电子邮件标准，使其能够支持：非ASCII字符文本；非文本格式附件（二进制、声音、图像等）；由多部分（multiple parts）组成的消息体；包含非ASCII字符的头信息（Header information）
MIME
Https
应用层、表示层、会话层
网络安全
消息内容获取
业务流分析
监听（保密性）
被动攻击
保证信息和信息系统随时为授权者提供服务，保证合法用户对信息和资源的使用不会被不合理的拒绝
中断（破坏可用性）
保证信息从真实的发信者传送到真实的收信者手中，传送过程中没有被非法用户添加、删除、替换等
篡改（破坏完整性）
伪造（破坏真实性）
主动攻击
保密性
完整性
可用性
处于国家和机构的利益和社会管理的需要，保证管理者能够对信息实施必要的控制管理，以对抗社会犯罪和外敌侵犯
可控性
人们要为自己的信息行为负责，提供保证社会依法管理需要的公证、仲裁信息证据
不可否认性
信息安全的基本属性
网络安全-主动攻击与被动攻击
黑客控制傀儡机往我们的服务器频繁发送请求，占用大量资源，导致真的请求过来后没有资源可处理
网络安全-DoS（拒绝服务）与DDoS
对包做监测，基本只监测数据格式是否正确
包过滤型防火墙
会检查包里面是什么，速度相对会慢一些
代理型防火墙
综合包过滤和代理防火墙，根据状态表做监测
状态监测型防火墙
网络级（都是通过通过屏蔽路由器让内网与外网相连接）
一端连接外网，一端连接内网
双穴主机
通过堡垒机连接内外网
屏蔽主机
通过两个路由器在中间部分隔离出一个非军事区DMZ地带，这里面可以放内外网都要访问的服务，如web服务，堡垒主机等
屏蔽子网
应用级（都是通过双穴主机或者说堡垒机连接内外网）
网络安全-防火墙
物理环境的安全性
操作系统的安全性
网络的安全性
应用的安全性
管理的安全性
安全防范体系
编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码
破坏的是引导盘、文件目录
引导区病毒
病毒
计算机木马是一种后门程序，常被黑客用作控制远程计算机的工具
木马
https://blog.csdn.net/zwj_jyzl/article/details/82914014
计算机病毒与木马
https://blog.csdn.net/m0_37609579/article/details/103172082
类似一个域内部计算机联通
内部网关协议
一个更大的域中，网关与网关之间的协议
外部网关协议
外部网关协议一般处理一个很大的域，即超多网关在同一级，内部网关协议，少量计算机（或网关）在同一级，导致它们处理的方式不同
内部网关协议与外部网关协议
https://blog.csdn.net/JankinChan/article/details/104883940
Web安全 常用网络测试命令（Ipconfig、ping、nslookup、tracert、netstat）
https://baike.baidu.com/item/%E7%94%B5%E5%AD%90%E9%82%AE%E4%BB%B6%E5%8D%8F%E8%AE%AE/4105152?fr=aladdin
常用的电子邮件协议有SMTP、POP3、IMAP4，另外还有MIME
电子邮件协议
常用协议
入侵检测系统（intrusion detection system，简称“IDS”）是一种对网络传输进行即时监视，在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备
入侵检测系统
其他
计算机网络与信息安全（8）
软件计划
定义阶段
软件设计
程序编码
开发阶段
运行维护
维护阶段
瀑布模型（自上而下，一步步进行）
概要设计
详细设计
编码
测试对象是编码，以详细设计为依据测试模块接口、局部数据结构、边界条件、独立的路径、错误处理
单元测试
测试对象是详细设计，以概要设计为依据测试模块间的接口和通信
集成测试
测试对象是概要设计，以需求分析为依据测试恢复测试、安全性、强度、性能、可靠性、安装（要有对应的硬件）
系统测试
用户主导
验收测试
V模型（自上而下，一步步进行）
演化
维护
测试
实现
设计
分析
喷泉模型（该模型是唯一一个面向对象的模型，各阶段是相互迭代和无间隙的）
客户也无法描述清楚自己的需求，项目经理与客户沟通，然后不断分析，产生原型
原型化模型
演化模型
螺旋模型
确定项目范围和边界
识别系统的关键用例
展示系统 的候选架构
评估项目费用和时间
评估项目风险
初始
分析系统问题领域
建立软件架构基础
淘汰最高风险元素
细化
开发剩余的构建
构件的组装与测试
构建
进行β测试
制作发布版本
用户文档定稿
确认新系统
培训、调整产品
交付
统一过程（用例驱动，以架构为中心，迭代和增量）
极限编程
https://blog.csdn.net/hu19930613/article/details/82154764
敏捷方法
软件开发模型
①分析当前的情况，做出反映当前物理模型的DFD；②推导出等价的逻辑模型的DFD③设计新的逻辑系统，生成数据字典和基元描述；④建立人机接口，提供可供选择的目标系统物理模型的DFD⑤确定各种方案的成本和风险等级，据此对各种方案进行分析⑥选择一种方案⑦建立完整的需求规约
步骤
数据流
加工
数据存储
外部实体
数据流、加工和数据存储用于构建软件系统内部的数据处理模型，而外部实体表示存在于系统之外的对象，用来帮助用户理解系统数据的来源和去向，外部实体包括：人/物、外部系统、组织机构等
元素
结构化方法
原型法
面向对象方法
面向服务的方法
软件开发方法
需求的任务
需求的过程
需求的分类
应用的工具
高内聚，低耦合
https://blog.csdn.net/weixin_40562161/article/details/90240954
模块设计原则
IPO图
PDL
程序流程图
N/S盒图
完成一个单一功能，各个部分协同工作，缺一不可
功能内聚
处理元素相关，而且必须顺序执行，上一个输出是下一个输入
顺序内聚
所有处理元素集中在一个数据结构的区域上
通信内聚
处理元素相关，而且必须按特定的次序执行
过程内聚
所包含的任务必须在同一时间间隔内执行
瞬时内聚
完成逻辑上相关的一组任务
逻辑内聚
完成一组没有关系或松散关系的任务
偶然内聚
内聚性（由高到低）
两个模块之间没有直接关系，它们之间的联系完全是通过主模块的控制和调用来实现的
非直接耦合
一组模块借助参数表传递简单数据（传值）
数据耦合
一组模块通过参数表传递记录信息（数据结构）（传引用）
标记耦合
模块之间传递的信息中包含用于控制模块内部逻辑的信息
控制耦合
一组模块都访问同一全局简单变量（传值），而且不是通过参数表传递该全局变量的信息
外部耦合
多个模块都访问同一个公共数据环境
公共耦合
一个模块直接访问另一个模块的内部数据；一个模块不通过正常入口转到另一个模块的内部；两个模块有一部分程序代码重叠；一个模块有多个入口
内容耦合
耦合性（由低到高）
用户操作控制
减轻用户的记忆负担
保持界面一致
人机界面设计
https://www.cnblogs.com/Zhanghaonihao/p/9097034.html
管道过滤器体系结构
架构
确定无效与有效等价类设计用例尽可能多的覆盖有效类设计用例只覆盖一个无效类
等价类划分
处理边界情况时最容易出错选取的测试数据应该恰好等于、稍小于、稍大于边界值（取三个值做测试）
边界值分析
错误推测
因果图
黑盒测试也称功能测试，是通过测试来检查每个功能是否都能正常使用，测试时，完全不用考虑程序内部结构和程序内部特征，在程序接口进行测试，测试的依据是软件需求规格说明
黑盒测试法
语句覆盖
判定覆盖
条件覆盖
条件判定覆盖
路径覆盖
白盒测试的几种覆盖方法：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、组合覆盖和路径覆盖详解https://blog.csdn.net/LOVEYSUXIN/article/details/82592588
白盒测试是对软件的过程细节做细致的检查，它允许测试人员利用程序内部逻辑结果和有关信息设计或选择测试用例，可以不考虑程序的功能，因此，测试用例的设计仅与模块设计说明书及源程序有关
白盒测试法
灰盒测试法
动态测试
桌前检查
代码审查
代码走查
静态测试
第一次测试出bug，修改后再测试
回归测试
一定的条件下，能够达到的最大负载如要求并发500，响应时间0.5ms，能达到此的话即通过
负载测试（类似额定功率）
达到失效的情况下，它所成承受的压力测试看看多少并发，将导致网页打开时间超过1分钟（失效状态）
压力测试（类似最大功率，超过即失效（失效也是人为规定的，如网页一分钟还打不开））
最少需要多少个测试用例，即可走遍所有结点（流程图->有向图）
环路复杂度（与最少需要的测试用例数相等）
McCabe复杂度
对请求作出响应所需要的时间
响应时间
指单位时间内系统处理用户的请求数
吞吐量
https://blog.csdn.net/zhongbeida_xue/article/details/84029308
软件性能常用术语
软件测试
可理解性
可测试性
可修改性
可维护性因素决定
即bug
改正性维护
适用环境，如市场环境有变化，硬件设施有变化
适应性维护
为将来可能发生的事做维护
预防性维护
即新需求，扩充功能，提升性能
完善性维护
软件维护类型
软件维护
可行性研究和项目任务书
需求规格说明
功能规格说明
设计规格说明（包括程序和数据规格说明）
开发计划
软件集成和测试计划
质量保证计划、标准、进度
安全和测试信息
开发文档
培训手册
参考手册和用户指南
软件支持手册
产品手册和信息广告
产品文档
开发过程的每个阶段的进度和进度变更的记录
软件变更情况的记录
相对于开发的判定记录
职责定义
管理文档
软件工程国家标准-软件文档管理指南-按阅读对象分类
功能性
可靠性指与在规定的一段时间和条件下，软件能维持其性能水平能力有关的一组属性
https://blog.csdn.net/starshinning975/article/details/102893787
MTTR/MTTF/MTBF
衡量可靠性指标
可靠性
易用性
维护性
可移植性
https://blog.csdn.net/HermitSun/article/details/92164226
可靠性和可用性
https://blog.csdn.net/GarfieldGCat/article/details/90010771
软件质量保证
CL0（未完成的）
CL1（已执行的）
CL2（已管理的）
CL3（已定义级的）
CL4（定量管理的）
CL5（优化的）
https://blog.csdn.net/lishanleilixin/article/details/89712013
软件过程改进（CMMI）软件成熟度模型
软件工程
范围管理
时间管理
https://blog.csdn.net/nilxin/article/details/1108636
成本管理
质量管理
人力资源管理
沟通管理
风险管理
采购管理
整体管理
项目干系人管理
风险发生的概率乘以风险造成的损失
风险曝光度
项目管理
总时差（松弛时间）：活动的总时差等于该活动最迟完成时间与最早完成时间只差，或该活动最迟开始时间与最早开始时间之差
求关键路径：即使工期最长的路径
关键路径法
前导图法
箭线图法
活动排序
配置管理（Configuration Management，CM）是通过技术或行政手段对软件产品及其开发过程和生命周期进行控制、规范的一系列措施。配置管理的目标是记录软件产品的演化过程，确保软件开发者在软件生命周期中各个阶段都能得到精确的产品配置
配置管理
系统开发基础（11）
属性（数据）+方法（操作）+对象ID
对象
实体对象的抽象，通常来自域模型（现实世界），用来描述具体的实体，通常映射到数据库表格与文件中。
实体类是用于对必须存储的信息和相关行为建模的类。实体对象（实体类的实例）用于保存和更新一些现象的有关信息，例如：事件、人员或者一些现实生活中的对象。实体类通常都是永久性的，它们所具有的属性和关系是长期需要的，有时甚至在系统的整个生存期都需要
实体类
控制对象的抽象，主要用来体现应用程序的执行逻辑，将其抽象出来，可以使变化不影响用户界面和数据库中的表。
控制类用于对一个或几个用例所特有的控制行为进行建模，它描述的用例的业务逻辑的实现，控制类的设计与用例实现有着很大的关系。在有些情况下，一个用例可能对应多个控制类对象，或在一个控制类对象中对应着对个用例。它们之间没有固定的对应关系，而是根据具体情况进行分析判断，控制类有效将业务逻辑独立于实体数据和边界控制，专注于处理业务逻辑，控制类会将特有的操作和实体类分离，者有利于实体类的统一化和提高复用性
控制类
边界对象的抽象，通常是用来完成参与者（用户、外部系统）与系统之间交互的对象，例如：From、对话框、菜单、接口等
边界类是系统内部与系统外部的业务主角之间进行交互建模的类。边界类依赖于系统外部的环境，比如业务主角的操作习惯、外部的条件的限制等。它或者是系统为业务主角操作提供的一个GUI，或者系统与其他的系统之间进行一个交互的接口，所以当外部的GUI变化时，或者是通信协议有变化时，只需要修改边界类就可以了，不用再去修改控制类和实体类。业务主角通过它来与控制对象交互，实现用例的任务。
边界类
具有相同属性的对象的集合
https://blog.csdn.net/koko7958/article/details/45083279
类
复用机制
继承与泛化
隐藏对象的属性和实现细节，仅对外公开接口
封装
不同对象收到同样的消息产生不同的结果
https://blog.csdn.net/zybqmy/article/details/49582521
同样名称的方法，参数不一样，调用不同的方法
参数多态
同样名称的方法，定义该方法的类型不同，用不同的表现
过载多态
1+‘1’= ‘11’
隐式转换
强制多态
多态
一种特殊的类，他只有方法定义没有实现
接口
一个类可以有多个同名而参数类型不同的方法
重载
模板类
消息是异步通信的
消息和消息通信
设计目的单一的类
单一职责原则
对扩展开放，对修改封闭
开放-封闭原则
子类可以替换父类
李氏（Liskov）替换原则
要依赖于抽象，而不是具体实现；针对接口编程，不要针对实现编程
依赖倒置原则
使用多个专门的接口比使用单一的总接口要好
接口隔离原则
要尽量使用组合，而不是集成关系达到重用目的
组合重用原则
一个对象应道对其他对象有尽可能少的了解
迪米特（Demeter）原则（最少知识法则）
https://blog.csdn.net/qq_34760445/article/details/82931002
面向对象设计的7大原则
面向对象的基本概念
类图
对象图
包图
组合结构图
构件图
部署图
制品图
结构图
系统与外部参与者的交互
用例图
强调按时间顺序
顺序图
通信图（协作图）
定时图
状态图
活动图
交互概览图
行为图
UML
表示为类与类之间的继承关系，接口与接口之间的继承，类对接口的实现关系。
依赖关系（Dependency）
泛化（Generalization）
关联关系（Association）
聚合关系（Aggregation）
整体与部分生命周期相同
复合关系（Composition）
接口与类之间的关系
实现关系(Realization/Implementation)
https://www.jianguoyun.com/p/DddOijAQ8daJCRiu0OED
图解地址
关系
动态生产对象
定义一个创建对象的接口，但由子类决定需要实例化哪一个类，工厂方法使得子类实例化的过程推迟
工厂方法模式（factory method）
生产一系列对象
提供一个借口，可以创建一系列相关或相互依赖的对象，而无需指定它们具体的类
抽象工厂模式（abstract factory）
克隆对象
用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象
原型模式（prototype）
单实例
保证一个类只有一个实例，并提供一个访问它的全局访问点
单例模式（singleton）
复杂对象构建
将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示
构建器模式（builder）
创建型模式
转换接口
将一个类的接口转换成用户希望得到的另一种接口，它使原本不相容的接口得以协同工作
适配器模式（adapter）
继承树拆分
将类的抽象部分和它的实现部分分离开来，使它们可以独立地变化
桥接模式（bridge）
将对象组合成树形结构以表示“整体-部分”的层次结构，使得用户对单个对象和组合对象的使用具有一致性
组合模式（composite）
附加职责
动态地给一个对象添加一些额外的职责，他提供了用子类扩展功能的一个灵活的代替，比派生一个子类更加灵活
装饰模式（decorator）
对外统一接口
定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用
外观模式（facade）
文章共享文字对象
提供支持大量细粒度对象共享的有效方法
享元模式（flyweight）
为其他对象提供一种代理以控制这个对象的访问
代理模式（proxy）
结构型模式
传递职责
通过给多个对象处理请求的机会，减少请求的发送者与接受者之间的耦合，将接收对象连接起来，在链中传递请求，直到有一个对象处理这个请求
职责链模式（chain of responsibility）
日志记录，可撤销
将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作
命令模式（command）
虚拟机的机制
给定一种语言，定义它的文法表示，并定义一个解释器该解释器用来根据文法表示来解释语言中的句子
解释器模式（interpreter）
数据库数据集
提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示
迭代器模式（iterator）
不直接引用
用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互
中介者模式（mediator）
在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态
备忘录模式（memento）
联动
定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新
观察者模式（observer）
状态变成类
允许一个对象在其内部状态改变时改变它的行为
状态模式（state）
多方案切换
定义一系列算法，把它们一个个封装起来，并且使它们之间可相互替换，从而让算法可以独立于使用它的用户而变化
策略模式（strategy）
定义一个操作中的算法骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重新定义算法的某些特定步骤
模板方法模式（template method）
表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作
访问者模式（visitor）
行为型模式
设计模式的分类
面向对象技术（12）
出题一般算数组中某个元素的存储地址
数组
上三角矩阵
下三角矩阵
稀疏矩阵
顺序表
每个元素除了存储自己的值以外还存储下一个元素的地址，最后一个不存
单链表
最后一个存开头元素的地址
循环链表
每个元素存前后元素的地址，最后一个没有后，第一个没有前
双向链表
单链表删除节点
单链表插入节点
双链表删除
双链表插入
链表的基本操作
链表
顺序存储与链式存储对比
先进先出
队列
先进后出
栈
循环队列
队列与栈
线性表
https://blog.csdn.net/duan19920101/article/details/51579136
散列表
广义表是n个表元素组成的有限序列，是线性表的推广
通常用递归的形式进行定义，记做：Ls（a0，a1...）
基本运算：取表头head（Ls）和取表尾tail（Ls）
一般考察计算深度与长度、以及如何取其中的某个元素
广义表
根为第一层
结点的层次
树的最大层次
深度
多少个孩子子节点
节点的度
节点的度中最大的
树的度
一颗树的总结点数为这棵树的所有节点的度数之和加1（根节点）
https://blog.csdn.net/qq_21550189/article/details/100766734
树的节点计算
度
叶子节点
分支节点
内部节点
父节点
子节点
兄弟节点
节点
满二叉树
完全二叉树
非完全二叉树
二叉树
二叉树的重要特性
根左右
前序遍历
左根右
中序遍历
左右根
后续遍历
从上往下，从左往右
层次遍历
二叉树的遍历
给定前序遍历，中序遍历求二叉树
反向构造二叉树
孩子节点-左子树节点
兄弟节点-右孩子节点
树转二叉树
左孩子小于根，右孩子大于根
若该键值节点已存在，则不再插入
若查找二叉树为空树，则以新节点为查找二叉树
将要插入节点键值与插入后父节点键值比较，就能确定新节点是父节点的左子节点，还是右子节点
插入节点
若待删除节点是叶子结点，则直接删除
若待删除节点只有一个子节点，则将这个子节点与待删除的父节点直接连接
若待删除的节点p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点s，用节点s的值代替节点p的值，然后删除节点s，节点s必是叶子节点或者只有一个子节点，按上面两种情况删除即可
删除节点
查找二叉树
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
哈夫曼编码
哈夫曼树又称为最优树.1、路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。2、结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。3、树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
基本术语
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。ps：结果可能有多种树，频率（权值，合并后的也算），权值小的在左（0），权值大的在右（1）
构造
最优二叉树（哈夫曼树）
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
空链域：每一个节点有左右两个指针，n个节点共有2n个链域，而n个节点只需用n-1个指针就可互连（因为连接n个点只需n-1条直线），所以还剩下2n-(n-1)=n+1个
线索二叉树
是查找二叉树，且任意节点的左右子树深度不能超过1
平衡二叉树
仅左子节点存在孩子结点
单支二叉树
树与二叉树
在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图（complete graph）
在无向图中，若每对顶点之间都有两条有向边相互连接，则称该图为完全图
完全图
用一个n阶方阵R来存放途中个节点的关联信息，其矩阵元素Rij定义为：Rij={1 若定点i到定点j有邻接边；0 若定点i到定点j无邻接边}（所以也是一个对角矩阵，存储时只记录一半的数据即可（((n*n-n)/2) + n））
邻接矩阵
首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针
邻接表
https://blog.csdn.net/smarter_shability/article/details/69664755
图的存储
首先访问出发顶点V依次从V出发搜索V的任意一个邻接点W若W未访问过，则从该点出发继续深度优先遍历，它类似于树的前序遍历
深度优先
首先访问出发顶点V然后访问与顶点V邻接的全部未访问顶点W、X、Y...然后再依次访问W、X、Y...邻接的未访问的顶点
广度优先
图的遍历
我们把用有向边表示活动之间开始的先后关系，这种有向图称为用顶点表示活动网络，简称AOV网络
一个有向图的拓扑序列可能有多个，按照图的每个顶点的方向连接起来即可
拓扑排序
图的最小生成树
https://blog.csdn.net/weixin_37853880/article/details/80320765
图
数据结构与算法基础（10）
源程序
词法分析
语法分析
这里一般指静态语义分析
语义分析
中间代码生成（可有可无）
代码优化（可有可无）
中间代码转低级语言代码，需要考虑硬件系统结构，编译型语言才有（解释型语言可直接通过解释器（如html语言与浏览器），无需生成目标代码）
目标代码生成
目标程序
https://www.cnblogs.com/blknemo/p/12596098.html?ivk_sa=1024320u
源程序->预处理（宏的替换（语言自带的函数处理）、合并模块、删去注释等）->编译->汇编得到机器语言->链接
字符流->词法分析->符号流->语法分析（语法是否正确，括号、dowhile语句是否完整等）->语法树->语义分析（是否有除以0等）->语法树->中间代码生成器->中间表示形式->代码优化器-中间表现形式->目标代码生成器->目标代码
编译
详解
编译过程（从上到下）
短语文法 P中任意产生式，均有α至少含有一个非终结符
0型
上下文有关文法 α的绝对值<=β的绝对值 （α的绝对值指α中符号的个数）
1型
上下文无关文法 α为非终结符中的一个
2型
不能既有aB又有Ba
正规文法 产生式形如 (A->a或A->aB)或者（A->a或A->Ba）A、B是非终结符，a是终结符
3型
从上到下，满足上面的，下面的才可能满足
文法
语法推导树
ε表示不输入任何值就能到下一个状态
不能有ε
确定的有限自动机
不确定的有限自动机
有限自动机
无限自动机
区别有限自动机有唯一的初态
自动机
必须有起始符与终结符
正规式
数字数据类型
布尔类型
字符类型
枚举类型
指针类型
常见数据类型
顺序类型
if、switch
选择结构
while、do while
循环结构
程序控制结构
数据类型与程序控制结构
https://www.jianguoyun.com/p/DXbvtUQQ8daJCRic-uED
将表达式排成二叉树，优先级高运算符在上面（有个简易算法，蓝笔的）
表达式
程序语言基础
传值调用
传址（引用）调用
传递方式
函数调用
科学计算，执行效率高
fortran语言
为教学而开发的，表达能力强
Pascal语言
指针操作能力强，高效
C语言
函数式程序语言，符号处理，人工智能
lisp语言
面向对象，高效
c++语言
面向对象，中间代码，跨平台
Java语言
面向对象，中间代码，.Net
C#语言
逻辑推理，简洁性，表达能力，数据库和专家系统
prolog语言
解释型，面向对象，脚本语言
python语言
各种程序语言的特点
https://www.cnblogs.com/kelamoyujuzhen/p/9396447.html
处理宏
预处理
将c语法的c源码，翻译为汇编语法的汇编源码。
将ASCII的汇编源码，翻译为能够被CPU执行的机器指令
汇编
将多个文件链接成一个可执行文件，并添加启动代码
链接
以上四步称为编译链接，简称编译，与最上面的编译过程其实差不多，只是从不同角度分析编译过程
C语言从源码到启动，经历了什么
程序设计语言与语言处理程序基础（3-5）
人耳：20Hz-20kHz
乐器：20Hz-20kHz
说话：300Hz-3400Hz
声音的带宽
单位时间内记录声音数据的次数（录制音频根录制动画一样，一帧一帧记录）
采样频率
一般是8位或16位
每一帧用多少位二进制来表示
采样精度（采样的位数）
为了降低失真率
采样频率应为声音最高频率2倍
采样
analog（模拟） to digital converter
A/D转换：采样->量化->编码
wave、MP3、MIDI
常见音频格式
（采样频率kHz*精度bit（量化）/采样位数bit）*通道数/8bit
每秒容量（bps）
音频相关概念
亮度
色调
某个颜色加入白色光的程度
饱和度
每英寸可以被表示成的点数
图像扫描DPI
图像相关概念
色数，每个像素的位数的所有组合情况（色数=2^位数）
图形与图像相关概念
直接作用于人的感觉器官，使人产生直接感觉的媒体声音、图形、图像、动画，如人类的各种语言，自然界的活动图像，动画等
感觉媒体
指为了加工、处理和传输感觉媒体而人为研究、构造出来的一种媒体，常见的有各种编码方式，如文本编码、图像编码、声音编码
表示媒体
表现和获取信息的物理设备，如输入显示媒体键盘、鼠标和麦克风等；输出显示媒体显示器、打印机、音响
显示媒体（表现媒体）
存储是数据的物理设备，如磁盘，光盘和内存等
存储媒体
传输数据的物理载体，如电缆，光缆和交换设备
传输媒体
媒体的种类
空间冗余
时间冗余
视觉冗余
信息熵冗余
结构冗余
知识冗余
数据压缩基础
无损压缩能够还原（如.rar，可以解压还原），有损不能还原（如.raw转为jpg。无法再还原了）
一类是无损压缩编码法，也称冗余压缩法或熵编码法；另一类是有损压缩编码法，也称为熵压缩法
有损压缩与无损压缩
常见的多媒体标准
多媒体基础知识（3）
著作权的保护期限，作品的作者是公民的，保护期限至作者死亡之后第50年的12月31日；作品的作者是法人、其他组织的，保护期限到作者首次发表后第50年的12月31日；但作品自创作完成后50年未发表的，不再受《著作权法》保护。但是作者的署名权、修改权、保护作品完整权的保护期不受限制
1.不需要申请，作品完成即开始保护2.绘画或摄影作品原件出售（赠予）著作权归原作者，原件拥有者有：所有权、展览权
保护对象：著作权、文学、会话、摄影等作品
著作权法（版权）
1.不需要申请，作品完成即开始保护2.登记制度便于举证
软件著作权软件作品
软件著作权法计算机软件保护条例
需要申请，专利权有效期是从申请日开始计算
专利权
专利法
到期可续
需要申请，核准之日起商标受保护
商标权
商标法
1.商业秘密包括技术与经营两个方面2.必须有保密措施才能认定商业秘密
商业秘密权
反不正当竞争法
保护范围与对象
保护期限
知识产权人确定
中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权
开发软件所用的思想、处理过程、操作方法或者数学概念不受保护
法律、法规，国家机关的决议、决定、命令或其他具有立法、行政、司法性质的文件，及其官方正式译文时事新闻立法、通用数表、通用表格和公式
著作权法不适用于下列情形
不侵权：个人学习、研究或者欣赏；适当引用；公开演讲内容；用于教学或科学研究；复制馆藏作品；免费表演他人作品；室外公共产所艺术品临摹、绘画、摄影、录像；将汉语作品译成少数名族语言作品或盲文出版
侵权：未经许可，发表他人作品；未经合作作者许可，将与他人合作创作的作品当做自己单独创作的作品发表的；未参加创作、在他人作品署名；歪曲、篡改他人作品的；剽窃他人作品的；使用他人作品，未付报酬；未经出版者许可，使用其出版的图书期刊的版式设计的
侵权判定（五星）
国际标准：iso，iec等国际标准化组织
GB-中国、ANSI-美国、BS-英国
国家标准
区域标准
行业标准
地方标准
企业标准
项目规范
标准的分类
标准代号+专业类号+顺序号+年代号
国际、国外标准代号
强制标准代号GB、推荐性标准代号GB/T、指导性标准代号为GB/Z、实物标准代号GSB
我国国家标准代号
由汉语拼音大写字母组成
行业标准代号
由DB加上省级行政区代码的前两位
地方标准代号
由Q加上企业代号组成
企业标准代号
标准的编号
标准化基础知识
知识产权与标准化（2）
数据流图的基本概念
三种基本控制结构:顺序结构、选择结构和循环结构
缺陷检测 { WHILE（接收图像） DO{ 检测所收到的所有图像； IF（出现一张图像检测不合格） THEN{ 返回产品不合格； } ENDIF } ENDDO}
控制结构
结构化语言
数据流图（15）
数据库设计（15）
展现了一组用例、参与者（actor）以及它们之间的关系。
表示参与者与用例之间的通信，任何一方都可发送或接受消息。
指向消息接收方
关联Association
就是通常理解的继承关系，子用例和父用例相似，但表现出更特别的行为；子用例将继承父用例的所有结构、行为和关系。子用例可以使用父用例的一段行为，也可以重载它。父用例通常是抽象的。
指向父用例
泛化Inheritance
包含关系用来把一个较复杂用例所表示的功能分解成较小的步骤。
指向分解出来的功能用例
包含Include
扩展关系是指用例功能的延伸，相当于为基础用例提供一个附加功能。
指向基础用例
扩展Extend
【泛化关系】：是一种继承关系，表示一般与特殊的关系，它指定了子类如何特化父类的所有特征和行为。例如：老虎是动物的一种，即有老虎的特性也有动物的共性。【箭头指向】：带三角箭头的实线，箭头指向父类
【实现关系】：是一种类与接口的关系，表示类是接口所有特征和行为的实现.【箭头指向】：带三角箭头的虚线，箭头指向接口
实现（Realization）
【关联关系】：是一种拥有的关系，它使一个类知道另一个类的属性和方法；如：老师与学生，丈夫与妻子关联可以是双向的，也可以是单向的。双向的关联可以有两个箭头或者没有箭头，单向的关联有一个箭头。【代码体现】：成员变量【箭头及指向】：带普通箭头的实心线，指向被拥有者（老师类-学生类->课程）（老师与学生是双向n:m，学生拥有课程）
关联（Association)
【聚合关系】：是整体与部分的关系，且部分可以离开整体而单独存在。如车和轮胎是整体和部分的关系，轮胎离开车仍然可以存在。聚合关系是关联关系的一种，是强的关联关系；关联和聚合在语法上无法区分，必须考察具体的逻辑关系。【代码体现】：成员变量【箭头及指向】：带空心菱形的实心线，菱形指向整体
聚合（Aggregation）
【组合关系】：是整体与部分的关系，但部分不能离开整体而单独存在。如公司和部门是整体和部分的关系，没有公司就不存在部门。组合关系是关联关系的一种，是比聚合关系还要强的关系，它要求普通的聚合关系中代表整体的对象负责代表部分的对象的生命周期。(鸟与翅膀，鸟爪)【代码体现】：成员变量【箭头及指向】：带实心菱形的实线，菱形指向整体
组合(Composition)
【依赖关系】：是一种使用的关系，即一个类的实现需要另一个类的协助，所以要尽量不使用双向的互相依赖.【代码表现】：局部变量、方法的参数或者对静态方法的调用【箭头及指向】：带箭头的虚线，指向被使用者（人--->手机）（人使用手机）
依赖(Dependency)
泛化 = 实现 > 组合 > 聚合 > 关联 > 依赖
各种关系的强弱顺序：
类图与对象图
通信图
https://blog.csdn.net/qq_35495763/article/details/80764914
UML建模（15）
递归技术
二分查找
将一个规模大的问题分为规模小的子问题，大问题的解为小问题解的合并
分治法
从某个点开始先走完一条路（到某个边界），然后回退到上一个分叉点，走另一条路，此路走到底，比较两条路中解，选取最符合题意的解，然后向上回溯，到上一个分叉点，走另一条路，继续对比
回溯法
总是选取最优解
贪心法
将一个规模大的问题分为规模小的子问题，大问题的最优解包含小问题的最优解
https://blog.csdn.net/sinat_19594515/article/details/102738781
动态规划法
时间复杂度
<1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个；<2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数。<3>.针对所有的元素重复以上的操作，除了最后一个；<4>.重复步骤1~3，直到排序完成。
冒泡排序
选择排序
<1>.从第一个元素开始，该元素可以认为已经被排序。<2>.取出下一个元素，在已经排序的元素序列中从后向前扫描<3>.如果该元素（已排序）大于新元素，将该元素移到下一位置<4>.重复步骤3，直到找到已排序的元素小于或等于新元素的位置；<5>.将新元素插入到该位置后；<6>.重复步骤2~5
插入排序
希尔排序
快速排序
归并排序
堆排序
桶排序
基数排序
计数排序
https://www.cnblogs.com/z937741304/p/11629213.html
十大排序算法
有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。
https://blog.csdn.net/achesong/article/details/88428895
0-1背包问题
https://blog.csdn.net/c18219227162/article/details/50412333
矩阵链乘
https://blog.csdn.net/hrn1216/article/details/51534607
最长公共子序列
分数背包与01背包问题不同点就是如果某物品无法被全部放入可以放入一部分
https://blog.csdn.net/wdays83892469/article/details/79765419
分数背包
常见问题
数据结构及算法应用（15）
Java抽象类
面向对象程序设计（15）
软件设计师知识点
0 条评论
回复 删除
下一页
