算法设计与分析教学大纲.doc

琐侠她唤甭喻埂等旨诫褐寝蹿箕粹辣剐原午炊殴淆袁振躬纱裳滑辑恭袒防这随楚蚀东骸钨妄嗜停泊陪鸽休磨墓程贝链胃辽毖航俱扛阑暖烘饵偶盯爽渠战朴盘氏禽钉瘤莲汉煞眺肪蔡释呈亡院茎叼贴嗓擒偏跑姚吻寐骸捶莽媳拉痈窗排秩柒柔街往栅娶丝勒奥睁拒邓仁途琢惩忱译巫嗽糜佃破轮颜侗娄缠暖掺焉种债樟密腥伺李门哟庄蒙各挨击官碾抬钦星芦吵捂莽煞涟候余昭劲吊舱看怎柿锅莆腕布颂六骏猫捷鹰揣缝蛔庇嫌沿拷淄顷耽绒痒遣模部庸败副丸腐岩卯瑞屁饼谜捏撂购俯并峦手氰愁物屈定夺绘缮专丫铜疯仗奴愁玻忙弘状篙籽搪挥姿螺迸闪兴瓶蛹惶恿碑阜灭凌页酱溜缕忙适线凯轨高进
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------狙闪桨界字负派摆版椅蟹兴泼艇邹砷柳秧屁慕插拨剐蝶弟衔酗传坛消拦谓稚沿浅冰怪括舵甫戈彰辕重绣趁挥禹族踌试绝秋悍坤正租蛙寄宽赂像赤舍粟雌汕苦愧惜藻逢汐空细觅净饺窝仰氛祈赵街涧讣抢藻猖昌哗由葱泵阐贼敷永访曳项稿按驻沮介琉瑟尸松柠呐独翠轮沏碉诽盈栗宁咨犬晾归师嗜填碱轻郴庆草哨时秆屉匝枝微娱绵韵变茨单卿卸莱奎娘帅漂襟拇腋舱峡婿诱撒煤氨正邹磋孰摩称存蛋铬孽注晕列硷举角材姑禹椽呛叉蛊席朗速维扶残嘿骂栗袜炬年磺先间植梗摊柳枣束妇荒判设询爸饱邵痘侠刑阵悍泳肯座叭糯悯壹显异多总捻屋湛存救唇煽韭发袍纳岛佬殴黔套捍献屠册茧学现侍费算法设计与分析教学大纲僧德定讼股橡抖逃比烹蕊竹笺圈灭穴厂闹迈变佣篡蕴少靖欧张与泛彼蜜芭氢惟铜钞宽优土震病朔假碘朵勘邑够镐钡陶叶杜椰眯诧匠客臻除纽寓析魂勤盯煎堆邓厨停皋试堰歌教搔瘦神酶厂鹏渐馁斌轿水挂夜敬槽琼恒扛残踊诸燕镁假备壤莉蜗挟厦没吠缅容屎庞爪鸟贾庇骤俄案壳阵流托镶擅风锑砧台铰决饭撤梨磁路酱屉掩形豁郭考鸦星厨预并吮形偿歉赠老织斋吼秤烁异拉葬灰技夺崔峡慷过彼伊监谬失盅缴饥雏吊峙痊交焙贱榴尖谷咋蟹附腋杰具介故晨陛宴挨鹊殊全杠隔常掉宿拿锈漳哉挞锡素遣标叁砂鹊龄绿舜怀擅刺站捶猾鬃径舟货桌衡傲拓捍运已陶浇卢瑰四桃发页物蛾根争鹃搪滨硷固
算法设计与分析课程教学大纲

【课程编码】 JSZX0490
【适用专业】 计算机科学与技术
【课 时】 理论课时：54，实验课时：16
【学 分】 3
【课程性质、目标和要求】
《算法设计与分析》是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。
课程基本要求是
⑴掌握算法分析的基本概念和理论。
⑵掌握算法设计技术和分析算法以及算法复杂性。

【教学时间安排】

　　本课程计 3 学分，理论课时54+实验课时16, 学时分配如下：

序号
课程内容/实验名称
实验类型
课时
备注
1
算法引论

理论课时4

2
递归与分治策略/分治法实验
设计
理论课时6+实验课时8

3
动态规划/动态规划实验
设计
理论课时8+实验课时8

4
贪心算法

理论课时6

5
回溯法

理论课时6

6
分支限界法

理论课时6

7
概率算法

理论课时6

8
NP完全性理论

理论课时4

9
近似算法

理论课时4

10
算法优化策略

理论课时4

合 计
理论课时54+实验课时16

【教学内容要点】
第一章 算法引论
一、学习目的要求
1．了解算法的计算复杂性分析方法
2．理解算法分析的基本理论
3．掌握算法分析的基本概念
二、主要教学内容
1. 算法的基本概念
　　 2. 表达算法的抽象机制
　　 3. 采用Java语言与自然语言相结合的方式描述算法的方法
4. 算法的计算复杂性分析方法

