《算法分析与设计》课程教学大纲_第1页
《算法分析与设计》课程教学大纲_第2页
《算法分析与设计》课程教学大纲_第3页
《算法分析与设计》课程教学大纲_第4页
《算法分析与设计》课程教学大纲_第5页
已阅读5页,还剩4页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

算法设计与分析课程教学大纲AlgorithmDesign&analysis学时数:48其中:实训学时:10课外学时:0学分数:3适用专业:信息与计算科学一、课程的性质、目的和任务算法设计与分析是信息与计算科学专业的专业课,其内容是研究计算机领域及其它有关领域中的一些常用算法,它是计算机科学通常要解决的主要问题之一,因而也是各专业方向可以选修的一门重要的专业基础课。通过本课程的学习,使学生掌握算法设计的常用方法,以便运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法,并力争做到快捷、有效,从而提高程序设计的质量。除此,还要使学生学会分析算法、估计算法的时空复杂性,以便理解并科学评估有关处法。因而,对于计算机专业的技术人员,学习和掌握这方面的知识是很有必要的。二、课程教学的基本要求(一)算法概述1、了解算法与程序的概念。2、掌握算法复杂性分析及其有关的概念。(二)递归与分治策略1、理解递归的概念。2、了解分治法的基本思想。3、掌握二分收缩技术。4、掌握Strassen矩阵算法。5、了解棋盘覆盖问题的算法。6、理解合并排序和快速排序算法。7、了解线性时间选择算法。(三)动态规划1、掌握动态规划算法的概念和步骤。2、掌握矩阵的连乘算法设计和分析。3、掌握动态规划算法的基本要素。4、了解凸多边形最优三角剖分算法。5、了解多边形游戏问题的算法分析。6、了解图象压缩算法分析。7、掌握电路布线问题的算法分析。8、掌握流水作业调度。9、了解背包问题的算法分析。10、了解最优二叉搜索树的算法分析。(四)贪心算法1、掌握贪心算法的概念。2、掌握贪心算法的基本要素。3、了解最优装载问题的算法分析。4、了解哈夫曼编码的算法分析。5、了解单源最短路径的Dijkstra算法的设计与分析。6、了解最小生成树的Prim和Kruskal算法的设计与分析。(五)回溯法1、掌握回溯法的算法框架。2、掌握批处理作业调度问题的算法设计与分析。3、了解符号三角形问题的算法设计与分析。4、了解背包问题的回溯法的算法分析。5、了解最大团问题的算法设计与分析。6、了解回溯法的效率分析。(六)分支限界法1、掌握分支限界法的基本思想。2、掌握单源最短路问题的分支限界法分析。3、了解旅行售货员问题的算法设计与分析。(七)概率算法1、掌握概率算法的基本特征,4类概率算法2、理解随机数在概率算法中扮演的角色3、掌握数值概率算法4、了解舍伍德算法、拉斯维加斯算法、蒙特卡罗算法(八)NP完全性问题1、了解NP完全性问题的概念。2、理解求解问题的计算模型。3、了解P类问题和NP类问题。4、了解NP完全问题。5、了解一些典型的NP完全问题。三、课程教学内容、重点及难点第一章算法概述一、算法与程序(一)算法与程序的概念(二)算法与程序的区别二、表达算法的抽象机制(一)高级程序设计语言的优点(二)抽象数据类型以及使用抽象数据类型带给算法设计的好处三、描述算法(一)Java语法的程序结构、数据类型(二)方法、异常处理、类、通用方法、垃圾收集(三)用Java处理递归四、算法复杂性分析(一)算法的计算复杂性(时间、空间)分析方法重点重点:表达算法的抽象机制,算法的描述,算法复杂性分析。难点:算法复杂性分析。第二章递归与分治策略一、递归的概念(一)递归算法的概念(二)用递归的方式定义阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi问题并分析基复杂度二、分治法的基本思想(一)分治法的基本思想和一般原则三、二分搜索技术四、大整数的乘法五、Strassen矩阵乘法六、棋盘覆盖七、合并排序八、快速排序九、线性时间选择十、最接近点对问题十一循环赛日程表重点:重点:递归的一般方法,分治法的一般方法、归并分类和快速分类算法。难点:递归与分治策略分析。第三章动态规划一、矩阵连乘问题(一)矩阵连乘问题介绍(二)用动态规划法解矩阵的连乘积的最优计算次序问题的步骤1、分析最优解的结构2、建立递归关系3、计算最优值4、构造最优解二、动态规划算法的基本要素(一)最优子结构(二)重叠子子问题(三)备忘录方法三、最长公共子序列四、凸多边形最优三角剖分五、多边形游戏六、图像压缩七、电路布线八、流水作业调度九、0-1背包问题十、最优二叉搜索树重点:重点:动态规划的一般方法、0/1背包问题、最优二叉搜索树。难点:多边形最优三角剖分、最优二叉搜索树、流水作业调度问题。第四章贪心算法一、活动安排问题二、贪心算法的基本要素(一)贪心选择性质(二)最优子结构性质(三)贪心算法与动态规划算法的差异三、最优装载四、哈夫曼编码(一)前缀码(二)构造哈夫曼编码(三)哈夫曼算法的正确性五、单源最短路径(一)算法基本思想(二)算法的正确性和计算复杂性六、最小生成树(一)最小生成树性质(二)Prim算法(三)Kruskal算法七、多机调度问题八、贪心算法的理论基础(一)拟阵(二)带权拟阵的贪心算法(三)任务时间表问题(三)任务时间表问题重点:重点:贪心设计策略的一般方法,最短路径算法、最小生成树算法。难点:最小生成树算法、最短路径算法。第五章回溯法一、回溯法的算法框架(一)问题的解空间(二)回溯法的基本思想(三)递归回溯(四)迭代回溯(五)子集树与排列树二、装载问题三、批处理作业调度四、符号三角形问题五、n后问题六、0\1背包问题七、最大团问题八、图的m着色问题九、旅行售货员问题十、圆排列问题十一、电路板排列问题十二、连续邮资问题十三、回溯法的效率分析重点:重点:回溯的一般方法、8-皇后问题、图的着色。难点:8-皇后问题、图的着色问题。第六章分支限界法一、分支限界法的基本思想(一)分支限界法的基本思想(二)分支限界法的分类二、单源最短路径问题三、装载问题四、布线问题五、0\1背包问题六、最大团问题七、旅行售货员问题八、电路板排列问题九、批处理作业调度重点:重点:分支限界法的基本思想。难点:0-1背包问题、旅行售货员问题。第七章概率算法一、随机数(一)概率算法的基本特征,概率算法的分类(二)随机数在概率算法中扮演的角色二、数值概率算法(一)用随机投点法计算π值(二)计算定积分(三)解非线性方程组三、舍伍德算法(一)线性时间选择算法(二)跳跃表四、拉斯维加斯算法(一)n后问题(二)整数因子分解五、蒙特卡罗算法(一)蒙特卡罗算法的基本思想(二)主元素问题(三)素数测试重点:概率算法的基本特征。重点:概率算法的基本特征。难点:数值概率算法。第八章NP完全性问题一、计算模型(一)随机存取机RAM(二)随机存取存储程序机RASP(三)RAM模型的变形与简化(四)图灵机(五)图灵机模型与RAM模型的关系(六)问题变换与计算复杂性归约二、P类与NP类问题(一)非确定性图灵机(二)P类与NP类语言(三)多项式时间验证三、NP完全问题(一)多项式时间变换(二)Cook定理四、一些典型的NP完全问题(一)合取范式的可满足性问题(二)3元合取范式的可满足性问题(三)团问题(四)顶点覆盖问题(五)子集和问题(六)哈密顿回路问题(七)旅行售货员问题重点:重点:P类问题和NP类问题的基本概念,多项式时间验证及变换,Cook定理及定理的证明。难点:Cook定理及定理的证明,哈密顿回路问题。四、课程各教学环节要求(一)本课程共安排54课时,其中原理采用多媒体讲授44课时上机实践10课时。(二)作业:按教学进度要布置相应的作业,反映教学目的和基本要求。(三)考试:期末考试采取闭卷形式,计70%;平时作业计30%五、学时分配章节主要内容各教学环节学时分配作业题量备注讲授实验上机讨论习题课外其它小计一算法引论444二递归与分治策略6288三动态规划82106四贪心算法6288五回溯算法4265六分支限界法4264七概率算法442八NP完全性理论224合计38104841六、本课程与其它课程的联系本课程的目的是培养学生分析算法复杂度的初步能力,锻炼其逻辑思维能力和想象力,并使之了解算法理论的发展。因此本课程需要学生具备一定的编程基础,应该熟练掌握Java语言,数据结构理论和离散数学。七、教材与教学参考书(一)教材:王晓东.算法设计与分析.北京:清华大学出版社,2003。(二)教学参考书:[1]AnanyLevitin(美)编,潘彦译.Introduc

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论