《算法设计与分析》PPT课件 河南师范大学 李文凤

 
课件内容： 
第一章 概述 
掌握算法、算法复杂性和NP完全理论中的相关基本概念，理解并会运用算法复杂性分析方法。 
第一讲 算法、程序和算法复杂性概念 
第二讲 渐进复杂性 
第三讲 NP完全性理论 
单元测试 
第二章 递归与分治 
掌握递归和分治的基本算法策略思想，通过熟练掌握相关经典实例问题，学会运用它们分析问题和设计相应的算法。 
第一讲 递归的概念 
第二讲 分治法的基本思想 
第三讲 二分搜索技术 
第四讲 大整数乘法 
第五讲 Strassen矩阵乘法 
第六讲 棋盘覆盖问题 
第七讲 合并排序 
第八讲 快速排序 
第九讲 线性时间选择问题 
第十讲 最接近点对问题 
单元测试 
第三章 动态规划 
掌握动态规划算法策略的思想，通过熟练掌握相关经典实例问题，学会运用它们分析问题和设计相应的算法。 
第一讲 矩阵乘法 
第二讲 动态规划算法的基本要素 
第三讲 最长公共子序列 
第四讲 最大子段和 
第五讲 凸多边形最优剖分 
第六讲 0-1背包问题 
第七讲 最优二叉搜索树 
单元测试 
第四章 贪心算法 
掌握贪心算法的思想，通过熟练掌握相关经典实例问题，学会运用它们分析问题和设计相应的算法。 
第一讲 活动安排问题 
第二讲 贪心算法的基本要素 
第三讲 最优装载问题 
第四讲 单源最短路径问题 
单元测试 
第五章 回溯法 
掌握回溯算法的解题框架和设计要点，通过熟练掌握相关经典实例问题，学会运用它们分析问题和设计相应的算法。 
第一讲 回溯法的算法框架 
第二讲 装载问题 
第三讲 n皇后问题 
第四讲 图的m着色问题 
第五讲 旅行售货商问题 
第六讲 连续邮资问题 
单元测试 
第六章 分支限界法 
掌握分支限界算法的解题框架和设计要点，通过熟练掌握相关经典实例问题，学会运用它们分析问题和设计相应的算法。 
第一讲 分值限界法的基本思想 
第二讲 单源最短路径问题 
第三讲 布线问题 
第四讲 TSP问题 
单元测试 
第七章 随机算法 
掌握简单的随机数生成法-线性同余法，并掌握四种随机算法的基本思想，通过熟练掌握相关经典实例问题，学会运用它们分析问题和设计相应的算法。 
第一讲 随机数 
第二讲 数值随机化算法 
第三讲 舍伍德算法 
第四讲 拉斯维加算法 
第五讲 蒙特卡罗算法 
单元测试