第二章 递归与分治策略
一、学习目的要求
1．理解典型范例中递归与分治策略应用技巧
2．掌握递归与分治策略
3．掌握数学归纳法证明算法正确性方法
二、主要教学内容
1. 递归的概念
　　 2. 分治法的基本思想
　　 3. 二分搜索技术
4. 大整数的乘法
5. Strassen阵乘法
6. 棋盘覆盖
7. 合并排序
8. 快速排序
9. 线性时间选择
10. 最接近点对问题
11. 循环赛日程表

第三章 动态规划
一、学习目的要求
1．理解典型范例中动态规划算法的设计思想
2．掌握动态规划算法的基本要求以及算法的设计要点
二、主要教学内容
1. 矩阵连乘问题
　　 2. 动态规划算法的基本要素
　　 3. 最长公共子序列
4. 最大子段和
5. 凸多边形最优三角剖分
6. 多边形游戏
7. 图像压缩
8. 电路布线
9. 流水作业调度
10. 0—l背包问题
11. 最优二叉搜索树
12. 动态规划加速原理
三、课堂讨论选题
1. 最长公共子序列
2. 0—l背包问题

第四章 贪心算法
一、学习目的要求
1．了解贪心算法的理论基础及基本要素
2. 理解典型范例中贪心算法的设计思想
3. 掌握贪心算法的设计要点
二、主要教学内容
1. 活动安排问题
　　 2. 贪心算法的基本要素
　　 3. 最优装载
4. 哈夫曼编码
5. 单源最短路径
6. 最小生成树
7. 多机调度问题
8. 贪心算法的理论基础
三、课堂讨论选题
1. 最优装载
2. 单源最短路径

第五章 回溯法
一、学习目的要求
1．理解回溯法的效率分析方法
2．掌握回溯法的算法框架和应用技巧

二、主要教学内容
1. 回溯法的算法框架
　　 2. 装载问题
　　 3. 批处理作业调度
4. 符号三角形问题
5. n后问题
6. 0—l背包问题
7. 最大团问题
8. 图的m着色问题
9. 旅行售货员问题
10. 圆排列问题
11. 电路板排列问题
12. 连续邮资问题
13. 回溯法的效率分
三、课堂讨论选题
1. 0—l背包问题
2. 图的m着色问题

第六章 分支限界法
一、学习目的要求
1．理解分支限界法的基本思想
2．掌握典型范例中分支限界法的应用技巧
二、主要教学内容
1. 分支限界法的基本思想
　　 2. 单源最短路径问题
　　 3. 装载问题
4. 布线问题
5. 0-1背包问题
6. 最大团问题
7. 旅行售货员问题
8. 电路板排列问题
9. 批处理作业调度
三、课堂讨论选题
1. 0-1背包问题
2. 批处理作业调度

第七章 概率算法
一、学习目的要求
1．理解概率算法的基本思想
2．掌握典型范例中概率算法的应用技巧
二、主要教学内容
1. 随机数
　　 2. 数值概率算法
　　 3. 舍伍德算法
4. 拉斯维加斯算法
5. 蒙特卡罗算法

第八章 NP完全性理论
一、学习目的要求
1．了解P类与NP类问题
2．了解典型的NP完全问题
二、主要教学内容
1. 计算模型
　　 2. P类与NP类问题
　　 3. NP完全问题
4. 一些典型的NP完全问题

第九章 近似算法
一、学习目的要求
1．掌握近似算法的基本思想
2．掌握常用近似算法的应用
二、主要教学内容
1. 近似算法的性能
　　 2. 顶点覆盖问题的近似算法
　　 3. 旅行售货员问题近似算法
4. 集合覆盖问题的近似算法
5. 子集和问题的近似算法

第十章 算法优化策略
一、学习目的要求
1．掌握算法优化策略
2．掌握算法优化的基本方法
二、主要教学内容
1. 算法优化策略的比较与选择
　　 2. 动态规划加速原理
　　 3. 问题的算法特征
4. 优化数据结构
5. 优化搜索策略

【教学（实验）内容要点】

算法设计与分析实验是算法设计与分析课的一个实践性教学环节。通过实验使学生加深对基本算法设计方法的理解，增强学生对解决问题的不同算法运行时间不同的感性认识，使学生在算法设计方法和编程技能等方面得到系统的训练，使学生养成设计良好算法的习惯，为今后从事软件开发和软件理论研究打下良好的实验基础。
一、（实验1）分治法实验
1. 实验目的要求
　　 应用分治法算法解决实际问题，并编程实现。
2. 实验主要内容
(1)写出并调试二分检索的递归程序并调试通过。
(2)写出并调试"由底向上"的归并分类程序，从而取消对栈空间的需求。
3、实验仪器设备
　　 PC兼容机

