一. 简答题的基本内容（30分）

1. 记号O、W、[if !vml]

[endif] 的意义；

O：存在n0>0、c>0, 使得n>=n0有f(n) <=c*g(n)

Ω：存在n0>0、c>0, 使得n>=n0有f(n) >=c*g(n)

Θ：如果T(n)是Θ(g(n)),

T(n)是O(g(n)), Ω(g(n))


2. 分治法的基本步骤；

 1.分解：将原问题划分成为若干个规模较小并且相互独立，与原问题形式相同的子问题。

 2.解决： 若子问题规模较小而容易被解决就直接解，否则递归地解决各个子问题。

   3.合并： 将各个子问题的解合并为原问题的解。


3. 动态规划算法的两个基本要素；

  最优子结构和是否重叠子问题

  最优子结构就是子问题的最优解包含了子子问题的最优解。

  重叠子问题就是两个子问题之间是否有重叠的部分，子问题的解会被多次调用。


4. 设计动态规划算法的步骤；

  1.问题定义是否满足最优子结构

  2.递归关系即动态规划方程

  3.初值设定

  4.求解顺序


5. 分治法与动态规划两种算法策略的异同点；

  相同点：

 1.两者都是将大问题分解成若干个小问题

 2.两者都是依赖于小问题的解决来解决上一级较大的问题

  不同点：

 1.分治法往往用到递归计算，自上而下计算，而动态规划则直接自底向上计算。动态规划算法用递归的话时间复杂度会是指数级的。

   2.分治法在子问题上可能会重复计算，而动态规划中的子问题在一次计算后再次遇到就直接调用。

   3.分治法的子问题的解只可能使用一次，动态规划的子问题的解会反复调用



6. 贪心法的两个基本要素；

  最优子结构和贪心选择性

最优子结构就是：一个问题的最优解包含其子问题的最优解

  贪心选择性：即所求问题的整体最优解可以通过一系列局部最优选择，即贪心选择来达到

[if !supportLineBreakNewLine]

[endif]

7. 贪心法的算法正确性证明的基本策略；

   1、贪心算法领先：每一步都比其他算法好，从而能得到一个最优解。


2、交换论证(Exchange Argument):该方法的主要的思想也就是先假设存在一个最优的算法和我们的贪心算法最接近，然后通过交换两个算法里的一个步骤(或元素)，得到一个新的最优的算法，同时这个算法比前一个最优算法更接近于我们的贪心算法，从而得到矛盾，原命题成立。


3、结构论证(structural)：发现一个所有解都具有的界限，然后证明算法总是能达到这个界限。


8. 贪心法与动态规划两种算法策略的异同点；

  相同点：


动态规划和贪心算法都是一种递推算法  均用局部最优解来推导全局最优解


不同点：        


  动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。动态规划通常通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分。


  贪心算法依赖于当前已经做出的所有选择，采用自顶向下(每一步根据策略得到当前一个最优解，保证每一步都是选择当前最优的)的解决方法。贪心算法所做的贪心选择可以依赖于以往所做出的选择，但决不依赖将来所做的选择，也不依赖于子问题的解。


9. 在对图的深度优先搜索过程中，可将顶点的状态区为分哪三种类型、将有向图中的边区分为哪四种类型；

顶点状态：白色(未被发现的顶点)、灰色(已经发现，但还未搜索完成)、黑色(已经完成搜索的顶点)

有向图边的类型：树边、回边、前向边、横跨边



10. 如果有向带权图中存在边的权值为负的情形，如何判断图中是否存在负环；

  Bellman-Ford算法在|V|-1次迭代之后求得从源点到其他顶点的最多|V|-1条边的最短路径，在|V|-1次迭代之后再执行一次迭代过程，如果某个顶点的dist值减少了，说明图中存在负环。


11. 最大流、最小割的概念；

  令G = (V, E)为一个网络（有向图），并且有一个起源点 s 和一个超汇点 t，代表 s 是所有流的源头，t 是所有流的终点。

  流量限制条件： 对于每一个边e（u，v），0<=f(u, v)<=c(u,v)

  平衡条件： 

[if !vml]

[endif]

  最大流： 在容量网络G（V,E）中，满足弧流量限制条件和平衡条件且具有最大流量的可行流称为最大流。

  最小割：容量最小的割。

[if !vml]

[endif]



12. 最大流最小割定理的内容及其证明方法；

 定理： 网络中的最大流等于最小割

6. 定理一：如果f是网络中的一个流(不必须是最大流)，CUT（S，T）是任意一个割，那么f的值等于该割中的正向割边的流量和与逆向割边的流量和之差。

6.1.

推论1：如果f是网络中的一个流，CUT（S，T）是一个割，那么f的值不超过割CUT（S，T）的容量。


[if !vml]

[endif]

6.2. 推论2：网络中的最大流不超过任何割的容量。

7.

定理二：在任何网络中，如果f是一个流，CUT（S，T）是一个割，且f的值等于该割的容量，那么f是一个最大流，CUT（S，T）是一个最小割（容量最小的割）。

