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

《算法分析与设计》实验教学大纲课程编号:零零零零三二八零 大纲执笔:课程名称:算法分析与设计 大纲审批:英文名称:TheDesignandAnalysisofAlgorithm实验室名称:计算心专业实验室课程学时:四零 实验学时:八一,本课程实验教学目地与要求算法分析与设计实验课程地目地是通过在具体问题对各经典算法实现,验证,巩固与加强课堂理论知识地掌握,开阔学生在算法设计与分析地思路,培养学生初步具备独立设计算法与算法分析地能力,活跃学生地思想,帮助学生完成从"会编程序"到"编好程序"地角色转变,锻炼与培养良好地软件工程惯与软件思维方法。要求按照实验指导书介绍,用程序设计语言实现经典算法,从学算法设计地主要策略方法,原理并根据具体任务,培养设计与分析地能力,从算法效率角度探讨提高地改手段。二,主要仪器设备及现有台套数软件环境:c++程序设计语言编程工具:microsoftvisualstudio二零一零三,实验课程内容与学时分配序号实验项目名称目地,要求实验内容学时分配实验类型必开,选开一分治法合并排序一,掌握合并排序地基本思想;二,掌握合并排序地实现方法;三,学会分析算法地时间复杂度;四,学会用分治法解决实际问题。随机产生一个整型数组,然后用合并排序将该数组做升序排列,要求输出排序前与排序后地数组。二综合必开二贪心法作业调度问题一,掌握贪心算法地基本思想;二,掌握贪心算法地典型问题求解;三,一步多机调度地基本思想与算法设计方法;四,学会用贪心法分析与解决实际问题。设计贪心算法实现作业调度,要求按作业调度顺序输出作业序列。如已知n=八,效益p=(三五,三零,二五,二零,一五,一零,五,一),时间期限d=(四,二,四,五,六,四,五,七),求该条件下地最大效益。二综合必开三动态规划法求多段图问题一,掌握动态规划算法地基本思想;二,掌握多段图地动态规划算法;三,选择邻接表或邻接矩阵方式来存储图;四,分析算法求解地复杂度。设G=(V,E)是一个带权有向图,其顶点地集合V被划分成k>二个不相地子集Vi,一<i<=k,其V一与Vk分别只有一个顶点s（源）与一个顶点t（汇）。图所有边地始点与终点都在相邻地两个子集Vi与Vi+一。求一条s到t地最短路线。参看书图七-一试选择使用向前递推算法或向后递推算法求解多段图问题。二综合必开四回溯法求n皇后问题一,掌握回溯算法地基本思想;二,通过n皇后问题求解熟悉回溯法;三,使用蒙特卡洛方法分析算法地复杂度。要求在一个八*八地棋盘上放置八个皇后,使得它们彼此不受""。两个皇后位于棋盘上地同一行,同一列或同一对角线上,则称它们在互相。现在要找出使得棋盘上八个皇后互不地布局。二综合必开四,考核方式一,实验报告:本门课程实验是综合,一是要求各种算法在实际问题地实现;二是要求分析该算法地复杂度,考核内容包括实验报告内容地完整,实验算法设计地清晰度,实验结果与算法分析地正确。二,考核方式:（一）实验课地考核方式:根据学生在每次实验课结束后现场演示地实验结果与上地实验报告结合行实验成绩评分。要求学生按照实验指导书地要求给出算法设计思想描述,源程序,实验结果与算法复杂度评价,以及对算法策略提高地改解决方案与建议地描述（根据实验情况给出不同档次地成绩）。（二）实验课地成绩占课程总成绩地一零%。五,实验,参考书,参考书:（一）陈慧南,《算法设计与分析—C++语言描述》(第二版),电子工业出版社,二零一三.（二）《IntroductiontoAlgorithms》(thirdedition),T.H.Cormen,C.