《算法分析与设计》课程讲什么内容

编译原理和算法分析与设计相比，算法分析与设计更难。

算法分析的话比较偏重整数规划，数列的求解，组合数学等等，设计那就要靠悟性了，而且要见多识广，不管你使用的是什么语言，也不管语言怎么发展，数据结构是变不了多少的。算法设计也差不多，帮助你改善解决问题的思维。

算法分析与设计的内容：

算法设计与分析是整个CS课程体系当中最为重要的几门课程之一，因为这门课是现代计算机科学发展的核心课程，和离散数学、数理逻辑四论地位相当，号称必修中的必修，不过一般CS系不需要学数理逻辑四论，国内大学的四论教学开展的也不多。因此请大家一定要在这门课打好基础，学好这门课能让你未来的工作和学习非常轻松。

《计算机算法设计与分析(第3版)》为普通高等教育“十一五”国家级规划教材，是计算机专业核心课程“算法设计与分析”教材。全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、随机化算法、线性规划与网络流、NP完全性理论与近似算法等。书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。

为突出教材的可读性和可用性，章首增加了学习要点提示；章末配有难易适度的习题，分为算法分析题和算法实现题两部分；配套出版了《算法设计与实验题解》；并免费提供电子课件和教学网站服务。

第二题

1.背包问题是什么=、=我们教材不一样 不了解具体问题。。

2.4皇后

#include<iostream.h>

const int n = 4

const int n_sub = n - 1

int queen[n]

bool row[n]

bool passive[2*n-1]

bool negative[2*n-1]

int main()

{

int cur = 0

bool flag = false

queen[0] = -1

int count = 0

while(cur>=0)

{

while(cur>=0 &&queen[cur]<n &&!flag)

{

queen[cur]++

if(queen[cur] >= n)

{

queen[cur] = -1

cur--

if(cur>=0)

{

row[queen[cur]] = false

passive[queen[cur] + cur] = false

negative[n_sub + cur - queen[cur]] = false

}

false

}

else

{

if(row[queen[cur]] == false)

{

flag = true

if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {

flag = false

}

else

flag = true

if(flag) {

if(cur == n-1)

{

count++

}

row[queen[cur]] = true

passive[queen[cur] + cur] = true

negative[n_sub + cur - queen[cur]] = true

cur++

if(cur >= n) {

cur--

row[queen[cur]] = false

passive[queen[cur] + cur] = false

negative[n_sub + cur - queen[cur]] = false

}

flag = false

}

}

}

}

}

cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl

return 0

}

这个是代码。。。状态空间树这里画不出来。。。

第三题

你百度下基本都有的=、=。。。我百度出来不好意思贴了你自己去看下吧

比如1.的答案：

最坏情况给出了算法执行时间的上界，我们可以确信，无论给什么输入，算法的执行时间都不会超过这个上界，这样为比较和分析提供了便利。

通俗点说，算法就是解决问题的方法，因为和计算密切相关，所以不交方法，叫算法

数据结构是数据的组织方式。

算法通过操作和处理数据来解决问题，所以算法和数据结构是不分家的！

而计算方法是另一门课程。基本上是存数学的东西，看这里http://baike.baidu.com/view/754503.htm?fr=ala0_1_1

  三类问题都会涉及到多项式时间算法，我们先解决什么是多项式时间算法。

  多项式时间的算法的形式化定义是，对于规模为n的输入，在最坏情况下的运行时间是 ，其中k为某一 确定常数 。相对应的，有伪多项式时间算法，典型的0-1背包问题算法复杂度为 ，其运行时间与输入的规模相关，是伪多项式的。

  如以下表格中的都是P类问题。

  NP问题能找到多项式时间的验证算法。

  什么叫验证？例如，在哈密尔顿圈问题中，Z为图中点的一个序列。如果我们能设计一个多项式时间的判定算法，判定这个序列是否是一个哈密尔顿圈，那么称这个问题能在多项式时间内验证，序列Z是这个问题的一个证书（Certificate）。

如何证明一个问题是NP问题？

注意 ：不用证明这个问题没有多项式时间求解算法，因为P类问题是NP问题的子集，只需有证书验证过程即可。

   非形式化定义 ，如果一个NP问题和其他任何NP问题一样“不易解决”（归约），那么我们认为这一问题是NPC类问题或称之为NP完全问题。

   形式化定义 ，问题X是NP完全的，如果：

  NP问题可在多项式时间归约到NPC问题。特殊地，如果一个问题满足2，而 不一定 满足1，则称它是NP难度（NP-Hard）的。

  反过来，要证明一个问题Y是NP完全的。可以采用如下步骤：

写了这么多，我还是看不懂。就这样理解叭，P类问题是可以在多项式时间求解的问题，但大部分问题都是不能的。因此我们想用一些数据去验证它是不是这个问题的解，如果能在多项式时间验证出来，那么这个问题就是NP问题。其中，NP里最难的问题我们叫它NPC问题，但有些问题跟NPC问题差不多难，然而它又不是NP问题，就只好说它是NP难度的，也就是NP难问题（NP-Hard）。

  目的：我们希望在多项式时间内解决一个 判断 问题。

  准备：某一特定问题（A）的输入为该问题的实例。例如，寻找路径（PATH）问题的实例可以是图G、G中特定的点u和v以及一个特定的整数k（是否存在u到v长度为k的路径）。

  假设有另一不同的判定问题B，已知在多项式时间解决它的算法。我们将A的任何实例 α 转化成B的具有以下特征的某个实例 β：

  这一过程就是 多项式时间归约算法 。它提供了一种在多项式时间内解决A的方法：

参考资料 ：《算法导论》