算法设计与分析复习习题.pptx

算法设计与分析 授课教师：刘伟 电 话： 邮 件： 办 公 室：长安校区 2 号实验楼 303 室 （软件工程系办公室） 西安邮电大学计算机学院 复习与习题 I. 为什么要学习《算法设计与分析》？ II. 怎样学好《算法设计与分析》？ 西安邮电大学计算机学院 复习与习题 为什么要学习《算法设计与分析》？ （1）写程序的基础； （2）分析一些问题的手段和方法； （3）“大数据时代”的效率要求。 西安邮电大学计算机学院 复习与习题 怎样学好《算法设计与分析》？（如何做题目？有些题目的思路是怎么想出来的？） （1）先模仿、后创新； （2）精心学习经典例子和经典算法，不断积累； （3）勤学苦练。 持之以恒！ 西安邮电大学计算机学院 复习与习题 （下面的次序为推荐阅读的次序） （1）【计算机程序设计艺术第 3 版（第一卷、第二卷、第三卷）】 Donald E. Knuth的经典著作。《计算机程序设计艺术》三卷中文名为《基本算法》、《半数值算法》及《排序与查找》。 推荐的参考文献 西安邮电大学计算机学院 复习与习题 （2）【编程珠玑】 （3）【编程之美】 （4）【高质量C++/C编程指南，林锐】 （尽管不是一本专门讲解算法的书，但其中的很多思想有助于编写质量好的程序。 虽然针对C/C++，但书中的很多思想对任何语言平台，如 Java 等，都是适用的） （5）【代码之美】 西安邮电大学计算机学院 复习与习题 考试内容和试题基本情况 （1）课堂上讲解过在大纲之内的课本内容，包括： 第 1 章 算法概述 1.1 算法与程序 1.2 算法复杂性分析 第 2 章 递归与分治策略 2.1 递归的概念 2.2 分治法的基本思想 2.3 二分有哪些信誉好的足球投注网站技术 2.4 大整数的乘法 西安邮电大学计算机学院 复习与习题 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 快速排序 第 3 章 动态规划算法 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 最长公共子序列 3.4 最大子段和 3.10 0-1背包问题 西安邮电大学计算机学院 复习与习题 第 4 章 贪心算法 4.1 活动安排问题 4.2 贪心算法的基本要求 4.3 最优装载 4.7 多机调度问题 第 5 章 回溯法 5.1 回溯法的算法框架 5.2 装载问题 5.3 批处理作业调度 5.5 n 后问题 5.8 图的 m 着色问题 西安邮电大学计算机学院 复习与习题 5.13 回溯法的效率分析 第 6 章 分支限界法 6.1 分支限界法的基本思想 6.3 装载问题 6.4 布线问题 6.6 最大团问题 西安邮电大学计算机学院 复习与习题 （2）所有的课内上机实验题目，具体内容请参阅 ppt “《算法设计与分析》- 上机题目解答.ppt”。 （3）所有题目涉及到程序设计语言部分均采用 C/C++ 语言，同学们在考试答卷时答案涉及到程序设计语言部分也必须采用 C/C++ 语言。 （4）本课程为校级考试，为书面闭卷形式。最后总成绩中平时作业和上机实验占 30%，期末考试占 70%。 西安邮电大学计算机学院 复习与习题 （5）期末试卷题目类型： 选择题（单选题）、简答题、算法设计题 试卷上 90% 的题目为上述（1）和（2）中的内容，10% 的题目（算法设计题）为用所学方法针对新问题设计算法。 西安邮电大学计算机学院 复习与习题 复习知识点 第 1 章