控制器:
(1)指令寄存器(IR) : CPU执行一条指令时,从内存储器取到缓冲寄存器中,再送入IR暂存;
(2)程序计数器(PC): 将要执行的下一条指令的地址;
(3)地址寄存器(IR): 当前CPU所访问的内存单元地址;
(4)指令译码器(ID): 对指令中的操作码字段进行分析解释;
多核CPU可以满足用户同时进行多任务处理的要求;
单核多线程CPU是交替地转换执行多个任务,只不过交替转换的时间很短,用户一般感觉不出来;
单核多线程和多核相比,多核的速度更快;
数据表示: 机器数对应的实际数值称为数的真值;
(1)正数的反码与原码相同,负数的反码是其绝对值按位取反.
(2)正数的补码与原码相同,负数的补码是其反码的末尾加1.
补码中0有唯一编码:[+0]补=0 0000000,[-0]补=0 0000000;
(3)补码的符号位取反就是移码;
(4)N=2E×F,
E称为阶码,F称为尾数.
用阶称码和尾数表示的数为浮点数,这种表示方法称为浮点数表示法;
浮点数所能表示的数值范围主要由阶码决定,所表示数值的精度则由尾数决定;
(5)“NAN”即”不是一个数”,当运算结果不是实数或者无穷;
(6)对阶:使两个数的阶码相同,把阶码小的数的尾数右移(小阶向大阶看齐,这样丢失的精度少);
校验码:码距是指任意两个合法编码之间有多少个二级制位不同;
(1)奇偶校验码:
在编码中增加一位校验位来使编码中1的个数为奇数(奇校验)或为偶数(偶校验),从而使码距变为2;
奇校验可以检测代码中奇数位出错的编码,不能发现偶数位出错的情况,当合法编码中的奇数位发生了错误时,
即编码中的1变成0或0变成1,编码中1的个数的奇偶性就发生了变化,从而可以发现错误;
(2)海明码:
利用奇偶性来检错和纠错的方法;
设数据位是n位,校验位是k位,则n和k必须满足:2k>=k+n+1;
(3)循环冗余校验码(CRC)利用生成多项式为k个数据位产生r个校验位来进行编码,其编码长度为k+r;
校验码是由信息码产生的,校验码位数越多,该代码的校验能力就越强.
在求CRC编码时,采用的是模2运算.模2加减运算的规则是按位运算,不发生借位和进位;
CISC(复杂指令集计算机)的基本思想是 进一步增强原有指令的功能,
用更为复杂的新指令取代原先由软件子程序完成的功能,实现软件功能的硬化,导致机器的指令系统越来越庞大,复杂;
弊端:指令集过分庞杂,难以优化编译使之生成真正高效的目标代码;
微程序技术是CISC的重要支柱,需要多个CPU周期,降低了机器处理的速度;
强调完善的中断控制,势必导致动作繁多,设计繁杂,研制周期长;
使芯片种类增多,出错几率大,成本提高而成品率降低;
RISC(精简指令集计算机)的基本思想是通过减少指令总数和简化指令功能降低硬件设计的复杂度,
使指令能单周期执行,并通过优化编译提高指令的执行速度,采用硬布线控制逻辑优化编译程序.指令系统进一步精简;
主要技术:重叠寄存器窗口技术;优化编译技术;超流水及超标量技术;硬布线逻辑与微程序控制相结合在微程序技术中;
指令的流水处理：
顺序方式优点是控制简单，缺点是速度慢，机器各部件的利用率低；
重叠方式在解释第K条指令的操作完成之前就可以开始解释第K+1条指令，通常采用的是第一次重叠，
即在任何时候，指令分析部件和指令执行部件都只有相邻两条指令在重叠解释。
这种方式的优点是速度有所提高，控制也不太复杂。缺点是会出现冲突，转移和相关等问题，在设计的时候必须想办法解决；
流水方式把重复的顺序处理过程解释为若干子过程，每个子过程能在专用的独立模块上有效地并发工作，
”一次重叠“是把一条指令解释分解为两个子过程，而“流水”则是分解为更多的子过程；
吞吐率是指单位时间内流水线处理机流出的结果数,对指令而言，就是单位时间内执行的指令数。
流水线开始工作，需经过一定时间才能达到最大吞吐率，这就是建立时间。
按存储器的工作方式可分为读/写存储器和只读存储器。
(1)读/写存储器（RAM）；
(2)只读存储器（ROM）
① 固定只读存储器（Read Only Memory）在厂家生产时就写好数据，其内容只能读出不能改变。一般用于存放系统程序BIOS和用于微程序控制；
② 可编程的只读存储器（Programmable Read Only Memory,PROM）。其中的内容可以由用户一次性写入，写入后不能再修改；
③ 可擦除可编程的只读存储器（EPROM）内容既可以读出，也可以由用户写入，写入后还可以修改。
紫外线照射15-20分钟以擦去所有信息，然后再用特殊的电子设备写入信息；
④ 电擦除可编程的只读存储器（EEPROM）与EOROM相似，EEROM中的内容既可以读出，也可以进行改写。
只不过这种存储器是用电擦除的方法进行数据的改写；
⑤ 闪速存储器（Flash Memory）简称闪存，闪存的特性介于EPROM和EEPROM之间，类似于EEPROM,也可以使用电信号进行信息的擦除操作。
整块闪存可以在数秒内删除，速度远快于EPROM。
按访问方式分类：
(1)随机存储器（RAM）可对任何存储单元存入或读取数据，访问任何一个存储单元所需的时间是相同的；
(2)顺序存储器（ROM）访问数据所需要的时间与数据所在的存储位置相关，磁带是典型的顺序存储器；
(3)直接存储器（DAM）介于随机存取和顺序存取之间的一种寻址方式；
相联存储器是一种按内容访问的存储器,特别适合于信息的检索和更新;
高速缓存位于CPU与主存之间; 容量一般在几千字节到几兆字节之间; 速度一般比主存快5-10倍,由快速半导体存储器构成;
其内容是主存局部域的副本,对程序员来说是透明的;
主存地址转换成Cache存储器的地址,称为地址映像;
(1)直接映像：主存的块与Cache块的对应关系是固定的; 优点是地址变换简单,缺点是灵活性差;
(2)全相联映像：允许主存的任一块可以调入Cache存储器的任何一个块的空间中;
优点是主存的块调入Cache的位置不受限制,十分灵活.
缺点是无法从主存块号中直接获得Cache的块号,变换比较复杂,速度比较慢;
(3)组相联映像：是前两种方式的折中,是将Cache中的块再分成组.组采用直接映像方式而块采用全相联映射方式.
替换算法:使Cache获得尽可能高的命中率;
常用替换算法有:随机替换算法,先进先出算法,近期最少使用算法,优化替换算法;
Cache的性能分析:降低Cache失效率的方法主要有选择恰当的块容量,提高Cache的容量和提高Cache的相联度等;
Cache容量越大,则命中率越高,随着Cache容量的增加,其失效率接近0%(命中率逐渐接近100%).
但增加Cache容量意味着增加Cache的成本和增加Cache的命中时间;
外存储器:CPU不能直接访问外存中的程序和数据,只有将其以文件为单位调入主存才可以访问;
固态硬盘具有传统机械硬盘不具备的读写速度,质量轻,能耗低及体积小等特点,但价格较贵,容量较低,一旦硬件损坏,数据较难恢复;
微型计算机中最常用的内存与接口的编址方法:
(1)内存与接口地址独立编址方法:编程序或读程序时很容易使用和辨认.
缺点是用于接口的指令太少,功能太弱;
(2)内存与接口地址统一编址方法:用于内存的指令全都可以用于接口,增强了对接口的操作功能,在指令上不再区分内存或接口指令;
缺点在于整个地址空间被分成两部分,其中一部分分配给接口使用,剩余的为内存所用,这经常会导致内存地址不连续.
由于用于内存的指令和用于接口的指令是完全一样的,维护程序时就需要根据参数定义表仔细加以辨认;
程序查询方式:通过CPU执行程序来查询外设的状态,判断外设是否准备好接收数据或准备好了向CPU输入的数据;
缺点: 降低了CPU的利用率; 对外部的突发事件无法做出实时响应;
中断方式因为CPU无需等待而提高了效率;
中断嵌套:即一个中断服务程序中嵌套着另一个中断服务程序;
直接内存存取(DMA)不需要CPU的任何干涉,只需要CPU在过程开始时启动与过程结束时的处理,实际操作由DMA硬件直接执行完成;
在DMA传送数据期间,CPU不能使用总线;
通道的出现进一步提高了CPU的效率,其是以增加更多的硬件为代价的;
总线是指计算机设备和设备之间传输信息的公共数据通道.总线上所有设备共享,可以将计算机系统内的多种设备连接到总线上;
(1)数据总线(DB) 用来传送数据信息,是双向的;
(2)地址总线(AB) 用于传送CPU发出的地址信息,是单向的.
(3)控制总线(CB) 用来传送控制信号,时序信号和状态信息等;
CB中每一条的信息传送方向是单方向且确定的,但CB作为一个整体则是双向的.
结构框图中,凡涉及到控制总线CB,均是以双向线表示;
授权侵犯:为某一特权使用一个系统的人 却将该系统用作其他未授权的目的;
拒绝服务:对信息或其他资源的合法访问被无条件拒绝,或推迟与时间密切相关的操作;
窃听:信息从被监视的通信过程中泄露出去;
截获/修改:某一通信数据项在传输过程中被改变,删除或替代;
人员疏忽:一个授权的人为了金钱或利益,或由于粗心将信息泄露给未授权的人;
完整性破坏:通过对数据进行未授权的创建,修改或破坏,使数据的一致性遭到破坏;
资源耗尽:某一资源(如访问端口)被故意超负荷地使用,导致其他用户的服务被中断;
对称加密技术:对称加密采用了对称密码编码技术,其特点是文件加密和解密使用相同的密钥;
例:DES,三重DES,RC-5,IDEA,AES;
非对称加密算法需要两个密钥:公开密钥与私有密钥是一对;
只能使用专用密钥解密由其公用密钥加密后的任何信息;
非对称加密算法的保密性比较好,它消除了最终用户交换密钥的需要,
但加密和解密花费时间长,速度慢,不适合于对文件加密,而只是用于对少量数据进行加密; 常用算法RSA;
PKI采用证书进行公钥管理,通过第三方的可信机构(认证中心,即CA)把用户的公钥和用户的其他标识信息捆绑在一起,
其中包括用户名和电子邮件地址等信息,以在Internet上验证用户的身份.
PKI把公钥密码和对称密码结合起来,在Internet上实现密钥的自动管理,保证网上数据的安全传输;
数据的机密性是指数据在传输过程中不能被非授权者偷看;
完整性是指在传输过程中不能被非法篡改;
有效性是指数据不能被否认;
信息摘要主要用于数字签名,对特定的文件而言,是唯一的.
信息摘要可以被公开,他不会透露相应文件的任何内容;
SSL协议可以被总结为:一个保证任何安装了安全套接字的客户和服务器间事务安全的协议,它涉及所有的TCP/IP应用程序;
失效率:单位时间内失效的元件数与元件总数的比例;
串联系统可靠性:R=R1R2...RN
并联系统可靠性:R=1-(1-R1)(1-R2)...(1-RN)
提高计算机的可靠性一般采取如下两项措施:
(1) 提高元器件质量; (2) 发展容错技术;
Fortran是第一个被广泛用来进行科学和工程计算的高级语言;
PASCAL是一种过程式,结构化设计程序语言;
Ruby是一种解释性,面向对象,动态类型的脚本语言;
PHP是一种在服务器端执行的,嵌入HTML文档的脚本语言;
Delphi是一种可视化开发工具,在采用面向对象的编程语言Object Pascal和基于构件的开发结构框架;
命令式语言 Fortran,PASCAL和C语言;
C,PASCAL等都是典型的结构化程序设计语言;
C++,Java和Smalltalk是面向对象程序设计语言的代表;
函数式语言的代表:LISP,常见的函数式语言有Haskell,Scala,Scheme,APL等;
PROLOG具有很强的推理功能,适用于编写自动定理证明,专家系统和自然语言理解等;
程序中的数据对象可以具有左值或右值,左值指存储单元(或地址,容器),右值是值(或内容).
变量具有左值和右值,在程序运行过程中其右值可以改变;
常量只有右值,在程序运行过程中其右值不能变;
(1)词法分析:对源程序从前到后(从左到右)逐个字符地扫描,从中识别出一个个“单词符号”.
“单词”符号是程序设计语言的基本语法单位,如关键字,标识符,常数,运算符和分隔符(如标点符号,左右括号)等;
(2)语法分析:根据语言的语法规则将单词符号序列分解成各类语法单位,如“表达式”语句和“程序”等;
(3)语义分析:分析语法结构的含义,检查源程序是否包含静态语义错误,并收集类型信息供后面的代码生成阶段使用;
(4)中间代码生成:根据语义分析的输出产生中间代码.
“中间代码”是一种简单且明确的记号系统,可以有若干种形式,他们的共同特征是与具体的机器无关.
最常用的一种中间代码是与汇编语言的指令非常相似的三地址码,其实现方式常采用四元式;
(5)代码优化:优化过程可以在中间代码生成阶段进行,也可以在目标代码生成阶段进行.
由于中间代码不依赖具体机器,此时所做的优化一般建立在对程序控制流和数据流分析的基础上,与具体的机器无关.
优化所依据的原则是程序的等价变换原则;
(6)目标代码生成:把中间代码变换成特定机器上的绝对指令代码,可重定位的指令代码或汇编指令代码,这个阶段的工作与具体的机器密切相关;
描述语言语法结构的规则称为文法,为四种类型:即0型,1型,2型和3型.这4类文法之间的差别在于对生成式要施加不同的限制;
0型文法也成为短语文法,其功能相当于图灵机,任何0型语言都是递归可枚举的;反之,递归可枚举集也必是一个0型语言;
1型文法也成为上下文有关文法,这种文法意味着对非终结符的替换必须考虑上下文;
2型文法就是上下文无关文法,非终结符的替换无需考虑上下文.
3型文法等价于正规式,因此也被称为正规文法或线性文法;
属性文法是对上下文无关文法的扩充;
中间代码,将源程序首先翻译成中间代码表示形式,以利于与机器无关的优化处理.
常见的中间代码有后缀式,三元式,四元式和树等形式;树形表示.(中根排序)
优化就是对程序进行等价交换,使得从变换后的程序能生成更有效的目标代码.
所谓等价,是指不变程序的运行结果;
所谓有效,是指目标代码的运行时间较短,占用的存储空间较少;
优化可在编译的各个阶段进行.
最主要的优化是在目标代码生成以前对中间代码进行的,这类优化不依赖于具体的计算机;
目标代码生成由代码生成器实现.
代码生成器以经过语义分析或优化后的中间代码为输入,以特定的机器语言或汇编语言代码为输出;
解释程序是另一种语言处理程序,在词法,语法和语义分析方面与编译程序的工作原理基本相同,
但是在运行用户程序时,他直接执行源程序或源程序的中间表示形式. 解释程序不产生源程序的目标程序,这是他和编译程序的主要区别;
高级语言编译与解释方式比较:
(1)效率：在解释方式下运行程序时,解释程序可能需要反复扫描源程序,
每一次引用变量都要进行类型检查,甚至需要重新进行类型分配,从而降低了程序的运行速度.
以解释方式运行程序需要更多的内存,因为系统不但需要为用户程序分配运行空间,而且要为解释程序及其支撑系统分配空间;
编译程序除了对源程序进行语法和语义分析外,还要生成源程序的目标代码并进行优化,所以这个过程比解释方式需要更多的时间.
虽然与仔细写出的机器程序相比,由编译程序创建的目标程序运行的时间一般更长,需要占用的存储空间更多,
但源程序只需要被编译程序一次就可以多次运行;
(2)灵活性：由于解释程序需要反复检查程序,这也使得解释方式能够比编译方式更灵活.
当解释器直接运行源程序时,“在运行中”修改程序就成为可能,例如增加语句或者修改错误等.
另外,当解释器直接在源程序上工作时,它可以对错误进行更精确的定位;
(3)可移植性：解释器一般也是用某种程序设计语言的编写的,因此只要对解释器重新编译,就可以把解释器运行在不同的环境之中;
线性表采用顺序存储结构的优点是可以随机存取表中的元素,缺点是插入和删除操作需要移动元素;
插入一个新元素需要移动的元素个数为: N/2;
删除元素时需要移动元素个数: N-1/2;
线性表的链式存储:节点空间只有在需要的时候才申请,无需实现分配,进行插入和删除,其实质都是对相关指针的修改;
当线性表采用链表作为存储结构时,不能对数据元素进行随机访问,但是具有插入和删除操作不需要移动元素的优点;
双向链表可以从表中任意的结点出发,可以从表中任意结点开始遍历整个链表;
循环链表可以从表中任意节点开始遍历整个链表;
静态链表,借助数组来描述线性表的链式存储结构,用数组元素的下标表示元素所在结点的指针;
设循环队列Q的容量为MAXSIZE,初始时队列为空,且Q.rear和Q.front都等于0;
元素入队时,修改队尾指针Q.rear=(Q.rear+1)%MAXSIZE;
元素出队时,修改队头指针Q.rear=(Q.front+1)%MAXSIZE;
含有子串的串称为主串;
空串是任意串的字串;
串相等:指两个串长度相等且对应序号的字符也相同;
串比较:两个串比较大小时的ASCⅡ值作为依据.
比较操作从两个串的第一个字符开始进行,字符的码值大者所在的串为大;若其中一个串先结束,则以串长者为大;
赋值操作StrAssign(s,t):将串s的值赋给串t;
连接操作Concat(s,t):将串t接续在s的尾部,形成一个新串;
子串的定位操作通常称为串的模式匹配,子串也成为模式串;
假设主串和模式串的长度分别为n和m,位置序号从0开始计算,朴素模式匹配算法匹配成功时字符间的平均比较次数为:1/2(n+m);
在最好情况下匹配算法的时间复杂度为O(m+n),最坏情况下的平均比较次数为1/2m(n-m+2),最坏情况下的时间复杂度为O(n*m);
数组的顺序存储:
以行为主序优先存储的地址计算公式为:Loc(aij) = Loc(a11) + ((i-1)*n+(j-1))*L;
以列为主序优先存储的地址计算公式为:Loc(aij) = Loc(a11) + ((j-1)*m+(i-1))*L;
若对称矩阵中的每一对元素仅占用一个存储单元,那么可将n2个元素压缩存储到能存放n(n+1)/2个元素的存储空间中;
矩阵的三元组表:(行标,列标 ,值);
广义表的长度是指广义表中元素的个数.广义表的深度是指广义表展开后所含的括号的最大层数;
结点的度.一个结点的子树的个数记为该节点的度.
结点的层次.根为第一层;
树的高度.一棵树的最大层数记为树的高度或深度.
二叉树第i层(i>=1)上最多有2i-1个结点.
高度为k的二叉树最多有2k-1个结点(k>=1).
对于任何一颗二叉树,若其终端节点数为n0,度为2的节点数为n2,则n0=n2+1.
具有n个结点的完全二叉树的深度为[log2n]+1.
遍历二叉树的基本操作就是访问结点,不论按照那种次序遍历.
对于含有n个结点的二叉树,遍历算法的时间复杂度都为O(n).
自上而下,自左至右逐层访问树中各个结点的过程就是层序遍历;
树的带权路径长度为树中所有叶子节点的带权路径长度之和.
树的双亲表示法: 对于求指定节点的双亲和祖先都十分方便,但对于求指定结点的孩子及后代则需要遍历整个数组.
树的孩子表示法: 树的孩子表示法便于查找每个结点的子孙,若要找出指定结点的双亲则可能需要遍历所有的链表.
用户也可以将双亲表示法和孩子表示法结合起来,形成树的孩子双亲表示结构;
含有n个顶点的无向完全图共有n(n-1)/2条边.
有向完全图中弧的数目为n(n-1).
顶点的度表示该顶点的入度和出度之和.
边(或弧)带权值的图称为网.
深度优先搜索类似于树的先跟遍历;
广度优先搜索的特点是尽可能先进行横向搜索,即最先访问的顶点的邻接点也先被访问.
普里姆算法:寻找与顶点相邻且代价最小的边的另一个结点.时间复杂度:O(n2),与边数无关,适合于求边稠密的网的最小生成树.
克鲁斯卡尔算法:选择代价最小的边.时间复杂度:O(eloge),与图中的顶点数无关,因此该算法适合于求边稀疏的网的最小生成树.
拓扑排序算法的时间复杂度为O(n+e);在从源点到汇点的路径中,长度最长的路径称为关键路径.关键路径上的所有活动均是关键活动.
如果任何一项关键活动没有按期完成,就会影响整个工程进度,而缩短关键活动的工期通常可以缩短整个工程的工期.
顺序查找的平均查找长度为 n+1/2;
顺序查找方法在n值较大时,其平均查找长度较大,查找效率较低.
优点:简单且适应面广,对查找表的结构没有要求,无论记录是否按关键字有序排列均可应用;
折半查找的平均查找长度为n+1/n log2(n+1)-1;
折半查找比顺序查找的效率要高,但它要求查找表进行顺序存储并且按关键字有序排列.
当需要对表进行插入或者删除操作时,需要移动大量的元素;
折半查找适合用于表不易变动,且有经常查找的情况;
分块查找又称为顺序查找,是对顺序查找方法的一种改进,其效率介于顺序查找与折半查找之间.
首先将表分成若干块,每一块的关键字不一定有序,但块之间是有序的,即最后一块中所有记录的关键字大于前一块中最大的关键字.
此外,还建立了一个”索引表”,索引表按关键字有序.
第一步在索引表中确定待查记录所在的块;第二步在块内顺序查找.
长度为n的表均匀地分成b块,每块含有s个记录,平均查找长度为:(b+1)/2+(s+1)/2=1/2(n/s+s)+1;
其平均查找长度不仅与表长n有关,而且与每一块的记录数s有关.
平衡二叉树又称AVL树,它或者是一棵空树,它的左子树和右子树都是平衡二叉树,而左子树和右子树的高度差的绝对值不超过1.
只有在树的形态比较均匀的情况下,查找效率才能达到最佳.因此,希望在构造二叉排序树的过程中,保持其为一颗平衡二叉树.
根据设定的哈希函数和处理冲突的方法,
将一组关键字映射到一个有限的连续的地址集(空间)上,并以关键字在地址集中的”像”作为记录在表中的存储位置,
这种表称为哈希表,这一映射过程称为哈希造表或散列,所得的存储位置称为哈希地址或散列地址;
冲突只能尽可能减少而不能完全避免,因为哈希函数是从关键字集合到地址集合的映像,
如果一个标识符对应一个存储地址,那就不会发生冲突了,
但这是不可能也没有必要的,因为存储空间难以满足;
对于哈希表,主要考虑两个问题:一是如何构造哈希函数,二是如何解决冲突;
哈希表的查找:虽然哈希表在关键字与记录的存储之间建立了直接映像,但由于”冲突”的产生,
使得哈希表的查找过程仍然是一个给定值和关键字进行比较查找的过程.
因此,仍需要以平均查找长度衡量哈希表的查找效率;
直接插入排序是一种简单的排序方法，
具体做法是: 在插入第i个记录时，R1、R2、...Ri-1:已经排好序，这时将Ri的关键字ki依次与关键字ki-1,ki-2等进行比较，
从而找到应该插入的位置并将Ri插入，插入位置及其后的记录依次向后移动。
直接插入排序是一种稳定的排序方法,其时间复杂度为O(n2);
冒泡排序:n个记录进行冒泡排序的方法是:
首先将第一个记录的关键字和第二个记录的关键字进行比较，
若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，
依此类推，直到第n-1个记录和第n个记录的关键字比较过为止。
上述过程称为第一趟冒泡排序,其结果是关键字最大的记录被交换到第n个记录的位置上。
然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n- 1个记录的位置上。
最多进行n-1趟，所有记录有序排列。
若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。
冒泡排序是一种稳定的排序方法,其时间复杂度为O(n2);
简单选择排序: n-1+i个记录中选出关键字最小的记录,并和第i个记录进行交换,当i等于n时所有记录有序排列.
简单选择排序是一种不稳定的排序方法,其时间复杂度为O(n2);
希尔排序:先将整个待排记录分割成若干个子序列,然后分别进行直接插入排序,
待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序;
希尔排序是一种不稳定的排序算法,据统计分析其时间复杂度为O(n1.3);
快速排序:通过一趟排序将待排的记录划分为独立的两部分你,称为前半区和后半区,
其中,前半区中记录的关键字均不大于后半区记录的关键字,然后再分别对这两部分记录继续进行快速排序,从而使整个序列有序;
快速排序算法的时间复杂度为O(nlog2n),快速排序被认为是平均性能最好的一种,
若初始记录按关键字有序或基本有序时,快速排序的性能退化为时间复杂度是O(n2),快速排序是不稳定的排序方法;
在一个堆中,堆顶元素(即完全二叉树的根节点)必须为序列中的最大元素(或最小元素),并且堆中的任意棵子树也都是堆.
若堆顶为小元素,则成为小顶堆;若堆顶为最大元素,则成为大顶堆.
对于记录数较少的文件来说,堆排序的优越性并不明显,但对于大量的记录来说,堆排序是很有效的;
堆排序的时间复杂度为O(nlogn),堆排序是一种不稳定的排序算法;
“归并”是将两个或两个以上的有序文件合并成一个新的有序文件,需要辅助空间n个(与待排记录相等),时间复杂度为O(nlogn);
基数排序的思想是按组成关键字的各个数的值进行排序,它是分配排序的一种;
基数排序是一种稳定的排序方法;
(1)若待排序的记录数目n较小,可采用直接插入排序和简单选择排序;
(2)若待排记录按关键字基本有序,宜采用直接插入排序或冒泡排序;
(3)若n较大,则应采用时间复杂度为O(nlogn)的排序方法;
当记录本身信息量较大时,为避免耗费大量的时间移动记录,可以采用链表作为存储结构;
外部排序就是对大型文件的排序,待排序的记录存放在外存.
在排序过程中,内存只存储文件的一部分记录,整个排序过程需要进行多次内外存间的数据交换;
操作系统的四个特征是并发性,共享性,虚拟性和不确定性;
操作系统的功能可分为处理机管理,文件管理,存储管理,设备管理和作业管理五大部分;
(1)进程管理; 对处理机的执行”时间”进行管理;
(2)文件管理; 文件存储空间管理,目录管理,文件的读/写管理和存取控制;
(3)存储管理; 对主存储器”空间”进行管理;
(4)设备管理; 对硬件设备的管理;
(5)作业管理; 任务,界面管理,人机交互,图形界面,语音控制和虚拟现实等;
程序并发执行破坏了程序的封闭性和可再现性,使得程序和执行程序的活动不再一一对应.
为了解决这一问题,需要研究进程间的同步与互斥问题;
进程就绪:一个进程获得了除处理机外的一切所需资源,一旦得到处理机即可运行;
操作系统内核是计算机系统硬件的首次延伸,是基于硬件的第一层软件扩充;
信号量分为如下两类:①公用信号量;
实现进程间的互斥,初始值为1或资源的数目;②私用信号量;
实现进程间的同步,初始值为0或某个正整数;
PV操作是实现进程同步与互斥的常用方法,P操作和V操作是低级通信原语,在执行期间不可分割.
P表示申请一个资源,V表示释放一个资源;
死锁的处理策略主要有四种:鸵鸟策略,预防策略,避免策略和检测与解除死锁;
分页原理:将一个进程的地址空间划分成若干个大小相等的区域,称为页.
相应地,将主存空间划分成与页相同大小的若干个物理块,称为块或页框.
在为进程分配主存时,将进程中若干页分别装入多个不相邻的块中.
软件生存周期包括可行性分析与项目开发计划,需求分析,设计(概要设计和详细设计),编码,测试,维护等活动;
瀑市模型的优点是，容易理解，管理成本低;强调开发的阶段性早期计划及需求调查和产品测试。
不足之处是，客户必须能够完整、正确和清晰地表达他们的需要:
在开始的两个或3个阶段中，很难评估真正的进度状态;
当接近项目结束时，出现了大量的集成和测试工作;直到项目结束之前，都不能演示系统的能力。
在瀑布模型中，需求或设计中的错误往往只有到了项目后期才能够被发现，对于项目风险的控制能力较弱，
从而导致项目常常延期完成，开发费用超出预算。
增量模型作为瀑布模型的一个变体,具有瀑布模型的所有优点;
第一个可交付版本所需要的成本和时间很少;
开发由增量表示的小系统所承担风险不大;由于很快发布了第一个版本,因此可以减少用户需求的变更;
运行增量投资,即在项目开始时,可仅对一个或两个增量投资;
演化模型特别适用于对软件需求缺乏准确认知的情况;
原型方法比较适合于用户需求不清,需求经常变化的情况.当系统规模不是很大也不太复杂时,采用该方法比较好;
螺旋模型:对于复杂的大型软件,开发一个原型往往达不到要求.
螺旋模型将瀑布模型和演化模型结合起来,加入了两种模型均忽略的风险分析,弥补了这两种模型的不足;
螺旋模型强调风险分析,使得开发人员和用户对每个演化层出现的风险有所了解,从而做出应有的反应.
因此,该模型特别适用于庞大,复杂且具有高风险的系统;
喷泉模型是一种以用户需求为动力,以对象作为驱动的模型,适合于面向对象的开发方法;
喷泉模型的各个阶段没有明显的界限,开发人员可以同步进行,要求严格管理文档;
统一过程(UP)模型是一种”用例和风险驱动,以架构为中心,迭代并且增量”的开发过程,由UML方法和工具支持;
统一过程的典型代表是RUP,RUP是UP的商业拓展,完全兼容UP,但比UP更完整,更详细;
极限编程XP由 价值观,原则,实践和行为4个部分组成;
4大价值观:沟通、简单性、反馈和勇气。
5个原则:快速反馈、简单性假设、逐步修改、提倡更改和优质工作。
12个最佳实践:计划游戏(快速制定计划、随着细节的不断变化而完善)、
小型发布(系统的设计要能够尽可能早地交付)、
隐喻(找到合适的比喻传达信息)、
简单设计(只处理当前的需求，使设计保持简单)、
测试先行(先写测试代码，然后再编写程序)、
重构(重新审视需求和设计，重新明确地描述它们以符合新的和现有的需求)、
结队编程、
集体代码所有制、
持续集成(可以按日甚至按小时为客户提供可运行的版本)、
每周工作40个小时、
现场客户和编码标准。
水晶法认为每一个不同的项目都需要一套不同的策略、约定和方法论，认为人对软件质量有重要的影响，
因此随着项目质量和开发人员素质的提高，项目和过程的质量也随之提高。
并列争球法使用迭代的方法，其中把每30天一次的迭代称为一个“冲刺”，并按需求的优先级别来实现产品。
多个自组织和自治的小组并行地递增实现产品。协调是通过简短的日常情况会议来进行，就像橄榄球中的“并列争球”。
自适应软件开发(ASD)有6个基本的原则:有一个使命作为指导; 特征被视为客户价值的关键点;
过程中的等待是很重要的，因此“重做”与“做”同样关键;
变化不被视为改正，而是被视为对软件开发实际情况的调整:
确定的交付时间迫使开发人员认真考虑每一个生产的版本的关键需求;风险也包含其中;
敏捷统一过程(AUP)“在大型上连续”以及在“在小型上迭代”;
黑盒测试也成为功能测试,在完全不考虑软件的内部结构和特征的情况下,测试软件的外部特性;
常用技术有等价类划分,边界值分析,错误推测和因果图等;
白盒测试也成为结构测试,根据程序的内部结构和逻辑来设计测试用例,
对程序的路径和过程进行侧式,检查是否满足设计的需要;
常用的技术有逻辑覆盖,循环覆盖和基本路径测试;
调试发生在测试之后,其任务是根据测试时所发现的错误找出原因和具体的位置,进行改正.
调试工作主要由程序开发人员进行,谁开发的程序就由谁来进行调试;
系统维护主要包括硬件维护,软件维护和数据维护;
COCOMO模型估算代码行;
Putnam估算模型是一种动态多变量模型,它是假设在软件开发的整个生存周期中工作量特有的分布;
Gantt图是一种简单的水平条形图,它以日历为基准描述项目任务;
Gantt图能清晰地描述每个任务从何时开始,到何时结束,人物的进度情况以及各个任务之间的并行性.
但他不能清晰地反映出各个任务之间的依赖关系,难以确定整个项目的关键所在;
PERT图是一个有向图,图中的箭头表示任务,它可以标上完成该任务所需的时间;
PERT要不仅给出了每个任务的开始时间、结束时间和完成该任务所需的时间，
还给出了任务之间的关系，即哪些任务完成后才能开始另外一些任务，以及如期完成整个工程的关键路径.
图中的松弛时间则反映了完成某些任务时可以推迟开始时间或延长其所需完成的时间。
但是,PERT图不能反映任务之间的并行关系。
风险控制:
①风险避免. 应对风险的最好办法是主动地避免风险，即在风险发生前分析引起风险的原因，然后采取措施,以避免风险的发生;
②风险监控. 项目管理者应监控某些因素，这些因素可以提供风险是否正在变高或变低的指示。
③RMMM计划. RMMM计划将所有风险分析工作文档化,并由项目管理者作为整个项目计划中的一部分来使用;
软件质量特征:
(1)Mc Call软件质量模型:第一层是质量特征,第二层是评价准则,第三层是度量指标;
(2)ISO/IEC 9126 软件质量模型由三个层次组成:第一层是质量特征,第二层是质量子特征性,第三层是度量指标;
1.功能性(Functionality):
适应性——对规定任务能否提供一组适应任务的功能的能力。
准确性——是否能够得到正确或相符的结果的能力。
互用性——与其他规定的系统进行交互的能力。
依从性——软件是否符合相关标准、法律法规等的能力。
安全性——是否能避免对程序及数据非法访问或意外访问的能力。
2.可靠性(Reliability):
成熟性——由故障引起软件失效的频率。
容错性——在出现错误后维持规定的运行的能力。
易恢复性——在故障发生后恢复至正常状态的能力。
3.易使用性(Usability):
易理解性——用户为理解软件逻辑及应用所要付出的努力。
易学性——用户为了学习软件使用所要付出的努力。
易操作性——用户对软件进行操作和控制所要付出的努力。
4.效率(Efficiency):
时间特性——响应和处理及软件执行功能时的所需耗费的时间（吞吐量）。
资源特性——响应和处理及软件执行功能时所需耗费的资源及持续时间。
5.可维护性(Maintainability):
易分析性——为诊断缺陷或失效时所需付出的努力。
易改变性——为对软件进行修改、排错等所需付出的努力。
稳定性——对软件进行修改后造成风险或无法预期结果的频率。
易测试性——为确认软件修改是否有效所需付出的努力。
6.可移植性(Portability):
适应性——软件转移到不同环境时所需付出的努力。
易安装性——在指定环境下安装软件所需付出的努力。
一致性——软件是否符合可移植性的约定。
易替换性——软件在该环境中替代指定软件的能力。
其中，前三者又被称为内部质量，后三者称为外部质量。
第一层质量特性的含义如下：
功能性:当软件在指定条件下使用时，软件产品提供明确的和隐含要求的功能的能力；
可靠性:在指定条件下使用时，软件产品维持规定的性能水平的能力；
可使用性:在指定条件下使用时，软件产品被理解、学习、使用和吸引用户的能力；
效率:在指定条件下使用时，相对于所用资源的数量，软件产品可提供适当性能的能力；
可维护性:软件产品纠错、改进功能或适应环境、需求和功能规格说明的变化可被修改的能力；
可移植性:软件产品从一种环境迁移到另外一种环境的能力。
软件容错技术:提高软件质量和可靠性的技术大致可以分为两类,
一类是避开错误,即在开发过程中不让差错潜入软件的技术;
另一类是容错技术,即对某些无法避开的差错,使其影响减至最小的技术;
实现容错的主要首段是冗余.
冗余是指对于实现系统规定功能是多余的那部分资源,包括硬件,软件,信息和时间.
冗余技术分四类:结构冗余,信息冗余,时间冗余,附加冗余技术;
无直接耦合：两个模块之间没有直接的关系，它们从属于不同模块的控制与调用,他们之间不传递任何信息.
因此,模块间的耦合性最弱,模块的独立性最高;
数据耦合：指两个模块之间有调用关系，传递的是简单的数据值，相当于高级语言中的值传递。
标记耦合：指两个模块之间传递的是数据结构。
控制耦合：指一个模块调用另一个模块时，传递的是控制变量，被调用模块通过该控制变量的值有选择地执行模块内的某一功能。
因此，被调用模块应具有多个功能，哪个功能起作用受调用模块控制。
外部耦合：模块间通过软件之外的环境联结(如I/O将模块耦合到特定的设备、格式、通信协议上)时称为外部耦合。
公共耦合：指通过一个公共数据环境相互作用的那些模块间的耦合。
内容耦合：当一个模块直接使用另一个模块的内部数据，或通过非正常入口转入另一个模块内部时，这种模块间的耦合称为内容耦合。
偶然内聚(巧合内聚)：指一个模块内的各处理元素之间没有任何联系。
逻辑内聚：指模块内执行若干个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。
时间内聚：把需要同时执行的动作组合在一起形成的模块称为时间内聚模块。
过程内聚：指一个模块完成多个任务，这些任务必须按指定的过程执行。
通信内聚：指模块内的所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或者产生相同的输出数据。
顺序内聚：指一个模块中的各个处理元素都密切相关于同一功能且必须顺序执行，前一功能元素的输出就是下一功能元素的输入。
功能内聚：这是最强的内聚，指模块内的所有元素共同作用完成一个功能，缺一不可。
DFD中描的是数据流而不是控制流;
有输入但是没有输出,我们称之为”黑洞”;
输入不足以产生输出,我们称之为”灰洞”;
外部实体是指存在于软件系统之外的人员或组织,他指出系统所需数据的发源地(源)和系统所产生的数据流动的归宿地(宿);
某个源和某个宿可以是同一个人员或组织; 一个加工的输出数据流不能与该加工的输入数据流同名;
父图与子图平衡是指任何一张DFD子图边界上的输入/输出数据流必须与其父图中对应加工的输入/输出流保持一致;
如果父图中某个加工的一条数据流对于子图中的几条数据流,
而子图中组成这些数据流的数据项全体正好等于父图中的这条数据流,那么他们依然是平衡的;
绑定是一个把过程调用和响应调用所需执行的代码加以结合的过程.
在一般的程序设计语言中,绑定是在编译时进行的,叫做静态绑定.
动态绑定则是在运行时进行的,因此,一个给定的过程调用和代码的结合直到调用发生时才进行;
通过实体间的关系寻找对象常常没有问题,困难在于寻找(选择)系统关心的实质性对象,实质性对象是系统稳定的基础;
经验表明,从应用定义域概念标识对象是非常合理的,完成上述工作后写出规范文档,文档确定每个对象的范围;
对象可以可以用预先开发的源代码实现,称这样的部分为构件;
(1)单一责任原则：就一个类而言，应该仅有一个引起它变化的原因。
即，当需要修改某个类的时候原因有且只有一个，让一个类只做一种类型的责任。
(2)开放封闭原则：软件实体(类、模块、函数等)应是可以扩展的,开放的;但不可修改的，即封闭的。
(3)里氏替换原则：子类型必须能够替换掉他们的基类型。
即，在任何父类可以出现的地方，都可以用子类的实例来赋值给父类型的引用。
当一个子类的实例能够替换任何其超类的实例时，它们之间才具有是一个(is-a) 关系。
(4)依赖倒置原则：抽象不应该依赖于细节，细节应该依赖于抽象。即，高层模块不应该依赖于低层模块，二者都应该依赖于抽象。
(5)接口分离原则：不应该强迫客户依赖于它们不用的方法。
接口属于客户，不属于它所在的类层次结构。
即:依赖于抽象，不要依赖于具体，同时在抽象级别不应该有对于细节的依赖。这样做的好处就在于可以最大限度地应对可能的变化。
上述(1)~ (5) 是面向对象方法中的五大原则。除了这五大原则之外，Robert c. Martin提出的面向对象设计原则还包括以下几个。
(6)重用发布等价原则：重用的粒度就是发布的粒度。
(7)共同封闭原则：包中的所有类对于同一类性质的变化应该是共同封闭的。
一个变化若对一个包产生影响，则将对该包中的所有类产生影响，而对于其他的包不造成任何影响。
(8)共同重用原则：一个包中的所有类应该是共同重用的。如果重用了包中的一个类，那么就要重用包中的所有类。
(9)无环依赖原则：在包的依赖关系图中不允许存在环，即包之间的结构必须是个直接的无环图形。
(10)稳定依赖原则：朝着稳定的方向进行依赖。
(11)稳定抽象原则：包的抽象程度应该和其稳定程度一致。
类的实例化过程是一种实例的合成过程，而不仅仅是根据单个类型进行的空间分配、初始化和绑定。类属类可以看成是类的模板;
0OPL中的继承机制体现了一条重要的面向对象程序设计原则:开发人员在构造程序时不必从零开始，而只需对差别进行程序设计。
支持维承也是0OPL与传统程序设计语言在语言机制方面最根本的区别。
一般情况下，对象接收它能够识别的消息，拒绝它不能识别的消息。
对于一个对象而言，任何外部的代码都不能以任何不可预知或事先不允许的方式与这个对象进行交互。
通常，消息的名字就是这个对象中外界可知的某个方法的名字。
在消息中，经常还有一组参数(也就是那个方法所要求的参数)，将外界的有关信息传给这个对象。
单元测试是系统构件的分体测试。
将测试好的系统构件接起来看它们之间相互作用的正确性称为综合测试。
最后是整个系统的测试，包括软件系统所在相关环境的测试。
综合测试尽可能在早期阶段处理，因为通信是系统开发的实质。
所有对象有预定义的界面，这也有利于综合测试。
当综合测试继续到较高层次时，那么越来越多的对象就会被逐步连接起来。
面向对象的综合测试是由底向上的测试。
在图形上,把一个消息表示为一条有向直线,通常在表示消息的线段上总有操作名;
状态表示为一个圆角矩形，通常在圆角矩形中含有状态的名称及其子状态。
活动是描述计算机过程执行的步骤序列，注重步骤之间的流而不关心哪个对象执行哪个步骤。
活动的一个步骤称为一个动作。
在图形上，把动作画成一个圆角矩形，在其中含有指明其用途的名字。
状态和动作靠不同的语境得以区别。
类图展现了一组对象,接口,协作和他们之间的关系;
对象图展现了某一时刻一 组对象以及它们之间的关系，描述了在类图中所建立的事物的实例的静态快照。
用例图(Use Case Diagram)展现了一组用例、参与者(Actor) 以及它们之间的关系。
用例之间的扩展关系(<<extend>>) 和包含关系(<<include>>),
参与者和用例之间的关联关系，用例与用例以及参与者与参与者之间的泛化关系。
交互图用于对系统的动态方面进行建模。
一张交互图表现的是一个交互，由一组对象和它们之间的关系组成，包含它们之间可能传递的消息。
序列图是强调消息时间顺序的交互图;通信图是强调接收和发送消息的对象的结构组织的交互图:交互概览图强调控制流的交互图。
序列图是场景的图形化表示,描述了以时间顺序组织的对象之间的交互活动;
通信图强调收发消息的对象的结构组织,在早期的版本中也被称作协作图,通信图强调参加交互对象的组织;
状态图展现了一个状态机,它由状态,转换,事件和活动组成.状态图关注系统的动态视图,
对于接口,类和协作的行为建模尤为重要,强调对象行为的事件顺序;
创建型模式与对象的创建相关;结构型模式处理类或对象的组合;行为模式对类或对象怎样交互和怎样分配职责进行描述;
创建型模式抽象了实例化过程,他们帮助一个系统独立于如何创建,组合和表示它的那些对象;
1.Abstract Factory(抽象工厂):提供一个创建一系列相关或相互依赖对象的接口,而无需指定他们具体的类;
2.Builder(生成器):将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示;
3.Factory Method(工厂方法):定义一个用于创建对象的接口,让子类决定实例化哪一个类;
4.Prototype(原型):用原型实例指定创建对象的种类,并且通过复制这些原型对象创建新的对象;
5.Singleton(单例):保证一个类仅有一个实例,并提供一个访问它的全局访问点;
结构型设计模式涉及如恶化组合类和对象以获得更大的结构.结构型类模式采用继承机制来组合接口或实现;
1.Adapter(适配器):将一个类的接口转换成客户希望的另一个接口.使得原本因接口不兼容而不能一起工作的那些类可以一起工作;
2.Bridge(桥接):将抽象部分与实现部分分离,使他们都可以独立地变化;
3.Composite(组合):将对象组合成树形结构以表示”整体-部分”的层次结构;
4.Decorator(装饰):动态地给一个对象添加一些额外的职责.就增加功能而言,装饰模式比生成子类更加灵活;
5.Facade(外观):为子系统中的一组接口提供一个一致的界面,外观模式定义了一个高层接口,使得这一子系统更加容易使用;
6.Flyweight(享元):运用共享技术有效地支持大量细粒度对象;
7.Proxy(代理):为其他对象提供一种代理以控制这个对象的访问;
行为设计模式设计算法和对象间职责的分配.行为模式不仅描述对象或类的模式,还描述他们之间的通信模式.
1.Chain of Responsibility(责任链):使多个对象都有机会处理请求,从而避免请求的发送者和接收者之间的耦合关系;
2.Command(命令):将一个请求封装为一个对象,从而使得可以用不同的请求对客户进行参数化;
3.Interpreter(解释器):给定一个语言,定义它的文法的一种表示,并定义一个解释器,这个解释器使用该表示来解释语言中的句子;
4.Mediator(中介者):用一个中介对象来封装一系列的对象交互.
中介者使各个对象不需要显式地相互引用,从而使其耦合松散,而且可以独立地改变他们之间的交互;
5.Memento(备忘录):在不破坏封装性的前提下捕获一个对象的内部状态,并在对象之外保持这个状态.
这样以后就可以将对象恢复到原先保存的状态;
6.Observer(观察者):定义对象间的一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新;
7.State(状态):允许一个对象在其内部状态发生改变时改变他的行为.对象看起来似乎修改了它的类.
8.Strategy(策略):定义一系列算法,把他们一个个封装起来,并且使他们可以相互替换.使得算法可以独立于使用他们的客户而变化;
9.Template Method (模板方法):定义一个操作中的算法骨架，而将一些步骤延迟到子类中。
模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。
10.Visitor(访问者):表示一个作用于某对象结构中的各元素的操作。它允许在不改变各元素的类的前提下定义作用于这些元素的新操作。
递归由两个基本要素:边界条件,即确定递归到何时终止,也称为递归出口;
递归模式,即大问题是如何分解成小问题的,也成为递归体;
分治法的设计思想时将一个难以直接解决的大问题分解成一些规模较小的相同问题,以便各个击破,分而治之;
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
然而，不同子问题的数目常常只有多项式量级。
如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。
为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。
不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。
当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。
若其具有以下两个性质可以考虑用动态规划法来求解:最优子结构,重叠子问题;
贪心法在解决问题的策略上是仅根据当前已有的信息做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变.
贪心法并不是从整体最优考虑,他所做出的选择只是在某种意义上的局部最优;
不能保证总能获得全局最优解,但通常能得到较好的近似最优解;
一般具有两个重要性质:最优子结构,贪心选择性质;
回溯法有“ 通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。
回溯法在用来求问题的所有解时要回溯到根，且根结点的所有子树都已被搜索遍才结束;
而用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的方法称为回溯法，它适用于解一些组合数较大的问题。
回溯法的求解目标是找出T中满足约束条件的所有解，
而分支限界法的求解目标是找出满足约束条件的一个解，
或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
伪代码是介于自然语言和程序设计语言之间的方法,它采用某一程序设计语言的基本语法,同时结合自然语言来表达;
数据库系统是存储信息的系统,数据库管理系统是数据管理软件,数据库是数据的仓库或容器;
数据的独立性是指数据与程序独立，将数据的定义从程序中分离出去，由DBMS负责数据的存储，
应用程序关心的只是数据的逻辑结构，无须了解数据在磁盘上的数据库中的存储形式，
从而简化应用程序，大大减少了应用程序编制的工作量。
数据恢复的原理非常简单，就是要建立冗余(Redundancy)数据。
换句话说，确定数据库是否可恢复的方法就是其包含的每一条信息是否都可以利用冗余存储在别处的信息重构。
冗余是物理级的，通常认为逻辑级是没有冗余的。
ODBC (开放式数据库互连)和JDBC(Java程序数据库连接)标准定义了应用程序和数据库服务器通信的方法，
即定义了应用程序接口，应用程序用它来打开与数据库的连接、发送查询和更新以及获取返回结果等。
共享内存访问问题会随着CPU个数的增加变得难以解决;
数据库有”型”和”值”的概念,”型”是指对某一数据的结构和属性的说明,”值”是型的一个具体赋值;
概念模式反映的是数据库的结构及其联系，所以是相对稳定的;而实例反映的是数据库某一时刻的状态，所以是相对变动的。
需要说明的是，概念模式不仅要描述概念记录类型，还要描述记录间的联系、操作以及数据的完整性和安全性等要求。
但是，概念模式不涉及存储结构、访问技术等细节。只有这样，概念模式才算做到了“物理数据独立性”。
内部记录并不涉及物理记录，也不涉及设备的约束。
它比内模式更接近于物理存储和访问的那些软件机制，是操作系统的一部分(即文件系统)。
数据按外模式的描述提供给用户，按内模式的描述存储在磁盘上，
而概念模式提供了连接这两级模式的相对稳定的中间层，并使得两级中任意一级的改变都不受另一级的影响。
全码(All-Key).关系类型的所有属性组是这个关系模式的候选码,称为全码;
完整性规则防止的是对数据的意外破坏;
关系R与S的差是由属于R但不属于S的元组构成的集合; R-S;
投影Π:关系R中选出若干属性列A组成新的关系;
连接θ:从R与S的笛卡尔积中选取属性间满足一定条件的元组;
等值连接。当θ为“=”时，称之为等值连接，记为R⋈S;
自然连接。自然连接是一种特殊的等值连接，
它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果集中将重复属性列去掉,记为R⋈S;
需要特别说明的是，一般连接是从关系的水平方向运算，而自然连接不仅要从关系的水平方向运算，
而且要从关系的垂直方向运算因为自然连接要去掉重复属性，如果没有重复属性，那么自然连接就转化为笛卡儿积。
R÷S应当满足在X上的分量值x的象集YX包含关系S在属性组Y上投影的集合;
左外连接。取出左侧关系中所有与右侧关系中任一元组都不匹配的元组，
用空值null填充所有来自右侧关系的属性，构成新的元组，将其加入自然连接的结果中。
右外连接。取出右侧关系中所有与左侧关系中任一元组都不匹配的元组，
用空值null填充所有来自左侧关系的属性，构成新的元组，将其加入自然连接的结果中。 全外连接:完成左外连接和右外连接的操作;
字符串匹配运算符 LIKE 与_和%进行单个,任意个字符匹配;若涉及两个以上的表,则成为连接查询;
元组含有空值时:空值在任何聚集操作中被忽视. NULL值又可以在分组属性中看作是一个一般的值;
SQL提供了可为关系和属性重新命名的机制,这是通过使用AS子句来实现的;
规范化:将一个第一级范式的关系模式转换成若干个高一级范式的关系模式,这个过程称之为规范化;
1NF:若关系模式R中的每一个分量是一个不可再分的数据项,则关系莫斯R属于第一范式;
冗余度大; 引起修改操作的不一致性; 插入异常; 删除异常;
2NF:当1NF消除了非主属性对码的部分函数依赖,则成为2NF;
3NF:当2NF消除了非主属性对码的传递函数依赖,则成为3NF;
3NF的模式必是2NF的模式。产生冗余和异常的两个重要原因是部分依赖和传递依赖。
因为3NF模式中不存在非主属性对码的部分函数依赖和传递函数依赖，所以具有较好的性能。
备份方法:静态转储和动态转储; 海量转储和增量转储.日志文件;
海量转储是指每次转储全部数据;增量转储是指每次只转储上次转储后更新过的数据;
并发操作带来的数据不一致性有三类:丢失修改,不可重复读和读脏数据;
两段封锁协议:是指所有事务必须分两个阶段对数据项加锁和解锁。
即事务分两个阶段，第一阶段是获得封锁，事务可以获得任何数据项上的任何类型的锁，但不能释放:
第二阶段是释放封锁，事务可以释放任何数据项上的任何类型的锁，但不能申请。
封锁的粒度:封锁对象的大小称为封锁的粒度。
封锁的对象可以是逻辑单元(如属性、元组、关系、索引项、整个索引甚至整个数据库)，
也可以是物理单元(如数据页或索引页)。
中继器(实现物理层协议转换，在电缆间转发二进制信号)、
网桥(实现物理层和数据链路层协议转换)、
路由器(实现网络层和以下各层协议转换)、
网关(提供从最低层到传输层或以上各层的协议转换)和交换机等。
物理层的互连设备有中继器和集线器;
数据链路层的互连设备有网桥和交换机;
路由器是网络层的互连设备,用于连接多个逻辑上分开的网络;通常把网络层地址信息称为网络逻辑地址,把数据链路层地址信息称为物理地址;
网关是应用层的互连设备;
家庭拨号上网就是通过PPP在用户端和运营商的接入服务器之间建立通信链路;
X.25 是在公用数据网上以分组方式进行操作的DTE (数据终端设备)和DCE (数据通信设备)之间的接口，
X.25只是对公用分组交换网络的接口规范说明，并不涉及网络的内部实现，
它是面向连接的,支持交换式虚电路和永久虚电路。
IP所提供的服务通常被认为是无连接的和不可靠的,与此相对应的就是面向连接的传输(如TCP);
IP的主要功能包括将上层数据(如TCP、UDP数据)或同层的其他数据(如ICMP数据)封装到IP数据报中;将IP数据报传送到最终目的地;
为了使数据能够在链路层上进行传输，对数据进行分段;确定数据报到达其他网络中的目的地的路径。
地址解析协议(Address Resolution Protocol, ARP) 及反地址解析协议(RARP)是驻留在网际层中的另一个重要协议。
ARP的作用是将IP地址转换为物理地址，RARP的作用是将物理地址转换为IP地址。
IP地址短缺的问题使用具有更大地址空间的IPv6协议;
网际层ICMP就是一个专门用于发送差错报文的协议;
TCP有助于提供可靠性;而UDP有助于提高传输的高速率性;
主机域名由以下4部分组成:计算机主机名.本地名.组名.最高层域名;域名和IP地址是一一对应的;
C类网络地址占有3个字节，它是最通用的Internet 地址。
使用最高三位为110 来标识此类地址，其余21位为真正的网络地址，因此C类地址支持221-2个网络。
主机地址占最后1个字节，每个网络可多达28-2个主机。C类网络地址第一个字节的十进制值为192~ 223.
最常用的C类地址使用前3个字节来识别网络，最后一一个字节 (8位)识别主机。因此，子网掩码是255.255.255.0.
Internet服务如域名服务,远程登录服务,电子邮件服务,WWW服务和文件传输服务等;
1.域名服务:DNS是一种分布式地址信息数据库系统; 在访问主机的时候只需要知道域名,通过DNS服务器将域名转变为ip地址.
DNS的作用是UDP端口,端口号为53;
2.远程登录服务:Telnet远程登录;
3.电子邮件服务:E-mail服务器主要采用SMTP(简单邮件传输协议);
在TCP/IP网络上的大多数邮件管理程序使用SMTP来发信,
且采用POP(Post Office Protocol,常采用的是POP3)来保管用户未能及时取走的邮件.
简单邮件传送协议和用于接收邮件的POP3均是利用TCP端口.SMTP所用的端口号是25,POP3所用的端口号是110;
信息安全包括五个基本要素:机密性,完整性,可用性,可控性与可审查性;
计算机病毒具有隐蔽性,传染性,潜伏性,触发性和破坏性等特点;
破坏数据完整性:以非法手段窃得对数据的使用权，删除、修改、插入或重发某些重要信息，
以取得有益于攻击者的响应;恶意添加，修改数据，以干扰用户的正常使用。
拒绝服务攻击:它不断对网络服务系统进行干扰，改变其正常的作业流程，执行无关程序使系统响应减慢甚至瘫痪，影响正常用户的使用，
甚至使合法用户被排斥而不能进入计算机网络系统或不能得到相应的服务。
网络安全控制技术目前有防火墙技术、加密技术、用户识别技术、访问控制技术、网络反病毒技术、网络安全漏洞扫描技术、入侵检测技术等。
美国电器和电子工程师学会标准(IEEE);
美国国防部标准(DOD-STD);
国际电工委员会(IEC);
国际标准ISO;
已正式公布的行业代号有QJ(航天),SJ(电子),JB(机械)和JR(金融)等;
地方标准的代号:由大写汉语拼音DB加上省,自治区,直辖市行政区划代码的前两位数字;
国际上比较通用的ASCⅡ码(美国信息交换标准代码);
著作权(也称为版权)是指作者对其创作的作品享有的人身权和财产权.
人身权包括发表权,署名权,修改权和保护作品完整权等;
财产权包括作品的使用权和获得报酬权,即以复制,表演,播放,展览,发行,摄制电影,电视,录像或者改编,翻译,注释,编辑等方式使用作品的权利,
以及许可他人以上述方式使用作品并由此获得报酬的权利;
计算机软件和实用艺术品受著作权保护的同时,权利人还可以通过申请发明专利和外观设计专利获得专利权称为工业产权保护的对象;
著作权法保护的计算机软件是指计算机程序及其有关文档;
计算机程序包括源程序和目标程序,同一程序的源程序文本和目标程序文本视为同一软件作品;
计算机程序的文档是指用自然语言或者形式化语言所编写的文字资料和图表,
用来描述程序的内容,组成,设计,功能规格,开发情况,测试结果及使用方法等.
文档一般以程序设计说明书,流程图和用户手册等表现;
计算机软件的著作人身权:发表权;开发者身份权(也成为署名权);
计算机软件的著作财产权:丧失该合法复制品所有权时,负责将备份复制品销毁.
除约定合同外,未经该软件著作权人许可,不得向任何第三方提供修改后的软件;
计算机软件著作权的权利自软件开发完成之日起,保护期为50年.保护期满,除开发者身份权以外,其他权利终止.
一旦计算机软件著作权超出保护期,软件就进入共有领域;在一般情况下,损害他人著作财产权或人身权的行为都是违法行为;
合作开发的软件,其著作权的归属由合作开发者签订书面合同约定;无书面合同或者未作明确约定的,其著作权人由受托人享有;
智力活动的规则和方法,即人们进行推理,分析,诊断,运算,处理,记忆等思维活动的规则和方法;
授予专利权的条件:新颖性,创造性和实用性;
数据流分析是对事务处理所需的原始数据的收集及经处理后所得数据及其流向，一般用数据流图(DFD)来表示。
DFD不仅指出了数据的流向，而且指出了需要进行的事务处理(但并不涉及如何处理，这是应用程序的设计范畴)。
数据字典包括数据项、数据结构、数据流、数据存储和加工5个部分;
需求分析阶段的成果是系统需求说明书，主要包括数据流图、数据字典、各种说明性表格、统计输出表和系统功能结构图等。
系统需求说明书是以后设计、开发、测试和验收等过程的重要依据。
数据流图是对业务处理过程从高层到底层的一级抽象，高层抽象流图一般反映系统的概貌。
对数据的引用较为笼统，而底层又可能过于细致，不能体现数据的关联关系，
因此要选择适当层次的数据流图，让这一层的每一部分对应一个局部应用，实现某一项功能，从这一层入手，就能很好地设计分E-R图。
在形成数据字典的过程中，数据结构、数据流和数据存储都是根据现实事物来确定的，
因此都已经基本上对应了实体及其属性，以此为基础，加以适当调整，增加联系及其类型，就可以设计分E-R图。
①属性不可再分，即属性不再具有需要描述的性质，不能有属性的属性。
②属性不能与其他实体发生联系，联系是实体与实体间的联系。
合并的目的在于在合并过程中解决分E-R图中相互间存在的冲突，
消除分E-R图之间存在的信息冗余，使之成为能够被全系统所有用户共同理解和接受的统一的,精炼的全局概念模型。
E-R图的冲突主要有以下三类:属性冲突,命名冲突,结构冲突;
拆分E-R图的合并过程中要对其进行优化,具体可以从以下三个方面实现;
(1)实体类型的合并;实体个数减少,有利于减少将来数据库操作过程中的连接开销;
(2)冗余属性的消除;
(3)冗余联系的消除;直接联系可以通过间接联系所表达,可消除直接联系;
测试中一定要有非设计人员的参与;
由于数据库重构的困难和复杂性,数据库的重构一般都在迫不得已的情况下才进行.
一旦应用需求变化太大,需要对全部数据库结构进行重组,说明该数据库系统的生命周期已经结束,需要设计新的数据库应用系统;
用例建模技术用于描述系统使用的模型，其建模过程是以用户为中心的建模过程，
先识别问题中的参与者，再根据参与者确定每个参与者的用例、定义用例之间的关系、确定模型的过程。
用例模型作为后续面向对象分析和设计的基础。
注意:要小心选用用例之间的关系，一般来说， 这些关系都会增加用例和关系的个数，从而增加用例模型的复杂度。
在设计算法时需要做的第一件事就是完全理解需要解决的问题,仔细阅读问题的描述;
准确地理解算法的输入是什么?要求算法做的是什么?即明确算法的入口和出口,这是设计算法的切入点;
在构思和设计了一个算法之后,必须清楚,准确地将所设计的求解步骤记录下来,即描述算法;
“时间-速度”,一个好算法是反复努力和重复修正的结果.设
计者的时间显然也是一种资源,在实际应用中,常常是项目进度迫使我们改进算法;
组合问题一般都是最优化问题,因此也成为组合优化问题,即寻找一个组合对象,
例如一个排列,一个组合和一个子集,这个对象能够满足特定的约束条件并使得某个目标函数取得极值:价值最大或者成本最小;
解决问题的重点应放在面向对象的设计上;
京公网安备 11010502036488号