8.

定理三：最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。

证明：

  1.存在一个割（A,B），使得割的容量等于流量。

  2.流f就是一个最大流

  3.图中不存在一条增广路。


13. 带需求和下界的流通问题；




14. Hill-climbing和best-first等搜索算法的基本思想；

  爬山法：爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。

 步骤：

  1.构造由根组成的单元素栈S

  2.如果top(S)是目标节点，停止，否则转步骤三。

  3. Pop（S）

  4. S的子节点按照启发测度由大到小的顺序压入S

  5.如果S是空的失败否则转到第二步

  Best-first搜索：Best-First策略是根据一个评价函数 f(n) ，在目前产生的所有节点中选择具有最小评价函数值的节点进行扩展。它结合了深度优先搜索和广度优先搜索的优点，具有全局化观念，而爬山法仅仅具有局部优化观念。

 步骤：

  1.使用评价函数构造一个堆H，首先构造由根组成的单元素堆

  2.如果H的跟root是目标节点就停止。

  3.从H中删除root，把root的子节点插入H

  4.如果H空那么失败，否则转到第二步


15. 分支限界算法的基本思想；

分支界限搜索的基本思想是用某种策略(比如爬山发、Best-First策略)产生分支，发现优化解的一个界限，缩小解空间，从而提高求解的效率。


16. A*算法设计的基本要求与最优性的证明方法；

  A*算法是利用启发式函数，best-first策略进行搜索从而更早地发现优化解的一种算法。

 A*算法的启发函数：

  G(n)=从树根到n的代价。

  H*(n)=从n到目标节点的优化路径的代价。

  F(n)= g(n) + h*(n)是节点n的代价

 把h(n) <= h*(n) 称为启发式函数。


 基本要求：

  1.使用best-first策略搜索树

  2.节点n的代价函数为f(n) = g(n) + h(n)， g(n) 是从根到n的路径代价，h(n)是从n到某个目标节点的优化路径代价。

  3.对于所有的n, h(n) <= h*(n)

  使用best-first策略搜索树，如果A*选择的节点时目标节点，则该节点表示的解是优化解。

 证明：

   令n是任意扩展到的节点，假定t是选中的目标节点但不是最优的。

   证明f(t) = g(t) 是优化解代价

  1. A*算法使用best-first策略，f(t)<=f(n)

  2. h(n)<=h*(n)，有f(t) <= f(n) <= f*(n)

  3. {f*(n)}中必有一个为优化解的代价，令其为f*(s),s为最优的但没有被选中，那么有f(t)<=f*(s)

  4. t是目标节点h(t)=0, 所以f(t)=g(t)+h(t)= g(t)=f*(t)

  5.有 f(t) = g(t) = f*(t)<=f*(s)说明s不是最优的节点

  矛盾了，所以t是最优的节点



17. “多项式归约（reduction）”的概念与用途；

 A可以多项式归约到B（A<=ρB）:

     有一个函数f，能使A的输入在多项式的时间内转化为B的输入。 A的解为真则B的解也为真。 B至少和A一样难。

 用途：

  1.如果A<=ρB，并且B能够在多项式时间内解决那么A也能在多项式时间内解决。

  2.如果A<=ρB，并且A不能够在多项式时间内解决那么B也不能在多项式时间内解决。

  3.如果A<=ρB且B<=ρA, 那么有A≡ρB


18. P 问题、NP问题、NP完全问题、NP困难问题（NP-hard problem）的概念；

 P问题：在多项式时间内可解的问题

 NP问题： 可以在多项式时间内验证一个解的问题。

 NP完全问题：如果所有的NP问题能够在多项式时间内规约为一个NP问题，那么此问题就是NPC问题，

  1. B∈NP

  2. A≤ρB 对于所有的A∈NP

NP困难问题：所有的问题能够在多项式时间内规约为一个NP问题，但这个问题不是NP问题，此问题为NPH问题。满足2不满足1


19. NP完全问题的证明方法；

  1. 证明B是NP问题，在多项式的时间内验证一个解

 2.证明一个已知的NP问题能在多项式时间内规约为问题B，不需要证明所有的NP问题归约为B。


20. 常见的NP完全问题

 NP问题：

     1.TSP问题

     2.哈密尔顿回路问题

     3.图的着色问题。

NP完全问题：

    1. Packing problem

：   Set-packing Independent-Set

2.Covering problem：    Set-Cover  Vertex-Cover

3.Constraint satisfaction(约束满足) problem：   SAT     3-SAT

3.Sequcing problem：    哈密尔顿回路 TSP问题

4.Partitioning problem：  3D-Matching  3-Coloring

5.Numerical problem：   Subset-Sum（子集和问题）   KnapSack

 

二. 应用题 （40分）

多段图上的最短路径动态规划推导



图的深度优先搜索算法的扩展及应用

  判环，topo排序


强连通分量的划分算法


