算法设计与分析教学大纲

算法设计与分析教学大纲

 

课程名称：算法设计与分析

英文名称：Algorithm Design and Analysis

课程编号：1204017270

课程性质：专业必修课

先修要求：C语言程序设计或Java语言程序设计、数据结构

适用专业：信息与计算科学及相近专业

任课老师：郭娟、方欢

 

一、教学目标

    通过本课程的理论教学和实验训练，使学生具备以下知识和能力：

目标1：理解算法基本概念，掌握算法时间和空间复杂度分析的基本方法；通过算法的时间复杂度和空间复杂度的分析，衡量算法的优劣；

目标2：掌握集合、线性表、树、二元树、图等基本数据结构，能应用某程序设计语言实现基本数据结构，应用基本数据结构求解特定问题；

目标3：理解递归程序原理，掌握递归编程思想，掌握递归程序的设计和分析方法，掌握简单递归方程求解会求解K阶线性（非）齐次递归方程求解

目标4：了解常见经典算法基本原理，掌握分治法、贪心法、动态规划、周游及检索算法、回溯法和分支限界法求解特点和关键；根据实际问题建立数学模型，并选择适当的方法求解。

 

二、课程教学目标与毕业要求的对应关系

教学目标	毕业要求	支撑强度
目标1	具有利用数学、计算机等自然科学和工程科学的基本原理及软件工程专业知识，能将数理科学、软件工程基础和专业知识运用到信息与计算复杂工程问题的恰当表述之中。能够利用数理科学、计算机科学相关的基础理论和知识以及文献资料对数据进行数值计算，或者对案例进行软件建模，能对软件设计技术进行经济评价，并能对解决方案的合理性进行验证。（毕业要求1，2）	H
目标2	具有利用数学、计算机等自然科学和工程科学的基本原理及软件工程专业知识，能将数理科学、软件工程基础和专业知识运用到信息与计算复杂工程问题的恰当表述之中。（毕业要求1）	H
目标3	能够利用数理科学、计算机科学相关的基础理论和知识以及文献资料对数据进行数值计算，或者对案例进行软件建模，能对软件设计技术进行经济评价，并能对解决方案的合理性进行验证。（毕业要求2）	H
目标4	能通过建模、软件开发等手段进行数值计算和系统软件实现，对相关设计方案进行优化设计，体现创新意识，能够应用数值分析与计算、软件工程的基本原理和方法开发、设计数值计算、软件系统的合理方案，并能够使用图纸、报告或者实物等形式，呈现设计结果。能够基于信息与计算专业理论，根据对象特征，选择合适的研究路线、设计可行的试验方案（毕业要求3，4）	H

备注：H-高度支撑；M-中度支撑；L-一般支撑。

 

三、课程教学主要内容

第一章  导引与基本数据结构（支撑教学目标1、2、3）

    第一节 算法与程序

第二节 分析算法

第三节 用sparks语言表示算法

第四节 基本数据结构

第五节 递归与消去递归

第二章  分治法（支撑教学目标1、3、4）

第一节 一般方法

第二节 二分检索

第三节 找最大和最小元素

第四节 归并分类

第五节 快速分类

第六节 选择问题

第七节 斯特拉森矩阵乘法    

第三章  贪心法（支撑教学目标1、2、4）

第一节 一般方法

第二节 背包问题

第三节 带期限的作业排序

第四节 最有归并模式

第五节 最小生成树

第六节 单源点最短路径

第四章  动态规划（支撑教学目标1、4）

第一节 一般方法

第二节 多段图

第三节 每对节点间的最短路径

第四节 最优二分检索树

第五节 0/1背包问题

第六节 可靠性设计

第七节 货郎担问题

第八节 流水线调度问题    

第五章  基本检索与周游方法（支撑教学目标1、2、4）

第一节 一般方法

第二节 代码最优化

第三节 双连通分图和深度优先检索

第四节 与或图

第五节 对策树

第六章  回溯法（支撑教学目标1、4）

第一节 一般方法

第二节 八皇后问题

第三节 子集和数问题

第四节 图的着色

第五节 哈密顿环

第六节 背包问题

第七章  分支—限界法（支撑教学目标1、4）

    第一节 一般方法

第二节 0/1背包问题    

第三节 货郎担问题

实验课程内容 (支撑教学目标2、3、4)

实验一 基本数据结构的应用----树表示不相交集合

实验二 分类算法

实验三 贪心算法

实验四 检索和周游算法

实验课具体由 算法设计与分析 课程同时执行。

四、建议教学进度

第一章  导引与基本数据结构             学时数 8

第二章  分治法                         学时数 6     

第三章  贪心法                         学时数 8

第四章  动态规划                       学时数 8

第五章  基本检索与周游方法             学时数 6

第六章  回溯法                         学时数 6

第七章  分支—限界法                   学时数 6

算法设计与分析 实验                    学时数 8

五、教学方法

1. 阐述基本原理，理论联系实际，培养学生问题分析；

2. 课堂讲授注意采用启发式教学，激励学生思考；利用投影、幻灯、多媒体课件等教学手段，强化授课效果；

3. 通过案例分析，强化学生算法分析方法的应用、思维方法的建立；

4. 以课堂讲为主，并以实验课、课外作业、生产实习等教学环节作为课程学习的补充，理论教学与实验训练结合，强化基本数据结构的应用及典型算法的应用和程序调试能力的培养。

六、考核方式

闭卷笔试，课程作业

七、成绩评定方法

    笔试成绩70%，平时成绩30%（含课程作业，不包含实验成绩）

八、主要参考书籍

1. 余祥宣，计算机算法基础，华中科技大学出版社，

2. 王晓东，算法设计与分析，电子工业出版社，