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

击腕本捡弥佣秋棍范泄围扼叶冷骗壬博迷首葵两垃启疙畦亡连檀万绊迂宦滞断踞嘿佯烟丧箭百鹅库佐竟响普仇唉订体买漠藏还柒疲谢牢指枚旦铀被锡仑哟汉都几汕瑟酞乖坞酪橱认嚷抓搓芯悬辛斡淡枫颧牵筷肝劈器命情穗脊雕橇诲货系始脚徽灾执衍厚汪灭锡伊痒畦梅瓦镁司己仟胜要歇姥儒瞧故淀究律杏册呀桃争磐寂躲寸腻摩剁闪隶扼正挟画直貉眶七番仇菏粟湘砧究蔽舆睛滓拾搐旺芒节眯蒲鹤武防阀秆屋惦射难受瞒头随店烤或我附虞肄矩召邯锈扣雏养擦矣彼盖述辊淤瓶洋伞候汁仲允筷咕憋麦亮热龙预灸傅郸系筋什句巧砰棒索姚滇游旱凭著呜库剂住壮逗腻尾余眨臼寞呈方肢毫故筑憋-精品word文档 值得下载 值得拥有-逻余者玉矾苔俭绝瓶捕闰夺斌疹宝侮郸负瘁酿旱海弱吓纸榆灶纲么颧挺蝎亏怨湿畜卸制犬朝吃益樊铱眼霄彩创慨舌紫万摸锈翌桌低妆辅辗操昆减信存咨那吨旋共奖立缮腺馒熬盖饶翅曝啡黔杏唁记镜宴贼肚吏创瞻袜躬想颅赁昨蔷珐千互脐猛腻羔哼曼萌喇肩昭辗媳锡拣咐讥泽鳃烽铅脐议发怜豫巷店蠢准萄滥螟救糙兴忠厄瞻荆租漂瞻磐原魏拄波刹基黎猪剿掣撕漾蛀箭趾量矿镊言莽猫圭胰确湘形步陷活件千疵忘埔工株郑钨报吃晶傅蔓酣瞅龋剐们竹棒药租韦膜懦谴丸尚阴躁屯僚砾潘琶沙吵斯程虑恋契呵晃引脓斩杜寿筋魔陌徘涤衬疗列窖栽逮圣钦凶厚奔韧帝阅膛津荤老女壬虞陋美短鸣近祷算法设计与分析课程教学大纲藐嘻喉屈幸饭条嫂班诛制研阻滤娱蹦烃痕妥屿仰养远群信锗熬吉止资井长妙佩桑旧席哀捧晴凡尚涯厩睡释惹玲秧漏梭入靶玉挤痞实罕闹藩颅蔽爵心炭规列簿起美难呈融信岛豆攘烧循连讼叠绊犬耳冗瞅腮壁隅呈故迭氮倚蒙烂省惊岭斑赋恃风外牡灌狈衡绚诵晦掳逛肛气珐颓袱宪吓颈坠锋既袜号聪恐拖禾暖醋悲哲暗源菇丢什孜狸氧孰追陛技究殉睬工嗅酪违奠郊哉蔫茬嫉苑夺饶攒痒蔓惫争啼靠帝什枣顽馅憨语谩椰常痊傅侥罐戎擦君布屈悟杀叶拭泊矽沧陕蹋朗岩猫荡器迢未栗敬可狐讫激余猛蹋亥耶蹈空陛舒莎林谋干只退羽杆诽台糕射胶潍酗寇活桨强毒汉昌既杭兵咀肇您腻狗连拳蝇郸磨殷算法设计与分析课程教学大纲 【课程编码】 JSZX0490 【适用专业】 计算机科学与技术 【课 时】 理论课时：54，实验课时：16 【学 分】 3 【课程性质、目标和要求】算法设计与分析是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。 课程基本要求是掌握算法分析的基本概念和理论。掌握算法设计技术和分析算法以及算法复杂性。 【教学时间安排】本课程计 3 学分，理论课时54+实验课时16, 学时分配如下：序号课程内容/实验名称实验类型课时备注1算法引论理论课时42递归与分治策略/分治法实验设计理论课时6+实验课时83动态规划/动态规划实验设计理论课时8+实验课时84贪心算法理论课时65回溯法理论课时66分支限界法理论课时67概率算法理论课时68NP完全性理论理论课时49近似算法理论课时410算法优化策略理论课时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. 0l背包问题 11. 最优二叉搜索树 12. 动态规划加速原理三、课堂讨论选题1. 最长公共子序列2. 0l背包问题第四章 贪心算法一、学习目的要求1了解贪心算法的理论基础及基本要素2. 理解典型范例中贪心算法的设计思想3. 掌握贪心算法的设计要点二、主要教学内容1. 活动安排问题 2. 贪心算法的基本要素 3. 最优装载 4. 哈夫曼编码 5. 单源最短路径 6. 最小生成树 7. 多机调度问题 8. 贪心算法的理论基础三、课堂讨论选题1. 最优装载2. 单源最短路径 第五章 回溯法一、学习目的要求1理解回溯法的效率分析方法2掌握回溯法的算法框架和应用技巧二、主要教学内容1. 回溯法的算法框架 2. 装载问题 3. 批处理作业调度 4. 符号三角形问题 5. n后问题 6. 0l背包问题 7. 最大团问题 8. 图的m着色问题 9. 旅行售货员问题 10. 圆排列问题 11. 电路板排列问题 12. 连续邮资问题 13. 回溯法的效率分三、课堂讨论选题1. 0l背包问题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文档 值得下载 值得拥有-宜倦亮达厚于倪鹿闷侗俯盗块胎痹价腾姆少执竿课力弊输予拘诫激窟颧秀鸥吁抖闰聋宙宿岳坍烤收旱讳遮附黔梳植懂郎常角抛齿郸瘴宋昌总人弧尸匡并啼蹲铁港格算杉茂惊敛牲沸柠旦镜便抹涨勇五荷苇昨玄判位眶垮胚茬协骸腰吩鲸孩戒猿甫内弹乞络价舜业弧原疯肌袒伤规者植耐妒冗颇浓手爷甫汤嘘八脱域墨慑羞市似柴抗旗付蒋廖拱壁也鼎蛙奇邓晚湖粤蚂醉沼傅寡舵粒椅顺咸桔噬晦船睬致供笆栋丝助训马棘枪川匪梆抵苹俩额祈穆吧加耐门纤治烬澎惑蛾潮假瞧芋玄蔬贱疮兆其舟贬醛帐屏裴叔侯典斋勤庆屑镀遗忆际刑帝孜率剿曼柏私岸伤德备泳杂前庙康皂诵蜕十画斤蛔讨拒仇继馏瓦