计算机专业自考笔记
2021-06-25 17:07:52 20 举报AI智能生成
计算机专业考试自学笔记
作者其他创作
大纲/内容
数据结构
线性表
定义和基本运算
定义：a1-an的有限序列
基本运算：
空表
求表长度
获取某一位（下标）的链表节点
获取值为x在链表中的节点位置（下标）
插入一个新节点
删除一个节点
顺序存储和基本运算
顺序表
线性表中的数据，按照一定的逻辑关系，依次排列在其中（简单理解为数组）
数据结构为：一个struct中，有一个变量为数组array[]，以及一个长度标识，记录了array的长度
顺序表的运算
查找运算
array[i]直接下表访问
插入运算
在1...x...end中x的位置插入一个元素，则需要将从x之后的元素整体后移动，然后将新元素插入到x的位置，并且总长度的记录变量+1
删除运算
在1...x...end中x的位置删除一个元素x，则需要将从x之后的元素整体前移动，然后将元素x删除，并且总长度的记录变量-1
线性表的链式存储
单链表
数据结构为：struct中包含一个类型的变量对象以及一个指向下一个链表地址的指针next
单链表的基本运算
链表的建立
头插法
新数据在旧数据之前，链表顺序和插入顺序相反
尾插法
新数据在旧数据之后，链表顺序和插入顺序相同
查找运算
查找第i个元素，必须从头指针开始，计数j=0，然后依次指向下一个指针地址指向的对象，在比较if(i==j)如果等于则为找到，否则重复上述过程
查找值k的方法，和上述相同，只不过是要比较值k和链表节点中存储的值是否相等，相等则为找到，否则继续偏移
插入运算
首先将p指针移动到需要插入的位置x，将现有x位置的元素的地址保存到新增元素节点的指针中保存，然后把之前指向x元素地址的指针指向新增的元素地址
删除运算
指针移动到位置i，将i-1位置处节点的指针指向i+1位置处的元素地址，然后删除i节点
循环链表
链表尾指针地址保存起始节点的地址，形成环形链表
双向链表
在环形链表的数据结构中，新增一个pre指针，用于保存当前节点的上一个节点地址，双向链表可以避免查找节点的时候只能单向向后查找数据，而可以往前查找
双向链表在插入和删除的时候，需要同时修改pre指针和next两个指针
顺序表和链表的比较
数组和链表的区别
栈和队列
栈的定义
限定只能从一个方向删除和新增数据的线性表，新增称为入栈，删除称为出栈
因为栈是受限制的线性表，所以我们理解为数组的下标0为栈底，栈底始终保持不变，栈顶则是根据新增或者删除的数据对象进行改变的
数据结构为：struct中包含数组对象array[]，以及一个int变量top标识栈顶的位置
顺序栈的基本运算方法
置空栈
将struct中的top指针值赋值为-1（这里不能是0，因为数组0的下标代表的是第一个元素，而这里是将栈置空）
判断满栈
判断if(arraySize - 1 == top)
判断空栈
判断struct中的if(top == -1)
入栈
将新数据添加到栈顶，然后top+1
出栈
将栈顶的数据删除，然后top-1
取栈顶元素
获取元素array[top - 1]
栈的链式存储&运算
将栈的数据结构方式改为链表的形式，实现思路是，每新增一个数据，就把新增的元素，入栈到链表的起始处，同样出栈的时候也是从起始处开始
数据结构为：data+下一个节点的地址指针p，第一个栈元素的next指针为null，以后新增元素的next都指向前一个。另外需要一个top指针，用于始终指向栈顶
运算方式参考上面数组的6个方式，主要是操作判断指针next和top指针。另外链式存储不存在满栈
栈的应用
编程中的括号符号匹配运算
字符串回文判断（abccba就是回文的）
递归算法
队列
也是一种首先是的顺序表，限制是只允许顺序表的一边插入数据（入队），而另一边删除数据（出队）
数据结构为：struct中一个元素对象数组，以及两个int变量front（队列头），rear（队列尾）
队列运算&判断
空队列
fonrt==rear
入队
新增一个元素到数组对象中，并且rear+1
出队
删除数组对象中的第0个元素，并且front+1
数据结构
struct结构体中，包含一个array,以及一个记录开始位置的int变量front和一个记录尾部位置的变量rear
循环队列
循环队列就是将数组对象假想成当超过数组最大值后，rear指针从新指回栈顶，循环利用
循环队列的问题是，如果rear追上了front，则说明队列已满，因为判断队列是否为空也是判断front是否等于rear，在环形队列中就无法判断是满，还是空，所以有几种方法
1.在队列中引入计数器，计算一共现在有多少个元素个数
2.设立一个标识变量，用来标识是否是填满的，还是出队空了
3.在入队循环队列是，判断rear+1以后是否等于front，等于则标识为满队列了
链队列
用链表的形式存储数据的队列，限制表头删除，表位插入的单链表
数据结构为：
struct中一个数据元素的对象，以及一直指针next
另外需要创建两个struct类型的指针对象，用于指向链表头和链表尾
运算
运算逻辑和数组队列基本相同，只是一个是判断下标，一个判断指针对象
栈和队列的应用
中缀，后缀表达式
中缀
符号在两个数字中间如：8*9
后缀
计算时，从表达式的左边开始向右查找，找到第一个符号，记录位置为x,则此符号运算的数字是x-2和x-1，然后将算后的结果继续依照下一个符号累计向左计算
如：中缀为8+5*(9-1)=后缀为8591-*+
第一步：从8-5-9-1--，找到第一个符号减号，然后计算9-1
第二部：将9-1的结果8，然后用8*5
第三部：将8*5=40的结果+8，得出最后的结果48
中缀表达式和后缀表达式的转换
后缀的优势是：不仅可以免除括号运算符，也可以根据从左到右的运算规则，避免去记录优先级之类的算法规则
多维数组&广义表
多维数组定义和运算
按照行存储数据
a[i][j]赋值存储是，先把a[i][j]中j的数据全部存储完，i在加一
按照列存储数据
a[i][j]赋值存储时，先把i中的数组全部第一个复制完，然后j+1在把i从0开始赋值
矩阵的压缩存储
对称矩阵
对称矩阵-根据对角线一半为空时用一维数组保存[a00,a10,a11,a20,a21,a22...]
三角矩阵
根据对角线平分，一边是要存储的数据，另一边是常量c，存储方式和对称矩阵相同，只是在数组最后加上常量c的值
稀疏矩阵
稀疏矩阵：在多维数组中，有些值为0，有些不为0，且多为0的情况下。用三维数组来保存稀疏矩阵，i,j,v来保存，i标识行，j标识y，v标识具体的值数值，这样就可以保存下所有不为0的值
广义表基础
线性表的推广：线性表中，元素只是具体的值或者树。如果允许其元素存储数据为对象，则就是广义表
广义表中的元素对象，也可以是一个对象，这样层层嵌套
广义表例子及说明
A=()：空表
B=(a)：B是一个具有1个元素，长度为1的广义表
C=(a,(b,c))：C是第一个元素是原子，第二个元素是子表，长度为2的广义表
D=(A,B,C)=((),(a),(a,(b,c)))：D是第一个元素为空表的子表，第二个元素是有一个原子的子表，第三个元素是子表嵌套一个元素和一个子表，长度为3的广义表
表头-广义表的第一个元素，为表头
表尾-广义表表头以后所有的元素统称为表尾
广义表的基本运算
获取表头，获取表尾，计算长度length，计算深度deep
广义表的存储结构
广义表的数据结构通常是链式的，也就是指针生成的链表
数据结构struct是
tag：标识为0标识是子表，1标识原子
slink/data：tag为0时，slink指向的是其子表的地址，为1时代表的时data的数值
link：广义表和当前元素同级的下一个元素的地址
广义表的基本运算实现
广义表的创建
广义表的查找
广义表的输出
广义表求表头
广义表求表尾
广义表的深度
树&二叉树
树的概念
一个节点的孩子节点，称为节点的度
二叉树
二叉树的i层上，最多有2^(i-1)个节点
深度为k的二叉树，最多有2^k - 1个节点k>=1
深度
从根节点（0深度）开始，每一层节点加一个深度，包括叶子节点
根结点如果不为空，深度为1，如果跟结点为空，则深度是0
从根（0）开始树，到指定节点位其深度
高度
从叶子节点开始计算为0高度，每往上一层，高度加一（包含根节点），取值最大的一条树枝为树的高度
注意：对于树来说，高度和深度都是相同的，不同的是，当计算树中的某一个节点时，高度和深度可能就不同了
对任何一颗二叉树T，若其终端节点（叶子）数为n0，度数为2的节点数（非叶子节点）为n2，则n0=n2+1；即为叶子节点数比非叶子节点数的总和多1个
满二叉树
一颗深度为k且有2^k - 1个节点的二叉树，称为满二叉树
完全二叉树
若一颗深度为k的二叉树，前k-1层为满二叉树，且k层上的所有若干节点都在树的左边，则称其为完全二叉树
具有n个节点的完全二叉树的深度为logn + 1或者log(n+1)
①：非叶子层的节点数为满二叉树，所以第k-1层的节点数n1=2^(k-1)-1个节点；其中k为深度
②：若为满二叉树则所有节点为n2=2^k -1；其中k为深度
③：设完全二叉树所有节点树为x，则有n1<x<n2
④：对③中的3个项不等式取对数
⑤：特别说明，深度只有最后一层k如果有节点，则为n2的深度，没节点则为n1的深度
二叉树的存储结构
顺序存储，从根节点开始编号0，依次从左至右的累加编号每个节点，并且最后按照编号放进数组中
链式存储，即为struct结构体中，包含left和right指针，以及一个记录节点值的data
二叉树的运算
前序遍历
1.访问根节点。2前序遍历左子树。3前序遍历右子树
中序遍历
1.中序遍历左子树。2访问根节点。3中序遍历右子树
后序遍历
1.后序遍历左子树。2.后序遍历右子树。3.访问根节点
线索二叉树
双亲表示法
孩子链表法
孩子兄弟表示法
数据类型：struct里面有，data，left指针，right指针。其中left指针指向下一层子节点其中一个，右指针指向兄弟节点，没有则以null填充，依次类推构造成的结构表示法
双亲表示法和孩子链表法的总和
思路：根据先序，中序，后序遍历二叉树，每一个节点的前一个节点称为，直接前驱结点，后一个节点称为直接后续节点，树中，为空的左孩子指向直接前驱节点，为空的右孩子指向直接后续节点
树和森林
树，森林到二叉树的转换
先把森林所有兄弟节点之间划一根横线，然后除开左子树以外去掉其余子树与根节点的竖直链接。
二叉树转森林
所有子树先横向连线，转化为只有左子树的树结构，然后将右边的一颗子树坪拼接到右节点上
哈夫曼树及应用
压缩算法
左节点连接为0，右节点链接为1
根据个节点的权重，生成哈夫曼树，每次链接的是两个权重最小的节点
图
图的定义
一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
图的存储结构
邻接矩阵表示法
无向图中体现为，从节点0开始，每个节点标识其与其他节点是否存在链接，存在则在高阶矩阵“行”中体现为1，没有链接体现为0
有向图则体现为是否当前节点与其他节点有出度，有则为1，没有出度则为0
邻接表表示法
从v0点开始，指向的其他节点如v1，就建立一个链表，next指针指向v1，data为v0，以此类推（此方法类似于链表的孩子链表表示法）
在图的链接节点表示图中，用于标识节点与节点之间的关系
图的遍历
深度优先遍历
从某一个节点开始，优先遍历接下来节点连接数最多的一边（包括已经遍历到的节点），如果当前节点周围都被遍历到过，则回溯返回到上一个节点，在判断上个节点周围是否还有为遍历到的，以此类推
广度优先遍历
从某一结点开始，邻接节点的先后编号进行遍历保存，遍历完则进行他们的邻接节点的先后顺序进行保存遍历
图的生成树和最小生成树
生成树
在图论中，树往往被看作是“无回路”的图，生成树则是包含图中所有节点的树
最小生成树
带权重的图中，包含所有节点，权重最小的“无回路”生成树，称为最小生成树
prim算法
1.随机找到一个图中的点V0作为起始点
2.在V0的各个连接权重边上找到权重最小的边E0和点V1
3.在V0和V1的所有连接权重边上找到除E0外的，权重最小连接边E1和点V2
4.以此类推，直到所有点都包含其中，则生成的边集位最小生成树
Kruskal算法
1.遍历边集中的所有边
2.找到权重最小的边放入边集E中，和点集V中
3.在找到另一个权重最小的边放入边集E和点集V中，但是前提条件是：此边不能依靠和其他边串联的方式形成回路
4.以此类推，当图中所有点都包含在点集V中时，算法结束，则生成的边集位最小生成树
最短路径（Dijkstra迪杰斯特拉）
1.点集为V，点集V的补集~V，边集为E
2.确定起始点以后开始算法
3.起始点V0开始的有向图边中，取权重最小的值放入边集E中，并且将包含的点放入点集V中
4.计算与点集V中的所有点有连接的点到V0的权重值，取最小的权重值连接边放入边集E中，和将新增的点放入V中，同时从~V删除。（放入边集的连接线，是对应V中的点到新点的连接线，不是V0直连的线）
5.以此类推，当所有点包含在点集V中，~V为空时，算法完成
拓扑排序
概念：AVO网的组成过程，称为拓扑排序
拓扑排序，可理解为，先学A和B，在学C。其中AB是学C的先决条件
拓扑的起始点一般是入度为0的点
拓扑的排序方式有多种，并不唯一
步骤流程为
1.先从入度是0的开始删除该性质的所有顶点以及边，并且记录下该点的数值
2.继续重复1直至删除完所有顶点，并且获得最终的序号值，则最后的顺序为拓扑排序
排序
插入排序
直接插入排序
从第一个元素开始（视为已排序队列），循环比较未排序的元素中的第一位与已排序中的最后一位开始依次往前的元素，将其插入到比其小的值之后的位置
希尔排序
1.把array对半分成2部分分别为array1,array2；那array1[0]和array2[0]比较，那array1[1]和array2[1]比较，交换确定所有元素地址
2.合并为一个array，然后元素的1，3，5，7，9...开始比较大小并且交换位置，然后2，4，6，8...元素比较大小交换位置
3.最后进行一次插入排序
交换排序
冒泡排序
元素队列中两两比较，大的放在后，小的在前，有多少元素循环多少次
快速排序
从队列中取一个中间值，遍历一次，将小于中间值的放左边，大于中间值的放右边。在递归调用函数参数分别传入左边的队列和右边的队列
选择排序
直接选择排序
1.起始位置index=0；队列array；已排序队列{array[0]}；未排序队列{除array[0]外所有元素}
2.从队列的第index个元素开始，遍历未排序队列，遍历未排序队列中最小的一个与index元素交换；index++；循环此步骤直至最后
堆排序
1.利用完全二叉树的数据结构进行排序
2.父节点最大（或者最小，取决于倒序或者正序）
3.每次交换节点位置后，都需要把最大的数字节点移动到结构顶部
4.顶部节点与叶子层的最靠右的孩子进行交换位置，然后重复3和4，直至全部交换完毕
归并排序
1.队列array，元素n个；array[12]，array[34]，array[1234]，array[56]，array[78]，array[5678]，array[12345678]
2.未排序的元素要和已排序的队列进行再次排序的前提是：未排序的队列元素数量不得少于已排序元素个数（除非未排序元素全部使用）；且必须从2个元素排序开始累加
分配排序
基数排序
原始队列array；各位排序队列array1；十位排序队列array2
编号0-9个队列；首先将array中元素按照个位数大小push到对应的下标编号队列中；然后将元素依次从0队列开始pop出来形成新的队列array1；然后array1中的所有元素按照十位大小重新push到0-9的队列中；最后从队列0开始依次pop个队列中的元素，形成最后的排序结果array2。
桶排序
hashmap原理类似，预先设定一个队列array
hash值内容到队列array的指定下标内保存，array中元素为链表，如果不同元素计算出相同的hash，则放到同样的下标中并且和之前所有元素进行排序存放
内部排序方法的分析比较
时间复杂度
直接插入，选择，冒泡的时间复杂度为O(n^2)
快速，归并，堆排序的复杂度为O(nlog2n)
稳定性
直接插入，冒泡，归并和基数排序算法是稳定的
直接选择，希尔，快速，堆排序算法是不稳定的
空间复杂度
直接插入，直接选择，冒泡，希尔，堆需要的辅助空间为O1
快速排序需要辅助空间O(log2n)
归并排序需要辅助空间On
选择排序法时需要考虑的因素
排序的元素个数
元素的大小和存储结构
关键字的分布
稳定性的要求
时间空间复杂度
排序方法的选取
数据量较小时采用插入排序或选择排序
数据量较大时，用快速排序，堆排序，归并排序
数据量很大，关键字位数小，链式基数排序
关键字多数有序，选择直接插入排序或者冒泡排序
关键字比较次数与记录的厨师排列顺序无关的排序方法时选择排序
排序算法的稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变则称这种排序算法是稳定的；否则称为不稳定的。
查找
顺序表查找
数组形式的顺序查找
树表查找
查找条件：树满足左节点小于右节点；
开始查找时，目标值和根节点比较，如果目标值小于根节点，则与左子树的根节点比较，反之则与右子树的根节点比较；递归调用，直到找到正确的节点
散列表查找
hashmap原理
二分查找
从有序队列的中间查找(n+1)/2,其中n不包含上次的key节点，目标小于则从左边队列中递归使用二分查找，否则在右边队列中使用二分查找
B树
n阶B树的性质
1.子树最多n个，除根结点最少n/2个
2.关键字最多n-1个，最少n/2-1个
B树的插入
1.插入到对应关键字节点中
2.节点分裂是指：4阶B树节点array中把array[1]关键字升级到父节点中，并且独立出array[0]元素
B树的删除
1.需要保持满树的形态
2.删除节点后看是否需要合并，合并的要求就是关键字有序，以及条件1
B树的查找
1.先查找根节点，在根据B树的有序性，一次找到下个关键在哪个子树中，然后遍历该子树节点继续前面的步骤，知道找到为止
索引顺序查找
要求：序列按照一定的大小切割为各种块（块内不必排序）这些块的组合称为“索引表”，块与块之间必须满足前一个块最大的小于当前块最小的
查找：先根据key值找到对应的块区间，然后在块中进行遍历
离散数学
命题与命题公式
命题与命题联结词
命题与命题的表示
命题：具有唯一真值的陈述句叫做命题
真命题：真值为真的命题，称为真命题
假命题：真值为假的命题，称为假命题
真值不确定则不是命题
有些命题现在知识无法判定其真假，但有唯一真值，所以是命题
疑问，感叹，祈使都不是命题
悖论不是命题
命题标识符：标识命题的符号（P,Q）
命令常量（命题常项）：当某个命题标识符标识某个确定的命题
命题为真用T；假为F
复合命题与联结词
复合命题
原子命题通过联结词构成的命题
联结词
①：否定 "非P"
记作：非P
②：合取 "P并且Q" 等同于 &&
对称性：P^Q等同于Q^P
记作：P^Q
在集合概念中等同于∩（交集）
③：析取 "P或者Q" 等同于 ||
对称性：PvQ等同于QvP
记作：PvQ
在集合概念中等同于∪（并集）
④：条件 "如果P那么Q" 只有当P为T（真），Q为F（假）的时候，此判断式才为F
P,Q事件无逻辑关系
记作：P->Q
⑤：双条件 "P当且仅当Q" 两个命题都为T或者F时，才为T
记作：P<->Q
对称性
原子命题
不能再分解为更小的命题的命题
命题公式的等值演算
命题公式
命题常项
符号P代表一个具体的命题时，符号P称作命题常项，此时P的真值是确定的，所以称为常项
命题变元
当符号P仅仅表示一个命题，没有指明哪个命题时，P为命题变元；命题变元不是命题
合式公式
将命题用联结词和圆括号按一定的逻辑关系连接起来的符号串
①：单个命题变元和命题常项是合式公式，并称为原子命题公式
②：若A是合式公式，则"非A"也是合式公式
③：若A,B是合式公式，则(A^B),(AvB),(A->B),(A<->B)是合式公式
④：有限次的应用①，②，③形成的符号串是合式公式
联结词优先级："非">"^">"v">"->">"<->"
设A为一命题公式P1,P2,P3...Pn为出现在A中的所有命题变元，当对这些变元各指定一个真值，称为对A的一种指派或赋值
若指定的一种指派使A的值为真，则称为真指派
若指定的一种指派使A的值为假，则称为假指派
含n个命题变元的命题公式，他的指派数有2^n个
设A为一命题公式，若A在它的各种指派下
取值均为真，则称公式A为重言式（永真式）
其取任何值均为假，则称公式A为矛盾式（永假式）
至少存在一组为真指派，则称A是可满足式。
若可满足式A至少存在一个成假赋值，则称A为非重言式的可满足式
给定两个命题公式A和B，设P1,P2,P3...Pn为所有出现在A和B中的原子变元，若给他们任一组真值指派，A和B的真值都相同，称A和B是等值的（等价的），记为A<=>B；若至少存在一组真值指派，使得A与B的真值不相同，称A和B不等值（不等价）记作A<=/>B
常用的命题定律
双重否定律：A<=>非非A
幂等定律：A<=>AvA,A<=>A^A
结合律：(AvB)vC<=>Av(BvC)；(A^B)^C<=>A^(B^C)
交换律：AvB<=>BvA；A^B<=>B^A
分配律：Av(B^C)<=>(A^B)v(A^C)；A^(BvC)<=>(AvB)^(AvC)
吸收律：假定Av(A^B)<=>A 那么A^(AvB)<=>A
德摩根律：假定非(AvB)<=>非A^非B，那么非(A^B)<=>非Av非B
同一律：假定AvF<=>A，那么A^T<=>A（任意命题合取真,析取假都还其本身）
零律：假定AvT<=>T，那么A^F<=>F（任意命题合取假为假,析取真为真,其本身已不存在）
排中律：Av非A<=>T
否定律：A^非A<=>F
蕴含等值式：A->B<=>非AvB
等价等值式：A<->B<=>(A->B)^(B->A)
假言易位：A->B<=>非B->非A
等价否定等值式：A<->B<=>非A<->非B
归谬论：(A->B)^(A->非B)<=>非A
等值演算与蕴涵式
等值演算
定理1.1：设θ(A)是含公式A的命题公式，使用子公式B置换θ(A)中的A的所有出现，得到命题公式θ(B)，若A<=>B，则θ(A)<=>θ(B)
定理1.2：设A,B为两个命题公式，A<=>B，当且仅当A<->B为一个重言式。
定理1.13：当且仅当P->Q是一个重言式时，我们称“P蕴涵Q”并记作P=>Q，也叫永真条件式
①：对任意公式A，有A=>A
②：对任意公式A，B，C若A=>B，B=>C则A=>C
③：对任意公式A,B,C若A=>B,A=>C则A=>(B^C)
④：对任意公式A,B,C若A=>C,B=>C则(AvB)=>C
定理1.3：设A,B为两个命题公式，A<=>B的充要条件是A=>B,B=>A
蕴涵式
化简律
P^Q=>P
P^Q=>Q
附加律
P=>(PvQ)
变形附加律
非P=>P->Q
Q=>P->Q
变形简化律
非(P->Q)=>P
非(P->Q)=>非Q
假言推理
P^(P->Q)=>Q
拒取式
(P->Q)^非Q=>非P
析取三段论
(PvQ)^Q=>P
条件三段论
(P->Q)^(Q->R)=>(P->R)
等价三段论
(P<->Q)^(Q<->R)=>(P<=>R)
合取构造二难
(P->Q)^(R->S)^(P^R)=>Q^S
析取构造二难
(P->Q)^(R->S)^(PvR)=>QvS
前后件附加
P->Q=>(PvR)->(QvR)
P->Q=>(P^R)->(Q^R)
联结词完备集
设S是一个联结词集合，如果任何n(n>=1)元真值函数都可以由仅含S的联结词构成公式表示，则称S是联结词完备集
能用集合中的联结词，表达完公式的意义，就称为完备集
设P，Q为两个命题，P与Q的否定式是一个符合命题，称作P与Q的与非式，记作P↑Q，即P↑Q<=>非(P^Q)。符号↑称为非联结词
设P，Q为两个命题，P或Q的否定式是一个符合命题，称作P与Q的或非式，记作P↓Q，即P↓Q<=>非(PvQ)。符号↓称为非联结词
{↑}，{↓}都是联结词完备集
命题逻辑的推理理论
范式
范式的概念
命题变元及其否定统称为文字
简单析取式与简单合取式
简单合取式
仅有有限个文字构成的合取式成为简单合取式
简单合取式为矛盾式<=>同时包含此命题变元与其命题变元的否定式
简单析取式
仅有有限个文字构成的析取式称作简单析取式
简单析取式为重言式（永真式）<=>同时包含此命题变元与其命题变元的否定式
合取范式与析取范式
合取范式<=>A1^A2^A3...An，其中A1-n都是简单析取式
析取范式<=>A1vA2vA3..An，其中A1-n都是简单合取式
小项与大项
小项
由n个命题组成的简单合取式，每个命题必须出现且只能出现一次，且同一个命题不会与其否命题同时出现
性质①：每一个小项只在1种情况下为真值，其余情况都为假值
性质②：任意两个不同小项的合取式为矛盾式
性质③：所有小项的析取为重言式（永真式）
大项
由n个命题组成的简单析取式，每个命题必须出现且只能出现一次，且同一个命题不会与其否定命题同时出现
性质①：每个大项只有在一种情况下为假值，其余情况都为真值
性质②：任意不同的两个大项的析取为重言式（永真式）
性质③：所有大项的合取式为矛盾式
主范式
主析取范式
由n个命题组成的若干小项析取组成，即为主析取范式
主合取范式
由n个命题组成的若干大项合取组成，记为主合取范式
自然推理系统
推理H1^H2^H3...Hn证明C是有效推理的充要条件是H1^H2^H3..Hn->C是永真式（重言式）
谓词逻辑
谓词的概念与表示
谓词概念
表示主语的性质
谓词常项
表示具体性质或者关系的谓词
谓词变项
表示抽象的或泛指的性质或关系的谓词
量词与合式公式
量词符号
倒A（表示所有）
反E（标识存在）
谓词演算的等价式与蕴涵式
量词与否定连接词的关系
参考离散数学60页
前束范式
一个公式，如果量词均在全式的开头，他们的作用于，延伸到整个公式的末尾，则该公式称为前束范式
任意一个为此公式，均存在与之等值的前束范式
前束范式的存在定理
一般情况下，前束范式是不唯一的
谓词演算的推理理论
参考离散数学62，63页
集合
集合的基本概念
集合的概念
集合的表示法
列举法
将元素一一列出，并用逗号格力，花括号括起来
描述法
用自然语言进行描述，花括号括起来
图示法（文氏图）
用绘图的形式表达集合关系
常用符号
R:实数集
N:自然数集
Z:整数集
Q:有理数集
C:复数集合
集合的性质
任意两个集合A,B相等的充要条件是A,B互为子集
对于任意集合A，总有"空集"属于A
空集是唯一的
若A集合是拥有n个元素的有限集，则A的幂集✿A的元素个数为2^n
全集记为E
集合的运算
集合的基本运算
A,B为任意两个集合
A-B=A∩~B
A-B=A-(A∩B)
|A∪B|=|A|+|B|-|A∩B|
集合运算的恒等式
任意集合A,B,C有性质
①:A对称差B=B对称差A
②:A对称差 空集合=A
③:A对称差A=空集合
④:A对称差B=(A∩~B)∪(~A∩B)
⑤:(A对称差B)对称差C=A对称差(B对称差C)
有序对与笛卡儿积
有序对
顺序不能随意变更的集合
笛卡儿积
类似于向量里面的叉集，表示为AXB，做法是两个集合里面的元素依次按照顺序相乘
符号化表示AXB={<x,y>| x属于A^y属于B}
若集合A里面有m个元素，集合B有n个元素，则AXB的集合元素个数为m*n
|AxB|=|A|x|B|称为笛卡尔积的基数
任意集合A,B,C
1：Ax(B∪C)=(AxB)∪(AxC)
2：Ax(B∩C)=(A∩B)x(A∩C)
3：(A∪B)xC=(AxC)∪(BxC)
4：(A∩B)xC=(AxC)∩(BxC)
有A,B,C,D四个集合，则AxB包含于CxD的充要条件是A包含于C，且B包含于D
两个有序对集合相乘
关系与函数
关系及关系的性质
关系的定义及表示
设A,B是任意两个集合，AxB的子集R称为从A到B的二元关系，简称关系
空关系
R=空集合
全域关系
<x,y> x属于A^y属于A=AxA
恒等关系
<x,x>x属于A
二元关系也是有序对的集合，但它与笛卡尔集不同，关系可能仅在两个集合的部分元素之间有定义，而笛卡尔积是两个集合的每个元素的叉积
R是集合A上的二元关系
定义域：有序对中的第一个元素组成的。记作：domR=x | 存在y<x,y>属于R
值域：有序对中的第二个元素组成的。记作：ranR=y | 存在x<x,y>属于R
域：定义域与值域的∪，记作fldR=domR∪ranR
矩阵表示关系：有限集合X={X1,X2,X3...Xi},Y={Y1,Y2,Y3...Yj}用矩阵表示时1表示矩阵此处有关系则表示为1，否则为0
关系的性质
自反：所有a属于A，关系R，aRa
反自反：所有a属于A，关系为R，a非Ra
对称关系：所有a，b属于A，关系为R，若aRb，必有bRa
反对称关系：所有a，b属于A，关系为R，若aRb且a≠b，则b非Ra
传递关系：所有a,b,c属于A，若aRb且bRc，则必有aRc
关系的运算
关系的常规运算
如果关系Z和S是集合X到Y的两个关系，则Z和S的并，交，补，差仍是X到Y的关系
逆关系：设R是X到Y的关系，如果将关系R中的定义域和值域进行互换，则得到的新关系R^-1被称为逆关系
设R,R1,R2都是A到B的二元关系
(R^(-1))^-1=R
(R1∪R2)^-1=R1^(-1)∪R2^(-1)
书上86页
复合关系
R为A到B的关系，S为B到C的关系，则RoS则被称为复合关系
F是X到Y的关系，G是Y到Z的关系，H是Z到W的关系
(FoG)oH=Fo(GoH)
(FoG)^-1=G^-1oF^-1
R是集合A上的关系，幂R^n(n=1,2,3,4...)，递归的定义为R1=R,Rn=R(n-1)oR
关系矩阵的布尔运算
关系R的关系矩阵为MR，逆关系R^-1的关系矩阵MR的转置矩阵为MR^T
关系A，B，C中，从A到B的关系矩阵R1为mxn阶矩阵，B到C的关系R2是nxr阶矩阵，那么R1和R2的复合关系R1oR2是从A到C的关系，关系矩阵是mxr阶矩阵（描述中的m，n，r是矩阵中的索引下标）
关系的闭包
在原有子集的基础上，扩充父集合里面复合子集合满足要求的元素和性质，扩展后的关系我们称为原关系的闭包
关系R是非空有穷集合A上的二元关系
自反闭包=RUI(a)
对称闭包=RUR^-1
传递闭包=(RUR^2UR^...R^n)
等价关系与序关系
等价关系
相容关系-给定集合A上的关系p，如果p是自反的，对称的，则称p是A上的相容关系
等价关系-设R为A上的关系，若R是自反的，对称的，传递的，则称R为A上的等价关系
设R为等价关系，若<x,y>属于R，称x等价于y，记作x~y
给定非空集合A上的等价关系R，所有a，b属于A有aRb，当且仅当[a]R=[b]R
集合A的一个划分确定A的元素间的一个等价关系，划分中的集合是等价类
序关系
设A是一个非空集合，如果A上的关系R满足自反性，反对称性，传递性，则称R是A上的一个偏序关系，记作<=，称作偏序集
①：设<=是飞空集合A上的偏序关系，对所有a，b属于A，若<a,b>属于<=且a≠b，称a小于b，记为a<b
②：<a,b>属于<=或<b,a>属于<=,称a与b是可比的，否则称a与b是不可比的
③：设<A,<=>为偏序集，对所有a，b属于A，若a<b且不存在c属于A是的a<c<b，则称b覆盖a，记作COVA={<a,b>|a属于A^b属于A^b覆盖a}
④：偏序关系的关系图成为：哈斯图，表示规则为
A中每个元素可用顶点表示
所有a，b属于A，若a<b，则将a画在b的下方
所有a，b属于A，若b覆盖a，则在a，b之间画一条边
哈斯图中省略顶点到自身的边
拟序关系
集合A上的二元关系R若是，反自反和传递的，则称R为A上的拟序关系，记为<A,<>
集合A上的二元关系R是拟序的，则R必为反对称的
全序关系
设≤是非空集合A上的偏序关系，对所有a，b属于A，若必有a≤b或b≤a，则称≤是A上的全序关系，则<A,≤>是全序集
偏序关系不要求集合A中所有管束之间都存在偏序关系，如果集合A中任意两个元素之间都存在偏序关系，则为全序关系
设<A,≤>是一个偏序集，B包含于A，y属于B
若所有x（x属于B->y≤x）成立，则称y为B的最小元
是集合B中最小的元素，和集合B中所有元素都存在偏序关系
若所有x（x属于B->x≤y）成立，则称y为B的最大元
最大元与B中所有元素都是可比的，且都≥这些元素
若所有x（x属于B^x≤y->x=y）成立，则称y为B的极小元
极小元不一定和B中的所有元素均可比，但只要可比，就一定是≤其他元素
在集合B的子集中最小的元素
若所有x（x属于B^y≤x->x=y）成立，则称y为B的极大元
B中没有比它更大的元素
在集合B的子集中最大的元素
集合的最大元，最小元不一定存在，如果存在的话，一定是唯一的；而极大元，极小元可能存在多个。如果极大元只有一个的话，他一定是最大元，极小元只有一个的话，它一定是最小元
上界与下界，上确界与下确界
上界：设<A,≤>为一偏序集，对于B包含于A，如有a属于A，且对B中任意元素x都满足x≤a，则称a为子集B的上界
下界：同样对于B中任意元素x，都满足a≤x，则称a为B的下界
上确界：设<A,≤>为偏序集，有子集B包含于A，若a为B的任一上界，且对B的所有上界y，均有a≤y，则称a为B的最小上界，称为上确界
下确界：同样若b为B的任一下界，若对B的所有下界z，均有z≤b，则称b为B的最大下界，称为下确界
良序集
设<A,≤>为全序集，如果A的任何非空子集都含有最小元，则称<A,≤>为良序集
函数
函数的概念
F为二元关系，所有x属于domF都有唯一的y属于ranF与之对应，使xFy成立，则称F为函数，也称映射
函数与关系的差异
①：函数要对定义域中的所有元素都有定义，而关系可以只针对一部分元素有定义。
②：函数定义域中的x只能有唯一的y值与之对应。而关系中可以同一个x值有多个y对应
单射
在定义域中的任意唯一x，都有唯一的值域值y和它对应（x和y是一一对应关系）
满射
值域y上的所有值，都能在定义域中找到x与之对应（值域每个值都有被映射到）
双射
即是满射，又是单射的
反函数与逆函数
当y=f(x)为双射时，有x=g(y)，则称g函数是f函数的反函数，记g函数为：f^-1
必须是双射才有反函数
也可称双射函数的反函数为逆函数
复合函数
设函数y=f(x)，则foIy=Ixof=f（Ix或Iy表示反自反x或y）
设y=f(x)，z=g(y)都是双射
f^-1of=Iy,fof^-1=Ix
(f^-1)^-1=f
(fog)^-1=g^-1of^-1
函数复合，不满足交换律，即fog≠gof
设y=f(x) z=g(y) z=f(g(x))
若f和g都是满射，则fog也是满射
若f和g都是单射的，则fog也是单射
若f和g都是双射的，则fog也是双射
代数系统的一般概念
代数系统
设A为任意集合，从A^n到B的映射，成为集合A上的一个n元运算。如果B包含于A，则我们称这个运算是封闭的
A为一个若干大的集合
A^n的意思是集合A中n个元素可以构成的集合个数比如A中1和2，可以构成集合{1,2};{2};{1};空集，但是一定有2个元素组成的集合就是{1.2}和{2,1}
如果A中部分元素组成的子集合经过运算（映射）过后形成的集合B还是包含于集合A，就称为这个运算是封闭的
运算
一元运算
补集运算~（只需要全集和一个子集合A进行运算）
二元运算
∩，∪，-，对称差（需要两个子集合进行运算）
是可以是任意形式的
代数系统
一个非空集合A，联通若干个定义在该集合上的运算，f,g,h,j,k所组成的系统，称为代数系统，简称代数，记作<A,f,g,h,j,k>
幺元
左幺元
设*为集合A上的二元运算，如果存在一个eL，使得所有x属于A时，eL*x=x，则称eL是A种关于*运算的左幺元
右幺元
设*为集合A上的二元运算，如果存在一个eR，使得所有x属于A时，x*eR=x，则称eR是A种关于*运算的右幺元
如果存在e属于A，即有左幺元，又有右幺元 则称为e是关于运算符*的幺元，则有左幺元=右幺元=幺元，且幺元是唯一的
零元
左零元
如果有一个元素OL，对于任意元素x属于A都有OL*x=OL，则称Ol为A中关于运算*的左零元
右零元
如果有一个元素OR，对于任意元素x（x属于A）都有x*OR=OR，则称OR为A中源于运算*的右零元
如果O即是左零元，又是右零元，则称O为A上关于运算*的零元，且零元是唯一的
幺元零元注意事项
设有代数系统<A,*>中，|A|>1（|A|代表集合A中的元素个数），若该代数系统中存在关于运算*的幺元e与零元O，则e≠O
逆元
左逆元
设有代数系统<A,*>中，e是关于运算*的幺元，若对于A中的某个元素a，有一个元素b，使得b*a=e，则称b是a的左逆元
右逆元
设有代数系统<A,*>中，e是关于运算*的幺元，若对于A中的某个元素a，有一个元素b，使得a*b=e，则称b是a的右逆元
若元素b即是左逆元，又是右逆元，则称它为在集合A中对于运算*的关于a的逆元，记作a^-1
特点：在代数系统中，左逆元和右逆元的存在性是独立的。所以左右逆元相等是一个重要的性质：
在代数系统<A,*>种，*是二元运算，A存在幺元e，且每一个元素都有左逆元。如果*是可结合运算，那么所有元素的左逆元都等于它的右逆元，且每个元素的逆元是唯一的
代数常数
代数系统的幺元和零元，称为代数常数
子代数
设V=<S,f1,f2,f3...fn>是代数系统，B包含于S，且B对f1,f2,f3..fn都是封闭的，B和S含有相同的代数常数，则称<B,f1,f2,f3..fn>是V的子代数系统，简称子代数
平凡子代数
如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B构成V的最小的子代数。最大（V本身）和最小的子代数称为V的平凡子代数
真子代数
若B是S的真子集，则B构成的子代数称为V的真子代数
群与半群
半群
设V=<S,*>是代数系统，*是集合S上的二元运算，若运算*是封闭且可结合的，则称V为半群
独异点
若半群存在幺元，则称为独异点
<N,+>;<Z,+>;<Q,+>;<R,+>中0是他们的幺元，所以他们都是关于+的独异点
设<S,*>是独异点，对于所有a，b属于S，且a，b均有逆元
(a^-1)^-1=a
若a*b有逆元，则(a*b)^-1=b^-1*a^-1
子半群
设<S,*>是一个半群，B包含于S，且B关于*是封闭的，那么称B是S的子半群
群
<G,*>是一个独异点，且G中所有元素x都有逆元x^-1，则称是一个群
举例：<Z,+> <R,+> <R,+>都是群，幺元是0，逆元是-x
有限群
<G,*>是一个群，G是有限集，则称为有限群。G中的元素个数叫做该群的阶数，记作|G|
平凡群
<G,*>群只有一个元素，即G={e}，|G|=1，则称为平凡群
交换群&Able群
<G,*>是一个群，且*满足交换律
<G,*>是群，e是幺元，所有a属于G，n属于Z（整数）定义a的n次幂为
a^n
e（n=0）
a^(n-1)a（n>0）
(a^-1)^m（n<0,n=-m）
阶元
<G,*>是群，e是幺元。所有a属于G，a^k=e成立的最小正整数k称为a的阶，记作|a|，a称为k阶元
如果不存在如上所说的数k，则称为无限阶元
注意和群的阶进行区分，这里的阶元是指的元素的阶元，而非群的阶
<G,*>为群，所有a，b属于G，所有n，m属于Z（整数）
(a^-1)^-1=a
(ab)^-1=b(^-1)a(^-1)
a(^n)a(^m)=a^(n+m)
(a^n)^m=a^nm
若G为Able群，(ab)^n=a(^n)b(^n)
幂等元
<G,*>中如果存在a属于G，a*a=a，则称a为幂等元，若运算*满足幂等律，则G中所有元素都是幂等元
<G,*>是群，G满足消去律，则对所有a，b属于G
若a*b=a*c，则有b=c
若b*a=c*a，则b=c
<G,*>是非平凡群，则群中不存在零元
<G,*>是一个群，对于所有a，b属于G，不存在唯一的元素x属于G，使得a*x=b
循环群
<G,*>是一个群，若在G中存在一个元素a，使得G中的任意元素都有a的幂组成，则称该群是循环群
生成元
元素a就是循环群G的生成元
子群
<G,*>是一个群，S是G的非空子集，如果<S,*>也构成群，则称S是G的子群，记作S≤G
子群判定定理（<G,*>是群，H是G的非空子集）
①：H≤G当且仅当这两个条件成立
所有a，b属于H时，有a*b属于H
所有a属于H，有a^-1属于H
②：H≤S当且仅当所有a，b属于H有a*b^-1属于H
子群判定定理三：<G,*>是群，H是G的有穷非空子集，则H≤G当且仅当所有a，b属于H，有a*b属于H
环与域(<A,+,*>是一个代数系统+是加法，*是乘法)
环
+和*都是二元运算如果满足
①：<A,+>是Abel群
②：<A,*>是半群
③：运算*对于运算+是可分配的
举例：所有的a，b，c都属于A
a*0=0*a=0
a*(-b)=(-a)*b=-(a*b)
(-a)*(-b)=a*b
a*(b-c)=a*b-a*c
(b-c)*a=b*a-c*a
为方便表示，把环中加法幺元记作0，乘法幺元记作1，环中任意元素a的加法逆元称为负元记作-a，乘法逆元称为逆元记作a^-1
零因子
左零因子
所有a，b属于A，a≠0且b≠0但是a*b=0（*此时不是乘法而是运算符），则a称为左零因子
右零因子
所有a，b属于A，a≠0且b≠0但是a*b=0（*此时不是乘法而是运算符），则b称为右零因子
元素即是左零因子，又是右零因子，则称为零因子
交换环
如果环A中乘法*满足交换律，则称A为可交换环
含幺环
如果环A中乘法*存在幺元（如：1），则称A为含有幺元的环，称为含幺环
无零因子环
所有a，b属于R，若a*b=0时，必有a=0或者b=0，则称A是一个无零因子环
整环
若A即是交换环，喊幺环，无零因子环，则称A为整环
设<R,+,*>是无零因子环，有a，b，c属于R。a*b=a*c。当且仅当R中乘法*适合消去律时，b=c
域
<R,+,*>是一个整环，且|R|≥2，若对所有a属于R^*=R-{0}，都有a^-1属于R，则称<R,+,*>是域
格与布尔代数
格的基本概念
格的定义
偏序集<A,≤>中的有限元素子集，如果存在上确界和下确界，则称为格
诱导代数系统
<A，≤>是一个格，A上定义二元运算^（∩）和v（∪）使得所有属于A的元素a，b，有a^b等于a和b的下确界，avb等于a和b的上确界，则称<A,^,v>为格<A,≤>所诱导的代数系统
对偶
<S,≤>是格，P是由格中元素及≤,≥,=,^,v符号表示的命题，如果将命题中的符号≤，≥，^，v分别改成≥，≤，v，^得到的命题P'，则称P和P'是对偶命题
如果命题P对一切格L为真，则P的对偶命题P'也对一切格L为真
格的性质
格<A,≤>中，所有a，b属于A都有
a≤avb，b≤avb
a^b≤a，a^b≤b
格<A,≤>中a，b，c属于A
a≤b且a≤c =>a≤b^c
a≥b且a≥c=>a≥bvc
格<A,≤>中a，b，c，d属于A
如果a≤b且c≤d，则avc≤bvd且a^c≤b^d
格<A,≤>中a，b，c属于A，由格A诱导的代数系统<A,^,v>有
交换律：avb=bva；a^b=b^a
结合律：av(bvc)=(avb)vc ; a^(b^c)=(a^b)^c
幂等律：ava=a ; a^a=a
吸收率：av(a^b)=a ; a^(avb)=a
由格<A,≤>诱导的代数系统必须满足以上4个定律
设<A,*，o>是一个代数系统，其中*和o都是二元运算，且此代数系统满足交换律，结合律，吸收率则可以得出结论
A上存在偏序关系≤，使得<A,≤>是一个格，且所有a，b属于A，有a^b=a*b ; avb=aob
设<L,^,v>是代数系统，其中^和v是二元运算，若^和v运算满足交换律，结合律，吸收率，则称<L,^,v>是一个格
<L,^,v>是一个格
①：所有a，b，c属于L，若a≤b，则a^c≤b^c,avc≤bvc
②：所有a，b，c，d属于L，有a≤b且c≤d=>a^c≤b^d,且avc≤bvd
子格
<L,^,v>是一个格，S是L的非空子集，若S关于运算^和v是封闭的，则称<S,^,v>是格L的子格
分配格与有补格
分配格
<A,^,v>是格，若对所有a，b，c属于A，满足
a^(bvc)=(a^b)v(a^c)
av(b^c)=(avb)^(avc)
格同态
设<A1,≤1>，<A2,≤2>是两个格，他们诱导的两个代数系统分别为<A1,^1,v1>和<A2,^2,v2>如果有一个映射f，使得a，b属于A1的元素满足f(av1b)=f(a)v2f(b)或者f(a^1b)=f(a)^2f(b)，则称f为代数系统A1到A2的格同态
格同构
当格同态中的映射f是双射时，称为格同构
格L是分配格，当且仅当L中不含有与钻石格或五角格同构的子格
小于五元的格都是分配格
任意一条“链”都是分配格
有补格
有界格（格<A,≤>）记作：<A,v,^,0,1>
性质
全上界
存在元素a属于A，使得所有x属于A都有x≤a，则称a为格A的全上界
偏序对的最大元，记作1
全下界
存在元素a属于A，使得所有x属于A都有a≤x，则称a为格A的全下界
偏序对的最小元，记作0
例子
钻石格
五角格
任何有限格L
补元
有界格<A,v,^,0,1>中，a属于A，若存在b属于A，使得avb=1,且a^b=0,称b和a互为补元，简称互补
任何有界格中，全下界0和全上界1总是互补的
有界分配格如果存在补元，则一定是唯一的
求补为一元运算用符号 ' 标识
有界格存在补元，称为有补格
布尔代数
有补分配格就是布尔代数
设有代数系统<B,^,v,',0,1>为代数系统，B至少包含两个元素，^和v为B上的二元运算，'为求补，对于所有a，b，c属于B
①：a^b=b^a ; avb=bva（交换律）
②：a^(bvc)=(a^b)v(a^c) ; av(b^c)=(avb)^(avc)（分配率）
③：在B中存在零元0，使av0=a，a^0=0；存在单位元1，使得a^1=a,av1=1
④：a'属于B，使a^a'=0,ava'=1(补元律)
满足以上4点，则<B,^,v,',0,1>为布尔格
性质
所有a属于B，(a')'=a
所有a，b属于B，(a^b)'=a'vb',(avb)'=a'vb'
图
图的基本概念（图G(V,E)）
顶点(V)
非空有限顶点集
顶点总数记为|V|
边(E)
边集
当顶点为u，v时，边可以表示为（u,v）或<u,v>
边总数记为|E|
图类别
稀疏图
相对顶点来说边比较少
零图
一条边也没有
密集图&稠密图
边数较多的图
平凡图
仅有一个顶点的图
有向图
图中的边均为有向边的图
无向图
图中的边只有无向边的图
n阶有向图
含有n个顶点的简单有向图G中，每个顶点都与其余的n-1个顶点邻接
n阶无向图
含有n个顶点的简单无向图G中，每个顶点都与其余的n-1个顶点邻接
简单图
无平行边，无自环的图
补图
图G中，V为点集，所有属于Kn但不属于E的边集和V构成的图，称为G相对于Kn的补图，记作~G
k-正则图（k为度数值）
无向图G中，如果每个顶点的度都是k，则称G为k-正则图
子图
图G<V,E>和图G'<V',E'>如果E'包含于E，且V'包含于V，则说G'是G的子图
生成子图
如果是G'是G的子图，且G'中点集V'=V，则说G'是G的生成子图
自补图
如果G是同构的，则称G为自补图
边类别
有向边&弧
图中限定从一个顶点指向另一个顶点
无向边
不限定方向的边
度
与无向图G中顶点u属于V关联的边数称作该点的度，记作deg(u)
孤立点
deg(u)=0
悬挂点
deg(u)=1
奇点
deg(u)%2 != 0
偶点
deg(u)%2==0
有向图中
以某一个顶点u为起点的有向边的个数称为u的出度记作deg(^+)(u);
以某一个顶点u为终点的有向边的个数称为u的入度记作deg(^-)(u);
顶点的出度入度之和等于该顶点的度数，即deg(u)=deg(^+)(u)+deg(^-)(u)
所有顶点的入度之和等于所有顶点的出度之和
图的性质
图G<V,E>中，顶点度数综合等于边数的两倍 Σdeg(u)=2|E|
任意图G，奇顶点必为偶数个
同构性
图G1和图G2的顶点和边分别存在一一对应且保持关联的关系（有一个映射f保持关联）记作G~=G'
图的连通性（G<V,E>）
定义
通路
G中顶点与边的交替序列F=vi0 ej0 vi1 ej1...vin ejn。称为连接vi0到vin的通路，其中vi0..是点，ej0是连接vi0到vi1的边
通路长度
ejn中n的个数
回路
若vi0=vin。F称为回路
简单通路
G中所有的ejn（n属于1-无穷大）都是不同的。F称为简单通路
简单回路
简单通路的起点和终点相等时。F称为简单回路
路径
F为简单通路，且除起点和终点，其余所有的点都不同，则F称为路径
初级回路
路径的起点终点相同，则称F为初级回路
连通图
无向图G中，u和v之间存在通路，则称顶点u和顶点v连同的，若G中任何两个不同顶点都是连同的，则称为连通图，否则称不连通图
无向图的连通性不能推广到有向图，有向图的u到v有一条路则称为可达，而不是连通
单侧连通
简单有向图G中，任何一对顶点间至少有一个顶点到另一个顶点是可达的
弱连通
在有向图中忽略边的方向看成无向图后，图是连通的，则称为弱连接
强连通
任何一对顶点之间是相互可达的
割点
无向图G中，w属于V，若删除w和与其连接的边后，图G不再连通，则称w为割点
割边&桥
无向图G为连通图，对任意的边e属于E，若删除e后无向图不再连通，则称e为割边
点割集
无向图G中，若存在点集V1包含于V，V2包含于V1，若删除V1中所有点以及与点关联的边后图G不连通，且删除V2中的点和点关联的边后图G为连通的，则称V1为G的点割集
边割集
无向图G中，若有边集E1包含于E，当删除E1中的所有边后得到的子图是不连通的，而删除了E1的任一真子集边集E2后子图是连通的，则称E1是G的边割集
定理
无向图G中，每个点点的度数至少为2，则G包含一条初级回路
图G中|V|=n，若从u到v 且u≠v存在通路，则从u到v比存在长度小于或等于n-1的一条通路
图的表示
邻接矩阵
表示法中，横向矩阵的布尔值非0表示出度，纵向非0表示入读，这样横向非0加上纵向非0就是这个点的总度数
另外，无向图如果存在连接，则横向和纵向都需要计数为1，有向图则根据方向表示来判断是否为1或者0
page：142页
图的应用
欧拉图与哈密顿图
欧拉图
欧拉通路：连通图G中，经过G中每条边一次且仅一次的通路，称为欧拉通路
欧拉回路：欧拉通路为回路的称为欧拉回路
有欧拉回路的图，称为欧拉图
含有欧拉通路，但没有回路的图，称为半欧拉图
欧拉图的充要条件：无向连接图G是欧拉图的充要条件是：G是连通的且无奇点
欧拉通路的充要条件是：无向连接图G是连通的且恰好有两个奇点
有向图是单向欧拉回路的条件是，当且仅当，图是可达的且每个顶点的出度等于入度
有向图是单向欧拉通路的条件是，当且仅当，除了两个顶点外，其余顶点的出度等于入度，这两个顶点的其中一个的入度比出度大1
哈密顿图
无向图G，若存在一条路L，经过图中每个顶点仅一次，则称L为哈密顿路。简称H-路
无向图G中，若存在一条回路L，经过图中每个顶点仅一次，则称为哈密顿回路。简称H-回路
具有哈密顿回路的图，称为哈密顿图。简称H-图
G为具有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n-1，则G中存在一条哈密顿路
G为具有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n，则G中存在一条哈密顿回路
平面图
设连通平面图G，面的次数之和等于其边数的两倍
设有一个连通平面图G，共有n个顶点和m个边，以及r个面，则n-m+r=2，此公式为欧拉公式
同胚
两个图G1,G2同构，或者经过反复插入或消去2度顶点后同构，则称为同胚
树及其遍历
树的基本概念
一个连通且无回路的无向图称为树
树中度数为1的节点称为叶节点，度数大于1的节点称为分支点。一个无回路的无向图称为森林。多颗互不相交的树的集合；
给定图T，有n个节点，则这些命题是等价的
T是数
T无回路，且T的任何两个顶点间有唯一一条路
T无回路，且有n-1条边
T是连通的，且有n-1条边
T是连通的，但删除任何一条边后边不再连通
T无回路，但增加任何一条边，将得到唯一的一个回路
若树中节点数n≥2，则树中至少含有两个叶节点
设G有n个顶点，m条边，和w个连通分量，则G为森林的充要条件是e=n-w
树T的每一个分支节点，都是树的割点
连通分量
无向图G的极大连通子图称为G的连通分量；我理解为形成森林的若干个树，每个树称为一个连通分量
极大连通子图
在这里我理解为森林中某个树本身
生成树&支撑树
设G<V,E>是无向连通图，若G的生成子图T是一棵树，则称T是G的生成树，也叫支撑树
树枝
无向生成图G在其生成树上的边，称为树枝
弦
无向生成图G不在其生成树上的边，称为弦
余树
所有弦的集合及其生成的子图称为余树
连通图至少有一棵生成树
带权图
设图G<V,E>，对于所有e属于E，指定一个数值w，称为边e的权（权重）。这样的图称为带权图,记作G=<V,E,W>,其中W是所有边的权组成的有限集
最小生成树
无向连通带权图G<V,E,W>中，T是G的一颗生成树，T的各边权值之和称为T的权，记作W(T)。G的所有生成树中权值最小的生成树称为最小生成树
使用克鲁斯卡尔算法生成的树T是最小生成树
有向树
如果有向图在不考虑边的方向时是一棵树，那么这个有向图称为有向树
有根树
如果这棵树恰巧一个节点的入度为0，其余所有节点的入度均为1，则称该有向树为有根树
根
入度为0的点称为根
叶子&叶节点
出度为0的点
根数分支点&内点
出度不为0的点且入度不为0的点
节点关系（u是有根树的一个分支点，从u到w有一条边，从u到w到z有一条有向路）
子节点&儿子
w为u的儿子 或子节点
父节点&父亲
u为w的父亲或父节点
兄弟节点
u和相同的顶点之间互称为兄弟节点
子孙
z是u的子孙
祖先
u是z的祖先
子树
树包含一个或多个节点，这些节点中的某一个称为根，而其他所有节点，被分成有限个互不相交的子集，每个子集又构成树，称为根的子树
有序树
在有向树T中，若每个节点的子节点之间指定某种次序，则T称为有序树
m叉树
在有根树中，若每一个节点的出度小于等于m，则称这棵树为m叉树
完全m叉树
如果每一个节点的出度恰好等于m或0，则称这棵树为完全m叉树
正则m叉树
若m叉树的所有叶节点的层次相同，则称为正则m叉树
二叉树的基本概念
设有完全m叉树T，其叶节点数为t，分支节点数为i，则(m-1)i=t-1
二叉树与树的遍历（参考page159）
先序遍历
中序遍历
后序遍历
概率论与数理统计
随机事件与概率
随机事件
随机试验与样本空间
随机事件的概念
一次试验中可能出现也可能不出现的事件
随机事件的关系与运算
事件的包含与相等
发生A事件的时候必定发生B事件
B包含于A
和事件
A和B必然会发生一个
AUB
积事件
A和B同时发生
A∩B
差事件
A事件发生B不发生
A-B
互不相容事件
A事件和B事件互斥
对立事件
A事件的逆事件A~ 和A事件互为对立事件（简单理解为非A）
概率
频率与概率
频率
在n次试验中，事件A出现的次数为nA，则nA/n为A事件出现的频率
概率是频率的近似值
古典概型
样本空间仅含有有限个样本点
每个基本事件发生的可能性相同
概率的定义与性质
设Ω是随机试验E的样本空间，对于E的每个事件A赋予一个实数，记为P（A），称P（A）为事件A的概率
0≤P(A)≤1，P（空）=0
对于任意事件A,B有P（AuB）=P(A)+P(B)-P(AB)
P(B-A)=P(B)-P(AB)
P(A~)=1-P(A)
条件概率
条件概率与乘法公式
在事件B发生的条件下，事件A发生的概率。记为P(A|B)
设A,B为两个事件，且P(B)>0,称P(A|B)=P(AB)/P(B)为事件B发生的条件下事件A发生的条件概率
P(AB)=P(A)P(B|A)=P(B)P(A|B)
全概率公式与贝叶斯公式
全概率公式
设事件A1，A2。。。。An满足两个条件
A1-An互斥，且发生的概率都大于0
A1UA2UA3...UAn=Ω，即所有Ai事件一定有一个发生，则称每个Ai为一个划分
全概率公式的意义就是，某个事件A在所有情况下发生的概率之和
叶贝斯公式
P(Ai)P(B|Ai)/关于事件B的全概率公式
个人理解为事件B有一定的概率发生，事件B是Ai的条件概率，事件Ai与B同时发生的概率，除以事件B的全概率公式，求出来的值为Ai在B条件下发生的概率
事件的独立性
事件的独立性
若P(AB)=P(A)P(B)则称A,B独立
若A,B相互独立，则A与B~,A~于B，A~与B~都相互独立
ABC为3个事件，若P(AB)=P(A)P(B),P(AC)=P(A)P(C),P(BC)=P(B)P(C),P(ABC)=P(A)P(B)P(C),则称A,B,C相互独立
n重伯努利试验
n次独立重复的试验
A为n重伯努利试验的事件，发生了k次的概率为：Pn(k)=Cn^kp^k(1-p)n-k,其中k=0，1，2，3....n
例题：射击目标4次，命中率0.8，求恰好命中2次的概率。
C42（0.8）²x（0.2）²=0.1536
Cnk的求法为：n！/k！
随机变量及其概率分布
离散型随机变量
随机变量的概念
把随机试验的结果数量化，与实数进行结合，形成类似函数的映射
设E是随机试验，样本空间Ω，如果每一个结果（样本点）w属于Ω都有一个实数X(w)与之对应，这样就得到一个定义在Ω上的实数函数X=X(w)。则X称为随机变量
离散型随机变量及其分布律
离散型随机变量
随机变量X只取有限多个，或可列无限多个值；如掷骰子的点数X=｛1.2.3.4.5.6｝
分布律
设X为离散型随机变量，取值可能为x1，x2，x3...且P(X=xk)=pk，k=1，2，3...则称pk为X的分布律（或概率分布）
如掷骰子可以为1，2，3，4，5，6则P（X=1，2，3，4，5，6）的概率p1,p2,p3,p4,p5,p6就称为这个随机变量的概率分布
样本空间Ω的所有概率总和为1
0-1分布及二项分布
0-1分布
随机变量的取值只可能是0和1
实例比如：掷硬币
0-1分布是二项分布的特例
二项分布
若随机变量X的可能取值为0，1...n，n为正整数，而X的分布律为pk=P(X=k)=Pn(K)=Cn^kp^kq^(n-k)，其中0<p<1,p+q=1,则称X服从参数为n，p的二项分布；记作X~B(n，p)
二项分布的应用场景初步理解为：知道一个试验的发生概率，知道时间发生的总次数n，求发生k次出现的情况的概率。
泊松定理
δ>0是常数，n是任意正整数，在n重伯努利试验中，记事件A在一次试验中发生的概率为pn，当n->正无穷，有npn->δ
见书Page59
大概看懂，不能理解
该定理的意义是给出一个公式，可以用于取得近似值，用于解决在二项式计算中值很大不方便计算时使用；当实验次数趋于无穷大时，可以用泊松定理公式(δ^k/k!)*e^-δ 来近似计算值
泊松分布
满足泊松定理表达式的随机变量X，就称其满足泊松分布
随机变量的分布函数
分布函数的概念
分布函数本质上是一种累计概率，作用是统计出出现在区域中的概率，且可以统计为分段函数等的形式
F(x)=P(X≤x)，x属于(-无穷，+无穷)
x是事件的概率点，X为概率统计即小于x的所有概率
也可以理解为，分布函数是分布律的条件下，各个分布律范围的和
分布函数的性质
0≤F(x)≤1
F(x)是不减函数，即对于任意x1<x2有F(x1)≤F(x2)
F(-无穷)=0，F(+无穷)=1
F(x)右连续，F(x+0)=F(x)
连续性随机变量及其概率密度
连续型随机变量及其概率密度
均匀分布与指数分布
正态分布
随机变量函数的概率分布
离散型随机变量函数的概率分布
连续性随机变量函数的概率分布
多维随机变量及其概率分布
随机变量的数字特征
大数定律与中心极限定理
统计量及其抽样分布
参数估计
假设检验
数据库系统原理
数据库系统系统概述
1.数据库的基本概念
1.数据：描述事物的符号记录
2.数据库
定义：长期存储在计算机内，有组织的，可共享的大量数据集合
特点
1.永久存储
2.有组织
3.可共享
3.数据库管理系统
定义：位于用户与操作系统之间的一层数据管理软件
功能
1.数据定义；提供了数据的定义语言DDL（表，视图，存储过程，触发器）
2.数据操作功能；提供了数据操纵语言DML（查询，插入，删除，修改）
3.数据库的运行管理；保证数据的安全性，完整性，多用户并发使用，发生故障后的系统恢复
4.数据库的建立与维护
创建数据库，数据库空间维护，数据库备份，恢复，重组只功能和性能你监视
5.数据组织，存储，管理功能
索引查找，顺序查找
6.其他功能
通信，数据传输等
4.数据库系统（DBS）
定义：包括数据库，数据库管理系统，相关实用工具，应用程秀，数据库管理员（DBA）和用户
2.数据库管理技术的发展
一：人工管理阶段
①：数据不存在在计算机内
②：应用程序管理数据
④：数据面向应用
二：文件系统阶段
①：数据的管理者：文件系统，数据可长期保存
②：数据面向的对象：某一个应用程序
③：数据的共享程度：共享性差，冗余度大
④：数据的结构化：独立性差，数据的逻辑结构改变必须改应用程序
⑤：数据控制能力：应用程序自己控制
三：数据库系统阶段
①：数据集成
②：数据共享性高
③：数据冗余小
④：实施统一管理与控制
⑤：数据一致性
⑥：数据独立性高
⑦：减少应用程序开发和维护的工作量
3.数据库系统的结构
①：数据库系统的三级模式结构
1.模式：也称为概念模式或逻辑模式，它是数据库中全体数据的逻辑结构和特征的描述
2.外模式：也称为子模式或用户模式，它是数据库用户能够看见和事用的局部数据的逻辑结构和特征的描述
3.内模式：也称为存储模式，它是计算机中物理结构和存储方式的描述
4.三级模式结构的两层映像与数据独立性
1.外模式/模式映像（逻辑独立性）
2.模式/内模式映像（物理独立性）
②：数据库系统的运行与应用结构
1.C/S模式
2.B/S模式
③：数据模型
1.数据特征与数据模型组成要素
1.数据结构：描述的是系统的静态特性，即数据对象的数据类型、内容、属性以及数据对象之间的联系
2.数据操作：数据操作描述的是系统的动态特征，是对各种对象的例允许执行的操作集合。
3.数据的约束条件：数据约束描述数据结构与数据见的语法和语义关联，包括相互制约、依存关系，数据动态变化规则、以保证数据的正确性，有效性与相容性
2.数据模型的分类
1.概念层数据模型
1.实体（entity）
2.属性（attribute）
3.码（Key）
4.域（Domain）
属性的取值范围
5.实体型（Entity Type）
用实体名及属性名集合来抽象和刻画。同类实体称为实体型
6.实体集（Entity Set）
7.联系（Relationship）
1对1
1对多
多对多
2.概念模型的表示方法（ER图）
1.实体用矩形
2.联系用菱形
3.属性用椭圆形
2.逻辑层数据模型
1.层次模型
2.网状模型
3.关系模型
4.面向对象模型
3.物理层数据模型：也称为数据的物理模型，其描述数据数据在存储介质上的组织结构，是逻辑模式的物理实现。每一种逻辑模型在是实现时都有与其相对应的物理模型
关系数据库
1.关系数据的概述
2.关系数据模型
1.关系数据结构
二维表（数据库表）一张表就是一个关系
基本术语
1.表（table）；由表名，列（属性），行（记录or元组）
2.关系（Relation）；表名就是关系名
3.列（Column）；也称作字段（属性）
4.属性（Arrtibute）；也就是列，表中属性的个数称作关系的“元”或“度”
5.行（Row）；称作元组或者记录
6.元组（Tuple）；一行记录
7.分量（Component）；元组中的一个属性值
8.码或键（Key）；一个或者多个属性组合成一个唯一的标识
9.超码或超键（Super Key）；在关系中的一个码中移去某个属性，也能代表唯一的码称为超码
10.候选码或候选键（Candidate Key）；在关系中一个码中不能移除任何一个属性，移除后就不能代表唯一，则称这类码为候选码或候选键
11.主码或主键（Primary Key）；挑选关系中的一个候选码用来标识关系的元组
12.全码或全键（All-Key）；一个关系模式的所有属性集合就是全码或全键
13.主属性（Primary arrtibute）和非主属性（Nonprimary Arribute）；关系中包含任何一个候选码中的属性称为主属性，不包含任何一个候选码的属性称为非主属性
14.外码或外键（Foreign Key）；当关系中某个属性不是当前关系的主码或候选码，而是另一个关系中的主码或候选码时，称该属性为当前关系模式的外码或外键
15.参照关系（Referencing）和被参照关系（Referenced）；参照关系称为从关系，被参照关系称为主关系，以外码作为主码的称为被参照关系；外码所在的关系称为参照关系。
16.域（Domain）；属性的取值范围
17.数据类型（Data Type）；每个列都有相应的数据类型
18.关系模式（Relation Schema）；在关系数据库中，关系模式是型（type），关系是值，即关系模式是对关系的描述
19.关系数据库（Relation Database）；以关系模型作为数据的逻辑模型，并采用关系作为数据组织方式的一类数据库，数据库操作建立在关系代数的基础上。
2.关系操作集合
1.基本的关系操作
1.查询；选择、投影、连接、除、并、交、差、笛卡尔积
2.数据更新；插入、删除、修改
3.关系操作的特点；操作的对象都是集合
2.关系数据语言的分类
代数方式；主要有关系代数，通过对关系的操作来表达查询要求
逻辑方式；关系演算，它使用谓词来表达查询要求的方式
3.关系代数
集合运算符
并、差、交、笛卡尔积
专门的关系运算符
选择、投影、连接、除
比较操作符
大于、大于等于、小于、小于等于、等于、不等于
逻辑操作符
非、与、或
3.关系的完整性约束
1.实体完整性约束
实体完整性约束是指关系的主属性，即主码的组成不能为空，也就是关系的主属性不能为空值
2.参照完整性约束
实体之间存在某种联系，保证表于表之间的属性关系，保证数据完整性
3.用户定义完整性约束
针对某一应用环境的约束条件，反映了具体应用设计的数据应满足的要求
4.关系模型完整性约束的检验
插入、删除、更新以后数据不出错
3.关系数据库的规范化理论
1.关系模式中可能存在的冗余和异常问题
1.数据冗余
在一列中重复出现的数据值
2.更新异常
数据冗余导致的多行元组更新
3.插入异常
插入空值到非空属性中
4.删除异常
删除所有信息以后找不到对应信息
2.函数依赖与关键字
定义：设R是任意给定关系，对于R中的属性X的每一个值，R中的属性Y只有唯一值与之对应，则称X函数决定Y，或称Y函数依赖于X，记错X->Y，其中X称为决定因素
如：学号->学生姓名
1.完全函数依赖
定义：R为任一关系，X、Y为其属性集，若X->Y，切对于X中的任何真子集X`都有X`-/->Y，则称Y完全依赖于X
如：小范围内（出生地址，日期，性别）->姓名
2.部分函数依赖
定义：R为任意关系，X、Y为其属性集，若X->Y，且X中存在一个真子集X`满足X->Y，则称Y部分函数依赖于X
如：（学号，身份证号）->姓名
3.传递函数依赖
定义：R为给定关系，X、Y、Z为其不同属性子集，若X->Y，Y-/->X，Y->Z，则有X->Z则称Z转递依赖于X
如：（学号->专业->系）则有（学号->系）
关键字（候选码的概念一样）
定义：R为任意关系，U为其所含的全部属性，X为U的子集，若有完全函数依赖X->U，则X为R的一个候选关键字
3.范式于关系规范化过程
第一范式1NF
满足最低要求的（（行列和元）数据全部切分到不可再分互不影响）
第二范式2NF
在第一范式的基础上进一步满足一些新要求（数据存在冗余，进行表的切分，减少数据冗余）
第三范式3NF及其改进型是BCNF
在第二范式的基础在进行步满足新要求（保证主键唯一性）
数据库设计
1.数据库的设计概述
1.生命周期
1.数据库分析设计
1.需求分析
2.概念设计
3.逻辑设计
4.物理设计
2.数据库的实现与操作
1.实现
2.操作&监督
3.修改&调整
2.数据库的重要目标
1.满足应用功能需求
2.良好的数据库性能
3.数据库设计的内容
1.数据库结构设计
2.数据库行为设计
4.数据库的设计方法
1.直观设计法
2.规范设计法
1.新奥尔良设计法
2.给予er模型的数据库设计方法
3.给予第三范式的设计方法
3.计算机辅助设计法
5.数据库设计的过程
1.需求分析
2.结构设计&行为设计
3.数据库实施
4.数据库运行与维护
2.数据库设计的基本步骤
1.需求分析
1.确定数据库范围；确定数据库应该支持哪些功能
2.应用过程分析；了解并分析数据与数据处理间的关系。在范围确定之后数据库设计人员应了解对数据做何处理何处理对策略以及结果。
3.收集与分析数据
1.静态结构；指不施加应用操作到数据上时，数据到原始情况。（如：配置表）
2.动态结构；应用操作施加于数据之后数据到状况。（如：普通数据）
3.数据约束；使用数据时到特殊要求
4.编写需求分析报告
1.数据库到应用功能目标
2.表明不同用户视图范围
3.应用处理过程需求说明
4.数据字典
5.数据量
6.数据约束
2.概念结构设计
在需求分析中，产生到需求分析报告基础上，按照特定到方法设计满足用户需求到信息结构，此结构称为概念模型。一般采用E-R图作为概念模型到描述工具
3.逻辑结构设计
1.概念设计
2.模型转换
3.自模式设计&应用程序设计说明
4.设计评价
5.物理设计
4.物理设计
确定数据库存储位置，方法，结构，建立索引，物理块大小，缓冲区大小，数据压缩等选择等。
5.数据库等实施
1.加载数据
2.应用程序设计
3.数据库试运行
6.数据库等运行和维护
经过运行，确认无故障，系统能投入生产实际运行中标志者数据库设计和应用开发等基本完成。系统维护中最困难的工作时数据库的重组和重构。
3.关系数据库设计方法
1.关系数据库设计过程与各级模式
二级映像（概念模式-逻辑模式的映像；逻辑模式-内模式的映像），三级模式（外模式-模式-内模式）
2.概念结构设计方法
1.E-R图表示方法；1对1（1:1），1对多（1:N），多对多（N:M）
2.局部信息结构设计
1.确定局部范围
2.选择实体
3.确定实体关键字属性
4.确定实体间联系
5.确定实体的属性
3.全局信息结构设计
1.属性冲突
2.命名冲突
3.结构冲突
3.逻辑结构设计方法
1.E-R图向关系模型的转换
2.数据模型的优化；多对多关系优化
3.设计用户子模式
4.物理设计方法
1.建立索引
2.建立聚集
SQL与关系数据库基本操作
1.SQL概述
SQL的组成；定义语言DDL、数据操纵语言DML、数据控制语言DCL
2.MySQL预备知识
1.常量
1.字符串常量；由单引号或双引号扩起来的字符序列
2.数值常量；整数常量和浮点数常量
3.16进制常量；0xA8
4.日期时间常量；如：“1999-06-14”数据类型为Date
5.bit
6.布尔值；TRUE或FALSE FALSE=0 TRUE=1
7.NULL值；无数据
2.变量
1.用户可以在表达式中使用自己定义的变量，称为用户变量
3.运算符
1.+-*/%
2.比较运算符：= > < >= <= <>&!= <=>
3.逻辑运算符
1.NOT或！ 逻辑非
2.AND或&& 逻辑与
3.OR或｜｜ 逻辑或
4.XOR 逻辑异或
4.表达式
定义：把常量，变量，复杂计算，运算符等组合起来得到一个值
5.内置函数
ABS函数（绝对值函数）；sort（排序函数）；COUNT（聚合函数）等
3.数据定义
1.数据库模式定义
1.创建数据库 Create database
2.选择数据库 user db_xxx
3.修改数据库 alert databases db_xxx
4.删除数据库 drop databases db_xxx
5.查看数据库 show databases
2.表定义
1.数值类型
1. INT
2.FLOAT DOUBLE DECIMAL
2.日期和时间类型
1.日期类型 DATE YEAR
2.日期时间类型 DATETIME TIME
3.时间戳类型 TIMESTAMP
3.字符串类型
1.固定长度类型 CAHR 最长255
2.可变长度类型 VARCHAR 最长是65535
3.文本类型 TEXT
4.创建表 create table
5.修改字段 alter table tb_xxx
6.删除字段 alter table tb_xxx drop [coloumn]
7.重命名 alert table xxx rename to xxx
8.删除表 drop table xxx
9.查看表 show tables
10.查看表结构 show coloumns from xxx
3.索引定义
索引
用途划分
1.普通索引（index）
2.唯一性索引（unique）
3.主键（primary key）
4.全文索引（fulltext引擎MyISAM）
5.聚簇索引（引擎innodb）
列级索引
单列索引
组合索引
1.索引的创建
CREATE INDEX index_name ON xxx
2.索引的查看
SHOW index
3.索引的删除
DROP INDEX index_name on XXX
4.数据更新
1.INSERT INTO 插入语句
2.DELETE FROM 删除语句
3.UPDATE 更新语句
5.数据查询
1.SELECT WHERE语句
6.视图
数据库编程
1.存储过程
1.储存过程的基本概念
一组完成某特特定功能的sql语句集
优点
1.提高运行速度
2.增强sql灵活性功能性
3.可以降低网络通信量
4.减轻了程序编写的工作量
5.简介实现安全控制
语法格式
CREATE procedure [存储过程名](参数)
2.创建存储过程
修改结束符语法：delimiter$$
因为在mysql运行命令中结束符为；所以为了代码中有分号发生冲突，所以需要上面这个先修改结束符
3.存储过程体
1.局部变量：Declare 变量名 变量类型[默认值]：例如 Declare sno char（10）
2.SET语句：SET 变量名=expr[,变量名=expr]...
3.SELECT ...INTO语句：返回的结果只能有一行例如：select CLOUMN(A,B,C) INTO VALUES(A,B,C) where....
4.流程控制语句
1.IF语句
语法格式为：IF ...THEN...ELSEIF...ELSE...ENDIF
2.CASE
语法格式为：CASE value WHEN parm==value THEN...END CASE
3.循环语句
WHILE
WHILE 条件为真 DO 执行内容 END WHILE
REPEAT
REPEAT 执行内容 UNTIL 条件为真 END REPEAT
LOOP
LOOP 执行内容 END LOOP
5.游标
1.定义：DECLARE 游标名 CURSOR FOR 查询条件
2.打开游标：OPEN 游标名
3.读取数据：FETCH 游标名 INTO 变量名
4.关闭游标：CLOSE 游标名
4.调用存储过程
CALL 存储过程名(参数...)
5.删除存储过程
DROP PROCEDURE [IF EXISTS] 存储过程名
2.存储函数
1.创建存储函数
1.查看：SHOW FUNCTION STATUS
2.创建语法：CREATE FUNCTION 函数名(参数) RETURNS 返回值
2.调用存储函数
语法格式：SELECT 函数名（参数）
3.删除存储函数
语法格式：DROP FUNCTION [IF EXISTS] 函数名
数据库安全与保护
1.数据库完整性
1.完整性束条件的作用对象
1.列级约束：varchar（10），varchar为类型，10为长度
2.元组约束：元组之间字段关系相互约束，比如开始时间小于结束时间
3.表级约束：元组之间，关系之间的联合约束
2.实体与实现完整性约束
1.实体完整性：保证记录不重复，primary key保证键值唯一
候选键约束关键字unique进行约束
1.一个表只能存在一个主键，可以定义多个候选键
2.定义主键约束时，系统会自动生成primary key索引，定义候选键约束时，系统自动产生unique索引
2.参照完整性
定义：主要指两个表之间的关系，保证数据的正确性，不能凭空出现不存在的业务关联。比如没有教师，就不应该有教师数据
语法格式：references 外键 [其他表主键]
3.自定义完整性
非空约束
自定义约束；语法是：约束CHECK（分数>=0 and 分数<=150）
3.命名完整性约束
语法为：CONSTRAINT [约束名]
4.更新完整性约束
1.删除（修改）完整性约束
ALTER TABLE [表明] DROP FOREIGN KEY [外键约束名]
ALTER TABLE [表明] DROP PRIMARY KEY
ALTER TABLE [表名] DROP [约束名]
2.添加约束
ALTER TABLE [表名] ADD [CONSTRAINT 约束名] PRIMARY KEY(字段名)
ALTER TABLE [表名] ADD [CONSTRAINT 约束名] FOREIGN KEY (外键字段名) REFERNCES被参照表（主键字段名）
ALTER TABLE [表名] ADD [CONSTRAINT 约束名] UNIQUE KEY (主键字段)
2.触发器
保护表数据的数据库对象
CREATE TRIGGER 触发器名称 触发器时间 触发事件 ON 表名 FOR EACH ROW 触发内容
DROP TRIGGER [IF EXIST][数据库].触发器名字
使用触发器
insert
update
delete
3.安全性与访问控制
1.用户账号管理
1.创建用户账号
语法格式：CREATE USER user [IDENTIFIED BY [PASSWORD] '密码']
IDENTIFIED BY 可以指定密码；PASSWORD()函数用于加密设置的密码在数据库中的记录
其中user的格式为'user_name'@'host_name'
查看用户信息：SELECT user,passord from mysql.user;
2.删除用户
语法格式：DROP USER 用户名，用户名
3.修改用户账户
语法格式：RENAME USER 旧用户名 TO 新用户名
需要有CREATE 和UPDATE权限
4.修改用户口令
语法格式：SET PASSWORD [FOR user]=PASSWORD('新密码')
不加[FOR user]表示修改当前用户；user须以'user_name'@'host_name'的格式
4.事务与并发控制
事务的概念
用户定义的一个数据库操作序列，这些操作，要么全部做，要么全部不做
事务是控制和操作的基本单位
事务的特性
1.原子性
2.一致性
3.隔离性
4.持续性
并发操作的问题
1.丢失更新
2.不可重复读
3.读脏数据
封锁
1.锁：允许或阻止一个事务对一个数据的存取特权
排他锁
共享锁
2.用封锁进行并发控制
排他锁就是互斥锁
共享锁就是只读锁
事务一直占有获得的锁，知道结束时释放
3.封锁的粒度
用来描述奉送的数据单元的大小；粒度越大，并发性越大，开销越大，复杂性也越大
4.封锁的级别
0级封锁；价值不大
1级封锁；没提交更新不算
2级封锁；不允许写不允许读提交的数据
3级封锁；任何提交不过
5.活锁或死锁
活锁；级别低的事务永远无法执行
死锁；两个事务循环使用彼此
6.可串行性
一个事务一个调度，按照顺序执行
5.备份与恢复
数据库应用设计与开发实例
数据库管理技术的发展
软件工程
软件开发的本质
软件工程概念的提出与发展
1.软件危机
1.软件开发的速度
2.软件制品的质量
3.软件开发的成本
2.软件工程
应用计算机科学理论和技术以及工程原则和方法，按预算和进度实现满足用户要求的软件产品的工程
3.软件工程的发展
20世纪60-80年代
开发模型、开发方法、支持工具
20世纪80年代末-至今
软件复用技术、软件生产管理
软件开发的本质
软件的概念
程序=开发+文档
软件开发的目标
映射
将问题域中概念映射为运营平台层面上的概念
软件开发的本质
不同抽象层属于之间的映射，以及不同抽象层处理逻辑之间的映射
1.如何实现这样的映射
技术问题
2.如何管理这样的映射
过程途径
问题建模
模型的概念
模型是一个抽象。
模型的类别
概念模型；描述软件是什么
软件模型；实现概念模型的软件解决方案，包括设计模型、实现模型、部署模型
软件需求与软件需求规约
需求与需求获取
需求的定义；有关与给要予构造的陈述，描述了待开发产品的功能，性能参数
需求的基本性质
必要的
少了它不行的功能
无歧义的
人们对这个需求的理解一致没有偏差
可测的
需求是否满足，有办法测量
可跟踪的
需求从提出到经过若干层映射后，是否还能找到对应的映射
可测量的
功能实现效果，是否可实现，结果是否正确
需求的分类
功能需求；是整个需求的主体（比如空调的制冷）
非功能性需求
性能需求
接口需求
设计约束
质量属性
需求发现技术
自悟
交谈
观察
小组会
提炼
结构化方法
结构化的分析方法
DFD
数据字典
决策树、决策表
掌握结构化设计方法
控制结构图、PAD图、N-S图等
需求分析面临的挑战
问题空间理解
人与人之间的通信，有效沟通
需求的变化性
需求技术的基本特征
提供方便的通信机制
鼓励需求分析人员使用问题空间的术语思考问题，编写文档
提供定义系统边界的方法
提供支持抽象的基本的机制
为需求分析人员提供多种可供选择的方案
提供特定的技术，适应需求的变化
结构化需求分析
需求分析中的基本术语
数据；客观事物的一种表示
信息；具有特定语义的数据
数据是信息的载体
数据流；数据的流动
加工；数据变换单元
数据存储
数据源和数据谭（数据目的地）
系统功能模型的表示方法
数据流图（DFD图）；一种表示数据变化的图形化工具
数据流程图的元素；数据源/数据谭，数据流，数据加工，数据存储
建模过程
自顶向下、逐步求精
建立系统环境图
0层图；从0层图开始对流程图中的要素编号
流程图的绘制过程
0层图；要对处理编号：1.2.3....
1层图；编号规则：1.1、1.2、2.1、。。。
建模过程2-数据字典
定义数据流程图中所有数据流和数据存储的数据结构
顺序结构：+
选择结构：|
重复结构：{ }
子界：m...n
建模过程3-加工的描述
判定表
也称为决策表，是一个二维表，它说明了每一种条件组合所产生的结果
左上限代表所有的条件；左下限代表可能的结果
右上限代表每一种条件的取值（用Y和N来表示）
右下限用X表示所对应的条件组合所产生的结果
判定树
也称为决策树，是用来描述在一组不同的条件下，决策的行动是根据不同条件及其曲直濑选择的处理过程。
结构化语言
若逻辑关系比较简单，可以用结构化自然语言来描述
应用中注意的问题
模型平衡问题
DFD图与数据字典的一致
底层加工的处理逻辑描述，与数据字典一致
信息的复杂性控制问题
上层数据流可以打包
下层模块的个数：4，5，6，7，8，9
每个加工的数据流不能太多；增加层次
表示方法
数据流；数据源--->数据谭
加工；椭圆形
数据存储；=====
数据源和数据谭；长方形
需求验证
验证：必要性、无歧义性、可测性、可跟踪行、可测量性。
需求中发现的错误类型
不正确的事实：40%
遗漏：31%
不一致：13%
歧义性：5%
错放：2%
其他：9%
结构化设计
总体设计：以系统为对象
把系统的功能需求分配到一个特定的软件系统结构中
引入两个概念
模块：软件中具有特定标识的独立成分
模块调用：模块之间的一种使用关系
总体设计的步骤
将DFD图映射为设计层面的模块及模块调用
将DFD图转换为初始的模块结构图
基于 高内聚、低耦合的软件设计原理，通过模块化，将出视的模块结构图转换为最终的结构图
两种映射方法
变换设计
基于变化的数据流程图是一个线性的顺序结构，由输入、输出和变换中心三部分组成
事务设计
基于事务的数据流程图中有一个事务处理中心，它将输入分为许多相互平行的加工路径，然后根据输入的属性，选择某一加工路径
模块化及其启发式规则
模块
模块通常由2部分组成：模块接口和模块体
如何将系统分解成软件模块
分而治之和抽象
自顶向下，逐步求精
形成模块层次结构
模块化
将一个待开发的软件分解成若干个简单的、具有高内聚，低耦合的模块，这个过程称为模块化
模块耦合
两个模块之间相互依赖程度的一种度量。依赖越大耦合越大，依赖越小耦合度就小
模块耦合类型
内容耦合：一个模块直接修改或操作另一个模块的数据
公共耦合：两个模块靠一个全局变量
控制耦合：一个模块向另一个模块传递控制信号
标记耦合：一个模块向两个模块传递一个公共参数
数据耦合：模块之间通过参数来传递数据
模块内聚
一个模块内部成分之间的相互关联程度的度量，是对模块内各处理动作组合强度的度量
内聚的类型
偶然内聚：模块的各成分没有任何关系
逻辑内聚：逻辑上相关的处理放一起
时间内聚：模块内的功能在同一时间完成
过程内聚：模块内的处理以特定的次序执行
通信内聚：操作统一数据集
顺序内聚：一个成分的输出作为另一个成分的输入
功能内聚：模块的所有成分完成单一的功能
启发式规则
高内聚、低耦合
改进软件结构，提高软件独立性。模块分解
模块规则适中
力求深度、宽度、扇出、扇入适中。
深度：表示起控制的层数
宽度：同一个层次上的模块总数的最大值
扇出：一个模块直接控制的下级模块的数目
扇入：有多个上级模块直接调用它
尽量使模块的作用域在其控制域内
模块的控制域：这个模块本身以及所有直接或间接从属它的模块集合
模块的作用域：受该模块内一个判断所影响的所有模块的集合
尽力降低模块接口的复杂度
力求模块功能可以预测
总体设计的3个阶段
初始阶段；根据DFD数据流图复审和精细化后，生成初步的模块结构图
精化阶段; 根据生成的精化模块结构图，进行模块的全局数据结构和模块的接口设计
复审阶段；对前两部生成的结构进行复审，必要时进行精化
设计规约
完整准确的描述需求规约所要求的所有功能模块，以及伴随功能模块而出现的非功能机构
概要设计规约（总体设计）
指明高层软件体系结构
系统环境
软件模块的结构
模块描述
文件结构和全局数据文件的逻辑结构
测试需求
详细设计规约
软件设计人员和程序员之间交流的媒体
个处理过程的算法
算法所设计的全部数据结构的描述
详细设计：以模块为对象
定义：具体描述模块结构图中的每一个模块，给出实现模块功能的实施机制，包括一组例程和数据结构
目标：将总体设计阶段产生的系统高层结构映射以相关术语表达的底层结构，也是系统的最终结构
设计方法：是一种基于结构的编程方法，即采用顺序结构、选择结构和重复结构进行编程，其中每一个结构只允许一个入口和一个出口
本质：是程序的控制流程线性化，实现程序动态执行顺序符合静态书写的结构，提高可读性
详细设计的工具
程序流程图
合图（N-S图）
出于要有一种不允许违背结构程序设计精神的图形工具的考虑
PAD图
是问题分析图，用二维树形结构的图来表示程序的控制流。
类程序设计语言PDL
也称为伪码，用正文形式表示数据和处理过程的设计工具
具有严格的关键字，用于定义控制结构和数据结构，同时可以使用自然语言
面向对象方法-UML
知识结构
1.UML提供了哪些属于，用于抽象表达客观世界中的各种事物
2.UML提供了哪些术语，用于抽象表达客观世界中的各种事务之间的关系
3.UML提供了哪些术语，用于抽象表达客观世界中的各个模型
面向对象建模过程步骤
1.需求获取
建立用例（use case）模型和用例场景
2.需求分析
建立活动图和状态图
类图
顺序图
3.编写需求规格说明书
4.需求验证
UML术语表
表达客观事物的术语
1.对象（object）
2.类（class）
类语义的进一步表达
详细叙述类的职责
通过类/操作的注解，详细注释类的定义
通过类/操作的注解，详细注释各操作的前置条件和后置条件
详细描述类的状态机（状态图）
详述类的内部结构（活动图）
类与其他类的协作（协作图）
类的语义表达的详细程度取决于建模的意图
为了与最终用户和领域专家沟通：较低的形式化手段
为了支持正向和逆向工程：采用给较高的形式化手段
为了对模型进行推理，证明其正确性：采用很高的形式化手段
类在建模中的用途
模型化问题域中的概念
建立系统的职责分布模型
模型化建设中使用的基本类型
类要满足的基本条件
一个结构良好的类，必须符合下列条件
明确抽象了问题域或解域中某个有形事务或概念
包含了一个笑的、明确定义的职责集，很好的实现
很好的地分离了抽象和实现
3.接口
接口的含义
接口是操作的一个集合，其中每个操作描述了类、构件或子系统的一个服务
接口的表示（interface）
在图中以圆圈表示"供接口" 用半圆表示“需接口”
使用中的问题
如何描述接口的语义
应用中应当注意的问题
应用中注意的问题
接口只能被其他的类目使用，本身不能访问其他类
接口描述类的外部可见操作，通常是该类的一个特定有限行为
接口不描述其中操作的实现，也没有属性和状态
接口之间没有关联、泛化、实现和依赖
4.协作
协作是一个交互，设计交互的三个要素：交互各方，方式，内容
椭圆虚线
5.（use case）用例/用况
对一组动作序列的描述，系统执行这些动作产生对特定参与者有值的，可观察的结果
椭圆
6.主动类
至少具有一个进程或线程的类，能够启动系统的控制活动，并且其对象的行为通常与其他元素行为并发的
表示方法：两条竖线
用来模型化系统中的并发行为
7.构件/组件
系统设计中的一种模块化的部件，通过外部接口隐藏了它的内部实现
具有相同接口的构件可以相互替代
构件可以嵌套
构件用于表达解空间中可独立标识的成分
8.制品
系统中包含物理信息的，可替代的物理部件
部署制品：这类制品是构成一个可执行系统必要而充分的制品，入DLL、EXE文件
工作产品制品：这类制品本质上是开发过程的产物，由源代码文件、数据文件等用来创建不熟制品的事物
执行制品：这类制品是作为一个正在运行的系统的结果而被创建的，一般存在于内存中
9.节点
在运行时存在的物理元素，通常表示一种具有记忆能力和处理能力的计算机资源
表达关系的术语
关联
描述的是类和类之间的静态关系
是一种结构关系，是对一组具有相同结构、相同链的表述
链：对象之间具有特定语义的抽象
聚合：一个类包含在另一个类中（我和我买的书）
组合：聚合的一种特殊形式（我和我的器官）
泛化
特殊类（子类）的对象拥有其一般类（父类）的全部属性和服务，称作特殊类对一般类的继承
细化
类之间的语义关系，其中一个类约束了另一个类的执行
依赖
一种使用关系，用来描述一个类使用另一个类的信息和服务
绑定
导出
允许
实例
关系术语的使用
结构关系
继承关系
精化关系
依赖关系
表达组合关系的术语-包
模型元素的分组
UML的模型表达格式
类图
表达了系统的静态结构信息，即系统由哪些类组成，类之间的关系
构建类图的三个关键问题
有哪些类
类如何描述，属性及操作
类之间的联系
用例(use case)图
系统的使用者，在使用系统时的交互过程的一个文字描述序列
是一种表达系统功能模型的图形化工具
状态图
使用状态、时间、和转换来记录对象在生命周期中所经历的状态序列
1.初态：对象的初始状态时途中任何时间都未对该对象起作用时的状态
2.通常状态：状态代表对象生命周期中的某一个瞬间
3.状态转换：转换表名作为对事件的响应结果，对象将从一种状态转换到另一种状态并执行某个动作
4.状态转换的条件：触发状态转换的时间在状态转换字符串中命名。双击一个状态转换，除状态签名外，还可用用字符串为其加注临界条建，动作表达式等标签
状态图中的3个术语
状态：一个实例所处的特定阶段、所具有的对外呈现以及所能提供的服务
事件
信号事件
调用事件
时间事件
变化事件
状态转移
顺序图
顺序图表示了对象之间传送消息的时间顺序，也就是对象之间的交互顺序
这些交互是指在场景或用例的事件流中发生的
每一个对象（类）用一条生命线来表示；即用垂直线代表整个交互过程中对象的生命期
生命线之间的箭头连线代表消息
顺序图中的基本元素包括
活动者，指用例中的活动者
对象，指在用例中的内部对象
生命线：在顺序途中的一个对象下面的竖线，用以显示这个对象的生命期
消息，指场景内由事件流定义的内部事件成为在对象和活动者或其他对象之间的消息
同步消息；返回消息，返回消息用虚线、箭头也不是实心来表示
反身消息；消息的发送方和接收方同一个对象
异步消息；没有返回值的消息，用非实心箭头表示
定时消息；对消息附加时间约束条件
控制操作子
为了控制交互行为描述的复杂性，以便更清晰的表达顺序图中的复杂控制
1.选择执行操作子（Opt）由两部分组成，一个是监护条件，一个时控制体
2.条件执行操作子（alt）控制提通过水平线将其分成一些部分，每一部分表示一个条件分支，每个分支有一个监护条件
3.并发执行操作子（par）通过水平线将其分成多个部分，每一部分表示一个并行计算。
4.迭代操作子（loop）
面向对象方法-RUP
是对象管理组织所推荐的一个有关过程的标准，是基于UML的一种过程框架。
1.知识结构
过程模型
1.需求获取模型
2.需求分析模型
3.软件设计模型
4.软件实现模型
5.软件测试模型
RUP的特点
以用况（用例）驱动的、以体系结构为中心的迭代、增量式开发
1.用况驱动；在系统的生命周期中，用用例作为基础，驱动系统有关人员对索要建立系统的功能需求进行交流
2.以体系结构为中心
系统体系结构；是对系统语义的概括描述，对所有项目有关人员都能理解
关注子系统、构件、接口、协作、关系和节点等重要模型元素，忽略其他细节
3.迭代与增量
迭代时重复的部分
增量式增加的部分
初始阶段基本目标
获得与特定用例和平台无关的系统体系结构轮廓
位系统建立商业案例
确定项目边界
从业务角度指出该项目的价值
生命周期目标里程碑
细化阶段
分析问题领域，建立健全的体系结构基础编制项目计划，淘汰项目中最高风险元素
生命周期结构里程碑
构造阶段
形成最终的系统体系结构
开发完整的系统
确保产品可以开始向客户交付
初始功能里程碑
交付阶段
确保软件对最终用户可用
基于用户反馈的少量调整
产品发布里程碑
核心工作流
6个核心过程工作流，3个核心过程支持工作流
1.需求获取
RUP运用用例技术来获取需求
需求获取的基本步骤
列处候选的需求：特征列表
搜取特征：时一个新的项（Item），并且要有简要的描述
理解系统语境：领域模型或业务模型
创建领域模型或业务模型
业务用例模型：业务参与者和业务用例
业务对象模型：三个术语：工作人员、业务实体、工作单元：用交互图和活动图来表达
捕获功能需求：用例模型
发现和描述参与者
发现并描述用例
确定用例的优先级
精化用况
构造用户界面模型
用例模型的结构化
捕获非功能性需求：补充需求或者针对一些特定的用例
2.需求分析
目标：在系统用例的模型基础上，创建系统分析模型以及体系结构描述
1.术语
分析类：时类的一种衍生类型，很少有操作和特征标记，而用责任来定义其行为，并且期属性和关系也是概念性的
2.用例细化
用例细化是一个协作
针对一个用例，在继续划分为更小的相互作用的细化
3.分析包
体现了局部化，问题分离的设计原理
把一些变化限制到一个业务过程、一个参与者的行为或者一组紧密相关的用例，形成一些不同的分析包
体现，高内聚，低耦合
2.分析模型的表达
分析模型是由 分析系统 来定义的
分析系统包含一组具有层次结构的包
一个包可以包含一些分析类和用况细化
3.分析的主要活动
体系结构分析
标识分析包
处理分析包之间的共性
标识服务包
定义分析包的依赖
标识重要的实体类
标识分析包和重要实体类的公共特性需求
用例分析
标识分析类
描述分析类之间的交互
类的分析
标识责任
标识属性
标识关联和聚合
包的分析
包的分析
确保分析包尽可能与其他包相对独立
确保分析包实现了它的目标，即细化了某些领域类或用例
描述依赖
需求分析总结
三个术语：分析包、分析类、用例细化
四个步骤
体系结构分析
细化用例
对类分析
对包进行分析
一个成果：分析模型
3.软件设计
软件设计：定义满足需求规约所需要的软件结构
RUP的设计目标：定义满足系统/产品分析模型所规约需求的软件结构
1.相关术语
设计类
用例细化
设计子系统
接口
2.设计模型、部署模型及相关视角下的体系结构描述
1.设计模型
设计子系统
设计类
用例细化
接口
2.部署模型：时一个对象模型，描述的是系统的物理分布，即如何把功能分布在各个节点上
3.设计的主要活动
活动1：体系结构设计
表示节点和它们的网络配置
标识子系统和它们的接口
标识在体系结构方面有意义的设计类和它们的接口
标识一般性的设计机制
活动2：用例的设计
标识参与用例细化的设计类
标识参与用况细化的子系统和接口
活动3：类的设计
概括描述设计类
标识操作
标识属性
标识关联和聚合
标识泛化
描述方法
描述状态
活动4：子系统设计
维护子系统的依赖
维护子系统所提供的接口
维护子系统内容
RUP设计小结
RUP设计的特点
使用了一种公共的思想来思考设计，并使得设计可视化
给出了有关子系统、设计类和接口的需求
支持对底线工作的分解，可以由不同开发设计组可能同时处理和管理的部分
RUP的设计方法
给出表达设计模型的基本成分术语
规约了设计模型的语法，知道模型的表达
给出了创建设计模型的过程以及相应的指导
RUP的设计模型
设计子系统和服务子系统，以及它们的依赖、接口和内容
设计类，以及它们具有的操作、属性、关系及实现需求
用例细化
设计模型视角下的体系结构描述
RUP的部署模型
节点，它们的特征以及连接
主动类到节点的初始映射
设计阶段的活动
体系结构设计
设计用例
设计类
设计子系统
RUP设计对实现的影响
设计子系统和服务子系统由实现子系统予以实现
射击类由文件化构件予以实现
在规划实现工作使，将要使用用例细化以产生一些构造
在节点上部署构件、形成分布系统时，将使用部署模型和网络配置
4.RUP的实现和测试
RUP的实现目标
基于设计类和子系统生成构件
对构成进行单元测试
进行集成和连接
把可执行的构件映射到部署模型
RUP实现的主要活动
实现体系结构
集成系统
实现子系统
实现类
完成单元测试
RUP的测试
包括内部测试、中间测试和最终测试
RUP测试包括的主要活动
计划测试
设计测试
实现测试
执行集成测试
执行系统测试
评价测试
软件测试
软件测试的目标与测试过程模型
软件测试的目的
通过软件测试尽可能多发现并且改正软件中存在的错误
软件测试的对象
软件=程序+文档
测试对象：各个阶段产生的源程序和文档
软件测试的定义
软件测试：按照特定规程发现软件错误的过程
使用人工或自动手段，运行或者测定某个系统的过程，检测它是否满足规定的需求，了解预期与实际结果之间的差异
测试和调试的区别
测试证明失败，调试证明正确
测试已知条件开始
测试时有计划
测试是一个发现错误、改正错误、重新测试的过程
测试的执行有规程
测试由独立的测试小组完成
测试的执行和设计可由工具支持
测试过程模型
测试设计
环境模型
对象模型
错误模型
测试执行
测试结果比较
软件测试技术
人工测试
个人复查
走查
会审
机器测试
黑盒测试
白盒测试
路径测试技术
是一种白盒测试技术
一句的时程序的逻辑结构
采用控制流程图来表达被测程序模型
通过合理的选择一组穿过程序的路径，以达到某种测试度量
1.控制流程图
是一种表示程序控制结构的图形化工具，其基本元素是过程快、节点、判定
过程块：没有被判定或节点分开的程序语句
判定：是一个程序点，控制流出现分叉
节点：也是程序点，控制流汇聚的地方
链：过程块、判定、节点之间具有特定语义的一种关系，用“→”来表达
路径：由若干条链组成的链的集合（对软件测试而言，路径都是从入口开始，从出口结束）
2.测试策略
路径覆盖：执行所有可能穿过程序控制流程的路径，最强的测试度量
语句覆盖：至少执行程序中所有语句一次，最低的测试度量
分支覆盖：至少将程序的每个分支执行一次，条件覆盖于条件组合覆盖
3.路径的选取与用例设计
最小的强制性测试需求是语句覆盖率
路径选取的一般原则
选择最简单的，具有一定功能含义的入口，出口
在已选择的基础上，选择五循环的路径，选取短路径，简单路径
选取没有明显功能含义的路径，研究该路径为什么存在
基于事务流的测试技术
是一种功能测试技术
属于黑盒测试技术
事务：从系统用户角度触发，所见到的一个工作单元，有其生，有其亡
短信提醒
节日问候
数据更新
事务流：是系统行为的一种表示方法，为功能测试建立了程序的动作模式。
事务流程图：表达系统的行为，多个事务流的并行
并生：事务处理产生一个新事务，由此这两个事务继续执行
丝分裂：事务处理产生两个新事务
汇集：事务的不同活动可以汇集在一起
吸收：一个事务可以被另一个事务吸食
结合：两个事务结合后产生一个新事务
等价类法
根据I/O特定，划分为N个区段，那么抽取区段内任意一个条数据进行测试，就能代表区段内的任何数据进行测试的结果
边值分析法
是一种根据I/O边界等价类上或紧靠边界的条件，选择测试用例的更有效的方法
因果图法
输入条件和输出结果，通过分析它们的因果图，转换成一张判定表，为每种输入条件的组合设计测试用例
原因和原因的约束关系
E（互斥）：只能有一个成立
I(包含)：至少有一个条件成立
O（唯一）：有且仅有一个成立
R（要求）：当a出现时，b必须出现
M（屏蔽）：当a=1时，b必须是0；当a=0时，b不确定
因果图生成步骤
步骤1：找出模块的原因（输入条件的等价类）和结果
步骤2：分析原因和结果之间的对应关系，画出因果图
步骤3：在因果图上标志出一些特定的约束和限制条件
步骤4：把因果图转换成判定表
软件测试步骤
单元测试
测试单个程序模块，测试逻辑和功能是否正确
单元测试要考虑模块的4个特征
模块接口
局部数据结构
重要的执行路径
错误执行路径
单元测试还需要开发驱动模块和承接模块
驱动模块：调用被测试模块的模块
承接模块：被测试模块调用的模块
集成测试
模块之间的接口正确性
两种策略
自顶向下的集成测试：需要设计承接模块
自底向上的集成测试：需求设计驱动模块
有效性测试
发现软件的功能和需求规约是否一致
软件生存周期过程及管理
软件生存周期过程概述
基本思路：过程类->过程->活动->任务 ; 关系都是（1:n）
软件生存周期过程分类
基本过程
与软件生产直接相关的活动集
包括5个过程
获取过程
供应过程
开发过程
运行过程
维护过程
支持过程
是指有关各方按他们的目标所从事的一系列支持活动集。
文档过程
配置管理过程
质量保证过程
验证过程
确认过程
联合评审过程
审计过程
问题解决过程
组织过程
与软件生产组织有关的活动集
包括4个过程
管理过程
基础奢侈过程
培训过程
改进过程
《ISO/IEC软件生存周期过程12207-2008》标准
2个过程类、7个过程组、43个过程
2个过程类
系统语境过程（4/7个过程组）
协议过程组
项目过程组
技术过程组
组织上项目使能过程组
软件开发的过程（3/7个过程组）
软件实现过程组
软件支持过程组
软件复用过程组
过程描述
结构：过程->活动->任务
供应过程
1.意图：为获取放提供满足所协商需求的产品或服务
2.活动和任务
机遇标识
供应方投标
合同协商
合同执行
3.结果
1.标志了产品或服务的获取方
2.对获取方的要求作必要响应
3.建立获取方和供应方之间的协议
4.供应方开发了满足所协商商品需求的产品/服务
5.按所协商的需求向获取方交付了相应的产品/服务
软件实现过程
1.意图：把规约好的接口、行为和实现约束转换为一些动作，创建“软件项”的软件产品和服务作为系统元素
2.活动和任务
软件实现策略
3.结果
1.定义了实现策略
2.标志了有关设计方面的实现技术方案
3.实现了一个软件
4.按提供协议，把软件打包成一个软件并且存储
软件需求分析过程
1.意图：建立软件部分的需求
2.活动任务
1.建立软件需求和文档
2.评估软件需求，并建立相关的评估结果文档
3.按软件复审过程进行软件需求复审
3.结果
1.需求已分配给系统的软件元素
2.已分析软件需求的正确性和可测性
3.以了解软件需求对运行环境的影响
4.在软件需求和系统需求之间建立了一致性和可跟踪性
5.已定义了实现软件需求的优先级别
6.软件需求已得到批准并按照需求进行了调整
7.针对软件需求的更改对成本、进度和技术影响，已进行了相应的评估
8.建立了软件需求的基线，并于有关部门进行了沟通
软件体系结构设计过程
1.意图：为软件的实现和按需求进行验证提供设计方案
2.活动和任务
软件体系结构设计
3.结果
开发一种软件体系结构设计，描述实现该软件需求的的软件项
设计每一个软件项的内部、外部接口
软件验证过程
1.意图：证明软件产品是否满足了规约需求
2.活动和任务
1.过程实现
2.验证
3.结果
1.开发并实现了验证策略
2.标识了验证准则
3.执行了所需要的验证活动
4.标识并记录了缺点
5.给出了可用于客户和其他参与者的验证活动结果
软件确认过程
1.意图：正是所期望使用的软件产品是否满足需求
2.活动和任务
过程实现
确认
3.结果
开发并实现了确认策略
标识了所有需要的软件工作产品的确认
执行了所需要的确认活动
标识并记录了发现的问题
提供了证据证明：软件产品能够按照用户所期望的方式来使用
给出了可用于客户和其他参与人员的验证活动结果
应用说明
1.系统和软件
软件是整个系统的组成部分
区分系统需求分析和软件需求分析
2.与《ISO/IEC系统生存周期15288》的关系
3.组织层和项目层
项目可能由组织执行
4.过程之间的时序关系
没有明确过程、活动、任务之间的时间依赖的序列
支持活动之间的迭代和再现
5.过程分解
把过程划分为一些更小的“片段”
6.生存周期模型和阶段
用生存周期模型对系统或软件产品的生存模型化
模型由阶段组成
7.剪裁
针对特定的清空，修改生存周期过程
软件生存周期模型
含义：软件产品开发、运行、维护中有关过程、活动和任务的框架，覆盖了从该系统的需求定义到系统的使用终止
作用：不但为软件开发确定了一些抽象层，还定义了每一个抽象层之间的基本关系
瀑布模型
系统需求
软件需求
需求分析
设计
编码
测试
运行
瀑布模型的原理
自上而下具有相互衔接的固定顺序
每一阶段的输入，即工作对象以及本阶段的工作成功，作为输出传送到下一个阶段
瀑布模型的贡献
在确定系统怎么做之间存在一个需求阶段，它鼓励对系统做什么有一个规约
在系统构造之间有一个设计阶段，它鼓励规划系统的结构
每一阶段都有评审，允许获取方和用户的参与
前一步作为下一步被认可的、文档化的基线
瀑布模型存在的问题
要求客户能够完整、正确和清晰的表达它们的需求，并要求开发人员一开始就理解这一应用
由于需求的不确定性，使设计、编码和测试阶段都可能发生延期，并且当项目接近结束时，出现大量的集成和测试工作
在开始的阶段中，很难评估真正的进度状态，并且直到项目结束之前都不能演示系统的功能
在一个项目的早期阶段，过分的强调了基线和里程碑处的文档，并可能需要花费更多的时间用于建立一些用处不大的文档
增量模型
增量模型融合了瀑布模型的基本成分（重复应用）和原型实现的迭代特征，该模型采用随着日程时间的进展而交错的线性序列，每一个线性序列产生软件的一个可发布的“增量”。
前提：需求可结构化
适用于“技术驱动”的软件产品开发
原理
增量1：分析-》设计-》编码-》测试
增量2：分析-》设计-》编码-》测试
增量3：分析-》设计-》编码-》测试
增量模型的优点
第一个可交付版本所需的成本和时间较少
由于很快发布第一个版本，可以减少用户需求的变更
允许增量投资，即开始时支队一个或两个增量投资
增量模型的缺点
如果没有对用户的变更要求进行规划，那么产生的初始增量可能会造成后来增量的不去稳定
如果需求不像早期思考的那样稳定和完整，那么一些增量就可能需要重新开发，发布
由于进度和配置的复杂性，可能会增大管理成本，超出组织的能力
演化模型
演化模型是一种全局的软件生周期模型属于迭代开发
演化模型主要针对实现不能完整定义需求的软件开发
该模型可以表示为：第一次迭代（需求-》设计-》实现-》测试）->反馈->第二次迭代（需求-》设计-》实现-》测试）...
优点
任何功能一经开发就能进入测试以便验证是否符合产品需求
帮助导除高质量的产品要求
帮助软件开发活动的盲目性
缺点
很容易弱化需求分析阶段的工作
螺旋模型
螺旋模型是在“瀑布模型”和演化模型的基础上，加入两者都忽略的风险分析所建立的一种软件开发模型
螺旋模型强调风险分析，使得开发人员和用户对每个演化层出现的风险有所了解，继而做出应有的反应
因此特别适用于庞大、复杂并具有高风险的系统
工作过程
制定计划：确定软件目标，选定技术方案，弄清项目开发的限制条件
风险分析：分析评估所选方案，考虑如何识别和消除风险
实施工程：实施软件开发和验证
客户评估：批评古开发工作，提出修正建设指定下一步计划
螺旋模型的特点
“风险驱动”的方法体系
关注解决问题的基本步骤
喷泉模型
是一种以用户需求为动力，以对象为驱动的模型，主要用于采用面向对象技术的软件开发项目
喷泉模型认为：软件开发过程自下而上周期的各阶段是相互迭代和无间隙的特征
过程规划与管理
属于“组织上项目使能过程组”
包括四个环节
过程规划（P）
过程建立
选择软件生存周期模型
细化所选择的生存周期模型
为每一个活动或任务标识合适的实例数目
确定活动的时序关系，并检查信息流
建立过程计划的文档
成果：项目的过程计划
过程监控
软件生存周期过程的监控
软件生存周期过程改变所产生的影响评估
改变的实施
实现改变
过程检测（C）
过程执行（D）
过程调整（A）
集成化能力成熟度模型CMMI
背景与原理
集成化能力成熟度模型
目的：改善软件开发过程，能够按时不超预算的开发出高质量的软件
CMMI
软件CMM
产品集成开发CMM
系统工程CMM
CMMI的应用
过程途径的基本假设：系统或产品的质量高度受开发和维护中所使用的过程质量的影响
质量支撑点
人员
规程和方法
工具和设备
CMMI模型部件
CMMI是一种过程改善框架
过程改善：是指认为设计的一个活动程序，其目的是改进组织的过程性能和成熟度，并改进这一程序的结果
由一些过程域组成，过程域由自己的确定专用目标和公共目标。用符号长方形
每个专用目标和公共目标的实现，分别以来一些实践，用菱形
每个专用实践由自己的子实践和确定的典型工作产品符号用椭圆形，资料性部件
每个过程域还有意图陈述，间接性注释以及相关的过程域
过程域
一个业务域中一束相关的实践，当他们一起得以实现时，就满足被认为对该过程与的改善具有重要的一组条件
CMMI有22个过程域，分为4类
项目管理类
规划
监控
定量项目管理
集成项目管理
风险管理
提供方协议管理
工程类
需求开发
需求管理
技术解决方案
产品集成
确认
验证
支持类
配置管理
过程和产品质量保证
测量与分析
原因分析与解决
决策分析与解决
过程管理类
组织过程定义
组织过程性能
组织过程培训
组织过程关注
组织过程创新与部署
专用目标
一个过程域中都有一个或多个专用目标
描述该过程域必须呈现的一些独有特征
专用目标可用于帮助确定一个过程域是否得以满足
专用实践
对于达到专用目标是重要的活动
起网以专用时间所描述的活动，会导致达到一个过程域的专用目标
公用目标和公用实践
可用于多个过程域
典型工作产品
专用实践所产生的输出样品
典型工作产品是：重大偏差的记录
子实践
对专用实践、公用实践的详细描述
公用实践的精化
为一个共用实践唯一的应用于一个过程域，提供了相关的指导
意图描述
用来描述过程域的意图
简介性解释
用来描述该过程域中所设计的主要概念
相关过程域
用来描述该过程域所引用的相关过程域
国营了过程域之间的关系
CMMI的等级
能力等级
是一种过程改善路径，该路径可使组织针对单一过程域不断改善
过程能力
遵循一个过程可达到的语气结果的程度
表征组织对一个过程域的改善，是不断改善一个给定的过程域的一种手段
能力等级
包含一个共形目标及其相关的共性实践，它们与一个过程域相关联，能够改善组织同拿个过程域相关联的过程
能力等级0
未完成级；过程不完整
能力等级1
已执行级；实现了过程域的特定目标
能力等级2
已管理级；建立了基本的项目管理过程来跟踪费用进度和功能特性
能力等级3
已定义级；按照组织的裁剪指南从组织的标准功能中裁剪出来的一个已管理过程
能力等级4
已量化管理级；使用统计和其他定量技巧控制一个已定义的过程
能力等级5
已持续优化级；经过改进的一个量化管理过程
成熟度等级
是一种过程改善路径，该路径可以使组织针对一组过程域不断改善
一组过程域所有目标的一种改善等级。
成熟度等级
成熟度等级1：初始级
过程是混乱的，应付式的
成熟度等级2：已管理
能够确保过程按照预定方针得到计划和执行
过程域
配置管理
测量与分析
项目监控
项目规划
过程和产品质量保证
需求管理
提供方协议管理
成熟度等级1中的过程域
成熟度等级3：已定义
过程得到了很好的描述和理解，并应用标准、规程、工具及方法来表现
过程域
决策分析与解决
集成项目管理
组织过程定义
组织过程关注
成熟度等级2中的过程域
成熟度等级4：量化管理
组织和项目未知量和过程绩效建立了量化目标并将其作用管理过程的标准
过程域
组织过程性能
定量项目管理
成熟度等级3中的过程域
成熟度等级5：持续优化
点关注通过间进行和革新性过程改进和技术改进来持续性的改进过程的绩效
过程域
原因分析与解决
组织创新与部属
成熟度等级4中的过程域
成熟度等级和能力等级的关系
为了达到成熟度等级2，2级所包含的所有过程域必须达到的能力等级2或更好
为了达到成熟度等级3，2级、3级所包含的所有过程域必须达到的能力等级3或更高级
为了达到成熟度等级4，2，3，4级所包含的所有过程域必须达到能力等级3或更高级
过程域举例
两个过程域：项目规划（2级）和需求开发过程（3级）
1.项目规划
意图：建立并维护项目活动计划的定义
索要满足的专用目标、共用目标以及所要试试的实践
专用目标
SG1:建立估算
专用实践
估算项目规模
建立工作产品和任务属性的估算
定义项目生存期
确定工作量和成本估算
SG2;:开发项目计划
专用实践
建立预算和进度
标志项目风险
规划数据管理
规划项目资源
规划需求要的知识和技能
规划利益相关的参与方
建立项目计划
SG3:获得对该计划的承诺
专用实践
评审该项目的计划
调和工作和资源等级，是之一致
获得计划承诺
公用目标
GG2：共用目标2
共用实践
建立组织策略
规划过程
提供资源
指派责任
培训人员
管理配置
标志相关利益方的参与
监控过程
客观的评估符合型
高层管理是叫评审状态
巴国城制度化为一个已管理过程，对达到共用目标的专用实践实施了PDCA
2.需求开发
意图：生成并分析客户需求、产品需求和产品部件需求
专用目标和专用实践
专用目标
开发客户需求
专用实践
引出要求
开发客户需求
开发产品需求
专用实践
建立产品和产品构件的需求
分配产品构建需求
标识接口需求
分析并验证需求
专用实践
建立操作概念和场景
建立所需功能的定义
分析需求
分析需求，以达到权衡
确认需求
共用目标和共用实践
共用目标：把过程制度化为一个已定义过程
建立一个已定义过程设计需求开发过程和共用目标2的有关内容
收集改进信息
0 条评论
下一页
