“算法设计与分析”课程教学大纲与教学规程.docx

“算法设计与分析”课程教学大纲与教学规程 “算法设计与分析”课程教学大纲和教学规程 1.课程基本信息 课程编号： 课程名称（中文）：算法设计与分析 课程名称（英文）：The design and analysis of algorithms 开课学期： 见培育方案与教学安排 课程类别： 专业基础课程 课程学时数与学分： 56学时（4学分，不含试验课时，4学时/周） 试验学时数与学分： 28学时（学分计算并入计算机科学试验课程，4学时/次/周） 先修课程： 高等数学或数学分析，线性代数或高等代数，概率论与数理统计，离散数学，高级语言程序设计，数据结构 教学形式： 课堂讲授 + 课外教学 + 试验教学（试验课程实行单列） 运用教材： 张德富，算法设计与分析，国防工业出版社，2009,8。 教学参考书： 1 T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms(the second edition)，The MIT Pre，2001 该书国内已引进，见算法导论（其次版）（影印版，中文本），高等教化出版社，2003 2 M.H.Alsuwaiyel，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，1998 M.H.Alsuwaiyel，吴伟昶 等译，算法设计技巧与分析（中文版），电子工业出版社，2004 3 Sartaj Sahni著，汪诗林等译，数据结构、算法与应用-C+语言描述，机械工业出版社，2003 4 王晓东编著，计算机算法设计与分析，电子工业出版社，2005 5 Gilles Braard, Paul Bratley.FUNDAMENTALS OF ALGORITHMICS(算法基础)，清华高校出版社，2005 注：1和2两本书为主要教学参考书。 大纲制定者： 张德富、赵致琢、苏 畅（厦门高校计算机科学系） 大纲审定者： 赵致琢（厦门高校计算机科学系） 2课程性质、类别与任务 “算法设计与分析”是计算机科学与技术专业一门重点专业基础课程，也是学科核心专业基础课程之一，属于必修课程。本课程主要介绍算法的基础学问，包括抽象计算模型、算法基本概念、算法困难性分析基础、算法设计的基本方法、以及算法困难性理论基础。通过本课程的学习，要求学生理解并娴熟驾驭：了解可支持算法运行的抽象机器计算模型，算法的定义和困难性概念，算法设计的基本技术方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法以及高级图论算法等，理解并驾驭算法困难性的分析方法、NP完全性理论基础等计算困难性的基本学问以及完全性证明概要。通过教学和实践，培育学生运用数学工具和方法分析问题和从算法的角度运用数学工具解决问题的基本实力，培育学生设计算法和分析算法困难性的基本实力，训练学生的逻辑思维实力和想象力，从而使他们能够正确地分析和评价一个算法，进一步设计出真正有效或更有效的算法，并使之了解算法理论的基础学问和发展概况。在教学中，激励学生运用算法学问解决各个学科的实际计算问题，培育学生初步的独立开展科研工作的实力和理论联系实践，解决实际问题的实力，同时，为后续课程以及将来的探讨工作供应必要的算法设计与分析的基础。 此外，协作试验课程的教学，学生应理论联系实际，理论指导实践，通过规范地完成一系列算法设计试验进一步巩固所学的相关书本学问，在学问、实力、素养上得到进一步的提高。 3课程教学的基本要求（教学内容和教学重点） “算法设计与分析”内容的重点是各种常用的算法设计方法和困难性分析方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法，以及高级图论算法、时空困难性的分析方法、NP完全性理论基础。课程教学的基本要求是通过教学活动，使每一个学生较好地驾驭课程的主要内容，同时具备对实际问题应用所学学问设计出有效算法并编程实现这些算法的实力。课程的教学内容主要包括如下学问点，其中，属于重点的内容用黑体标示，今后教学改革拟增加的内容用“”标示，部分非重要内容用括弧标注为“一般了解”： 基本概念：问题; 抽象计算模型；算法的概念；算法正确性;算法效率；问题下界 算法的评估：时间困难性和空间困难性分析；算法的最优、最差和平均效率；渐近困难性符号和基本效率类型；非递归算法的数学分析；概率分析（一般了解）；分摊分析（一般了解）；算法的阅历分析；算法可视计算方法； 递归：递归设计；递归算法转非递归算法；递归算法的设计实例；递归算法的数学分析，三种求解递归方程的方法； 分治法：分治法的基本思想；分治法设计的特点；分治法的时间困难性；分治法的应用（大整数乘法和Straen矩阵乘法；棋盘覆盖）； 基本的排序算法及其困难性分析：插入排序；堆排序；快速排序；排序算法困难度分析及其比较（此处的教学重点在于算法分析，透过算法分析从中深化了解算法的特性，进一步揭示设计更为有效的算法的思路和途径）； 动态规划方法：动态规划的基本要素（含最优性原理）；矩阵连乘问题；0/1背包问题；装配线的调度问题；最长公共子序列； 贪心算法：贪心算法的基本要素；背包问题；哈夫曼编码；活动选择问题；贪心算法的理论基础（一般了解）； 回溯法：回溯法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；n皇后问题；子集合问题；回溯法的效率分析； 分支限界法（分支定界法）：分支限界算法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；分支限界法的效率分析； 网络与高级图论算法：最短路径问题（Prim算法；Kruskal算法；Dijkstra算法；Warshall算法和Floyd算法）；最大流问题（Ford-Fulkerson标号算法等）；最小费用最大流问题（最小费用算法等）；匹配问题及其求解算法； 问题的困难性：NP完全性理论基础（P类与NP类问题，NP完全性问题及其归约；NP完全性证明；典型的NP完全问题）； 如何求算法困难性的下界（一般了解）。 4关于教学目标、教学内容的建议和教学过程中应当留意的事项 算法设计与分析是计算机科学的核心问题之一。由于计算机科学与技术的大多数探讨都与算法紧密相关，因此，高起点的算法理论基础逐步成为了高素养计算机科学与技术特地人才应当具备的必要的理论修养。设计算法的目的是要解决大量实际问题，对于较困难的问题要求能设计出有效的算法。大量的探讨实践表明，一个问题求解质量和效率的凹凸，主要取决于算法设计的质量。因此，算法设计与分析的重点是驾驭算法的概念和基础理论，运用数学工具分析问题，从计算方法的角度如何给出非数值计算问题的计算方法、采纳算法设计的常用方法设计算法，驾驭分析和估计算法困难性的方法，并特殊留意以下几点： 第一，在介绍算法的基本概念时，应当着重介绍计算模型、算法的概念、考察算法的角度和算法评估的标准、困难性分析的方法以及算法探讨的目标与实际问题的关系； 2 其次，在介绍一些数据结构已经学习过的排序算法时，不应过多强调算法设计，而应当重点结合算法分析技术，用分析的方法评价算法的优劣，从分析结果得到设计更优算法的启示。在介绍高级的数据结构时，重点应放在对数据结构的困难性分析上； 第三，在介绍算法设计的基本方法（例如分治法、贪心法、动态规划方法、回溯法与分支限界法）时，应当通过对大量经典问题的算法设计与分析，使学生渐渐驾驭算法设计与分析的技巧，并特殊留意各种算法的比较分析。例如，递归与分治、贪心与动态规划、回溯与分支限界； 第四，在介绍NP完全性理论时，应当着重从问题的分类以及各类问题的性质、相互关系入手进行探讨，揭示问题的本质，从而为算法的设计供应方法指导。另外，应当着重驾驭问题的转化及NP完全性理论的有关证明思想； 第五，在介绍线性规划问题及其相应算法时，应当着重介绍该算法的应用； 第六，激励老师将自己的探讨或最新算法设计与分析的思想，结合到教学过程之中，激励和帮助学生运用所学的学问去解决实际问题，驾驭理论与实践相结合的思想方法。 第七，激励老师结合学科范型（也称范式），将学科方法论的内容融入教学过程之中（对老师暂不作基本要求），以帮助学生建立与“算法设计与分析”课程内容相关的科学的思想方法。 5课外教学要求 本课程的课外教学内容和形式主要由学生阅读经典教材，任课老师辅导、答疑、批改作业、实践环节等几部分构成。本课程要求学生在有时间的状况下，尽可能完成教材中全部的习题。学生应在任课老师的帮助下，仔细听课，反复思索，大量完成作业，在学习中反复进行阅读、思索、做习题，通过阅读、思索、做习题、分析、联想、概括、归纳、总结等多种有效的方式方法，比较全面、精确地驾驭课程的主要内容和教学重点。 任课老师（包括助教）每周支配1次辅导、答疑，每次2小时。每次辅导、答疑至少应有一位老师参与，一般不得合并执行。主讲老师应批改全班学生作业量的5%，参与辅导、答疑的次数不少于总次数的1/5，以驾驭教学的效果，调控教学进度。 课程对学生作业的质量要求是：正确、简洁、规范。 要求做题正确，意味着学生必需驾驭基本概念、基本原理、基本方法、基本技术等课程的基本学问，基本学问不驾驭，就很难正确解答问题，这是对学生学问水平和解决问题实力的考核。要求做题简洁和规范，意味着在正确解题的状况下，不应当存在“拖泥带水”和“东拉西扯”的问题，书面表达简练、规范，与教材中例题求解的表述基本一样。这些，正反映出学生在这方面训练有素，这是对学生素养的考核。 6课程的试验教学 试验课程将支配一些有代表性的上机试验单元与本课程相呼应，目的是通过试验让学生体会理论与实践高度统一的学科特点，进一步相识理论、抽象、算法设计等三个过程及其相互关系，形成对学科范型更深化的体会和相识。它要求学生从分析问题动身，利用所学的算法设计技术去解决某一实际问题。通过试验工作，借助程序设计语言，驾驭运用数据结构、算法和程序解决一些实际问题的方法。 学生应根据理论联系实际，理论指导实践的要求，在实际操作中规范地完成各项试验。通过试验工作，借助程序设计语言，设计并实现算法，进一步驾驭运用数学工具，分析问题，提出求解方法，设计算法，分析算法的困难性，对算法进行科学的评价等方面得到严格的训练。 试验教学根据试验单元进行，一个试验单元完成后或相近内容的一组试验单元完成后，每一个学生要撰写和提交试验报告。任课老师应依据每一个学生的试验报告和完成试验的状况，在学期结束时给出学生该门课程的学术评语和成果，并与四个学年全部试验课程评语一起，最终产生对学生的实践实力作出综合评定的学术评语与成果。学术评语应着重从发展的眼光和视角，考察学生是否能够理论联系实际，理论指导实践，根据试验课程的教学要求，规范地完成试验单元，较好或基本驾驭了试验教学的内容。 3 在试验课程单列之前，课程的实践环节拟支配28学时（实际执行7次共7*4=28学时），教学内容由大纲确定，试验课程单列之后，试验考核成果单独计算，不计入课程考核成果。各试验单元和内容如下： 试验单元一：用贪心法求解一个详细问题的试验（程序实现）； 试验单元二：用动态规划方法求解一个详细问题的试验（程序实现）； 试验单元二：用回溯法求解一个详细问题的试验（程序实现）； 试验单元四：用分支限界法求解一个详细问题的试验（程序实现）； 试验单元五：用高级图论算法求解一个详细问题的试验（程序实现）。 上述五个试验完成后，每个学生应提交二个试验报告。前三个试验完成后提交一个试验报告，后两个试验完成后，提交一个试验报告。 7考核的方式方法 课程结束考核方式： 闭卷考试 课堂考试时间： 3小时（180分钟） 考试命题： 任课老师命题，教研室分管该课程的负责人和分管教学的系副主任审题； 课程考试的命题内容要从大纲的要求动身，围绕本课程的教学内容、学问点和教学要求，着重从学问、实力、素养三个方面对学生进行全面的考核，重点考核学生运用学问解决问题的实力，同时考察学生的综合素养。考核范围为除了最终一周教学的内容外，其他大纲确定的学问点都在考试范围之内，课程考试的试卷命题范围不得免除期中考试已经考过的内容。试卷中不少于85%的内容应来自课程重点内容的范围，不少于10%的内容应来自课程非重点内容的范围，要求学生全面复习，以达到系统驾驭，全面考核的目的。试卷的题型要力戒避开文科标准化试卷的题型，避开出现简洁概念问答题和简答题。试卷题目数量一般为 5、 6、7题，以优秀学生在全部会做的状况下正常书写速度能够在120分钟内完成为宜。 试卷题目数量的削减与全面考核的目的并不冲突。由于考核的范围是明确的，只要老师不透露题型和范围，学生就必需全面复习，这样，即使题目不覆盖某些教学内容，也不会影响实际的教学效果。 随堂监考授权： 主讲老师和助教 期中考试： 由任课老师确定是否支配期中考试，主要用于检查教学状况。 最终成果计算方法： 期终考试成果80%+ 平常成果20% “算法设计与分析”课程教学大纲与教学规程 数据结构与算法课程教学大纲 数据结构与算法课程设计教学大纲 算法与数据结构教学大纲 数据结构与算法教学大纲 课程与教学论教学大纲 系统设计与UML课程教学大纲 建筑原理与设计课程教学大纲 网页设计与制作课程教学大纲 文字与版式设计课程教学大纲与教案 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第13页 共13页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页第 13 页 共 13 页