一、教学目的与基本要求
本课程主要采取教师课堂讲授,学生课后自学的形式,并辅以适量的上机操作练习,本课程是关于算法的方法论,是计算机软件设计的基础。主要讲授算法设计技术与分析技术。通过学习该课程,可以系统掌握算法设计、分析与证明的常用方法,培养算法设计与复杂性分析以及相应的解决问题的综合素质和能力。因此,该课程对于培养高质量计算机人才所必需的基本理论与知识、抽象思维能力、逻辑思维能力以及灵活运用算法解决问题的能力都有极大的帮助。对于未来从事计算机系统结构、系统软件以及应用软件研究与开发的专业人员是非常重要和必不可少的。
本课程介绍了python编程基础知识,双指针问题,哈希算法,深度优先遍历,广度优先遍历,回溯算法,贪心算法,动态规划算法,最短路径问题,分治算法等。
三、实验方法、特点与基本要求
要求掌握每次实验目的,达到对应的实验要求,能够独立完成规定的实践任务。通过对理论知识的了解的基础上来进行各实验,完成实验要求,从而巩固书本知识。
四、主要仪器设备
微机+windows操作系统+pycharm
五、实验项目的设置与内容提要
序号 |
实 验 项 目 |
主 要 内 容 |
学时 |
实验类型 |
每组人数 |
要求 |
教学目标 |
1 |
双指针 |
1、熟悉双指针在遍历数组中的应用。 2、熟练掌握双指针算法及其算法复杂度分析,了解利用双指针解决计算问题。
|
2 |
验证
|
1 |
|
了解 |
2 |
深度优先和广度优先遍历 |
1、熟练掌握图上广度优先搜索算法及其算法复杂度分析,了解利用广度优先搜索解决计算问题的建模过程。 2、熟练掌握图上深度优先搜索算法及其算法复杂度分析,了解深度优先算法的建模过程。
|
4 |
验证
|
1 |
|
掌握 |
3 |
回溯法 |
1、利用回溯法求对称的旅行商问题(TSP问题) |
2 |
验证 |
1 |
|
熟悉 |
4 |
贪心算法 |
1、了解贪心算法求解优化问题的过程 2、熟练掌握利用贪心算法求解典型的计算问题,如硬币找零、间隔任务规划等问题。了解利用替换法证明贪心策略是否能获得全局最优解的过程。 3、熟练掌握贪心算法在两个典型图搜索中的应用,即单源最短路径和最小生成树算法中,利用合理的数据结构优化算法复杂度的技巧。 |
2 |
验证 |
1 |
|
掌握 |
5 |
动态规划法 |
1、理解动态规划求解优化问题的典型步骤,以及动态规划算法求解计算问题的时间复杂度分析 2、熟练掌握利用动态规划算法求解一维、二维等典型优化问题,如斐波那锲数、拾捡硬币、连续子序列的最大值、矩阵的括号、0-1背包问题等。 |
4 |
验证 |
1 |
|
掌握 |
6 |
分治法 |
1、利用分治法编写归并,快速排序算法 2、分治算法程序分析与调试
|
2 |
验证 |
1 |
|
掌握 |
实验报告按照实验项目任选六个,按照要求的格式进行书写,并在规定时间内进行提交。
七、考核方式与成绩评定
1.实验考核内容:
(1)实验课出勤情况,必选实验课学生必须参加实验。
(2)积极主动认真做实验。
(3)实验方案过程结果要正确。
2.成绩评定标准:
优秀:实验中认真操作,实验报告独立完成,字迹工整,实验步骤清晰,数据处理及计算正确,有实验分析和总结(特别是总结出实验中出现的问题及解决的方法等);对实验过程自己设计的 ,实验步骤自己编写的,只要无根本性错误。
良好:实验中认真操作,实验报告独立完成,字迹工整,实验步骤清晰,数据处理及计算无根本错误。
中等:实验中认真操作,实验报告独立完成,实验步骤清晰,数据处理及计算无根本错误。
及格:实验中基本能认真操作,实验报告按标准格式独立完成,数据处理及计算无根本错误。
不及格:实验中不认真操作,实验报告不完成,抄袭实验报告,字迹潦草,数据处理及计算错误等。
八、推荐教材和教学参考书目与文献
《python算法设计与分析》王硕.北京.人民邮电出版社. 2020.05
参考书目与文献:《python算法详解》张玲玲编著.北京. 人民邮电出版社. 2019.6
大纲制订人:徐慧
大纲审定人:
教学院长(主任):
制订日期:2021年 3月 2 日