算法分析及设计

《算法分析及设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、...课程名称：算法分析及设计课程编码：C201课程学分：2适用学科：计算机应用技术算法分析及设计DesignandAnalysisofadvancedAlgorithms教学大纲一、课程性质算法的设计与分析是计算机科学的核心问题之一，是计算机科学与工程各专业学生及研究生的一门重要的专业基础课。其内容是研究计算机领域及相关领域中的一些常用的算法设计方法及算法的复杂性分析方法。同时，通过讲授NP理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。学习和掌握这些知识不仅对计算机专业的技术人员，而且对使用计算机的其他各专业技术人员都是必不可少

2、的。二、课程教学目的通过本课程的学习，应使学生掌握算法设计的常用方法，以便能够运用这些方法设计解决计算机应用中的实际问题的有效算法，并能够利用已有算法去解决实际问题。此外还要使学生学会分析算法，估计算法的时空复杂性，从而对算法做出科学的评价。三、教学基本内容及基本要求第一章绪论1、算法定义（了解）2、算法特征3、计算机求解问题过程4、算法描述语言5、算法分类第二章算法复杂性分析（要求全部掌握）1、算法复杂性2、算法复杂性计量3、复杂性的渐进形态4、渐进分析......5、递归方程解的渐进阶第三章算法设计的基本方法（要求全部掌握）1、贪心法2、分治法3、动

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完全问题近似解法......第八章新技术综述（一般了解）四、本课程与其他相关课程的联系

4、与分工先修课程：程序设计，数据结构，离散数学等。五、实践环节教学内容的安排与要求对作业中的一些典型问题，要求学生运用所学的算法设计方法给出相应的算法程序并上机实现，并给出具体算法程序的时空复杂性数值实验结果。六、本课程课外练习的要求课外练习为习题，每节的作业量不少于二道题。七、本课程的教学方法及使用现代化教学手段的要求教学方法以课堂教学为主，借助于计算机和投影设备将重要的算法描述及复杂性分析过程制作成生动、直观的教学课件，以提高教学效率和效果。八、本课程成绩的考查方法及评定标准作业：20%实验报告:20%期末考试：60%九、教材及参考书教材：“算法设计与

5、分析导引”卢开澄清华大学出版社 参考书：“算法设计与分析”周培德机械工业出版社 “算法与数据结构”傅清祥等电子工业出版社 “算法设计和分析”朱洪等上海科技文献出版社十、课程各章节学时分配章节内容总课时讲授课讨论、论文、备注 时实验、设计第1章绪论22 第2章算法复杂性分析44 第3章算法设计方法66 第4章图和网络算法44 第5章计算几何44 第6章概率算法22第7章NP完全性理论及近似66算法第8章新技术综述22习题课22合计32302......大纲撰写人：付晓玲大纲审阅人：刘文萍 责任教授：李也白系（教研室）主任：李也白学院负责人：张常年制（修）定

6、日期：2004年9月1日...