· 学校主页    · 学院主页

《算法设计与分析》

发布时间:2011-03-17  浏览次数:3587

 

算法设计与分析

 

 

 

一、课程基本信息
课程编号:0606512
课程中文名称:算法设计与分析
课程英文名称:Design and Analysis of Algorithms
课程性质:专业主干课
考核方式:考查
开课专业:计算机科学与技术、软件工程、保密与信息安全
开课学期:5
总学时:40(其中理论32学时,上机8学时)
总学分:2

授课教师潘海为韩启龙谢晓芹   马志强 张可佳


二、课程目的和任务
计算机算法设计与分析是计算机软件与理论、计算机应用技术专业的专业理论课程,它是计算机算法和软件的基础。算法设计与分析是高年级学生的重要专业课程,本课程的目的在于引导学生使用抽象思维的方式和规范化语言来描述客观世界中的计算问题,学会设计算法且分析算法的时间复杂性与空间复杂性,利用计算机编制程序解决问题的能力。
课程的教学任务是通过授课和实验的方式使学生掌握计算机算法的基本知识,包括问题的抽象和描述、程序设计的基本内容、方法和准则;算法分析的基本概念和基本理论,一些具体算法的复杂性分析;算法设计的基本方法、技术和分析方法;经典数值计算问题、递归与分治、动态规划、贪心法、回溯法、分支限界法和线性规划等解决问题的方法。

三、教学基本要求(含素质教育与创新能力培养的要求)
1.对算法、程序及其复杂性的分析方法有清楚的认识,建立起清晰的概念。
2.掌握算法及其复杂性分析方法的有关数学基础知识。
3.掌握经典问题及其解决算法的设计和分析方法等知识。
4.通过课程学习,提高学生的利用计算机这个工具解决实际问题的能力。
5.通过课程学习,使学生将对计算机程序设计的基本概念和并行化、网络化及智能化的算法有一个较为全面和系统的认识,形成分析、归纳和解决问题的抽象思维并且具有实际编程的能力。

四、教学内容与学时分配

第一章  算法概述(4学时)

介绍本课的学习目的,讲解算法复杂度分析的含义和复杂度计算的技巧,介绍相关表示法的定义、用途和用法,学会比较函数间的规模关系。

第二章  递归与分治(7学时)

掌握求解递归中猜测和证明的技巧,介绍分治方法求解问题的思想,介绍大整数乘法、矩阵乘法、二分搜索技术、线性时间选择、最接近点对等经典例子。

第三章  动态规划(6学时)

介绍动态规划算法在提高递归算法效率是的应用条件:最优子结构和重复子问题,并介绍最长公共子序列、凸多边形最优三角剖分、0-1背包、矩阵乘法、最优二叉搜索等经典例子。

第四章  贪心算法(6学时)

主要介绍贪心算法局部最优到全局最优的贪心选择性和最优子结构性质,介绍活动安排、最优装载、哈夫曼编码、单源最短路径等经典实例。

第五章  回溯算法(5学时)

介绍解空间的概念,理解回溯法系统搜索解空间的思想和算法平均效率高的原因,掌握两种回溯方法和深度优先搜索策略,并介绍装载问题、批处理作业调度、n后问题、0-1背包问题、m着色问题、旅行商问题等经典例子。

第六章       分支界限法(4学时)

介绍分支界限法利用求解最优化问题的本质原因,掌握掌握两种分支界限方法和广度优先队列搜索技巧,介绍单源最短路径问题、装载问题、0-1背包问题、旅行商问题等经典实例。

五、教学方法及手段(含现代化教学手段)
教学方法包括理论讲解、上机实习、学生自学和教师与学生互动的方式,通过平时测验和期末考试了解学生对课程知识掌握的。

六、实验(或)上机内容
 

实验一:分治方法上机实验。上机时数4学时,分2次上机每次2学时。

1次上机实验的内容:用分治思想设计实现二分搜索算法和快速排序算法,并且用不同数据量进行实验对比分析,要求分析算法的时间复杂性并且形成分析报告;

2次上机实验的内容:在快速排序算法基础上,进一步完成线性时间选择算法,并且用不同数据量进行实验对比分析,要求分析算法的时间复杂性并且形成分析报告;

实验二:动态规划算法与贪心算法的上机实验。上机时数4学时。

上机实验的内容:用动态规划思想设计实现最长公共子序列问题,0-1背包问题, 用贪心思想设计实现活动安排问题,背包问题,并且用不同数据量进行实验对比分析,要求分析算法的时间复杂性并且形成分析报告;

 七、教材及主要参考资料


 
教材:

许少华,富宇,潘海为,邱兆文,算法设计与分析,哈尔滨工业大学,2011年;

参考资料:
1. 王晓东,计算机算法设计与分析(第2版),北京:电子工业出版社,2006年;

2.傅请祥等,算法与数据结构,北京:电子工业出版社,2000年

3.A.V.AHO等, The Design and Analysis of Computer Algorithms,2000。

八,课程资料下载
第1讲

第2讲

第3,4讲

第5,6讲

第7,8讲

第9,10讲

第11,12讲

第13,14讲

第15,16讲

 

 

 

© 2017哈尔滨工程大学计算机科学与技术学院
地址:哈尔滨市南岗区南通大街145号哈尔滨工程大学21号楼 邮编:150001 电话:0451-82519406
管理维护:智能信息处理研究中心 技术支持:信息化处