算法设计与分析 期末复习一

• 填空
• 简答题

填空

1. 算法是一组有穷的规则，它规定了解决莫一特定类型问题的一系列运算

   数据结构+算法=程序

2. 在进行问题的计算分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是随机存取机RAM（Random Access Machine）；随机存取存储程序机RASP（Random Access Stored Program Machine）；图灵机（Turing Machine）。

3. 算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。

4. 计算机的资源最重要的是时间和空间资源。因而，算哒的复杂性有时间复杂性和空间复杂性之分。

5. f(n)=6*2^n+ n^{2,f(n)的渐进性态f(n)=O（==2}n==）。

6. 贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。

7. 许多可以用贪心算法求解的问题一般具有两个重要的性质：贪心选择性质和最优子结构性质。

简答题

1. 简单描述分治法的基本思想。
   分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立与原问题相同；对这k个子问题分别求解。如果子问题的规模依然不够小，则再划分为k个子问题，如此递归的进行下去，知道问题规模足够小，很容易求出其解为止；将求出的小规模问题的解合并为一个更大规模问题的解，自底向上逐步求出原问题的解。
2. 简述动态规划方法所运用的最优化原理。
   一个过程的最优策略具有这样的性质，即无论其初始状态及初始策略如何，其以后者决策对以前决策所形成的状态作为初始状态的过程而言，必然构成最优策略。
3. 何谓最优子结构性质？
   某个问题的最优解包含其子问题的最优解。
4. 简单描述回溯法基本思想。
   从一条路往前走，能进则进；不能进则退，换一条路再试。在一棵含有问题全部可能解的状态树上进行深度优先搜索，解为叶子结点。搜索过程总，每到达一个结点时，则判断该结点是否含有问题的解，如果可以确定该子树中不含问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索的过程，在回溯法中，并不是先构造处整棵状态树，再进行搜索，而是在搜索过程中，逐步构造出状态树，即边搜索边构造。
5. 何谓P、NP、NPC问题。
   P问题：多项式复杂程度的问题。
   NP问题：多项式复杂程度的问题。
   NPC问题：NP问题中最难的问题，只有把解域中所有可能都穷举之后才能得出答案。