算法分析及设计.doc

课程名称：算法分析及设计课程编码：C201课程学分：2适用学科：计算机应用技术算法分析及设计Design and Analysis of advanced Algorithms教学大纲一、课程性质 算法的设计与分析是计算机科学的核心问题之一，是计算机科学与工程各专业学生及研究生的一门重要的专业基础课。其内容是研究计算机领域及相关领域中的一些常用的算法设计方法及算法的复杂性分析方法。同时，通过讲授NP理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。学习和掌握这些知识不仅对计算机专业的技术人员，而且对使用计算机的其他各专业技术人员都是必不可少的。二、课程教学目的通过本课程的学习，应使学生掌握算法设计的常用方法，以便能够运用这些方法设计解决计算机应用中的实际问题的有效算法，并能够利用已有算法去解决实际问题。此外还要使学生学会分析算法，估计算法的时空复杂性，从而对算法做出科学的评价。三、教学基本内容及基本要求第一章 绪论1、 算法定义（了解）2、 算法特征3、 计算机求解问题过程4、 算法描述语言5、 算法分类 第二章 算法复杂性分析（要求全部掌握）1、 算法复杂性 2、 算法复杂性计量3、 复杂性的渐进形态 4、 渐进分析5、 递归方程解的渐进阶 第三章 算法设计的基本方法（要求全部掌握）1、 贪心法 2、 分治法3、 动态规划 4、 回溯法5、 分支限界法 第四章 图和网络算法（要求全部掌握）1、 基本概念 2、 树的算法3、 路的算法 4、 流的算法第五章 计算几何（要求全部掌握）1、 相交问题 2、 求夹角3、 求凸包 4、 判断一点在几何体内部5、 Voronoi图第六章概率算法（要求全部掌握）1、 概率算法简介 2、 随机数3、 素数的概率算法 4、 线性时间选择算法 5、 平面点集最近点对概率算法第七章 NP完全性理论及近似算法（要求全部掌握）1、 确定性图灵机 2、 非确定性图灵机3、 P类与NP类 4、 Cook定理与NP完全问题5、 NP完全问题近似解法 第八章 新技术综述（一般了解）四、本课程与其他相关课程的联系与分工先修课程：程序设计，数据结构，离散数学 等。五、实践环节教学内容的安排与要求对作业中的一些典型问题，要求学生运用所学的算法设计方法给出相应的算法程序并上机实现，并给出具体算法程序的时空复杂性数值实验结果。六、本课程课外练习的要求课外练习为习题，每节的作业量不少于二道题。七、本课程的教学方法及使用现代化教学手段的要求教学方法以课堂教学为主，借助于计算机和投影设备将重要的算法描述及复杂性分析过程制作成生动、直观的教学课件，以提高教学效率和效果。八、本课程成绩的考查方法及评定标准作业：20%实验报告: 20%期末考试：60%九、教材及参考书 教材：“算法设计与分析导引” 卢开澄 清华大学出版社 参考书：“算法设计与分析” 周培德机械工业出版社 “算法与数据结构” 傅清祥等 电子工业出版社 “算法设计和分析” 朱洪等上海科技文献出版社 十、课程各章节学时分配章节内容总课时讲授课时讨论、论文、实验、设计备注第1章 绪论22第2章算法复杂性分析44第3章算法设计方法66第4章图和网络算法44第5章计算几何44第6章概率算法22第7章 NP完全性理论及近似算法66第8章新技术综述22习题课2 2合计32302 大纲撰写人：付晓玲 大纲审阅人：刘文萍责任教授：李也白系（教研室）主任：李也白学院负责人：张常年制（修）定日期：2004年9月1日