图的传递闭包算法Warshall的基本思想与过程

  算法：

   设在n 个元素的有限集上关系R的关系矩阵为M

  1.置新矩阵为A

  2.置k=1

  3.对所有i如果A[i, k]=1，则对j=1,…n执行

         A[i, j]= A[i j]∪A[k, j]

  4. k增1

  5.如果k<=n转（3），否则停止。



Bellman-Ford算法的基本思想与过程


最大流最小割问题的求解算法Ford-Fulkerson（增广路径算法）


最大流最小割算法的应用，如二部图匹配、边不交路径问题、项目选择问题等


递归方程的求解方法

 1.迭代法

 2.换元法，替代法

 3.递归树法

 4.Master定理


三．算法设计题 （30分）

分治法：如统计逆序对、中位数查找、主元素查找问题等

统计逆序对：

   分解：将原数组按照下标分为两部分。

   合并：如果问题规模较小，合并。在合并过程中用一个临时数组将两数组元素从大到小排列，复制回原数组。若问题规模较大，继续递归求解。

时间复杂度：O(n log(n))

伪代码： 重要逆序对和逆序对的区别

     实验一

   中位数查找：带权中位数的查找

        每一次将数组分为小于一个元素值的，等于这个元素值的和大于这个元素值三部分，通过比较元素值x的下标k是否等于中位数下标，如果等于找到中位数，小于，则中位数一定在k的右边部分，大于一定在k的左边部分，继续查找直到等于n/2；

分解：

合并：


主元素查找问题：

   基本思路：类似于归并排序的递归方法。如果将数组A分成两个长度（接近）相等的两个子序列A1和A2，则如果数组Ａ中存在主元素，则A1或A2中也一定存在一个主元素。这样在对两个子序列进行合并的merge算法中，不需要进行排序，而是要分别检查A1或A2可能存在的主元素能否与另一个子序列（A2或A1）中的元素构成整个数组A中的主元素。由于这个merge算法一定可以在O(n)时间内完成，故整个算法的复杂度为O(nlogn)。

算法基本描述如下：

majority (A[1 . . . n])

if n = =1 return A[1]

let AL,AR be the first and second halves of A

ML = majority(AL) and MR = majority(AR)

if neither half has a majority

return “no majority”

else

check whether either ML or MR is a majority element ofA

if so, return that element

else return “no majority”



贪心法：Dijkstra算法、区间调度问题、区间划分问题等

 Dijstra算法: 

   两个集合S，T表示已被加入的顶点和未被加入的顶点，

时间复杂度：O(E logV)


     区间调度问题：

按照结束时间排序，比较之后的每个任务的开始时间是否比当前的结束时间大，加入调度队列。

 时间复杂度：O(n logn)


   区间划分问题：

   按照开始时间排序，设置一个优先队列放每一个区间内活动的最晚的结束时间，若新的活动的开始时间比最早的（也就是堆顶）结束时间还要早，那么这个活动肯定是不能够被选择的。

   时间复杂度：O(n logn)


动态规划：最长递增子序列问题、编辑距离问题、矩阵连乘问题、背包问题、树的最大独立集等

   最长递增子序列：

    子问题定义：dp[j]是到第j个元素为止的最长递增子序列的长度。原问

题就是dp[n]

    递归关系：dp[i] = max( dp[j]) + 1（<i，j>∈E）

    初值设定：dp[i] = 1   i∈n

    求解顺序：按照数组下标从小到大的顺序依次执行。

     时间复杂度：O(n2)


矩阵连乘问题：

 子问题定义：dp[i][j]为第i个矩阵乘到第j个矩阵的最小的代价，原问题就是dp[1][n]

 递归关系：dp[i][j] = min(dp[i][k] + dp[k+1][j] +p[i-1]*p[k]*p[j])  i<=k

 初值设定：dp[i][i]=0;


求解顺序：按照bottom-up的顺序，沿矩阵对角线按长度递增的顺序求解。


时间复杂度：O(n3)

伪代码：

    实验五

 编辑距离问题：

  子问题定义：dp[i][j]为第1个字符串到第i个字符为止换到第二个字符串到第j个字符为止所花费的最小代价。原问题为dp[n][m]

  递归关系：dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i][j-1])

  初值设定：dp[i][i] = 0, dp[i][0]=n, dp[0][i]=m

  求解顺序： 按照二维表的顺序从左至右从上至下求解。

时间复杂度：O(n2)

伪代码：PPT

背包问题：


树的最大独立集问题：

 子问题定义：I[u]为以u为根节点的最大独立集的大小。原问题为I(r)

 递归关系：有两种情况，u是最大独立集和u不是最大独立集。

I(u) = max(u的所有儿子的独立集的和I(w),

1+u的所有孙子的最大独立集的和)

     初值设定：叶子节点的每一个值都为1

 求解顺序：BFS的顺序遍历每一个顶点。

 时间复杂度：O(V+E)


图算法：深度优先搜索算法、最短路径问题等

时间复杂度：O(V+E)

  最短路径问题：bellman-ford

时间复杂度：O(V*E)