软设复习知识点（自用）

1 合法拓扑序列

【拓扑排序主要思想】
 有向图可以拓扑排序的条件是：图中没有环。
 具体方法：
 ⑴ 从图中选择一个入度为0的点加入拓扑序列。
 ⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。
 反复执行这两个步骤，直到所有结点都已经进入拓扑序列。

参考：

计算拓扑序列

http://www.cnblogs.com/taoziwel/articles/1856432.html

2 UML设计类中，类的关系分为Generalization（泛化），Dependency（依赖关系）、Association（关联关系）、Aggregation（聚合关系）、Composition（组合关系）五种

 

聚合：聚合关系是整体和个体的关系。普通关联关系的两个类处于同一层次上，而聚合关系的两个类处于不同的层次，一个是整体，一个是部分。同时，是一种弱的“拥有”关系。体现的是A对象可以包含B对象，但B对象不是A对象的组成部分。

 

组合：关联关系的一种，是比聚合关系强的关系。它要求普通的聚合关系中代表整体的对象负责代表部分的对象的生命周期。Composition（组合关系）是一种强的“拥有”关系，体现了严格的部分和整体的关系，部分和整体的生命周期一致。如果A由B组成，表现为A包含有B的全局对象，并且B对象在A创建的时刻创建。

 

关联：表现为变量（has a ）。类与类之间的联接，它使一个类知道另一个类的属性和方法。例如如果A依赖于B，则B体现为A的全局变量。关联关系有双向关联和单向关联。双向关联：两个类都知道另一个类的公共属性和操作。单向关联：只有一个类知道另外一个类的公共属性和操作。大多数关联应该是单向的，单向关系更容易建立和维护，有助于寻找可服用的类。

 

依赖：表现为函数中的参数（use a）。是类与类之间的连接，表示一个类依赖于另一个类的定义，其中一个类的变化将影响另外一个类。例如如果A依赖于B，则B体现为局部变量，方法的参数、或静态方法的调用。

 

泛化：表现为继承或实现关系（is a）。具体形式为类与类之间的继承关系，接口与接口之间的继承关系，类对接口的实现关系。

参考：http://www.51testing.com/html/93/n-234293.html

 

3 软件开发模型

 瀑布模型：将软件生命周期划分为制定计划、需求分析、软件设计、程序编写、软件测试和运行维护等六个基本活动，并且规定了它们自上而下、相互衔接的固定次序，如同瀑布流水，逐级下落。

瀑布模型强调文档的作用，并要求每个阶段都要仔细验证。但是，这种模型的线性过程太理想化，已不再适合现代的软件开发模式，几乎被业界抛弃，其主要问题在于：

（1） 各个阶段的划分完全固定，阶段之间产生大量的文档，极大地增加了工作量；

（2） 由于开发模型是线性的，用户只有等到整个过程的末期才能见到开发成果，从而增加了开发的风险；

（3） 早期的错误可能要等到开发后期的测试阶段才能发现，进而带来严重的后果。

 

 适用于需求明确的项目，如2011年11月软考软件设计师-上午试题）—第27题

●若全面采用新技术开发一个大学记账系统，以替换原有的系统，则宜选择采用(瀑布模型)进行开发。

 

v模型：瀑布模型的变种，说明测试活动是如何与分析和设计相联系的。

 

 喷泉模型：以用户需求为动力，以对象为驱动的模型.该模型认为软件开发过程自下而上周期的各阶段是相互重叠和多次反复的，就像水喷上去又可以落下来，类似一个喷泉。各个开发阶段没有特定的次序要求，并且可以交互进行，可以在某个开发阶段中随时补充其他任何开发阶段中的遗漏。

  缺点：由于喷泉模型在各个开发阶段是重叠的，因此在开发过程中需要大量的开发人员，因此不利于项目的管理。此外这种模型要求严格管理文档，使得审核的难度加大，尤其是面对可能随时加入各种信息、需求与资料的情况。

 

 螺旋模型：将瀑布模型和快速原型模型结合起来，强调了其他模型所忽视的风险分析，特别适合于大型复杂的系统。螺旋模型沿着螺线进行若干次迭代。

