2022~2023学年第1学期 《程序设计、算法与数据结构（三）》课程教学实施方案 一、课程概况 【课程名称】程序设计、算法与数据结构（三） 【课程性质】专业基础课、必修课 【教学对象】计算机类专业2021级学生 【层　　次】四年制大二本科生 【教学总学时】 48学时 【前修课程】 《程序设计、算法与数据结构（一）》、《程序设计、算法与数据结构（二）》 【后修课程】《离散结构》、《数据库原理与技术》、《Java程序设计》 二、教学地位与作用及主要教学目的 《程序设计、算法与数据结构（三）》是“问题求解”能力培养课程群最后一个阶段的课程。本课程致力于培养计算机类专业学生基本学科能力，包括计算思维能力、算法设计与分析能力、程序设计与实现能力和系统能力。通过课程学习，学生具备使用蛮力法、动态规划法、贪心法、回溯法、分支限界法等算法设计能力进行具体问题的分析、建模、求解的能力，为复杂工程问题求解打下坚实的基础。 三、课程选用教材 【使用教材】 《算法设计与问题求解》主编：邓泽林、李峰. 清华大学出版社. 2022年8月 　 【选用依据】 本书是全国高等学校计算机教育研究会“十四五”规划教材，具有如下特色： （1）注重经典算法设计与分析的知识传递，特别是对算法执行过程进行了详细的描述，使读者清晰掌握算法执行过程； （2）注重学生计算思维能力、问题求解能力的培养，在经典知识的基础上增加了能力拓展，及时引导读者将经典算法应用于问题求解； （3）配套例题及习题挑战度较高，符合国家级一流本科课程“两性一度”的要求，方便教师组织学生开展问题求解实践、分组研讨等，提高学生的问题求解能力； （4）提供了微课视频，注意引导学生开展自主学习。 【参考教材】 [1] 王红梅、胡明编《算法分析与设计（第2版）》北京 清华大学大学出版社，2017 [2] 王晓东编. 计算机算法设计与分析 (第三版)[M].北京：电子工业出版社，2011. [2] Thomas H.Cormen、Charles E.Leiserson等编.算法导论[M]. 北京：机械工业出版社，2006. [3] [美]Mark Allen Weiss编. 数据结构与算法分析[M]. 北京：人民邮电出版社，2007. [4] 陈慧南编，算法设计与分析：C++语言描述（第2版） [M].北京：电子工业出版社，2012. 四、教学手段和方法 1、本课程以计算机投影教学及上机练习方式完成。其中48学时全部为理论课学时，另外专门配有46学时的上机课。在讲授过程中，考虑到该课程注重动手、注重应用的特点，遵循深入浅出的原则，结合教材及教学大纲制作合适课堂教学的课件，以灵活生动的方式讲述本课程的全部内容。 五、教学特点 1、为了进一步的树立学生程序设计的思维，增高学生程序设计的能力，采用课前预习、课堂讲授、反转课堂、课后OJ刷题等手段，切实保证教学效果。 2、课前预习作业提交在学宝上完成，课后刷题在OJ上完成，课堂讲授主要由授课教师完成，反转课堂主要由学生完成，使学生从被动学习变为主动学习。 六、各章节教学重点与难点 【各章节教学重点与难点】（重点用★表示，难点用☆表示） 第1章 引言 1.1　概述 1.2　算法的基本概念、算法的描述方法 1.3　算法的时间复杂性分析(★☆) 第2章 递归算法设计 2.1　递归概述、递归算法设计思想 2.2　递归转非递归(★) 第3章 蛮力法 3.1 蛮力法的设计思想 3.2 查找问题、串匹配问题 3.3 选择排序、起泡排序(★☆) 3.4 0/1背包问题 3.5 矩形个数问题(★☆) 第四章 分治法 4.1 分治法的主要设计思想 4.2 最大子段和问题(★) 4.3归并排序(★) 4.4 棋盘覆盖问题(★) 4.5最近点对问题 4.6 凸包问题 第五章 回溯法 5.1 回溯法的概念 5.2 解0/1背包问题(★) 5.3 N皇后问题(★☆) 5.4 图的m-着色问题(★) 5.5 批处理作业问题(★☆) 5.6 迷宫问题 第六章 贪心法 6.1 贪心法的概念 6.2 部分背包问题(★) 6.3 最优装载问题 6.4 旅行商问题(★☆) 6.5 过河问题(★☆) 第7章 分支限界法 7.1 分支限界法的概念 7.2 多段图问题(★) 7.3 旅行商问题(★) 7.4 作业调度问题(★) 7.5 大富翁游戏(★) 7.6 最优装载问题(☆) 第8章　动态规划法 8.1　动态规划法的概念 8.2　解0/1背包问题(★) 8.3　最大子段和问题(★) 8.4　字符串相似度问题(★☆) 8.5　带通配符的字符串匹配(★) 第9章　图算法 9.1　图的定义与相关概念 9.2　最短路问题(★) 9.3　网络最大流问题(★) 9.4　二分图的求解方法(★☆) 第10章　计算几何 10.1　向量、点积、叉积 10.2　计算多边形面积(★) 10.3　点到直线的距离(★) 10.4　判断线段是否相(★☆) 10.5　凸包问题(★☆) 第11章　计算复杂性理论 11.1　问题的复杂性分类 11.2　可计算问题与不可计算问题(★) 11.3　P类问题和NP类问题(★) 【难点及解决办法】 采用课前预习、课堂讲授、反转课堂、课后刷题，讲授课程的重点和难点。 七、教学进度 该课程教学总学时为48学时。教学安排按照一学期8周进行，平均每周4学时。实验由专门的《程序设计、算法与数据结构（三）》实验课来完成。具体学时分配如表1所示。 表1 《程序设计、算法与数据结构（三）》教学学时分配 教学内容 总 学 时 其 中 课外辅导/课外实践 备注 讲课 实 验 上 机 其 他 第一章 2 第二章 4 第三章 4 第四章 4 第五章 4 第六章 4 第七章 6 第八章 8 第九章 4 第十章 4 第十一章 2 总复习 2 总计 48 八、教学辅导与测试 关于答疑：每周星期二 安排一次集中答疑，答疑地点：7教601。 关于作业：每章布置作业，作业内容与形式及测评方式根据教学大纲及教材内容确定。 关于测试 ：本课程为考试课程，成绩考核方法： 1、平时成绩占总成绩60%：40%课前预习（学宝评分）+20%翻转课堂（上课教师根据学生反转课堂表现给分）。 2、闭卷机试，考试成绩占总成绩40% 九、教学意见反馈 1、学生可以直接将教学反馈在QQ群中。 2、任课教师联系电话： 电话：0731-85258448 电子邮箱：lf@csust.edu.cn 2022年9月