《算法设计与分析》教学大纲.docx

算法设计与分析教学大纲适用意围：2O2X版本科人才培养方案涕程代码：()8140431课程性质：专业选修课程学分：4学分学时：N学时(理论48学时,实验16学时)先修课程：数据结构后续课程：无适用专业：数据科学与大数据技术、数据科学与大数据技术专升本开课单位：计算机科学与技术学院一、课程说明律法设计与分析是数据科学与大数据技术专业的专业选修课程.课程主要讲授舞法概述,贪心算法，通归与分治，动态规划，回溯算法，分支界限法，随机化算法和NP完全理论8个章节的内容，本课程主要用来培养学生的抽象能力、计豫思维解能力,应用能力和高效程序设计能力，猴以增进学生的理解、分析、组织以及推理能力，通过本课程的学习，学生应达到理解灯法设计的主要思想，能够应用典型的算法解决问应,并为后续课程和进一步深造打下坚实基础.本课程需要守好种好思想教育费任印.使课程与思想政治理论课同向同行,形成协同效应.二'课程目标通过本课程的学习,使学生达到如下目标：课程目标1：掌握算法的设计步骤和和交杂度分析.针对特定问卷，能步合理分析问题并建立数学矮型：针时特定解决方案，能纷证方案的合理性，并诳行复杂度分析，改进方案的不足。培养学生分析问烟的能力，引导学生独立思考解决向鹿，促进学生的个性化发展和提升.课程目标2：理解贪心算法.递归与分治,动态规划，回溯"法,分支界限法舞法的思想和原理，在实际开发中,能够选择相应的数据结构和算法解决程序设计中的难题.课程目标3：针对计驾机复杂工程何也能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案，三、课程目标与毕业要求4算法设计与分析3课程教学目标对数据科学与大数据技术专业的毕业要求的支推见表毕业要求指标点课程目标支撑M2.U分析2.3能运用数学、自然科学和数据科学与大数据技术工程科学基本原理，分析和验证解决方案的合理性,并能够掌握好决方案优化方法.课程目标1：掌握算法的设计步探和和更杂度分析,针对特定问起,能师合理分析同时并建立数学模型：针对特定解决方案，能检验证方案的合理性，并进行复杂度分析，改进方案的不足。培养学生分析问即的能力，引导学生独立刖考解决问题,促进学生的个性化发展和提升.H3.设计/开发解决方案3.I能步针对大数据应用系统设计与开发满足特定需求的模块或算法.课程目标2：理解贪心律法，递归与分治.动态规划,回溯算法，分支界取法算法的思想和原理,在实际开发中,能够选择相应的数据结构和算法解决程序设计中的难题。H4.研究4.2能好基于科学原理并采用科学方法对数据科学叮大数据技术领域相关问题选择研究路线，并设计实验方案.课程目标3：针对计算机更杂工程何速,能峙基于算法设计与分析方法,通过调研和分析.设计合适的研究方案.I1.注，表中-H（MXM（中）”表示课程与相关毕业要求的关联度.四、教学内容,基本要求与学时分配I.理论部分理论部分的教学内容、基本要求与学时分配见表2表2教学内容、基本要求与学时分配教学内容被学要求，：学点焦点理论学时实验学时对应的课程目标1 .算法概述1.1 算法的特征:1.2 算法的描述方式:1.3 算法设计的一般过程；1.4算法分析；1.5递推方程求解方法.教学要求，（1）理解算法与程序的关系以及与数据结构的关系：（2）能师抽望表达算法：3掌握定麻估计分法的红杂度的方法.BAI算法衣达的抽象机制，描述算法和J1.杂度分析。难点，招具体程序抽象为算法并对第法进行更朵度分析.1O1、2、32.递归和分治21递归与分治法的基本思想与概念：2.2-2.4二分查找.选第二大元素，循环赛日程表；2.5-2.7合并排序,快速排序和战性时间选择。教学襄求：（1）掌握通£1和分治的堪木思想和原理：2二分杳找，选第二大元素,循环赛日程表：（3）掌握合并排序快速排序在快速排序基础上理解税性时间选择的实现原理，点：分治法思想与艇本慨公的掌握Mt灵活利用分治和递归算法进行二分杳找，合并排序,快速持序。841、2、33.动态规划3.13.2动态规划的基本思想,矩阵连乘：3.3-3.5凸多边形最优三角剖分，最长公共子序列，加工顺序：3.6-3.7聚优二叉树搜索.0/1背包问题.教学要求，（1）掌握动态规划的域本思想:（2）熟练应用动态规划求解实际问避：CO掌握最长公共子序列，0/1背包问题与最优二叉树搜索；点：动态规划塔本思想以及与分治法的联系与区别.魔点，最长公扶子序列，0/1背包问燃与最优二叉树搜索.841、2、34贪心算法4.14.2贪心算法的基本微含，活动安排网时：1.3-1.6紧短路径算法,哈夫里编码；4.8最小生成树（Prim和KrUSkaI算法）,背包问题.收学要求，（D理解我心律法的班本概念与思想：（2熟炼应用贪心算法怖决最优袋找问遨哈夫蚣树和最短路径问题;（3）理解出小生成树的定义,以及两种豫法的原理.重点，掌握放心豫法的基本概念.难点：最短路径算法和最小生成树.611、2、35.回溯法5.1- 5.2回溯法的基本概念,典型的解空间结构：5.35.4千集树向遨：01背包和最大团：5.5- 5.6排列树:批处理作业调度和旅行商问SS：5.7-5.8tR.XW：图的m着色问题和最小旗量机零设计问题.求I（D掌握回溯法的M本概念，熟练应用回溯法解决实际问鹿：（2）能终对具体问题进行分析研究得到问遨的解空间结构.进而设计实验方案：（3）了解I可溯法的效率.重点：I可溯法的基本概念，n后向超，旅行商问题，回溯法效率分析，魔点：n后问题，旅行商问题，图的着色问题。62K2、3&分支限界法6.1分支限界法的基本思想：6.2-6.4旅行商问题.0背包向SS，布战RKf1.教学襄求t（1）掌握分支限界法的躯本思想和原理:（2）能够利用分支限界法解决旅行商问遨.0/1背包问题：（3）理解布线解XS的规则及表达方儿点；分支限界法的原理和范本思想.魔点：旅行商问题，0/1背包问题。621、2、37.IK机化算法7.1随机化算法类型及随机数生成擀：7.27.5数值随机化停法，蒙特卡罗算法,拉斯维加斯算法和台伍往能法.敦学要求：（1）求握概率眸法的求本思想和原理:（2掌榴简单分布的随机数生成；（3）掌握数值概率算法，拉斯维加斯尊法和蒙特卡罗算法.重点：J'解概率算法的基本思想.建点：如何产生不同分布的随机数，利用数值概率算法,拉斯维加斯算法和蒙特R岁算法求斜一线简单问鹿。6O1,2、38.NP完全理论1.1 1易解问时和难解问题定义：1.2 P类与NP问遨：1.3 NP完全问题：1.4 NP完全问超的近似蚱法.教学及求，理解P类与NP问题，NP完全问题的定义：2了解非确定性图兄机和多项式时间，点：掌握P类与NP问遨，W完全问8分类.难点:非确定性图灵机和多项式时间.4O1、2、3合计48162.实验部分实验部分的教学内容、基本要求与学时分配见表3。表3实险项目、实验内曾与学时实验项目实疆内容和要求实黯学时对应的课程目标1.递归与分治实验内容：合并排序，快速排序.实验要求：掌堀通归与分治算法思想，分析算法的复杂度.11、2、32.动态规划实设内容：矩阵连乘，培长公共子序列，凸多边形殿优三角剖分、图像压缩，流水作业调度，。”背包问遨,最优二叉树搜索（任选2个问逑即可.实验要求：掌握动态规划的基本思想,利用该算法解决一些具有全局以优结构的向题，41、2,33,贪心算法实设内容：城优装我问胭，哈夫树，最短跖径算法,最小生成树（Primf1.1.Kraska1.算法）（任选2个何卷完成即可）。实验要求，掌握贪心算法的基本思想,分析贪心算法的正确性.41、2、31分支限界法和回溯法实验内容，装我问咫.旅行1货员问遨.W1.背包问邈.n后问题和图的m着色向Je(任选I个问胭，两种算法完成即可)实H要求，掌根分支限界法和回溯算法基本思想,并比较与贪心算法的设计理念的不同之处。41、2、316五、教学方法及手段本课程以课堂讲授为主，结合讨论、案例、视频资源、实脸等教学手段完成课程教学任务和相关能力的培养，使得学生比较全面地理解算法的羯木方法与设计原理，井能铭分析算法的红杂度和评价算法优劣，在掌握各个算法特点和现杂度的权础上，根据设计御求设计不同的算法.在实5金教学环节中.通过案例教学和验证以掌握基本理论、基本知识和基本技能.培养学生自主学习能力、实际动手旎力,激发学生的创新处推。在实验前学生网复习和掌娓与本实验有关的教学内容：在实脸中要严格遵守实验纪律，按操作规程使用仪器：实舱结束后,按规定对仪器进行维护保养：每完成一项实3金，要认真完成一份实脸报告。六、课程资源I.推荐教材(1)王秋芬.算法设计与分析(Python版)M.北京：清华大学出版社.2021.2.参考书(1)王晓东.算法设计与分析习题解答(第四版)M)北京:清华大学出版社,2018.(2)科曼,ConnenTH,算法导论M,北京:机械工业出版社,2021.(3)巴尔加瓦.算法图解M1.北京:人民邮电出版社.2021.(4)王红梅.算法设计与分析(第3版M.北京：清华大学出版社,2022.3.期刊(1)MadhumathiR1.1.icnma1.arK.Dynamicoptima1.distributedresourcep1.anningforrenewab1.eenergybasedinterconnectednicrogridsusingteaching1.earninga1.gorithnU.Journa1.ofInte1.1.igent&FUZZySystems,2022.43(1).(2)ECanCes.E1.iriacherV,T1.e1.½vre.Convergenoeofagreedya1.gorithmforhigh-dimensiona1.convexnon1.inearprob1.cnsJ.Mathematica1.MOdC1.S&MethodsinApp1.iedSciences.2011.21(12):2433-2467.(3)刘国伟.任荚庄.靳雨欣等.以培养计。思维能力为导向的算法设计与分析教学方法探索U1.VtJrmttW,2022(05):189-195.(4)S1.cvinskyRM,SafuuhiH.Arecursivea1.gorithmfortheGtransformationand<ccratecomputationofincomp1.eteBcssc1.functinsJ.App1.iedNumerica1.Mathematics.2010,6(X12)：I411-147.(5)秦敏,王并阳.乔世权.算法设计与分析课程案例鞅学模式的探讨I几创新创业理论研究与实践,2022.5(11):145-147.4.网络资源(1)算法导论.网易公开操.'ncwvicwmoviccourscintro2ncwur1.=%2Fspecia1.%2Fopencofe*:12Fa1.gorithms.1.)tn1.(2)算法设计与分析.Bi1.ibi1.i.ht1.psvideBV1.1.s411.W7PB7from=search&scid=5419514692522206093&$pm_i1.frCm=333.337.0.0.七、课程考核对课程目标的支撑课程成绩由过程性考核成绩和期末测试成绩两制分构成,具体考核/评价细则及对课程目标的支撑关系见表4.表4课程考核用谭程目标的支撑考核环占比考核/评价细则课程目标123过程性考核15<1)根据课堂出勤情况和课堂I可答问咫情况进行考核，满分100分。<2>以平时考核成绩乘以其在总评成绩中所占的比例计入课程总评成绩.447实验12.5< 1>根据每个实验的实验操作完成情况和实验报告政属单独评分，满分100分：< 2>姆次实验单独评分，取各次实蛤成绩的平均(ft作为此环节的最终成绩。< 3>以实验成绩乘以其在总评成绩中所占的比例计入课程总评成绩.52.55作业22.5<>主要考.核学生对各酒节知识点的复习、理解和掌握程度，满分100分：<2>每次作业单独普分，取各次成绩的平均值作为此环节的最终成绩.<3>以作业成绩乘以其在总评成绩中所占的比例计入课程总评成绩.68.58期末考核50< 1)期末溯试成绩成绩100分，以测试成绩乘以其在总评成绩中所占的比例计入课程总评成绩.< 2>主要考核基本算法的原理和应用，包括递归,分泊，动态规划.贪心.分支限界法，付1潮免法和概率目法。< 3>测试题鞭包含塔空题、选择他、划断题和分析题等题型。202010合计：100分353530八、考核与成绩评定1 .考核方式及成愦评定考核方式：本濯理主要以课堂表现、实验、作业、期末测试等方式对学生进行考核评价.考核基本要求：考核总成绩由期末测试（占比50%）利过程性考核成绩（占比制组成我中：期末测试满分为100分，试遨类型为填空腮、选择即、判断题和分析璃等遨型，试卷中基本知识、基本理论、基本技能的试超分值不超过50%,综合应用题、分析超不低于50%；过程性考核湎分为100分，由课堂表现、实验和作业三部分组成，占过程性考核成绩的比例分别为30%、25%和15%.过程性考核和测试试题分值分配应与教学大纲各求节的学时璃木成比例。2 .过程性考核成绩的标准过程性考核方式Ifi点考核内容、评价标准、所占比揖见表5.«6过程性考核方式评价标灌考核方式所占比保）1.>x>9090>x>8080>x7070>x>60x<6030积极参与教学活动，踊跃回答问题,签到率大于95%.认真参与教学活动，回答问题准，签到率大于90%.偶尔参与教学活动，回答问题,签到率大于85%.上课不认真,偶尔参与鞅学活动,签到率大于80%.上课不认ft.不参与教学活动，签到率低于80%.实验25实脍预习认真,旎够熟练掌握方法与步骤,实验攥作过程熟练、规范,遵规守纪、团结协作，实5金结果详实、结论清晰、时论合理实脸前有预习.能畴掌握方法与步骡.实聆操作过程正确、规莅，避规守纪、团结协作.实验结果正确、讨论适当实险前有预习，基本能鲂掌旌方法与步骤，实验操作过程携木正确、无称作，实5金结果基本正确，讨论一般实险首有预习,不能掌握方法与步骡，实骁操作过程法本正%无协作,实验结果基本正确,无时论没有预习.不能完成实验：实验糜作步骤有误：实验结果不正确.没有分析讨论，作业45作业完将，思路清晰，准确率大于90%,字迹工整.作业完整，准确率大于80%,字迹工整.不交作业2次以内，准喘率大于7O.不交作业4次以内,准确率大于60.不交作业5次以£,准确率小于60%.