《《算法设计与分析》课程设计教学大纲》由会员分享，可在线阅读，更多相关《《算法设计与分析》课程设计教学大纲（4页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析课程设计教学大纲算法设计与分析课程设计教学大纲课程代码：课程代码：1011510210115102课程名称：算法设计与分析课程名称：算法设计与分析课程设计学时：课程设计学时：1 1 周周学分：学分：1 1 学分学分适应专业：；软件工程适应专业：；软件工程( (本科本科) )执笔人：银星执笔人：银星编写日期：编写日期：20072007 年年 8 8 月月一、课程设计的教学目的和任务一、课程设计的教学目的和任务通过本课程设计教学所要达到的目的是：培养学生用学到的书本知识解决 实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工 程上能力的技术，规范地开发大型、复杂、高
2、质量的应用软件和系统软件具有 关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基 本技能和科学作风方面受到比较系统和严格的训练。 本课程设计的任务是：学生应该根据所选题目完成方案设计、程序设计和 调试等任务，并完成相关文档的撰写。二、课程设计的内容和基本要求 利用算法设计与分析课程中所学到的编程知识和编程技巧，完成具有 一定难度和工作量的程序设计题目，帮助学生掌握编程、调试的基本技能，独 立完成所布置的任务。 课程设计的题目可由指导教师根据具体情况和大刚的要求来确定，参考题 目： 题目一,棋牌游戏设计 五子棋; 象棋; 围棋; 军棋; 跳棋; 24 点; 斗地主等, 要求:包
3、涵部分格局;设计游戏的核心算法;可视化的软件设计; 参考的知识:回溯法; 程序语言不限;题目二,地图着色问题(限 1 人完成) 设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并 保证使用的颜色总数最少.题目三,校园导航问题(限 1 人完成) 设计要求:设计你的学校的平面图,至少包括 10 个以上的场所,每两个场所 间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路 径(最短路径).题目四,学校超市选址问题(带权有向图的中心点)(限 1 人完成) 设计要求:对于某一学校超市,其他各单位到其的距离不同,同时各单位人员 去超市的频度也不同.请为超市选址,要求
4、实现总体最优.题目五,走迷宫游戏(限 1 人完成) 程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有 一个粮仓.游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓 处. 要求: 老鼠形象可辨认,可用键盘操纵老鼠上下左右移动; 迷宫的墙足够结实,老鼠不能穿墙而过; 正确检测结果,若老鼠在规定时间内走到粮仓处,提示成功,否则提示失败; 添加编辑迷宫功能,可修改当前迷宫,修改内容:墙变路,路变墙; 找出走出迷宫的所有路径,以及最短路径。 利用序列化功能实现迷宫地图文件的存盘和读出等功能。题目六,拓扑排序与关键路径在实际中的应用 1.判定问题是否存在拓扑序,如果是求关键路径
5、;求所有关键路径;求关键之关键; 2.将算法用在解决一个实际的应用问题中; 3.分析在数据结构课程中出现的算法是属于我们学过的那一种方法; 4.给出新的方法。题目七,最优二叉搜索树在数据库中的应用 实现该算法; 模拟一个数据库,该数据库具有动态的非顺序结构;题目八,积木游戏的设计 积木为矩形块,区间是矩形的设计; 积木为矩形块,T 形块,L 形块,区间是矩形的设计; 积木为矩形块,T 形块,L 形块,区间是凸边形的设计; 积木为矩形块,T 形块,L 形块,区间是矩形的设计; 积木为矩形块,T 形块,L 形块,区间是口袋的设计; 参考算法:典型的装箱问题(二维,三维) 1.贪婪算法(2 人) 要
6、求:(1),贪婪算法的基本思想 (2)给出背包问题的贪婪算法 (3)给出有限期计算机作业调度的贪婪算法 (4)给出上面两个算法的证明 (5)给出上面两个算法的程序(6)给出时间复杂度 2递归算法(2 人) 要求: (1)给出 01 背包问题的递归算法和程序 (2)给出 n 阶 hanoi 塔的递归算法和程序 (3)给出棋子移动的递归算法和程序 (4)给出 n 个元素全排列的递归算法和程序 (5)给出约瑟夫问题的递归算法和程序 3.回溯法(2 人) 要求: (1)给出回溯法的基本思想 (2)给出 n 后问题的回溯算法和程序 (3)给出子集和树问题的回溯算法和程序 (4)给出哈密顿回路的回溯算法和
7、程序 4.动态规划算法(2 人) 要求: (1)动态规划的基本思想 (2)给出最小代价子母树的动态规划算法和程序 (3)给出最短路径的动态规划算法和程序 (4)给出最优树的动态规划算法和程序 5.分治法(2 人) 要求: (1)分治法思想 (2)给出数据查找的算法和程序 (3)给出合并排序算法和程序 (4)给出快速排序算法和程序 (5)给出矩阵乘法的分治算法和程序 (6)给出多项式乘法的分治法和程序三三、课课程程设设计计方方式式、学学时时分分配配及及安安排排所有题目均按以下时间进度执行： 时间安排表 序号时间（天）内容安排备注 10.5 天方案设计 20.5 天程序框图 32 天编写程序代码
8、41 天程序调试分析和结果 51 天课程设计报告和总结 总计5（天）四四、考考核核方方式式与与成成绩绩评评定定标标准准 由指导教师根据学生在设计中的平时表现、任务的完成情况、课程设计报 告的质量等综合打分。考核标准包括：程序设计的可用性，实用性，通用性，可扩充性（40%） ；学生的动手能力，创新精神（30%） ；总结报告（30%） 。成绩 评定实行优秀、良好、中等、及格和不及格五个等级。优秀者人数一般不得超 过总人数的 20%。不及格者不能得到相应的学分，需重新做课程设计，经指导 教师考核及格后，方可取得相应学分。五五、教教材材及及主主要要参参考考资资料料 1 数据结构 （C 语言版） ，严蔚敏，清华大学出版社，2005 2 算法设计与分析 ，王晓东主编，清华大学出版社，2005 3汪诗林等译， 数据结构、算法与应用 ， （美）Sartaj Sahni 著，机械 工业出版社， 1999 4 数据结构与算法分析 ，CLIFFORD A. SHAFFER 著，张铭、刘晓丹 译，电子工业出版社，1998六、大纲说明六、大纲说明
