微机原理期末复习重点.pdfVIP

期末复习 汪小林 北京大学计算机系 机考安排 • 时间 – 6月8 日（周三）下午3:00~5:30 • 地点 – 信息学院机房（理科一号楼二楼） • 内容 – 与作业题目难度相当，主要考查对递归、分治 、排序、动态规划、贪心、回溯和分支限界等 算法设计方法。题目共8道，大家尽量做，主要 以通过题目数正态分布评分。 2 期末考试 • 时间 – 6月13 日（周一）14:00~16:00 • 地点 – 届时网上公布，下周考试时也会公布 • 内容 – 课程网站第1~19讲的内容 3 答疑安排 • 时间 – 下周周二至周五下午1:30~5:30 • 地点 – 各助教的实验室（待教学网上公布） – 或理科一号楼1335W （我的办公室） 4 算法设计与分析 • 算法分析的基础知识和方法 – 运行时间的渐进表示（最坏时间、平均时间） – 递归式求解、平摊分析、近似分析、竞争分析 • 算法设计的基本方法 – 递归/递推、分治、动态规划、贪心、回溯/分支限界 • 一些基本问题的分析与算法设计 – 排序问题、选择问题、网络流问题、计算几何问题、 NPC 问题、NPC近似解问题、在线问题 – 斐波那契数、LCS 、矩阵链乘法、MST 、最短路径、活 动安排、霍夫曼编码、任务调度、0-1背包、TSP、 5 掌握程度说明 • 熟练应用 – 能够熟练和灵活的应用相关知识、理论和方法解决各 种相关的实际问题 • 应用 – 能够应用所学知识、理论和方法解决相关的典型问题 • 掌握 – 理解并掌握所学的知识、理论和方法，理解问题内含 • 了解 – 一般性的了解相关知识，能够识别概念的正确与错误 6 算法分析的基础知识和方法 • 运行时间的渐进表示（熟练应用） • 最坏情形的运行时间（熟练应用） • 平均情形的运行时间（应用） • 递归式求解（熟练应用） – 代换法、递归树法、主方法 • 平摊分析（应用） • 近似分析-近似算法（掌握） • 竞争分析-在线算法（了解） 7 算法设计的基本方法 • 递归/递推 – 算法设计的能力（熟练应用） – 算法分析的能力（熟练应用） – 算法正确性证明（掌握） • 分治法 – 算法设计的能力（熟练应用） – 算法分析的能力（熟练应用） – 算法正确性证明（掌握） 8 算法设计的基本方法 • 动态规划 – 算法设计的能力（熟练应用） – 算法分析的能力（熟练应用） – 问题