（1） 制定计划：确定软件目标，选定实施方案，弄清项目开发的限制条件；

（2） 风险分析：分析评估所选方案，考虑如何识别和消除风险；

（3） 实施工程：实施软件开发和验证；

（4） 客户评估：评价开发工作，提出修正建议，制定下一步计划。

   螺旋模型由风险驱动，强调可选方案和约束条件从而支持软件的重用，有助于将软件质量作为特殊目标融入产品开发之中。但是，螺旋模型也有一定的限制条件，具体如下：

（1） 螺旋模型强调风险分析，但要求许多客户接受和相信这种分析，并做出相关反应是不容易的，因此，这种模型往往适应于内部的大规模软件开发。

（2） 如果执行风险分析将大大影响项目的利润，那么进行风险分析毫无意义，因此，螺旋模型只适合于大规模软件项目。

（3） 软件开发人员应该擅长寻找可能的风险，准确地分析风险，否则将会带来更大的风险

 

 演化模型：一种全局的软件(或产品)生存周期模型。属于迭代开发方法。

  该模型可以表示为：第一次迭代(需求->设计->实现->测试->集成)->反馈->第二次迭代(需求->设计->实现->测试->集成)->反馈->……

  即根据用户的基本需求，通过快速分析构造出该软件的一个初始可运行版本，这个初始的软件通常称之为原型，然后根据用户在使用原型的过程中提出的意见和建议对原型进行改进，获得原型的新版本。重复这一过程，最终可得到令用户满意的软件产品。采用演化模型的开发过程，实际上就是从初始的原型逐步演化成最终软件产品的过程。演化模型特别适用于对软件需求缺乏准确认识的情况。

参考：http://baike.baidu.com/view/8300.htm

 

 原型模型：允许开发人员快速地构造整个系统或系统的一部分来理解或澄清问题。可以有效地捕获系统需求。

主要思想：

先借用已有系统作为原型模型，通过“样品”不断改进，使得最后的产品就是用户所需要的。

4 UML

  业务用例和参与者一起描述组织或企业所支持的业务过程。业务用例描述了一系列动作的执行及产生对待特定业务主角具有价值的结果。

  业务对象模型描述业务结构及结构元素如何完成业务用例。

 

5 算法策略

 （1）分治算法 设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

   分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

 

 典型应用：归并排序、最大子段和问题

　（２）动态规划 基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

 

 　　　与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

 

典型应用：背包问题、最长公共子序列（LCS） 

　（３）贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

 

     贪心算法的基本思路：

    1.建立数学模型来描述问题。

    2.把求解的问题分成若干个子问题。

    3.对每一子问题求解，得到子问题的局部最优解。

    4.把子问题的解局部最优解合成原来解问题的一个解。

 

      贪心策略适用的前提是：局部最优策略能导致产生全局最优解

 

典型应用：迪杰斯特拉算法（用于求解图上的单源点最短路径，该算法an路径长度增次序产生最短路径。）、活动选择问题（若干个具有竞争性的活动要求互斥使用某一公共资源时，如何选择最大的相容活动集合）、背包问题。

　（４）回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

 

　（５）分支限界法 类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

 

典型应用：背包问题、皇后问题。

http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html

http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html

 

http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html

 

4 模块独立性（采用模块间的耦合和模块的内聚度量）

 一般来说，模块之间的耦合有7种类型，根据耦合性从低到高为非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。

(1)数据耦合 一个模块访问另外一个模块时，彼此直接通过数据参数（不是控制参数、公共数据结构或外部变量）来交换输入输出信息。

（2）标记耦合 一组模块通过数据结构本身传递

（3）公共耦合 一组模块都访问同一个公共数据环境

（4）内容耦合 一个模块直接访问另一个模块的内部数据、一个模块不通过正常人口转到另一个模块内部、两个模块有一部分程序代码重叠或一个模块有多个入口。