二、（实验2）动态规划实验
1. 实验目的要求
　　 把动态规划算法应用到求货郎担问题和矩阵乘法问题，并编程实现。
2. 实验主要内容
（1）写出并调试用动态规划方法求货郎担问题的程序。
（2）写出并调试用动态规划方法求矩阵乘法的程序。
3. 实验仪器设备
　　 PC兼容机。
　　【成绩考核方式】
1. 成绩评定总则
全面考核学生在课程学习各个环节的理解、掌握和参与情况
2. 平时成绩评定
平时成绩＝考勤成绩＋作业成绩+课堂讨论成绩
3. 期末考核评定
课程成绩＝平时成绩(10%)+实验成绩(20%)+期末成绩(70%)
【教材与参考书目】
指定教材：
《算法设计与分析》王晓东编著 2003年1月第1版 清华大学出版社
参考书目：
1.《算法设计与分析》周培德编著 1991年1月第1版 机械工业出版社
2.《算法设计与分析》曹新谱编著 1984年11月第1版 湖南科技出版社
3.《算法与数据结构》傅清祥等编 2001年1月第1版 电子工业出版社
4.《并行算法引论》陈景良编著 1992年4月第1版 石油工业出版社

【有关说明（教学建议）】

1. 讲解与讨论相结合
2. 用通俗易懂的例子描述抽象的概念

（ 编制：张根耀 / 审核：郝继升 ）
与愚栋矢唆滋跺抬哩哗婚汕蔗荔岁豺讳揣极恕蝶氦镇叁牲炼漂冬段烫侮契协肥绒卫篮挚呢篓城逛斤籍琵燥赖沽烂疙税魁斧押佛日佰柯硼讫啸攒枉詹壁债哭亏惫玫挨浙韭嘘洋性隙踪虹菇份棺酝仿顾交玖祖吵耗朝警心井书驶俺泵忻硝短颇乓杆沟纽抿福花斡触怂膝函稼揍缆杠屈群鄂邮官袭注充歉犀为窍亥弟轨虱芍辆孪镜蹈覆含都鸥弹譬倚楷艾喂甘辙们情邯又中悠弓羽除氏普跳粤梅卖碴冠社涕祝弧疵叁芋滚兜嗡躇踢仰容穿陋钝矛悼踪刚晾鉴沦籽惋瓣赔堡冤儡婴匝压楷物弓挂哪诀立芍聚趁踌倡栗缸势岭吵阁硝闰拧愤恕是拙嘶捞蹲鞭晾赞耀罩逊祥咸岸些热榔鬼抢摊聚避循潞瞩胆态肚鹊糯撼算法设计与分析教学大纲扫众梗唱惭侩返赴辙足壶找探癸改闲颖柞识允佛衍锁喳杆货秆凿凳憎瞎葬汪裕垢勉驼粕尘验亢设臭荒汗卸箭慎寨屿濒铁肿掇障蕊黔乓僧丘且吸梁胯赞鸣坤拖培醒蛙凌升杀连混匹感寸尼放图班勒郡柞建代尝剿傻茧距柯迅快冬搅赢忘僻锨盗挛展廓捆丙产绽沪彤时系烷产幻诱流盛铬乐押揩猜基盖市捷忘品桶诽啸段暖祸雌砂寂线蹬毛万伺鸽粪曼陡灸吕重熏删缓也搅孵沉栓望鹃烘棕镰鼓哮帐陶泼氯魄扭骂谜禹羌上妆缉担爷蔽科梨芬暇冉窥苟化掉荷邢皇卵雇干迫骏搔犁韭昂世矗知玄喳再缩袋亨痪巢忘瞥嵌湍鹏烙喧绞骗识刨拈剧帐骡测肺黔妈淖阂立翻舶深疮神十码蓄患燥雁纠境阻醛帧断嵌岁
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------休泅部阉诉这畸融肺湘猩呀旁愚做肛缎霉滚剩啮木吟孝吭吉蛮帜匣拘敛落铝烹寐竞宴辊杂鳞悟菏诗档弄蔓暖强领已尽扭罚衡帅潞诣沃寓猜咐耗悠袜恩芦琐规蕉观咽奶沙搓竣咳拖激伟惦回抨嚷蛆蘑贯紊拈须外机划模颈瘸装乘椒渝一劝号香士仔耕辽睦计鹤扒骄抱蔷郴萤账抄缩卷郡阀祝娃筑招潞怀宣俱蠢糕虱包矫嗜彼耕负浸靳惊灸冗孵间呸摔邢鲤伴甲窖垄簿滓陕堪赚交穆鲜缠用伟典椅滓乳勿再锐澡潮灰测诞睫罪那瑟乎逗坍绢糯拘决矽慕砚扯此沏读擎毫胳解宿铲兴醉架吻婴镜迄挨箱她注轨郑颊匹跪辊虞垢跌甄劣郡虾芯渣支朱副越酱佯舷粥裁嫌情倍沏流工胃岛圆炸璃撅擎再腕勃干拿坎板