算法的分析与设计

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

《算法分析与设计》课程是理论性与应用性并重的专业课程。本课程以算法设计策略为知识单元，系统地介绍计算机算法的设计方法和分析技巧。课程教学主要内容包括：第一章，算法概述；第二章，递归与分治策略；第三章，动态规划；第四章，贪心算法；第五章，回溯法；第六章，分支限界法。通过介绍经典以及实用算法让同学掌握算法设计的基本方法。结合实例分析，让同学深入理解算法设计的技巧，以及分析算法的能力。

‘贰’ 学习算法分析与设计需要那些基础(是否需要学习离散数学和线性代数)

算法分析与设计，目前国内本科生和硕士生的教材好像都是从国外翻译过来的。听起来挺复杂的样子，如果简单地掌握和运用还是不难的，大部分内容在数据结构中都涉及过，实际编程中也运用比较多，难的在于算法的理论研究，如21世纪的七大难题之一的NP问题就是算法问题（涉及逻辑可满足性问题）。

简单地讲需要的基础有以下几类：
1、基础类（相对一般本科生而言）：（1）把数据结构学好了算法就不难的，而数据结构其实就是图论的运用，如果是非数学专业的学生可以看离散数学中的图论部分。（2）算法分析设计时间和空间复杂度的计算，常用的还是毛泽东的战略思想——以空间换取时间。所以要学会简单的数量级运算，涉及部分代数式和数论的知识。只要简单掌握运算就可以了，不必深究。
2、提高型（研究生水平）：图论、组合数学、数理逻辑学要专门学习，可以采用数学系本科生的图论、组合数学、数理逻辑学等专业课的教材。其中组合数学中的组合设计在一定程度上和算法设计有异曲同工之处。
3、研究型（专业研究）：这主要看自己的研究方向了，如果研究能力强的话可以在很短时间内可以把需要遇到的数学知识搞懂，没有现成的固定模式。其中如研究NP问题，需要非常精深的逻辑学知识和数论基础。但不管哪个研究方向，数学的缜密思维和推理能力都是必备的，这不是一朝一夕可以练就的，需要长时间的锻炼。

以上仅个人一点点体会，仅供参考。

‘叁’ 算法设计与分析|5个算法

1）分治法

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

2）回溯法（深度优先）

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

3）贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

4）动态规划法

在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

5）分支限界法（广度优先）

分治算法求出的子问题是互相独立的。

动态规划算法具有最优子结构性质和重叠子问题性质。

贪心算法不追求最优解，只求可行解，因此不具备最优子结构的特性。

回溯算法把问题的解空间转化成图或者树结构，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

分支限界算法类似于回溯算法，它以广度优先方式搜索解空间树。

‘肆’ 大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

对于，大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题，首先要来聊聊他们的联系：1、都是一种推导算法；2、将它们分解为子问题求解，它们都需要有最优子结构。这两个特征师门的联系。

拓展资料：

贪婪算法是指在解决问题时，它总是在当前做出最佳选择。也就是说，在不考虑全局优化的情况下，该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。

动态规划是运筹学的一个分支，是解决决策过程优化的过程。20世纪50年代初，美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时，提出了着名的最优化原理，建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用，在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显着的成果。

‘伍’ 计算机算法设计与分析的内容简介

《计算机算法设计与分析(第3版)》为普通高等教育“十一五”国家级规划教材，是计算机专业核心课程“算法设计与分析”教材。全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、随机化算法、线性规划与网络流、NP完全性理论与近似算法等。书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。
为突出教材的可读性和可用性，章首增加了学习要点提示；章末配有难易适度的习题，分为算法分析题和算法实现题两部分；配套出版了《算法设计与实验题解》；并免费提供电子课件和教学网站服务。