算法分析与设计课程实验大纲4.docx

《算法分析与设计课程实验大纲4.docx》由会员分享，可在线阅读，更多相关《算法分析与设计课程实验大纲4.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计实验教学大纲课程编号：00003280大纲执笔人：课程名称:算法分析与设计大纲审批人：英文名称:The Design and Analysis of Algorithm实验室名称:计算中心专业实验室课程学时：40实验学时:8一，本课程实验教学目地与要求算法分析与设计实验课程地目地是通过在具体问题中对各经典算法实现，验证，巩固与加 强课堂理论知识地掌握，开阔学生在算法设计与分析中地思路，培养学生初步具备独立设计算 法与算法分析地能力，活跃学生地思想，帮助学生完成从“会编程序“到“编好程序”地角色转变, 锻炼与培养良好地软件工程习惯与软件思维方法。要求按照实验指导书介绍，用程序设计语

2、言实现经典算法，从中学习算法设计地主要策略 方法,原理并根据具体任务，培养设计与分析地能力,从算法效率角度探讨提高性地改进手段。二,主要仪器设备及现有台套数软件环境:C+程序设计语言编程工具:microsoft visual studio 2010三，实验课程内容与学时分配一序号实验工程 名称目地，要求实验内容学时 分配实验 类型必开， 选开1分治法合 并排序1,掌握合并排序地基 木用相2,掌戒3并排序地实 现方法；3,学会分析算法地时 间复杂度；4,学会用分治法解决 实际问题。随机产生一个整型数 组，然后用合并排序将 该数组做升序排列，要 求输出排序前与排序 后地数组。2综合 性必开2贪心法

3、作 业调度问 题1,掌握贪心算法地基 本思想；2,掌握贪心算法地典 型问题求解；3,进一步多机调度地 基本思想与算法设计 方法；4,学会用贪心法分析 与解决实际问题。设计贪心算法实现作 业调度，要求按作业调 度顺序输出作业序 列。如n=8,效益 p二(35,30,25,20,15,10, 5,1),时间期限 旧4,2,4,5,645,7),求 该条件下地最大效 益。2综合 性必开一序号实验工程 名称目地，要求实验内容学时 分配实验 类型必开， 选开3动态规划 法求多段 图问题1,掌握动态规划算法 地基本思想；2,掌握多段图地动态 规划算法；3,选择邻接表或邻接 矩阵方式来存储图；4,分析算法求

4、解地复 杂度。设G=(V,E)是一个带 权有向图，其顶点地集 合V被划分成k2个 不相交地子集 Vii=k,其中Vi与 Vk分别只有一个顶点 s (源)与一个顶点t(汇)。图中所有边地 始点与终点都在相邻 地两个子集M与Vi+i 中。求一条s到t地最 短路线。参看书图7-1 试选择使用向前递推 算法或向后递推算法 求解多段图问题。2综合 性必开4回溯法求 n皇后问 题1,掌握回溯算法地基 本思想；2,通过n皇后问题求 解熟悉回溯法；3,使用蒙特卡洛方法 分析算法地复杂度。要求在一个8*8地棋 盘上放置8个皇后，使 得它们彼此不受”攻 击二两个皇后位于棋 盘上地同一行，同一列 或同一对角线上，那

5、么称 它们在互相攻击。现 在要找出使得棋盘上 8个皇后互不攻击地 布局。2综合 性必开四，考核方式1,实验报告:本门课程实验是综合性,一是要求各种算法在实际问题中地实现;二是要求 分析该算法地复杂度,考核内容包括实验报告内容地完整性,实验算法设计地清晰度,实验结 果与算法分析地正确性。2,考核方式：(1)实验课地考核方式:根据学生在每次实验课结束后现场演示地实验结果与上交地实 验报告结合进行实验成绩评分。要求学生按照实验指导书地要求给出算法设计思想描述,源 程序,实验结果与算法复杂度评价，以及对算法策略提高地改进解决方案与建议地描述(根据 实验情况给出不同档次地成绩)o(2)实验课地成绩占课程总成绩地10%。五，实验，参考书1,：算法分析与设计实验指导书2,参考书：(1)陈慧南，算法设计与分析C+语言描述(第2版)，电子工业出版社,2013.(2) (Introduction to Algorithms(third edition),TH.Cormen,C.E.Leiserson,R.L.Rivest andC.Stein, the MIT Press,2001中文名算法导论(第二版)(影印版)，高等教育出版社.