《算法设计课程设计》课程教学大纲（本科）.docx

算法设计课程设计（Curriculum Design of Introduction to Algorithm Design）课程代码：06460037学分：1周数：1周（其中：讲课2学时；设计 学时；上机14学时；答辩 学时）先修课程：程序设计基础、离散数学、算法设计基础适用专业：物联网工程教材：无一、课程性质与目标（一）课程性质算法设计课程设计是必修的实践性教学环节之一，是对前期所学课程基础理论知识的一次 综合应用。它着眼于应用与理论知识的结合，能帮助学生进一步深化理解和灵活掌握教学内容，锻 炼和培养学生融会贯通及将书本知识用于解决实际问题的能力。（二）课程目标I.知识方面课程目标1.1:全面梳理算法设计基础相关的理论知识，进一步深入理解所涉及的逻辑结构、 存储结构等基本概念，熟练掌握不同结构下的算法设计与算法性能分析的方法。课程目标L2：熟悉软件开发的一般过程，初步掌握其中的问题分析、系统设计、程序编码、 测试等基本方法和技能。2 .能力和素质方面课程目标2.1：具备针对工程实际问题利用算法设计基础相关知识进行独立分析和设计的能 力。课程目标2.2：具备针对工程实际问题选用合适的数据结构并设计和实现相应算法的能力。课程目标2.3：具有撰写比较完善的课程设计报告进行论述的能力。（三）课程目标与专业毕业要求指标点的对应关系算法设计课程设计支撑专业培养计划中毕业要求4中的指标点4-2、指标点4-4和指标点4-6o1 .毕业要求4-2：理解工程活动中获取信息的必要性与基本方法，了解本专业的重要资料 来源，且掌握基本的获取技能。2 .毕业要求4-4：针对复杂物联网工程问题，能够基于专业技术与理论，选择合适的研究 路线，设计可行的实验方案。3 .毕业要求4-6：能够采用科学的方法对实验结果进行关联、分析和解释，并通过信息综 合得到有效结论。程目标 毕业要求磊课程目标1.1课程目标1.2课程目标2.1课程目标2.2课程目标2.3毕业要求4-2VV毕业要求4-4VVV毕业要求4-6VV二、内容与进度安排1 .内容及要求选题一校园导游程序内容描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、 简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游 览路径等问题。设计要求：程序采用文本界面或图形界面下进行交互的工作方式，完成如下功能：(1)查询各景点的相关信息；(2)选定某一景点作为起始点，可查询从该景点出发到其余各景点的最佳游览路径。选题二农夫过河内容描述：一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条船，由于船太小，只能装下农夫和 他的一样东西。在无人看管的情况下，狼要吃羊，羊要吃菜，请问农夫如何才能使三样东西平安过 河。设计要求：(1)为农夫过河问题抽象数据模型，体会数据模型在问题求解中的重耍性。(2)设计一个算法求解农夫过河问题，并输出过河方案。(3)分析算法的时间复杂度。选题三哈夫曼编码/译码器内容描述：利用哈夫曼编码进行通信可以提高信道利用率，缩短信息传输时间，降低传输成本。这要求在 发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码，对于全双工信道 （即可以双向传输信息的信道），每端都需要一个完成的编/译码系统。试为这样的信息收发站编写 一个哈夫曼编译码系统。设计要求：（1）初始化：输入一串字符（正文），计算不同字符（包括空格）的数目以及每种字符出现的 频率（以该字符出现的次数作为频率），根据权值建立哈夫曼树，输出每种字符的哈夫曼编码。（2）编码：利用建好的哈夫曼编码，对输入的正文进行编码，并输出。（3）译码：对得到的一串编码，利用哈夫曼编码进行译码，输出正确的正文。选题四几种排序算法的实现和性能比较内容描述：编程实现希尔、快速、堆、归并四种排序算法，并计算每种算法的比较、移动次数。要求待排 序数据从磁盘文件读入，实施排序后将数据写入另一文件。设计要求：（1）实现上述各种排序算法。（2）算法实现中给出每种排序方法从初始开始时的每一趟排序变化情况。（3）分析比较不同数据量大小下（10,50,100,500,1000,5000,10000,15000,20000）,各种算法的时间 性能差异。注：设计选题由任课教师根据学生情况指定选做其中一题即可，题目也可根据实际情况适当安 排。要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实 现等方面加深对课程基本内容的理解和综合运用。2 .进度安排本课程设计为1周，共5天，上机为14学时，学生需在上机前做好准备工作，最后1天为现 场检查时间，每位学生需现场演示并回答老师提出的问题。序号设计内容时间支撑的课程目标1方案设计1天1.1, 2.13程序编写2天1.2, 2.24系统测试1天1.2, 2.25系统演示与汇报1天2.3三、考核与成绩评定1 .考核材料平时考勤情况，预习准备情况，程序实现与演示情况，回答问题情况，课程设计报告、程序。2 .考核要求及权重注：可根据实际情况安排考核内容。考核内容考核要求考核权重备注平时考勤共考勤5次，每缺勤1次扣1分5%预习准备情况根据上机前的准备情况评分25%功能实现与演示根据现场演示功能情况评分50%回答问题根据现场演示对提问问题的回答情况 评分10%课程设计报告根据设计报告格式和内容情况评分10%四、大纲说明1 .学生在本课程设计前应学习了程序设计基础、离散数学、算法设计基础等课程，时 间上可安排在算法设计基础课程学习结束之后。2 .参考文献(1)数据结构(C+),王红梅，清华大学出版社,2011年6月第2版.(2)算法基础：打开算法之门，托马斯H.科尔曼著王宏志译，机械工业出版社，2015年第1 版.(3)数据结构(C语言版)，严蔚敏，清华大学出版社，1997年第1版.(4)数据结构(用面向对象方法与C+语言描述)，殷人昆，清华大学出版社,2007年第2版。2017年 8月 27日附录1课程设计考查内容与评分比重参见下表:考核内容成绩考核要求考核权重指标点平时考勤优秀(90-100)能提前高质量地完成实验任务，实验 过程中无违反纪律行为、表现积极。5%良(80-89)能提前完成实验任务，实验过程中无 违反纪律的行为、表现良好。中(70-79)能按时完成完成实验任务，实验过程 中无违反纪律的行为、表现较好。及格(60-69)能按时完成实验的基本任务，基本无 违反实验纪律的行为。不及格（60分以下）不能按时完成实验任务，或有违反实 验纪律的行为。预习准备情 况优秀(90-100)预习准备内容很充分25%4-2良(80-89)预习准备内容充分中(70-79)预习准备内容较充分及格(60-69)有一定的预习准备内容不及格（60分以下）预习准备内容没有或极少。功能实现与 演示优秀(90-100)实现所有功能，并有所增加；提示很 清晰；演示过程非常熟练；50%4-4良(80-89)实现所有功能；提示清晰；演示过程 熟练；中(70-79)有1个必须实现的功能不完善；提示 较清晰；演示过程熟练程度一般及格(60-69)有2个必须实现的功能不完善；有一 定提示；演示过程不熟练不及格（60分以下）有2个功能未实现；基本没有提示； 无法正常演示；回答问题优秀(90-100)完全正确，回答流利10%4-6良(80-89)正确中(70-79)基本正确及格（60-69）存在错误不及格（60分以下）错误设计报告优秀(90-100)项目齐全，格式清晰，分析过程完整， 设计完善，表达准确10%4-6良(80-89)项目较齐全，格式清晰，分析过程完 整，设计较完善，表达较准确中(70-79)项目较齐全，格式较清晰，分析过程 基本完整，设计基本完善，表达基本 准确及格(60-69)项目不够齐全，格式不够清晰，能表 达出一定的设计过程和思路不及格（60分以下）项目不齐全，格式混乱，不能表达设 计过程和思路附录2课程报告评分细则参见下表:考核内容成绩考核要求指标点课程报告优秀(90-100)报告结构完整，问题、算法及实现过程描述 清楚（图文并茂），有实验结果展示及全面 的分析，并对该实验进行有独到性的改进或 总结；4-4, 4-6良(80-89)报告结构完整，问题、算法及实现过程描述 清楚，有实验结果展示及比较全面的分析， 并对该实验进行总结；中(70-79)报告结构比较完整，问题、算法及实现过程 描述比较清楚，有实验结果展示及简单分 析；及格(60-69)报告结构基本完整，问题、算法及实现过程 描述基本清楚，有实验结果展示；不及格（60分以下）报告结构不完整，问题、算法及实现过程描 述不清楚，缺少实验结果展示，或者不同学 生之间报告类同；