软件设计师
2024-08-22 14:29:43 0 举报
AI智能生成
根据B站zst_2001的软考 软件设计师相关视频整理的笔记
作者其他创作
大纲/内容
题目
问题1:写出实体的名称
问题二:写出数据存储的名称
问题三:补偿缺失的数据流和起点终点
问题
图形说明
父图子图平衡
方法1
数据流的起点或终点必须有一个是加工
一个加工至少有一个输入数据流和一个输出数据流
方法2
阅读理解,数据守恒
方法3
问题3解题方法
答题格式
试题一
问题1:补充ER图中的联系
问题2:补充关系模式并给出主键和外键
子主题
父实体和子实体的联系
一个实体的存在必须依赖另一个实体叫做弱实体
主键是下划实线
外键是下划外键
子实体要有主实体的主键
一个空可能需要填多个属性
问题2解题方法
解题方法
试题二
问题1:补充用例图的参与者和用例名称
问题2:补充用例图用例之间的关系
问题3:补充类图名称
依赖
关联关系是类与类之间的联接,它使一个类知道另一个类的属性和方法。关联可以是双向的,也可以是单向的,
它是依赖关系更强的一种关系,他是一组链,链是对象之间的连接
关联
部分和整体的生命周期不一致,整体消失了,部分仍然存在部分可以脱离整体存在
聚合
部分和整体的生命周期一致,整体消失了,部分也消失了,部分不可以脱离整体而存在。
组合
实现接口
实现
继承父类
泛化/继承
继承是实线,实现是虚线
关系
类图
一个用例执行的时候,可能会发生一些特殊的情况或可选的情况,这种情况就是这个用例的扩展用例。
箭头指向主用例
扩展关系(<<extend>>)
一个用例执行的时候,必须执行另一个用例,这种情况就是这个用例的包含用例。
箭头指向被包含的用例
包含关系(<<include>>)
父用例去泛化子用例,子用例继承父用例的所有属性和行为,子用例可以替换父用例
泛化关系(generalize)
用例图
问题1解题方法:用例之间只有扩展,包含和泛化三种关联关系
注意文章中的标点符号,。还有数字
找文章中的英文,一般一个英文就是一个类
找出文章中带字段的信息类,一般一个信息就是一个类
找出图中继承和实现的关键关系,再文章中找
基本事件流就是正常流程的步骤分解,备选事件流就是异常分支情况
问题3解题方法
试题三
继承:extends
实现:implements
试题六
下午题
国家软考办官网:https://www.ruankao.org.cn/
考试时间:5月/11月
考试介绍
位权的表示
十进制用D表示,二进制用B表示,十六进制用H表示
按权展开法:注意:小数点前边的次方从0开始,小数点后边的次方从-1开始
R进制转十进制
除基取余法:注意:最后的余数要倒着排成结果
十进制转R进制
二进制-八进制转换
二进制-十六进制转换
进制转换
符号数的范围
原码:最高位是符号位,其余低位表示数值的绝对值
反码:正数的反码与原码相同,负数的反码是其绝对值按位取反(符号位不变)
补码零的表示是唯一的
符号位可以与数值位一起参加运算
与真值的对应关系简单且直观
可以简化计算机运算部件的设计
补码:正数的补码与原码相同,负数的补码是其反码末位加1(符号位不变)
移码:补码的符号位按位取反
码制(原码/反码/补码/移码)
浮点数的表示:N=尾数*基数`阶码次幂
运算过程:零操作数检查-->对阶操作-->尾数运算-->结果格式化及舍入处理
一般尾数用补码,阶码用移码
阶码的位数决定数的表示范围,位数越多范围越大
尾数的位数决定数的有效精度,位数越多精度越高
对阶时,小数向大数看齐;通过较小数的尾数右移实现的
特点:
浮点数
或 与 异或 非
a&&b&&c:只有a是true的时候才需要判断b的值
a||b||c:只要a是true,就不需要判断b和c的值了
短路原则:在逻辑表达式中,并不是所有的逻辑都会执行,只要满足条件 后边的就不执行了
逻辑运算
数据的表示
奇偶校验码的编码方法是:由若干位有效信息,再加上一个二进制位(校验位)组成校验码
奇校验:整个校验码(有效信息位和校验位中的1的个数为奇数)
偶校验:整个校验码(有效信息位和校验位中的1的个数为偶数)
例:男-0 女-1 奇校验就是男-01 女-10
只可检错,不可以纠错
奇偶校验码
CRC校验码的编码方法是:通过模二除法得到余数(校验位),前边加上信息位组成校验码
校验:将接收到的CRC码除于模二除法,如果正确则余数为0,如果某一位出错,则余数不为0
CRC循环冗余校验码
海明校验码的编码方法是:通过在不同的位置添加校验位,交叉校验,找出错误的信息位
校验:分组奇偶校验
可检错,也可以纠错
公式
海明校验码
校验码
位/比特---bit----b
字节------byte---B 1B=8b
KB---MB---GB---TB 1024
计算机基本单位
1.1.计算机基础知识
Arithmetic Logic Unit
算术逻辑单元ALU:数据的算术运算和逻辑运算
Accumulator Register
累加寄存器AC:为ALU提供一个工作区,用在暂存数据
Data Register
数据缓冲寄存器DR:写内存时,暂存指令和数据
Program Status Word
程序状态条件寄存器PSW:存状态标志与控制标志
Multiplication Quotient Register
乘商寄存器MQ:存放运算结果
运算器
Control Unit
控制单元CU:分析指令,给出控制信号
Program Counter
程序计数器PC:存储下一个要执行指令的地址
Instruction Register
指令寄存器IR:存储即将执行的指令
Adress
地址寄存器AD:保存当前CPU所访问的内存单元地址
Instruction Decoder
指令译码器ID:对指令中的操作码字段进行分析解释
时序部件:提供时序控制信号
控制器
CPU组成
程序控制
操作控制
时间控制
数据处理
CPU的功能
CPU
外存-->内存(随机存储器RAM 只读存储器ROM)-->Cache-->CPU寄存器
主存-外存:实现了虚拟存储系统,解决了主存容量不够的问题
Cache-主存:解决了主存与CPU速度不匹配的问题
层次化存储体系
Cache的内存是内存的一部分副本,对我们是透明的,Cache与主存地址的映射是由硬件自动完成的
随机替换算法。就是用随机数发生器产生一个要替换的块号,将该块替换出去
先进先出算法。就是将最先进入Cache的信息块换出去
近期最少使用算法。这种方法是将近期最少使用的Cache 中的信息块替换出去
优化替换算法。这种方法必须先执行一次程序,统计 Cache 的替换情况。有了这样的先验信息,在第二次执行该程序时便可以用最有效的方式来替换
替换算法的目标就是使Cache获得尽可能高的命中率
Cache 的命中率与 Cache 容量的关系:Cache 容量越大,则命中率越高,随着 Cache 容量的增加,其失效率接近 0%(命中率逐渐接近 100%)。但是,增加 Cache 容量意味着增加Cache 的成本和增加 Cache 的命中时间。
直接映像:主存中的块与Cache中块的对应关系是固定的,优点:地址变换简单,灵活性差
全相联映像:主存中的块与Cache中块的对应关系是任意的,优点:地址变化比较复杂,速度慢,灵活性高
组相联映像:组之间采用直接映像,组内采用全相联映像
Cache和主存的地址映像是有硬件完成的
Cache的三种地址映像
Cache
存储单元个数=最大地址-最小地址+1
按字存储:存储体的存储单元是字
按字节存储:存储体的存储单元是字节
编址内容
总容量=存储单元个数*编址内容
总片数=总容量/每片的容量
主存编址计算
按访问方式可分为按地址访问的存储器和按内容访问的存储器
相联存储器是一种按内容访问的存储器
分类
时间局部性:刚被访问的内容,立即又被访问
空间局部性:刚被访问的内容,它附近的内容也容易被访问
虚拟存储器由主存和辅存组成
主存主要由DRAM构成,DRAM动态随机存储器,DRAM需要周期性刷新来保持数据
SRAM静态随机存储器,
其他
存储系统
保存现场:处理完中断服务程序后,返回来继续处理主程序
中断响应时间:发出中断请求开始到进入中断服务程序的时间
中断向量表:用来保存中断服务程序的入口地址
实现多级中断嵌套,使用堆栈来保护断点和现场
中断
CPU和IO(外设)只能串行工作
CPU需要一直轮询检查,CPU的利用率低
一次只能读/写一个字
由CPU将数放入内存
分为无条件传送和程序查询方式两种
程序控制查询方式:
IO设备通过中断信号主动向CPU报告IO操作已完成
CPU和IO(外设)可并行工作,CPU利用率得到提升
程序中断方式:
CPU和IO(外设)可并行工作
仅在传送数据块的开始和结束时才需要CPU的干预
一次读/写的单位是块,不是字
由外设直接将数据放入内存
DMA方式是为了在主存与外设之间大数据量实现高效,批量数据交互。
CPU执行完当前总线周期即可释放总线控制权
直接存储器(DMA)方式:
数据传输控制方式
输入输出技术
一条总线同一个时刻仅允许一个设备发送,但允许多个设备接收
总线复用方式可以减少总线中信号线的数量
数据总线(Data Bus):在CPU与RAM之间来回传送需要处理或是需要存储的数据
地址总线(Address Bus):用来在RAM中存储数据的地址
控制总线(Control Bus):将微处理器控制单元的信号传送到周边设备
总线
1.2.计算机组成
一条指令就是机器语言的一个语句,是一组有意义的二进制代码,格式:操作码字段+地址码字段
指令
立即寻址方式:指令中存放的是操作数
直接寻址方式:指令中存放的是操作数的内存地址,操作数放在内存当中
间接寻址方式:指令中存放的是操作数地址的地址
寄存器寻址方式:指令中存放的是寄存器的地址,寄存器存放的是操作数
寄存器间接寻址方式:指令中存放的是寄存器的地址,寄存器存放的是操作数的内存地址
基址加变址寻址方式:操作数在存储器中,其有效地址是一个基址寄存器和一个变址寄存器之和
相对基址加变址寻址方式:操作数在存储器中,其有效地址是一个基址寄存器和一个变址寄存器和一个偏移量之和
立即寻址>寄存器寻址>直接寻址>寄存器间接寻址>间接寻址
寻址方式
Flynn分类法
CISC和RISC
流水线:是指在程序执行时多条指令重叠进行操作的一种准并行处理技术
优先按照理论公式计算,理论公式可以简化提取出t:(t1+t2+tn-1)+(n-1)*t
流水线执行时间
流水线吞吐率
加速比
流水线
1.3.指令系统
串联系统:R=R1*R2*R3*....Rn
并联系统:R=1-((1-R1)*(1-R2)*(1-Rn))
1.4.可靠性
进程是程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位,它由程序块,进程控制块(PCB),数据块三部分组成
PCB:进程控制块(PCB)是进程存在的唯一标志。内容包含进程标识符、状态、位置信控制信息、队列指针(链接同一状态的进程)、优先级、现场保护区等。
进程的2个基本属性:可拥有资源的独立单位;可独立调度和分配资源的基本单位。
线程:一个进程可以有多个线程,线程间共享资源
进程概念
阻塞:也称等待或睡眠状态,一个进程正在等待某一个事件发生而暂时停止运行,此时即使把CPU分配给进程也无法运行
就绪:一个进程获得了除CPU以外的一切所需资源,一旦获得CPU资源即可运行
运行:当一个进程在CPU上运行时
当挂起时会有静止阻塞和静止就绪状态,需要唤醒才能恢复激活
进程状态
P就是加锁 V就是解锁 S就是信号量P:S=S-1申请锁定资源,S<0检查资源是否足够V:S=S+1释放解锁资源,S<=0检查是否有进程排队,通知排队进程
PV操作的概念
互斥模型:打印机
同步模型:生产者--市场--消费者 市场就是单缓存区(有容量)
信号量与PV操作
前趋是P 后继是V
前趋图与PV操作
死锁四大条件:互斥 保存 等待 不剥夺
系统不可能发生死锁的最小资源数(w-1)*m +1<=n w是进程数 m是资源数 n是最小的资源数
死锁问题
进程调度
2.2.线程/进程
找磁道的时间,即寻道时间
找块(扇区)的时间,即旋转延迟时间/等待时间
传输时间
存取时间=寻道时间+等待时间
读取磁盘数据的时间包括三部分
2.3.存储管理
加密和解密是同一把密钥只有一把密钥
密钥分发有缺陷①加密解密速度很快②适合加量大量明文数据
对称加密(私有密钥加密)/非公开
加密和解密不是同一把密钥分别是公钥和私钥
用公钥加密只能用私钥解密,用私钥加密只能用公钥解密,不能通过一把推出另一把
用接收方的公钥加密明文可以实现防止窃听的效果
密钥分发没有缺陷①加密解密速度很慢
公钥用于加密和认证,私钥用于解密和签名?
非对称加密(公开密钥加密)/公开
混合加密
用户向CA机构申请数字证书,将个人信息和公钥发给CA机构CA机构颁给用户数字证书,数字证书用CA的私钥进行签名(加密)用CA的公钥验证(解密)数字证书得到用户的公钥
数组证书
DES3DESRC-5IDEAAESRC4
对称密钥
RSADSAECC
非对称密钥
Hash函数
MD5摘要算法
SHA-1安全散列算法
加密算法分类
3.0.加密技术
一.计算机系统
机器语言和汇编语言为低级语言
各类面向对象程序语言为高级语言
程序的三种基本控制结构是:顺序,选择,重复
便于为数据合理分配存储单元
便于对参与表达式计算的数据对象进行检查
便于规定数据对象的取值范围及能够进行的运算
程序中的数据必须具有类型的作用
1.1低级语言和高级语言
函数首部:返回值类型 函数名(形参)
函数体{ xxx.函数名(实参) }
函数定义:
将实参的值传递给形参,实参可以是变量、常量和表达式。
不可以实现形参和实参间双向传递数据的效果
值调用
将实参的地址传递给形参,形参必须有地址,实参不能是常量(值),表达式。
可以实现形参和实参间双向传递数据的效果,即改变形参的值同时也改变了实参的值。
引用调用
1.2传值调用和传引用(地址)调用
翻译源程序时不生成独立的目标程序
解释程序和源程序都要参与到程序的运行过程中
解释器
编译时将源程序编译成独立保存的目标程序
机器上运行的是与源程序等价的目标程序
源程序和编译程序都不再参与目标程序的运行过程
编译器
1.3编译和解释
编译方式:词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
解释方式:词法分析、语法分析、语义分析
编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换
编译器方式中,中间代码生成和代码优化不是必要,可省略
输入:源程序
输出:记号流
主要作用:词法分析阶段的主要作用是分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定
词法分析
输入:记号流
输出:语法树
主要作用:对各条语句的结构进行合法性分析;分析程序中的句子结构是否正确
语法分析
输入:语法树
主要作用:进行类型分析和检査
语法分析阶段可以发现程序中的所有语法错误
语义分析阶段不能发现程序中所有的语义错误
语义分析阶段可以发现静态语义错误,不能发现动态语义错误,动态语义错误运行时才能发现
语义分析
常见的中间代码有:后缀式、三地址码、三元式、四元式和树(图)等形式。
因为与具体的机器无关,使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性
中间代码生成
代码优化
主要作用:是把中间代码变换成特定机器上的特定指令代码
目标代码生成阶段的工作与具体的机器密切相关
寄存器的分配工作处于目标代码生成阶段
目标代码生成
编译过程概述
1.4编译和解释
不断收集、记录和使用源程序中一些相关符号的类型和特征等信息,并将其存入符号表中。
记录源程序中各个字符的必要信息,以辅助语义的正确性检查和代码生成。
1.5符号表
1.6正规式和正规集的关系
有限自动机是词法分析的一个工具,它能正确地识别正规集
确定的有限自动机(DFA):对每一个状态来说识别字符后转移的状态是唯一的
不确定的有限自动机(NFA):对每一个状态来说识别字符后转移的状态是不确定的
1.7有限自动机?
广泛地用于表示各种程序设计语言的语法规则
大多数语法规则可以用上下文无关文法来描述
1.8上下文无关文法?
中缀((a+b)*c------>后缀a b + c *
1.9中缀后缀表达式切换
1-2*(3+4)/5转中序
2.0中序后序表达式转换
二.程序设计语言
算法时间复杂度以算法中基本操作重复执行的次数
1.1时间复杂度和空间复杂度
线性表的存储结构分为顺序存储和链式存储。
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素
在这种存储方式下,元素间的逻辑关系无须占用额外的空间来存储
线性表采用顺序存储结构的优点是可以随机存取表中的元素,缺点是插入和删除操作需要移动元素
最好O(1)
平均O(n/2)
最坏O(n)
插入时间复杂度
平均O((n-1)/2)
删除时间复杂度
线性表的顺序存储
线性表的链式存储是用通过指针链接起来的结点来存储数据元素,
结构是数据域+指针域:数据域用于存储数据元素的值,指针域则存储当前元素的直接前驱或直接后继的位置信息,指针域中的信息称为指针(或链)。
平均O(n)
循环单链表
双链表
线性表的链式存储
2.1.线性表的存储结构
栈是只能通过访问它的一端来实现数据在储和检索的一种线性数据结构
栈的插入和删除是按先进后出的原则进行的
2.2.栈
循环队列
2.3队列
字符串
朴素模式匹配:就是一个一个的比较
串的前缀:包含第一个字符并且不包含最后一个字符的子串
串的后缀:包含最后一个字符并且不包含第一个字符的子串
第i个字符的next值 =从1~i-1串中最长相等前后缀长度+1
特殊情况:next[1]=0
KMP
串的模式匹配
2.4串
求第i个元素的地址位置
优先级低做题是可以代入计算
2.5一维数组
2.6二维数组
2.7对称矩阵
2.8三对角矩阵
2.9稀疏矩阵
结点的度。一个结点的子树的个数记为该结点的度
叶子结点。叶子结点也称为终端结点,指度为0的结点。
内部结点。度不为0的结点,也称为分支结点或非终端结点
结点的层次。根为第一层,根的孩子为第二层
树的高度。一棵树的最大层数记为树的高度(或深度)。
树的度。一棵树的最大度为树的度。
基本概念
满二叉树 完全二叉树 非完全二叉树
二叉树中的任意一个结点的左右子树高度之差的绝对值不超过1
平衡二叉树
根大于所有的左子树,小于所有的右子树
中序遍历得到的序列是有序序列
二叉排序树(二叉查找树)
最优二叉树卫称为哈夫曼树,\"另一个结点之间的通路,路径上的分支数目称为路径长度。
带权路径长度wpl=(叶子节点权值*路径长度)之和
(2)在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和(根结点的权值=左右孩子权值之和,叶结点的权值= Wi)
(3)从F中删除这两棵二叉树,同时将新二叉树加入到F中;
(4)重复(2)、(3)直到F中只含一棵二叉树为止,这棵二叉树就是Huffman树。
如何构造最优二叉树
最优二叉树(哈夫曼树)
M个字符可以用N位表示:2N次方大于等于M
求哈夫曼编码a=0 c=100 b=101
哈夫曼编码压缩比
哈夫曼编码
3.0树
有向图:若图中的每条边都是有方向的
无向图:若图中的每条边都是无方向的
完全图:若图中的每个顶点和其他顶点都有边
邻接矩阵表示法
邻接链表表示法
稠密图:适合表示边多的图, 比较密集
稀疏图:适合表示边少的图,比较稀疏
有向图:总度数=边数 无向图:总度数=2*边数
表示法
3.1图
边带权值的图称为网
3.2网
就是一个从一个顶点一直往下寻找,到头在返回
如果用邻接矩阵表示变量所有顶点需要时间复杂度:0(N²)
如果用邻接表表示变量所有顶点需要时间复杂度:0(n+e) n个顶点e条边
深度优先搜索
就是一个从一个顶点遍历所有相联的点,一层层遍历
如果用邻接表表示变量所有顶点需要时间复杂度:0(n+e) n个顶点e条边
广度优先搜索
3.3搜索
在 AOV 网中不应出现有向环
(1)在 AOV 网中选择一个入度为0(没有前驱)的顶点且输出它。
(2)从网中删除该顶点及与该顶点有关的所有弧。
(3)重复上述两步,直到网中不存在入度为0的顶点为止。
计算拓扑排序值
3.4拓扑排序AOV网
动态查找表可以对查找表结构进行修改,而静态查找表只是查询
静态查找表有:顺序查找,折半(二分)查找,分块查找
动态查找表有:二叉排序树,平衡二叉树,B_树,哈希表
只适合顺序存储结构,并且值是有序的
最多比较次数logn+1次
平均查找长度(n+1)/2
二分查找
3.5查找
常用的哈希函数构造方法有直接定址法、数学分析法、平方取中法、折叠法、随机数法和除留余数法
H:(H(key)+d)%m ,H(key)为哈希函数;m为哈希表表长;d为增量序列。
②d =1²,-1²,-2²,2²,-3²,3².........±k² (k≤m/2),称为二次探测再散列。
③d =伪随机数序列,称为随机探测再散列。
常见的增量序列有以下3种
开放定址法
在每个hash节点后边跟一个链表
链地址法(拉链法)
处理冲突的方法
在查找过程中需要和给定值进行比较的关键字的个数取决于下列3个因素:哈希函数、处理冲突的方法、哈希表的装填因子
装填因子越趋近于1,冲突率越高
装填因子=表中装入的记录数/哈希表的长度
哈希表的查找
3.6哈希表
3.7大顶堆/小顶堆
插入排序:把元素一个一个的插入前边已经排好序的元素中
希尔排序:把元素对半平方编号,相同编号的做插入排序替换,循环此操作
选择排序:找出元素中最小的元素和头位置替换,循环此操作
堆 排 序:把元素转成大顶堆,取出最大的元素,循环此操作
冒泡排序:把元素一直往前冒泡,找出最大的元素,循环此操作
快速排序:取第一个元素,从右边找出小于它的值替换,从左边找出大于它的值替换,循环此操作
归并排序:把元素对半拆分成单个元素在合并
归位的排序:选择排序,冒泡排序,堆排序,快速排序
稳定的排序:插入排序,冒泡排序,归并排序
4.1排序算法
三.数据结构
人身权包括发表权、署名权、修改权和保护作品完整权等
财产权包括作品的使用权和获得报酬权,
发表权有保护期限,其他都是永久保护
地域性:专利保护再那国申请,哪国才受保护
1.1著作权(版权)是指作者对其创作的作品享有的人身权和财产权。
计算机软件著作权依据《中华人民共和国著作权法》和《计算机软件保护条例》的规定
公民
法人
计算机软件著作权的主体
计算机程序包括源程序和目标程序,
计算机程序
文档一般以程序设计说明书、流程图和用户手册等表现
计算机软件的文档
计算机软件著作权的客体
软件著作权属于软件开发者,软件著作权自软件开发完成之日起产生
著作权的归属由委托者与受委托者签订书面合同约定;无书面合同或者合同未作明确约定的,其著作权由受托人享有
委托开发的软件著作权归属
1.2计算机软件著作权
我国反不正当竞争法规定了商业秘密的保护问题
商业秘密权包含技术信息和经营信息
1.3计算机软件的商业秘密权
实用新型专利权和外观设计专利权的期限为 10年,
我国发明专利的保护期为 20 年
作品发表权的保护期为作者终生及其死亡后50年。
商标权的保护期限自核准注册之日起10年内有效,可以无限次数的延长权利期限
保护期限
四.知识产权
实体:客观存在并可以相互区别的事物称为实体
简单属性:是原子的、不可再分的
复合属性:可以细分为更小的部分(即划分为别的属性)
单值属性:定义的属性对于一个实体都只有单独的一个值
多值属性:一个属性可能对应一组值。例职工可能有0个、1个或多个亲属
NULL 属性:当实体在某个属性上没有值或属性值未知时,使用 NULL 值,表示无意义或不知道。
派生属性:可以从其他属性得来。例:职工实体集中有“参加工作时间”和“工作年限”属性
属性:描述实体的特性称为属性
码:唯一标识实体的属性集称为码
域:属性的取值范围称为该属性的域
1.1概念数据模型
外模式:视图 概念模式:表 内模式:文件
可以保证数据的物理独立性
模式/内模式映像:存在于概念级和内部级之间,实现了概念模式和内模式之间的相互转换。
可以保证数据的逻辑独立性
外模式/模式映像:存在于外部级和概念级之间,实现了外模式和概念模式之间的相互转换。
内模式也称存储模式:定义所有的内部记录类型、索引和文件的组织方式,
1.2三级模式两级映射
关系:一个关系就是一张二维表,每个关系有一个关系名
元组:表中的一行即为一个元组,对应存储文件中的一个记录值
属性:表中的列称为属性,每一列有一个属性名
域:属性的取值范围
关系模式:对关系的描述称为关系模式;格式为:关系名(属性名1,属性名2,…,属性名n)
候选码(候选键):属性或属性组合,其值能够唯一地标识一个元组。
主码(主键):在一个关系中可能有多个候选码,从中选择一个作为主码。
主属性:包含在任何候选码中的属性称为主属性,不包含在任何候选码中诸属性称为非码属性。
外码(外键):如果一个属性是另外一个关系的码,则称其为该关系的外码。
全码:关系模式的所有属性组是这个关系模式的候选码,称为全码。
超码(超键):一个包含码的属性集称为超码,例如学号是码,则(学号,姓名)就是一个超码
基本术语
并差交笛卡儿积,选择投影连接
垂直投影,水平选择
投影
选择
θ连接
等值连接
自然连接
左外连接
右外连接
全连接:自然连接+左右连接关联不上的
连接
关系代数
1.3关系模型
CREATE VIEW 视图名(列表名)AS SELECT 查询子句[WITH CHECK OPTION]:
子查询可以是任意复杂的 SELECT 语句,但通常不允许含有 ORDER BY 子句和DISTINCT 短语
WITH CHECK OPTION 表示对 UPDATE、INSERT、DELETE 操作时保证更新、插入或删除的行满足视图定义中的谓词条件
组成视图的属性列名或者全部省略或者全部指定。如果省略属性列名,则隐含该视图由 SELECT 子查询目标列的主属性组成
视图
DROP INDEX StdentIndex,
索引
CREATE FUNCTION 数名(参数名参数类型)RETURN 返回值的数据类型[WITH ENCRYPTION]--如果指定了encryption 则函数被加密[AS]BEGINfunction body--数体RETURN 表达式;END
通过提供存储过程让第三方调用,将需要更新的数据传入存储过程,而在存储过程内部用代码分别对需要的多个表进行更新,从而避免了向第三方提供系统的表结构,保证了系统的数据安全。
存储过程
包括CREATE、ALTER和DROP等
包括INSERT(插入)、DELETE(删除)和 UPDATED(更新)等
UNION:并INTERSECT:交EXCEPT:差
投影查询,选择查询,排序查询,聚合函数,数据分组,内连接,外连接,子查询,EXISTS子查询
DML(Data Manipulation Language,数据操纵语言)
包括SELECT 查询表中的内容
DQL(Data QueryLanguage,数据查询语言)
GRANT INSERT ON TABLE S TO UserI WITH GRANT OPTION:
REVOKE SELECT ON TABLE S FROM PUBLIC:
REVOKE UPDATE(So) ON TABLE S FROM User1:
PUBLIC:PUBLIC参数可将权限赋给全体用户。
WITH GRANT OPTION:若指定了此子句,那么获得了权限的用户还可以将权限赋给其他人
权限管理
BEGIN TRANSACTION:事务开始。
COMMIT:事务提交
ROLLBACK:事务回滚。
事务具有原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)和持久性(Durability)。
事务管理
包括数据库对象的权限管理和事务管理等
DCL(Data ControlLanguage,数据控制语言)
1.4SQL语言的分类
部分函数依赖:{AB->C,A->C}
传递函数依赖:{A->B,B->C}
推理规则
1.5函数依赖
1NF:属性不可再分
2NF:消除非主属性对候选码的部分函数依赖
3NF:消除非主属性对候选码的传递函数依赖
BCNF:消除主属性对候选码的部分和传递函数依赖
4NF:消除非平凡且非函数依赖的多值依赖
数据冗余
修改异常
插入异常
删除异常
解决的问题
1.6三大范式?
将p自然连接后可以还原为R就是无损链接,保持函数依赖就是看看p是否全部支持函数依赖集F
1.7无损连接和支持函数依赖?
系统需求说明书,需书说明文档
数据流图、数据字典、各种说明性表格、统计输出表和系统功能结构图等
系统需求说明书为以后的逻辑设计和物理设计以及应用程序的设计都会以此为依据。
成果
用户需求分析阶段
概念设计阶段
逻辑设计阶段
物理设计阶段
数据库实施阶段
数据库运行维护阶段
1.8数据库设计的步骤
主要构件
属性冲突
相同意义的属性在不同的分 E-R 图上有着不同的命名,或是名称相同的属性在不同的分 E-R 图中代表着不同的意义,这些也要进行统一
命名冲突
同一实体在不同的分 E-R 图中有不同的属性,同一对象在某一分 E-R 图中被抽象为实体,而在另一分 E-R图中又被抽象为属性,需要统一
结构冲突
E-R 图之间的冲突主要有以下三类
两个具有1:1联系或1:n联系的实体可以予以合并,使实体个数减少,有利于减少将来数据库操作过程中的连接开销
实体类型的合并
合并后属性的可能出现冗余。因为合并后的 E-R 图中的实体继承了合并前该实体在分 E-R 图中的全部属性,属性间就可能存在几余,即某一属性可以由其他属性确定
冗余属性的消除
在分 E-R图合并的过程中可能会出现实体联系的环状结构,即某一实体 A 与另一实体B 间有直接联系,同时A 又通过其他实体与实体B发生间接联系。通常,直接联系可以通过间接联系所表达,可消除直接联系。
冗余联系的消除
E-R 图的合并优化主要有以下三方面
1.9E-R图
共享性:指数据存储在不同的结点数据共享
自治性:指每结点对本地数据都能独立管理
可用性:指当某一场地故障时,系统可以使用其他场地上的副本而不至于使整个系统瘫痪
分布性:指数据在不同场地上的存储
特点
分片透明:指用户或应用程序不需要知道逻辑上访问的表具体是怎么分块存储的
复制透明:指采用复制技术的分布方法,用户不需要知道数据是复制到哪些节点,如何复制的。
位置透明:指用户无须知道数据存放的物理位置
逻辑透明:指用户或应用程序无需知道局部场地使用的是哪种数据模型
透明性
2.0分布式数据库
候选键
非候选键:组成候选码的属性就是主属性,其他的就是非主属性
候选键/非候选键推导法
五.数据库
实体类的对象表示现实世界中真实的实体,如人、物等
人的接口可以是显示屏、窗口、web 窗体、对话框、菜单、列表框、其他显示控制、条形码、二维码或者用户与系统交互的其他方法
系统接口涉及到把数据发送到其他系统,或者从其他系统接收数据
接口类(边界类)的对象为用户提供一种与系统合作交互的方式,分为人和系统两大类
控制类的对象用来控制活动流,充当协调者
类可以分为三种
参数多态:是应用比较广泛的多态,被称为最纯的多态。
包含多态:在许多语言中都存在,最常见的例子就是子类型化,即一个类型是另一个类型的子类型。
通用的多态
过载多态:是同一个名字在不同的上下文中所代表的含义不同。
强制多态:编译程序通过语义操作,把操作对象的类型强行加以变换,以符合函数或操作符的要求
特定的多态
多态
封装继承多态
单一责任原则(Sigle Responsibility Principle,SRP)。就一个类而言,应该仅有一个引起它变化的原因
开放-封闭原则(Open & Close Principle,OCP)。对扩展开放;对修改封闭
里氏替换原则(Liskov Substitution Principle,LSP)。子类型必须能够替换掉他们的基类型
依赖倒置原则(Dependence Inversion Principle, DP)。高层模块不应该依赖于低层模块,二者都应该依赖于抽象
接口分离原则(Interface Segregation Principle,ISP)。依赖于抽象,不要依赖于具体
重用发布等价原则(Release Reuse Equivalency Principle,REP)。重用的粒度就是发布的粒度。
共同封闭原则(Common Closure Principle,CCP)。一个变化若对一个包产生影响,则将对该包中的所有类产生影响,而对于其他的包不造成任何影响。
共同重用原则(Common Reuse Principle,CRP)。一个包中的所有类应该是共同重用的。如果重用了包中的一个类,那么就要重用包中的所有类。
无环依赖原则(Acyclic Dependencies Principle,ADP)。在包的依赖关系图中不允许存在环,即包之间的结构必须是一个无环图形
稳定依赖原则(Stable Dependencies Principle,SDP)。朝着稳定的方向进行依赖。
稳定抽象原则(Stable Abstractions Principle,SAP)。包的抽象程度应该和其稳定程度一致
面向对象设计的原则
面向对象分析(0biect-Oriented Analysis,OOA)的目的是为了获得对应用问题的理解。理解的目的是确定系统的功能、性能要求
认定对象
组织对象
描述对象间的相互作用
确定对象的操作
定义对象的内部信息
面向对象分析包含5个活动:
面向对象分析
面向对象设计(Object-Oriented Design,OOD)是将 OOA 所创建的分析模型转化为设计模型,其目标是定义系统构造蓝图。
识别类及对象
定义属性
定义服务
识别关系
识别包
OOD 在复用 OOA 模型的基础上,包含与 0OA对应如下五个活动。
面向对象设计
面向对象程序设计(Object-Oriented Programming,OOP)的实质是选用一种面向对象程序设计语言,采用对象、类及其相关概念所进行的程序设计
面向对象程序设计
六.面向对象
结构事物通常是模型的静态部分
包括类(Class)、接口(Imnterface)、协作(Collaboration).、用例(Use Case)、主动类(Active Class)、构件(Component)、制品(Artifact)、结点(Node)
结构事物
行为事物是模型的动态部分
包括交互(Interaction)、状态机(State Machine)、活动(Activity)
行为事物
分组事物是模型的组织部分
最主要的分组事物是包(Package)。包是把元素组织成组的机制
分组事物
注释事物是模型的解释部分
这些注释事物用来描述、说明和标注模型的任何元素
注释事物
事物
类图展现了一组对象、接口、协作和它们之间的关系
类图给出系统的静态设计视图
UML类图对系统的词汇,简单的协作,逻辑数据库模式,进行建模
对象图展现某一时刻一组对象以及它们之间的关系
描述了在类图中所建立的事物的实例的静态快照
对象图
用例图展现了一组用例,参与者以及它们之间的关系。
参与者是与系统交互的外部实体,可能是使用者,也可能是与系统交互的外部系统、基础设备等。
参与者
用例就是系统的一个功能
用例是从用户角度描述系统的行为,它将系统的一个功能描述成一系列的事件,这些事件最终对操作者产生有价值的观测结果。用例是一个类,它代表一类功能而不是使用该功能的某一具体实例。
用例
序列图是场景的图形化表示,描述了以时间顺序组织的对象之间的交互活动
序列图展示了一个用例和多个对象的行为
返回消息不用实现
序列图
通信图(协作图)强调收发消息的对象的结构组织,
通信图有路径。为了指出一个对象如何与另一个对象链接,可以在链的末端附上一个路径构造型
通信图有顺序号。为表示一个消息的时间顺序,可以给消息加一个数字前缀
通信图有两个不同于序列图的特性
通信图
状态图展现了一个状态机,它由状态、转换、事件和活动组成
状态图关注系统的动态视图
状态
事件触发转换(迁移)
活动(动作)可以在状态内执行,也可以在状态转换(迁移)时执行。
题
事件
状态图
活动图是一种特殊的状态图,它展现了在系统内从一个活动到另一活动的流程
活动图
构件图展现了一组构件之间的组织和依赖
构件图/组件图
部署图是用来对面向对象系统的物理方面建模的方法,展现了运行时处理结点以及其中构件(制品)的配置
部署图
交互图包含序列图,通信图,交互概览图,计时图
静态建模:类图、对象图、用例图动态建模:序列图、通信图、状态图、活动图物理建模:构件图、部署图
图
七.UML
前面讲过,社会化的分工越来越细,自然在软件设计方面也是如此,因此对象的创建和对象的使用分开也就成为了必然趋势。因为对象的创建会消耗掉系统的很多资源,所以单独对对象的创建进行研究,从而能够高效地创建对象就是创建型模式要探讨的问题。
创建型模式
在解决了对象的创建问题之后,对象的组成以及对象之间的依赖关系就成了开发人员关注的焦点,因为如何设计对象的结构、继承和依赖关系会影响到后续程序的维护性、代码的健壮性、耦合性等。
结构型模式
在对象的结构和对象的创建问题都解决了之后,就剩下对象的行为问题了,如果对象的行为设计的好,那么对象的行为就会更清晰,它们之间的协作效率就会提高
行为型模式
区别
定义一个用于创建对象的接口,让子类决定实例化哪一个类。
Factory Method使一个类的实例化延迟到其子类。
意图
●当一个类不知道它所必须创建的对象的类的时候。
●当一个类希望由它的子类来指定它所创建的对象的时候。
●当类将创建对象的职责委托给多个帮助子类中的某一个,并且你希望将哪一个帮助子类是代理者这一信息局部化的时候。
适用性
工厂方法【Factory Method】
提供一个创建一系列相关或相互依赖对象的接口,而无须指定它们具体的类
●一个系统要独立于它的产品的创建、组合和表示时。
●一个系统要够个产品系列中的一个来配置时。
●当要强调一系列相关的产品对象的设计以便进行联合使用时。
●当提供一个产品类库,只想显示它们的接口而不是实现时。
Concrete:具体的
抽象工厂【Abstract Factory】
将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。
当创建复杂对象的算法应该独立于该对象的组成部分以及它们的装配方式时。
当构造过程必须允许被构造的对象有不同的表示时。
Director:导演
建造者【Builder】
用原型实例指定创建对象的种类,并且通过复制这些原型创建新的对象。
●当一个系统应该独立于它的产品创建、构成和表示时。
●当要实例化的类是在运行时刻指定时,例如,通过动态装载。
●当一个类的实例只能有几个不同状态组合中的一种时。 建立相应数目的原型并克隆它们,可能比每次用合适的状态手工实例化该类更方便一些。
原型【Prototye】
保证一个类仅有一个实例,并提供一个访问它的全局访问点。
当类只能有一个实例而且客户可以从一个众所周知的访问点访问它时
当这个唯一实例应该是通过子类化可扩展的,并且客户无须更改代码就能使用一个扩展的实例时。
单例【Singleton】
将一个类的接口转换成客户希望的另外一个接口。Adapter 模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
想使用一个已经存在的类,而它的接口不符合要求。
想创建一个可以服用的类,该类可以与其他不相关的类或不可预见的类(即那些接口可能不一定兼容的类)协同工作。
想使用一个已经存在的子类,但是不可能对每一个都进行子类化以匹配它们的接口。对象适配器可以适配它的父类接口。
Adaptee:适应者 SpecificRequest:具体的请求
适配器【Adaper】
将抽象部分与其实现部分分离,使它们都可以独立地变化。
不希望在抽象和它的实现部分之间有一个固定的绑定关系。例如,这种情况可能是因为,在程序运行时刻实现部分应可以被选择或者切换。
类的抽象以及它的实现都应该可以通过生成子类的方法加以扩充。这是 Bridge 模式使得开发者可以对不同的抽象接口和实现部分进行组合,并分别对它们进行扩充。
对一个抽象的实现部分的修改应对客户不产生影响,即客户代码不必重新编译。(C++)想对客户完全隐藏抽象的实现部分。
有许多类要生成的类层次结构。
想在多个对象间共享实现(可能使用引用计数),但同时要求客户并不知道这一点。
桥接【Bridge】
将对象组合成树型结构以表示“部分-整体”的层次结构。Composite 使得用户对单个对象和组合对象的使用具有一致性。
想表示对象的部分整体层次结构。
组合【Composite】
在不影响其他对象的情况下,以动态、透明的方式给单个对象添加职责。
处理那些可以撤销的职责。
当不能采用生成子类的方式进行扩充时。一种情况是,可能有大量独立的扩展,为支持每一种组合将产生大量的子类,使得子类数目呈爆炸性增长。另一种情况可能是,由于类定义被隐藏,或类定义不能用于生成子类。
装饰【Decorator】
为子系统中的一组接口提供一个一致的界面,Facade 模式定义了一个高层接口,这个接口使得这一子系统更加容易使用。
客户程序与抽象类的实现部分之间存在着很大的依赖性。入Facade 将这个子系统与客户以及其他的子系统分离,可以提高子系统的独立性和可移植性。
当需要构建一个层次结构的子系统时,使用Facade 模式定义子系统中每层的入口点。如果子系统之间是相互依赖的,则可以让它们仅通过 Facdde 进行通信,从而简化了它们之间的依赖关系。
门面【Facade】
运用共享技术有效地支持大量细粒度的对象,
一个应用程序使用 了大量的对象 。
完全由于使用大量的对象,造成很大的存储开销。
对象的大多数状态都可变为外部状态。
如果删除对象的外部状态,那么可以用相对较少的共享对象取代很多组对象。
应用程序不依赖于对象标识。由于Flyweight对象可以被共享,所以对于概念上明显有别的对象,标识测试将返回真值。
享元【Flyweight】
为其他对象提供一种代理以控制对这个对象的访问。
适用于在需要比较通用和复杂的对象指针代替简单的指针的时候,常见情况有
远程代理(Remote Proxy)为一个对象在不同地址空间提供局部代表
虚代理(Virtual Proxy)根据需要创建开销很大的对象。
保护代理(Protection Proxy)控制对原始对象的访问,用于对象应该有不同的访问权限的时候。
智能引用(Smmart Reference)取代了简单的指针,它在访问对象时执行一些附加操作。典型用途包括:对指向实际对象的引用计数,这样当该对象没有引用时,可以被自动释放:当第一次引用一个持久对象时,将它装入内存;在访问一个实际对象前,检查是否已经锁定了它,以确保其他对象不能改变它。
代理【Proxy】
使多个对象都有机会处理请求,从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链,并沿着这条链传递该请求,直到有一个对象处理它为止。
有多个的对象可以处理一个请求,哪个对象处理该请求运行时刻自动确定
想在不明确指定接收者的情况下向多个对象中的一个提交一个请求。
可处理一个请求的对象集合应被动态指定。
责任链【Chain of Responsibility】
将一个请求封装为一个对象,从而使得可以用不同的请求对客户进行参数化;对请求排队或记录请求日志,以及支持可撤销的操作。
抽象出待执行的动作以参数化某对象。Command模式是过程语言中的回调(Callback)机制的一个面向对象的替代品。
在不同的时 刻指定、排列和执行请求。- 一个Command 对象可以有-一个与初始请求无关的生存期。如果一个请求的接收者可用一种与地址空间无关的方式表达,那么就可以将负责该请求的命令对象传递给另-一个不同的进程并在那儿实现该请求。
支持取消操作。Command的Execute操作可在实施操作前将状态存储起来,在取消操作时这个状态用来消除该操作的影响。Command 接口必须添加一一个Unexecute操作,该操作取消上- -次Execute调用的效果。执行的命令被存储在-一个历史列表中。可通过向后和向前遍历这一列表并分别调用Unexecute和Execute来实现重数不限的“取消”和“重做”。
支持修改日志。这样当系统崩溃时,这些修改可以被重做- -遍。在Command接口中添加装载操作和存储操作,可以用来保持变动的一一个一致的修改日志。从崩溃中恢复的过程包括从磁盘中重新读入记录下来的命令并用Execute操作重新执行它们。
Invoker:祈求者 Receiver:接收者
装饰器【Command】
给定一个语言,定义它的文法的一种表示,并定义一个解释器,这个解释器使用该表示来解释语言中的句子。
该文法简单。对于复杂的发文,文法的类层次变得庞大而无法管理。此时语法分析程序生成器这样的工具是更好的选择。它们无须构建抽象语法树即可解释表达式,这样可以节省空间还可能节省时间。
效率不是一个关键问题。最高效的解释器通常不是通过直接解释语法分析树实现的,而是首先将它们转换成另一种形式。不过,即使在这种情况下,转换器仍然可用该模式实现。
解释器Interpreter
提供一种方法顺序访问一个聚合对象中的各个元素,且不需要暴露该对象的内部表示。
访问一个聚合对象的内容而无须暴露它的内部表示
支持对聚合对象的多种遍历。
为遍历不同的聚合结构提供一个统一的接口。
Aggregate:聚合
迭代器【Iterator】
用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用,从而使其耦合松散,而且可以独立地改变它们之间的交互。
一组对象以定义良好但是复杂的方式进行通信,产生的相互依赖关系结构混乱且难以理解。
一个对象引用其他很多对象并且直接与这些对象通信,导致难以复用该对象。
想定制一个分布在多个类中的行为,而又不想生成太多的子类。
Colleague:同事
中介者Mediator
在不破坏封装性的前提下捕获一个对象的内部状态,并在对象之外保存这个状态。这样以后就可以将对象恢复到原先保存的状态。
必须保存一个对象在某一个时刻的(部分)状态,这样以后需要时它才能恢复到先前的状态。
如果一个用接口来让其他对象直接得到这些状态,将会暴露对象的实现细节并破坏对象的封装性。
Originator :发起人 Caretaker:看管人
备忘录Memente
定义对象间的一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。
当一个抽象模型有两个方面,其中一个方面依赖于另一个方面,将这两者封装在独立的对象中以使它们可以各自独立地改变和复用。
当一个对象的改变需要同时改变其他对象,而不知道具体有多少对象有待改变时
当一个对象必须通知其他对象,而它又不能假定其他对象是谁,即不希望这些对象是紧耦合的
观察者Observer
允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类。
一个对象的行为决定于它的状态,并且它必须在运行时刻根据状态改变它的行为
一个操作中含有庞大的多分支的条件语句,且这些分支依赖于该对象的状态。这个状态常用一个或多个枚举常量表示。通常,有多个操作包含这一相同的条件结构。State模式将每一个条件分支放入一个独立的类中。这使得开发者可以根据对象白身的情况将对象的状态作为一个对象,这一对象可以不依赖于其他对象独立变化。
状态【State】
定义一系列的算法,把它们一个个封装起来,并且使它们可以相互替换。此模式使得算法可以独立于使用它们的客户而变化。
许多相关的类仅仅是行为有异。“策略\"提供了一种用多个行为中的一个行为来配置个类的方法。
算法使用客户不应该知道的数据。可使用策略模式以避免暴露复杂的、与算法相关的数据结构。
策略【Strategy】
定义一个操作中的算法骨架,而将一些步骤延迟到子类中。Template Method 使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步。
一次性实现一个算法的不变的部分,并将可变的行为留给子类来实现
各子类中公共的行为应被提取出来并集中到一个公共父类中,以避免代码重复。
控制子类扩展。模板方法旨在特定点调用“hook”操作(默认的行为,子类可以在必要时进行重定义扩展),这就只允许在这些点进行扩展。
模板方法【Template Method】
表示一个作用于某对象结构中的各元素的操作。它允许在不改变各元素的类的前提下定义作用于这些元素的新操作。
一个对象结构包含很多类对象,它们有不同的接口,而用户想对这些对象实施一些依赖于其具体类的操作。
需要对一个对象结构中的对象进行很多不同的并且不相关的操作,而又想要避免这些操作“污染”这些对象的类。Vsitor 使得用户可以将相关的操作集中起来定义在一个类中。当该对象结构被很多应用共享时,用 isitor 模式让每个应用仅包含需要用到的操作。
定义对象结构的类很少改变,但经常需要在此结构上定义新的操作。改变对象结构类需要重定义对所有访问者的接口,这可能需要很大的代价。如果对象结构类经常改变那么可能还是在这些类中定义这些操作较好。
访问者【Visitor】
八:设计模式
1.计算机系统层次结构图
2.程序顺序执行的特征
3.三态模型
判断是否发生死锁的公式:m>=n*(k-1)+1 n:进程数 m:不会发生死锁的最小资源数 k:每个进程需要的资源数
死锁的处理策略主要有4种:鸵鸟策略(即不理睬策略)、预防策略、避免策略和检测与解除死锁。
4.死锁
先分配,再申请
5.进程资源图:
6.最大资源和已分配资源数
时间局限性是指如果程序中的某条指令一旦执行,则不久的将来该指令可能再次被执行;
空间局限性是指一旦程序访问了某个存储单元,则在不久的将来,其附近的存储单元也最有可能被访问
先看状态位,在看访问位,然后修改位
7.程序局部性原理
8.分页存储管理
9.段页式存储管理
单缓存区
双缓冲区
10.缓存区
先来先服务
最短寻道时间优先
扫描算法/电梯调度算法
循环扫描算法
循环调度算法
11.磁盘调度算法
索引块从0开始
12.多级索引结构
全路径 D:\\Program\\Java\\f1.java
绝对路径 D:\\Program\\Java\\
相对路径 Java\\f1.java
13.文件目录
位示图:用二进制的一位来表示一个物理块的使用情况。
14.位示图
九.操作系统
无直接耦合。指两个模块之间没有直接的关系,它们之间不传递任何信息。
数据耦合。指两个模块之间有调用关系,传递的是简单的数据值,相当于高级语言中的值传递。
标记耦合。指两个模块之间传递的是数据结构。
控制耦合。指一个模块调用另一个模块时,传递的是控制变量,被调用模块通过该控制变量的值有选择地执行模块内的某一功能。
外部耦合。模块间通过软件之外的环境联结
公共耦合。指通过一个公共数据环境相互作用的那些模块间的耦合
内容耦合。当一个模块直接使用另一个模块的内部数据,或通过非正常入口转入另一个模块内部时,这种模块之间的耦合称为内容耦合。
1.耦合
偶然内聚(巧合内聚)。指一个模块内的各处理元素之间没有任何联系。
逻辑内聚。指模块内执行若干个逻辑上相似的功能,通过参数确定该模块完成哪一个功能。
时间内聚。把需要同时执行的动作组合在一起形成的模块称为时间内聚模块。
过程内聚。指一个模块完成多个任务,这些任务必须按指定的过程执行。
通信内聚。指模块内的所有处理元素都在同一个数据结构上操作,或者各处理使用相同的输入数据或者产生相同的输出数据。
顺序内聚。指一个模块中的各个处理元素都密切相关于同一功能且必须顺序执行,前一功能元素的输出就是下一功能元素的输入。
功能内聚。这是最强的内聚,指模块内的所有元素共同作用完成一个功能,缺一不可
2.内聚
整个系统是一个整体,解决复杂问题的一个很重要的原则就是把它分解成多个小问题分别处理
自顶向下的原则。首先抓住系统总的功能目的,然后逐层分解,即先确定上层模块的功能,再确定下层模块的功能。
信息隐蔽、抽象的原则。上层模块只规定下层模块做什么和所属模块间的协调关系,但不规定怎么做,以保证各模块的相对独立性和内部结构的合理性,使得模块与模块之间层次分明,易于理解、实施和维护。
一致性原则。要保证整个软件设计过程中具有统一的规范、统一的标准和统一的文件模式等。
明确性原则。每个模块必须功能明确、接口明确,消除多重功能和无用接口。
模块之间的耦合尽可能小,模块的内聚度尽可能高。
一个模块被其他模块调用时,直接调用它的模块个数称为模块的扇入系数。
一个模块直接调用其他模块的个数称为模块的扇出系数:
模块的扇入系数和扇出系数要合理。
模块的规模适当。
模块的作用范围应该在其控制范围之内。
3.系统结构设计原则
在系统规划和系统分析阶段通过文档进行沟通。
这里的文档主要包括可行性研究报告、总体规划报告、系统开发合同和系统方案说明书等。
用户与系统分析人员
通过文档在项目期内进行沟通。
这里的文档主要有系统开发计划(包括工作任务分解表、PERT图、甘特图和预算分配表等)、系统开发月报以及系统开发总结报告等项目管理文件。
系统开发人员与项目管理人员
系统测试人员可以根据系统方案说明书、系统开发合同、系统设计说明书和测试计划等文档对系统开发人员所开发的系统进行测试。
系统测试人员再将评估结果撰写成系统测试报告
系统测试人员与系统开发人员
在系统运行期间进行沟通。
用户通过系统开发人员撰写的文档运行系统。这里的文档主要是用户手册和操作指南。
系统开发人员与用户
这里的文档主要有系统设计说明书和系统开发总结报告。
有的开发总结报告写得很详细,分为研制报告、技术报告和技术手册3个文档
系统开发人员与系统维护人员
用户在使用信息系统的过程中,将运行过程中的问题进行记载,形成系统运行报告和维护修改建议
系统维护人员根据维护修改建议以及系统开发人员留下的技术手册等文档对系统进行维护和升级。
用户与维修人员
4.系统文档
数据字典有以下4类条日:数据项、数据流、数据存储和基本加工。
数据项是组成数据流和数据存储的最小元素
外部实体不在数据字典中
5.数据字典
十.结构化开发
1)初始级(Iitial)
建立了基本的项目管理过程和实践来跟踪项目费用、进度和功能特性,有必要的过程准则来重复以前在同类项目中的成功。
2)可重复级(Repeatable)
管理和工程两方面的软件过程已经文档化、标准化,并综合成整个软件开发组织的标准软件过程。
3)已定义级(Defimed)
制定了软件过程和产品质量的详细度量标准。
4)已管理级(Managed)
加强了定量分析,通过来自过程质量反馈和来自新观念、新技术的反馈使过程能不断持续地改进
5)优化级(Optimmized)
CMM成熟度级别
过程域未执行或未得到CL1中定义的所有目标
CL0(未完成的)
其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品,以实现支持过程域的特定目标。
CL1(已执行的)
其共性目标集中于已管理的过程的制度化。
CL2(已管理的)
其共性目标集中于已定义的过程的制度化。
CL3(已定义级的)
其共性目标集中于可定量管理的过程的制度化
CL4(定量管理的)
使用量化(统计学)手段改变和优化过程域,以满足客户要求的改变和持续改进计划中的过程域的功效
CL5(优化的)
CMMI成熟度级别
描述:按工序将问题化简,将功能的实现与设计分开,便于分工协作,即采用结构化的分析与设计方法将逻辑实现与物理实现分开。
软件实现方法是成熟的;
项目周期较短。
适应情形:
可使开发人员采用规范的方去:
严格地规定了每个阶段必须提交的文档;
要求每个阶段交出的所有产品都必须保证质量,经过小组的仔细验证。
优点:
不适用于需求不明确的产品
缺点:
瀑布模型
描述:把软件产品作为一系列的增量构件来分析、设计、编码、测试。每个构件由多个相互作用的模块构成
适用于需求经常改变的软件开发过程。
人员不足的情况下
包含瀑布模型所有优点
人员分配灵活,刚开始不用投入大量人力资源,
可以快速的推出核心产品。
逐步增加产品功能可以使用户有较充裕的时间学习和适应新产品。
后边的增量依赖于前边的增量,前边开发不好可能会造成后边的不稳定
增量(渐增)模型
描述:可以快速建立一个可以运行的程序,快速开发出一个让用户看得见的产品,再用户使用中不断优化完善
需求不明确,不完整,不准确
需求经常变化
陌生领域产品开发
减少由于需求不明显带来的开发风险
快速开发出一个让用户看得见的产品,再用户使用中不断优化完善
所选用的开发技术和工具不一定符合主流发展
快速建立的系统架构加上连续的迭代可能导致产品质量下降
不适用于规模很大,很复杂的产品
快速原型模型
增量(渐增)模型可以快速提供一个可交付的产品
快速原型模型可以快速提高一个有核心功能的产品,让业务使用看看是否符合需求
快速原型模型和增量(渐增)模型的区别
描述:在每个阶段之前都增加了风险分析过程的快速原型模型
特别适用于庞大、复杂并是有高风险的系统,
适用于内部开发的大规模软件项目。
主要优势在于它是风险驱动的。
减少了过多测试或测试不足所带来的风险;
采用螺旋模型需要具有相当丰富的风险评估经验和专业知识
如果未能识别风险,会造成重大损失
螺旋模型
描述:
适合于面向对象的开发方法
喷泉模型使开发过程具有迭代性和无间隙性,
允许各开发活动交叉、迭代地进行
这种模型要求严格管理文档,使得审核的难度加大。
喷泉模型
1.软件过程模型
XP 是一种轻量级(敏捷)、高效、低风险、柔性、可预测的、科学的软件开发方式。它由价值观、原则、实践和行为4个部分组成
4 大价值观:沟通、简单性、反馈和勇气。
极限编程(XP)
水品法认为每一个不同的项目都需要一套不同的策略、约定和方法论,
水晶法(Crystal)
并列争求法使用迭代的方法,其中,把每 30天一次的迭代称为一个“冲刺”,并按需求的优先级别来实现产品
并列争求法(Scrum)
ASD有6个基本的原则:有一个使命作为指导:特征被视为客户价值的关键点:过程中的等待是很重要的,
自适应软件开发(ASD)
2.敏捷方法
功能需求。考虑系统要做什么,在何时做,在何时以及如何修改或升级。
性能需求。考虑软件开发的技术性指标。例如,存储容量限制、执行速度、响应时间及吞吐量。
用户或人的因素。考虑用户的类型。例如,用户对使用计算机的熟练程度用户理解、使用系统的难度
环境需求。考虑未来软件应用的环境,包括硬件和软件。
界面需求。考虑来自其他系统的输入,到其他系统的输出,对数据格式的特殊规定,对数据存储介质的规定。
文档需求。考虑需要哪些文档,文档针对哪些读者。
数据需求。考虑输入、输出数据的格式,接收、发送数据的频率,数据的准确性和精度,数据流量,数据需保持的时间。
资源使用需求。考虑软件运行时所需要的数据、其他软件、内存空间等资源:软件开发、维护所需的人力、支撑软件、开发设备等。
安全保密要求。考虑是否需要对访问系统或系统信息加以控制,隔离用户数据的方法
可靠性要求。考虑系统的可靠性要求,系统是否必须检测和隔离错误
3.软件需求
信息系统测试应包括软件测试、硬件测试和网络测试
意义:系统测试是为了发现错误而执行程序的过程,成功的测试是发现了至今尚未发现的错误
目的:测试的目的就是希望能以最少的人力和时间发现潜在的各种错误和缺陷。
应尽早并不断地进行测试。
测试工作应该避免由原开发软件的人或小组承担,
在设计测试方案时,不仅要确定输入数据,而且要根据系统功能确定预期输出结果
在设计测试用例时,不仅要设计有效、合理的输入条件,也要包含不合理、失效的输入条件
在设计测试用例时,不仅要检验程序是否做了该做的事,还要检验程序是否做了不该做的事
严格按照测试计划来进行,避免测试的随意性。
妥善保存测试计划、测试用例,作为软件文档的组成部分,为维护提供方便。
测试例子都是精心设计出来的,可以为重新测试或追加测试提供方便。
系统测试阶段的测试目标来自于需求分析阶段
原则:
4.系统测试与调试
模块接口
局部数据结构
重要的执行路径
出错处理
边界条件
单元测试的内容:
5.单元测试
非增量式集成可以对模块进行并行测试,能充分利用人力,并加快工程进度。但这种方法容易混乱,出现错误不容易查找和定位。
一种是非增量集成,分别测试各个模块,再把这些模块组合起来进行整体测试;
增量式测试的范围一步步扩大,错误容易定位,更易于对接口进行彻底测试,并且可以运用系统化的测试方法
一种是增量集成,即以小增量的方式逐步进行构造和测试。
集成测试有两种方法
自顶向下集成测试:是一种构造软件体系结构的增量方法。模块的集成顺序为从主控模块(主程序)开始,沿着控制层次逐步向下
自底向上集成测试:就是从原子模块(程序结构的最底层构件)开始进行构造和测试。
回归测试:每当加入一个新模块作为集成测试的一部分时,软件发生变更,都要重新回归测试
自顶向下:不需要编写驱动模块,需要编写桩模块
自底向上:需要编写驱动模块,不需要编写桩模块
增量集成策略
6.集成测试
黑盒测试也称为功能测试,在完全不考虑软件的内部结构和特性的情况下,测试软件的外部特性
是否有错误的功能或遗漏的功能?
界面是否有误?输入是否正确接收?输出是否正确?
是否有数据结构或外部数据库访问错误?
性能是否能够接受?
是否有初始化或终止性错误?
黑盒测试主要是为了发现以下几类错误
等价类划分法将程序的输入域划分为若干等价类,然后从每个等价类中选取一个代表性数据作为测试用例。
等价类划分有两种不同的情况:有效等价类和无效等价类
等价类划分
边界值分析
错误推测
因果图
常用的黑盒测试技术
7.黑盒测试
白盒测试也称为结构测试,根据程序的内部结构和逻辑来设计测试用例,对程序的路径和过程进行测试,检查是否满足设计的需要
使被测试程序中的每条语句至少执行一次
语句覆盖
使得被测程序中的每个判定表达式至少都通过一次真和假值分支逻辑,因此判定覆盖也称为分支覆盖。
判定(分支)覆盖
使得每一判定语句中每个逻辑条件的各种可能的值至少满足一次。
条件覆盖
判定覆盖和条件覆盖的合集
判定/条件覆盖
使得每个判定中条件的各种可能值的组合都至少出现一次
条件组合覆盖
指覆盖被测试程序中所有可能的路径
路径覆盖
逻辑覆盖
使得循环中的每个条件都得到验证
循环覆盖
保证程序的每一条独立路径都执行过,即程序中的每条可执行语句至少执行一次
基本路径测试
常用的白盒测试技术
8.白盒测试
V(G)=m-n+2 V(G)是环路个数,m是有向弧数,n是节点数
V(G)=闭合区间+1
计算有向图G的环路复杂性的公式为:
9.McCabe 度量法
可理解性。指别人能理解系统的结构、界面、功能和内部过程的难易程度
可测试性。诊断和测试的容易程度取决于易理解的程度。
可修改性。模块的耦合、内聚、作用控制范围的关系等对可修改性的影响
10.系统可维护性的评价指标
文档是软件可维护性的决定因素
系统文档描述系统设计、实现和测试等各方面的内容。
软件系统的文档可以分为用户文档和系统文档两类
11.维护与软件文档
编写高质量文档可以提高软件开发的质量
文档也是软件产品的一部分,没有文档的软件就不能称之为软件。
软件文档的编制在软件开发工作中占有突出的地位和相当大的工作量
高质量文档对于软件产品的效益有着重要的意义
总的来说,软件文档只好不坏,选项中说软件文档不好的就是不正确的
12.软件文档
正确性维护。正确性维护是指改正在系统开发阶段已发生而系统测试阶段尚未发现的错误、
适应性维护。适应性维护是指使应用软件适应信息技术变化和管理需求变化而进行的修改。
完善性维护。这是为扩充功能和改善性能而进行的修改,主要是指对已有的软件系统增加功能与性能特征。
预防性维护。为了改进应用软件的可靠性和可维护性,为了适应未来的软/硬件环境的变化,应主动增加预防性的新的功能,
13.软件维护的内容一般有以下几个方面
可靠性是指一个系统对于给定的时间间隔内、在给定条件下无失效运作的概率
MTTF/ (1+MTTF)来度量,其中 MTTF 为平均无故障时间。
可靠性
可用性是在给定的时间点上,一个系统能够按照规格说明正确运作的概率。
MTBF/(1+MTBF)来度量,其中MTBF 为平均失效间隔时间。
可用性
可维护性是在给定的使用条件下,在规定的时间间隔内,使用规定的过程和资源完成维护活动的概率
1/(1+MTTR)来度量,其中 MTTR 为平均修复时间。
可维护性
14.软件可靠性,可用性,可维护性
((n-1)*n)/2 n是节点
15.沟通路径
Gantt图能清晰地描述每个任务从何时开始,到何时结束,任务的进展情况以及各个任务之间的并行性。
优缺点
Gantt 图
PERT 图不仅给出了每个任务的开始时间,结束时间,所需时间,还给出了任务之间的关系,即哪些任务完成后才能开始另外一些任务,
还给出了如期完成整个工程的关键路径。
图中的松弛时间则反映了完成某些任务时可以推迟其开始时间或延长其所需完成的时间。
PERT 图不能反映任务之间的并行关系,
PERT 图
项目活动图
16.管理图
十一.软件工程
软件配置管理其主要目标包括:变更标识、变更控制、版本控制、确保变更正确的实现、变更报告
软件配置管理其主要内容包括:版本管理、配置支持、变更支持、过程支持、团队支持、变化报告、审计支持
上下为两个不同的版本
软件配置管理其主要内容包括:软件配置标识、变更管理、版本控制、系统建立、配置审核、配置状态报告
1.软件配置管理
识别风险的一种方法是建立风险条目检查表
产品规模。与要开发或要修改的软件的总体规模相关的风险
商业影响。与管理者或市场所施加的约束相关的风险。
客户特性。与客户的素质以及开发者和客户定期沟通的能力相关的风险。
过程定义。与软件过程定义的程度以及该过程被开发组织遵守的程度相关的风险
开发环境。与用来开发产品的工具的可得性及质量相关的风险。
开发技术。与待开发软件的复杂性及系统所包含技术的“新奇性”相关的风险。
人员才干及经验。与软件工程师的总体技术水平及项目经验相关的风险。
已知风险和可预测风险类型
性能风险。产品能够满足需求且符合其使用目的的不确定程度。
成本风险。能够维持项目预算的不确定程度。
支持风险。开发出的软件易于纠错、修改及升级的不确定程度
进度风险。能够维持项目进度且按时交付产品的不确定程度。
风险因素定义方式
风险识别
在软件开发过程中进行风险分析时,风险控制活动的目的是辅助项目组建立处理风险的策略,有效的策略应考虑风险避免、风险监控、风险管理及意外事件计划
应对风险最好的办法应该是主动避免风险
风险控制
不确定性是指风险可能发生也可能不发生;
损失是指如果风险发生,就会产生恶性后果。
在进行风险分析时,重要的是量化每个风险的不确定程度和损失程度。
一般认为软件风险包含两个特性:不确定性和损失。
项目风险
技术风险
市场,策略,销售,管理,预算风险
商业风险
风险的类型
风险管理
风险预测从两个方面评估风险,即风险发生的可能性以及风险发生所产生的后果
风险暴露度公式:RE=P*C P是风险发生的概率C是风险发生时带来的项目成本
风险预测
定义风险参照水准是风险评估活动常用的技术
风险评估
ISO/EC9126软件质量模型由3个层次组成:第一层是质量特性,第二层是质量子特性,第三层是度量指标。
时间特性(Time behavior)。与响应和处理时间以及软件执行其功能时的吞吐量有关的软件属性
资源特性(Resource behavior)。与软件执行其功能时,所使用的资源量以及使用资源的持续时间有关的软件属性
效率
适应性(Suitability)。与对规定任务能否提供一组功能以及这组功能是否适合有关的软件属性
准确性(Accurateness)。与能够得到正确或相符的结果或效果有关的软件属性
互用性(Interoperability)。与其他指定系统进行交互操作的能力相关的软件属性
依从性(Compliance)。使软件服从有关的标准、约定、法规及类似规定的软件属性
安全性(Security)。与避免对程序及数据的非授权故意或意外访问的能力有关的软件属性。
功能性
成熟性(Matuity)。与由软件故障引起失效的频度有关的软件属性。
容错性(Fault tolerance)。与在软件错误或违反指定接口的情况下维持指定的性能水平的能力有关的软件属性。
易恢复性(Recoverability)。与在故障发生后,重新建立其性能水平并恢复直接受影响数据的能力,以及为达到此目的所需的时间和努力有关的软件属性。
易理解性(Understandability)。与用户为理解逻辑概念及其应用所付出的劳动有关的软件属性。
易学性(Learnability)。与用户为学习其应用(例如操作控制、输入、输出)所付出的努力相关的软件属性
易操作性(Operability)。与用户为进行操作和操作控制所付出的努力有关的软件属性。
易使用性
易分析性(Analyzability)。与为诊断缺陷或失效原因,或为判定待修改的部分所需努力有关的软件属性。
易改变性(Changeability)。与进行修改、排错或适应环境变换所需努力有关的软件属性。
稳定性(Stability)。与修改造成未预料效果的风险有关的软件属性。
易测试性(Testability)。为确认经修改软件所需努力有关的软件属性。
一致性(Confonmance)。使软件服从与可移植性有关的标准或约定的软件属性。
适应性(Adaptability)。与软件转移到不同环境时的处理或手段有关的软件属性。
易安装性(mstallability)。与在指定环境下安装软件所需努力有关的软件属性
易替换性(Replaceability)。与一软件在该软件环境中用来替代指定的其他软件的可能和努力有关的软件属性。
可移植性
各质量特性和质量子特性的含义
6.ISO/EC 9126 软件质量模型
7.Mc Call 软件质量模型
十二.软件工程
防火墙技术经历了包过滤、应用代理网关和状态检测技术三个发展阶段
按照受保护程序,从高到低正确的排列次序为--内网、DMZ 和外网
防火墙的工作层次是决定防火墙效率及安全的主要因素--防火墙工作层次越高,工作效率越低,安全性越高
包过滤防火墙对数据包的过滤依据包括:源IP 地址,源端口号,目的IP 地址
包过滤防火墙对网络层的数据报文进行检查
包过滤防火墙
应用代理网关防火墙是内部网和外部网的隔离点,它可对应用层的通信数据流进行监控和过滤
应用代理网关防火墙
状态检测技术防火墙
防火墙
计算机病毒的特征包括:传播性、隐蔽性、感染性、潜伏性、触发性、破坏性等
病毒
目的是使计算机或网络无法提供正常的服务
拒绝服务攻击是不断向计算机发起请求来实现的
拒绝服务攻击(Dos攻击)
攻击者发送一个目的主机已经接受过的报文来达到攻击目的
攻击者利用网络监听或者其他方式盗取认证凭据,之后再重新发送给认证服务器。
主要用于身份认证过程,目的是破坏认证的正确性。
重放攻击
使用某些合法用户的账号和口令登录到目的主机,然后再实施攻击活动
口令入侵攻击
被伪装成程序或游戏,当用户下载了带有木马的软件或附件时,这个程序就会向黑客发起连接请求,建立连接后黑客就实施攻击活动。
特洛伊木马攻击
采用端口扫描找到系统漏洞从而实施攻击
端口欺骗攻击
攻击者可以接收某一网段在同一条物理通道上传输的所有信息,
使用网络监听可以轻松截取包括账号和口令在内的信息资料
网络监听攻击
产生的IP数据包为伪造的源IP地址,以便冒充其他系统或发件人的身份。
IP欺骗攻击
SQL注入攻击
入侵检测技术:专家系统、模型检测、简单匹配
网络攻击
HTTP:超文本传输协议-默认端口号:80HTTPS:超文本传输安全协议-默认端口号:443FTP:文件传输协议-默认端口号:20/21SSH(Linux远程管理):安全壳协议-默认端口号:22TELNET:远程登录管理-默认端口号:23 SMTP:简单邮件传输协议-默认端口号:25TFTP:简单文件传输协议-默认端口号: 69POP3:邮局协议(第三个版本)-默认端口号: 1107.RPC:远程过程调用协议 8.NTP:网络时间协议9.DNS:域名解析系统10.DHCP:动态主机配置协议11.IMAP4:互联网信息访问协议(第四个版本)12.SMBD:提供文件共享和打印服务的服务器进程13.NMBD:客户端能浏览服务器的进程
网络安全常见协议
网络安全
十三.信息安全
物理层的互联设备有中继器和集线器
数据链路层的互联设备有网桥和交换机
网络层的互联设备有路由器
应用层互联设备有网关
参考模型共有7层,由低层至高层分别为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
网络设备
协议簇
可靠传输、连接管理、差错校验和重传、流量控制、拥塞控制、端口寻址
其中流量控制采用的是:可变大小的滑动窗口协议
TCP
不可靠、无连接、端口寻址
UDP
TCP/UDP
SMTP 发送简单邮件协议
MIME 发送扩展邮件协议
POP3 接收邮件协议
邮件
地址解析协议(ARP)及反地址解析协议(RARP)是网络层中的一个协议。
ARP的作用是将正P地址转换为物理地址,
RARP的作用是将物理地址转换为正地址。
单播传送响应,广播传输请求
ARP和RARP
URl
DNS域名查询的次序是:本地的hosts文件→本地DNS缓存→本地DNS服务器一根域名服务器。
DNS
IPV4是32位
IPV6是128位
IPV4/IPV6
ipconfig/release:DHCP 客户端手工释放IP地址
ipconfig/flushdns:清除本地DNS缓存内容
ipconfig/displaydns:显示本地DNS内容
ipconfig/registerdns:DNS 客户端手工向服务器进行注册
ipconfig:显示所有网络适配器的IP地址、子网掩码和缺省网关值
ipconfig/all:显示所有网络适配器的完整 TCP/IP 配置信息,包括 DHCP 服务是否已启动
ipconfig/renew:DHCP 客户端手工向服务器刷新请求(重新申请IP 地址)
Windows命令
路由
十四.计算机网络
走迷宫问题,如果不行在重新来
回溯法
大问题化简小问题,将所有小问题解决在合并
分治法
大问题化简小问题,并保持所有小问题的解,避免重复计算,获取全局最优解
动态规划法
每次求得局部最优解,将局部最优解累加起来就接近全局最优解
贪心法
十五.算法
软件设计师
0 条评论
回复 删除
下一页