算法分析与设计教学大纲

算法分析与设计课程（本科）教学大纲一、课程编号二、课程类别：选修课三、先修课程：程序设计、数据结构四、适用专业：计算机科学与技术，信息安全五、课程学分/学时： 2.5学分/40学时六、课程的性质与任务：计算机科学是一种创造性思维活动，其教育必须面向设计。

计算机算法分析与设计是面向设计的，因此，它是计算机科学和计算机应用的核心。

无论是计算机系统、系统软件和解决计算机的各种应用课题都可归结为算法的设计。

通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的精确的描述：分治法、贪心法、动态规划、回溯法等。

并掌握算法分析的方法。

从而将学生分析问题和解决问题的能力提高到高层理论的高度。

七、教学主要内容及学时分配(一）、引论（4学时）1.算法的定义及其特点2.算法分析的方法(二）、分治法（8学时）1.分治法的思想2.二分检索、归并分类法、快速分类法及其它们的算法分析3.Strassen矩阵乘法4.其他问题(三）、贪心方法（6学时）1.贪心方法的思想2.背包问题、最小生成树、单源最短路径问题3.其他问题(四）、动态规划（6学时）1.动态规划的思想2.多段图、每队节点之间的最短路径、0/1背包问题和货郎担问题3.其他问题(五）、基本检索与周游方法（4学时）1.二元树周游、树周游、图的检索和周游的一般方法(六）、回溯法（6学时）1.回溯法的思想2.8-皇后问题、背包问题3.以上算法的算法分析4.其他问题(七）、N P难度和NP完全问题（2学时）1.NP难度和NP完全概念(八）、其他有关方法简介（4学时）1.常见概率算法2.并行算法基本概念3.其它相关知识八、教学基本要求(一）、掌握算法的定义及其特点；掌握算法分析的方法。

(二）、掌握分治法的思想；重点掌握二分检索、归并分类法、快速分类法及其它们的算法分析；了解Strassen矩阵乘法。

(三）、掌握贪心方法的思想；理解背包问题、最小生成树、单源最短路径问题；理解以上算法的算法分析。

课程代码：《算法分析设计》课程实验教学大纲【编写】朱少林【审核】【课程类别】专业选修【课程学时】 34【开课学期】【实验学时】 16 - 34【授课专业】电子商务/信息管理/计算机科学与技术一、实验教学任务和目的无论是在计算机科学与技术的研究中，还是在计算机应用（包括管理信息系统和电子商务系统开发）中，都涉及大量的程序设计问题，而且随着研究和应用的深入，所遇到的问题越来复杂，对处理问题的效率要求也越来越高，了解和掌握求解问题的方法（算法）、设计出好的算法也就成为解决这些问题的关键，甚至成为其决定因素。

《算法分析与设计》课程的主要内容是讲授在计算机科学研究和应用中经常用到的一些算法，包括分枝法、贪心法、动态规划法、回溯法等，介绍这些算法设计的思路和算法的一般框架，并针对多个具体的应用问题设计出了相应算法。

其目的就是让学过该课程的学生掌握算法设计的基本思想和技巧，掌握几个基本和常用的算法。

《算法分析与设计》是一门实践性很强的课程，课程教学过程中，需要与课程实验相结合。

算法分析与设计实验的主要任务是针对给定的问题，设计出一个合适的算法或几个可供选择的算法，然后将算法用合适的程序设计语言实现并上机调试，并用合适的数据验证运行。

只有通过实验，通过让学生进行算法设计和编程实践并上机验证，才能让学生理解算法的思想，掌握算法设计的方法和掌握算法的精髓。

同时，通过算法实验，让学生掌握调试程序、改进算法的方法，学会通过对比选择最适合问题求解算法的方法；使学生将以前所学如《C语言程序设计》、《数据结构》等课程知识能有机结合并融会贯通；进一步培养学生的分析问题、解决问题的能力，提高学生素质，使其能更好地适应社会，满足社会对人才的需求。

二、实验教学基本要求1．程序设计语言与实验要求算法实验需要将算法转换成程序并上机验证，实验的主要工作是验证算法的正确性并测试算法的时空复杂度。

学生可以根据自己的喜好或对程序设计语言的掌握程度选择一个程序设计语言，如C/C++、PASSCAL等支持递归程序设计的语言，实验硬件环境要求是支持学生选定程序设计语言的计算机系统，（包含打印机更佳），学生应能熟练掌握计算机系统的使用，并具备熟练编写、输入和调试程序的能力。

《算法设计与分析》课程实验教学大纲Design and Analysis of Computer Algorithm总学时 16 总学分 0.5 实验学时 16一、基本情况1. 课程性质：专业实践2. 设课方式：独立设课3. 适用专业：计算机科学与技术专业4. 开课学期：第5学期5. 实验教材：《算法设计与分析》实验指导书6. 先修课程：高级语言程序设计、离散数学、数据结构二、课程简介算法设计与分析实验将覆盖计算机软件实现中的大部分算法，具有一定的深度和广度，目的是让学生掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略来分析、解决实际问题并编程实现。

同时，算法设计与分析实验是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。

通过理论联系实际，最终提高学生动手操作的能力以及分析问题和解决问题的能力，培养对算法的复杂性进行分析的逻辑思维能力。

三、实验目的与任务实验是教学内容的重要一环，其目的一方面是为了让学生掌握算法设计与分析中的一些常用的典型的算法设计思想和方法；另一方面是为了让学生切实掌握各种算法的具体实现方法，培养学生的实际动手能力，加强学生创新思维能力的培养。

四、课程的基本要求（1）了解实验目的，熟悉实验环境。

（2）预习实验，准备好实验题目和操作步骤。

（3）能编译调试源程序,分析错误原因并加以修改,得出正确结果。

（4）能运用所学的知识正确分析程序得出的结果，并能给出改进的方案。

（5）将上述各项要求及实验结果编写成实验报告。

实验前学生要认真预习实验内容，按要求编写源程序及准备测试数据。

实验中,要按操作规程操作计算机，集中精力调试程序,并认真测试实验数据。

对实验程序的故障应自行分析解决，不拷贝其它人的成果。

对实验得出的结果能加以分析，提出改进的具体措施。

掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略分析问题、解决实际问题并编程实现。

算法设计与分析教学大纲课程概述算法设计与分析是计算机专业的核心课程。

学习该课程对学习其他专业课奠定了扎实的基础，也对培养计算思维和求解问题的能力起到重要作用。

面对各个应用领域的大量实际问题，最重要的是分析问题的性质并选择正确的求解思路，即找到一个好的算法。

特别是在当今复杂、海量信息的大数据处理中，一个好的算法往往起到决定性的作用。

本课程注重针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。

课程主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。

本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程"算法设计与分析（高级）"中加以介绍。

课程的内容分成两大部分：算法的基础知识和通用算法设计技术与分析方法。

算法基础知识部分主要介绍算法相关的基本概念和数学基础。

比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。

通用算法设计技术与分析方法部分主要介绍分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术。

重点介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。

授课目标本课程从算法复杂性分析的基本方法和原理入手，以讲授算法设计的基本方法和原理、算法优化的基本方法和技巧为主，通过典型的问题及其相应的求解算法，以及算法复杂性的分析，达到完善学生的知识体系、培养学生的分析能力、拓展学生的思维方法，并鼓励学生把理论与实践相结合。

课程大纲01第一周基础知识（1）算法的基本概念及伪码描述，函数的渐近的界。

课时1.1 本周教学内容简介1.2 算法设计的两个例子1.3 问题的计算复杂度：排序问题1.4 货郎问题与计算复杂性1.5 算法及其时间复杂度1.6 算法的伪码表示1.7 函数的渐近的界1.8 有关函数渐近的界的定理1.9 几类重要函数02第二周基础知识（2）序列求和方法，递推方程求解。

算法设计与分析一、课程说明课程编号：130211Z10课程名称：算法设计与分析/Algorithm Design and Analysis课程类别：专业课学时/学分：48/3先修课程：数据结构、组合数学与图论、概率论、数理统计、程序设计基础适用专业：信息科学教材、教学参考书：1.《算法设计与分析基础》（第3版）Anany Levitin 著，潘彦译，清华大学出版社，20152.《算法设计技巧与分析》，M.H.Alsuwaiyel著，吴伟昶，方世昌等译，电子工业出版社，2005年3.《Introduction To Algorithms》（Second Edition），T.H.Cormen、C.E.Leiserson、R..L.Rivest and C.Stein，The MIT Press，20014.《计算机算法基础》（第二版），余祥宣、崔国华、邹海明，华中理工大学出版社，2003年。

二、课程设置的目的意义《算法设计与分析》是信息科学、计算机科学相关专业高年级本科生、研究生的一门重要专业基础课程。

通过本课程的学习，学生可以了解计算机应用中的各种常用算法，掌握设计和分析各种算法的基本原理、方法和技巧。

能运用所学到的知识熟练地分析各种算法并能指出解决同一问题的各种算法的好坏。

三、课程的基本要求知识要求：○1了解计算机应用中的各种常用算法。

○2了解评价算法的准则和方法。

○3掌握设计和分析算法的基本原理、方法和技巧。

○4用编程语言实现基本算法。

○5实际问题能够设计合理的算法并加以实现。

能力要求：○1培养学生利用算法设计的基本方法和理论等分析问题和解决实际问题的能力。

○2通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。

素质要求：○1使学生在解决实际问题、处理实际数据、进行编程时具备把算法设计的基本方法和理论用于实际应用的思想。

○2培养学生对算法美的认识，运用不同的算法也许都能够得到正确的结果，好的算法是有数学美的。