当前位置:   article > 正文

吉林大学算法设计与分析考前突击_吉林大学算法分析

吉林大学算法分析

简答题(25分)

  1. 以比较为基础的检索算法的时间下界是O(logn);
    以比较为基础的分类算法的时间下界是O(nlogn);
    简要说明理由:

  2. NP完全问题一定是NP难问题,但NP难问题不一定是NP完全问题;

  3. 算法的五大特性:确定性,能行性,输入,输出,有穷性。
    而计算过程只满足前4条特性,不满足“有穷性”;

  4. 最优性原理:
    无论过程的初始状态或者初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
    最优性原理成立的例子:流水线调度问题,货郎担问题;
    最优性原理不成立的例子:多段图问题(以乘法作为路径长度且出现负权边时 或 包含负长度环的任意两点间最短路径问题;

  5. P:所有可在多项式时间内由确定算法求解的判定问题的集合;
    NP:所有可在多项式时间内由不确定算法验证的判定问题的集合;
    COOK定理:可满足性在P内,当且仅当P=NP;
    NP-难度:如果可满足性约化为一个问题L,则称此问题L是NP-难度的。
    NP-完全:如果L是NP难度的而且L属于NP,则称问题L是NP完全的。
    可满足性问题:对于变量的任一一组真值指派确定公式是否为真。

  6. 贪心方法不一定能得到01背包问题的最优解。
    例如:

  7. 分支限界算法中c帽(x)是c(x)的下界;

  8. 问题状态:树中每一个节点确定所求解问题的一个问题状态;
    状态空间:由根节点到其他节点的所有路径确定了这个问题的状态空间;
    解状态:解状态是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解空间中的一个元组;
    答案状态:答案状态是这样一些解状态S,对于这些解状态,由根到S的那条路径确定了这问题的一个解。
    解空间的树结构即为状态空间树;

  9. 分治法的三个基本步骤:
    分:将n个输入分成k个不同的可独立求解的子问题;
    治:求出这些问题的解;
    合:通过适当的方法将每个问题的解合并成整个问题的解。

  10. 在这里插入图片描述在这里插入图片描述

计算题(35分)

分治法

一般方法的KDP描述&二分检索

在这里插入图片描述

归并分类

在这里插入图片描述

贪心法

带期限的作业问题

在这里插入图片描述
在这里插入图片描述

背包问题

在这里插入图片描述

动态规划

多段图问题

在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

构造最优二分检索树

在这里插入图片描述

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

01背包问题序偶对解法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可靠性问题

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

货郎担问题

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

流水线调度问题

在这里插入图片描述
在这里插入图片描述

回溯法

8-皇后及其变形(6-皇后)的效率估计问题:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

分支限界法

15-迷及其变形(9-迷):

  1. 画出LC检索状态空间树,并标出树中每个节点的c帽值。
    c帽(x) = f(x) + g帽(n),其中f(x)是由根到节点X的路径长度,g帽(x)是当前状态不在其目标位置的非空白牌数目。
    在这里插入图片描述
  2. 由初始状态判定是否能达到目标状态:当且仅当∑Less(i)+X为偶数可到达。
    在这里插入图片描述
    在这里插入图片描述
    这个好像画的有点问题,看个大概样子就行了,我没画完

证明题(15分)

估计就是作业上做过的证明题。

算法题(25分)

看命。

可参考https://blog.csdn.net/weixin_43633784/article/details/108117886

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/712179
推荐阅读
相关标签
  

闽ICP备14008679号