《算法设计与分析》PPT课件 郭楠 东北大学

 
课件内容： 
算法概述 
当我们在谈论算法时，我们在谈论什么？深度理解算法的内涵与外延。 
1.1算法概述 理解算法的定义及其内在性质。 
1.2算法求解过程 了解问题—算法—程序流程，理解算法设计、证明和分析的内涵。 
1.3计算复杂性分析 掌握算法复杂性的定义及分析方法。 
1.4计算模型 理解图灵机和递归两种计算模型，在计算模型上直观理解算法的内在性质。 
1.5分析给定算法的计算复杂性 通过具体实例掌握算法复杂性的分析方法。 
1.6算法设计与分析流程 了解算法设计策略、算法的正确性、渐近意义下的记号以及常见时间复杂性 
递归与分治 
掌握分治策略求解问题的适用条件、基本步骤以及时间复杂性的分析方法。 
2.1分治法的基本概念和算法框架 掌握分治法的基本思想和适用条件； 
2.2分治法的计算复杂性分析 基于代入法分析运行时间递归表达式和复杂性；基于递归树分析运行时间递归表达式和复杂性。 
2.3棋盘覆盖算法 掌握棋盘覆盖问题的算法设计与实现，能够分析算法复杂性。 
动态规划 
掌握动态规划策略的相关概念、采用动态规划策略求解问题所具备的基本要素（最优子结构性质和重叠子问题性质的定义及证明方法）、基本步骤以及时间复杂度的分析方法。 
3.1 动态规划的基本概念和算法框架 掌握动态规划的基本思想和要素；了解最优子结构性质及其证明方法；了解重叠子问题性质及其证明方法。 
3.2 矩阵连乘 掌握矩阵连乘问题的动态规划算法设计与实现，能够分析算法复杂性。 
3.3凸多边形最优三角剖分 理解凸多边形最优三角剖分问题与矩阵连乘问题的等价性，掌握凸多边形最优三角剖分问题的动态规划算法设计与实现，能够分析算法复杂性。 
3.4 最长公共子序列 掌握最长公共子序列问题的动态规划算法设计与实现，能够分析算法复杂性。 
3.5 最大子段和 掌握最大子段和问题的动态规划算法设计与实现，能够分析算法复杂性。 
3.6 图像压缩 掌握灰度图像无损压缩算法的设计，能够分析算法复杂性。 
3.7 0-1背包问题 掌握0-1背包问题的动态规划算法设计与实现，能够分析算法复杂性。 
贪心算法 
掌握贪心策略求解问题所具备的基本要素（最优子结构性质和贪心选择性质的定义及证明方法）、基本步骤以及时间复杂度的分析方法。 
4.1 贪心算法的基本概念和算法框架 了解贪心算法的基本思想和要素；贪心选择性质及其证明方法；以0-1背包和可拆分背包问题为例，理解贪心与动态规划在求解最优化问题时的区别和联系。 
4.2找零钱问题 掌握活找零钱问题的贪心算法设计与实现，能够分析算法复杂性。 
4.3哈夫曼编码 掌握哈夫曼编码的基本内容。 
回溯法 
掌握回溯策略求解问题的适用条件、基本步骤以及时间复杂度的分析方法。 
5.1回溯法的基本概念和算法框架 了解树搜索策略的基本思想、回溯法的基本思想；掌握子集树、排列树与完全n叉树的性质。 
5.2装载问题 掌握装载问题的回溯算法设计与实现，能够分析算法复杂性。 
5.3 0-1背包问题 掌握0-1背包问题的回溯算法设计与实现，能够分析算法复杂性。 
5.4 TSP问题 掌握TSP问题的回溯算法设计与实现，能够分析算法复杂性。 
5.5图的m着色 掌握图的m着色问题的回溯算法设计与实现，能够分析算法复杂性。 
分支限界法 
掌握分支限界策略求解问题的适用条件、基本步骤以及时间复杂度的分析方法。对比分析回溯和分支限界策略求解同一问题时的区别和联系。 
6.1分支限界法的基本概念和算法框架 了解分支限界法的基本思想，理解两种树搜索策略的区别和联系。 
6.2 0-1背包问题 掌握0-1背包问题的分支限界算法设计与实现，能够分析算法复杂性。 
6.3TSP问题 掌握TSP问题的分支限界算法设计与实现，能够分析算法复杂性。 
6.4布线问题 掌握布线问题的分支限界算法设计与实现，能够分析算法复杂性。