《随机算法》课程教学大纲

1、随机算法课程教学大纲一、课程基本信息课程名称（中文）随机算法课程名称（英文）Randomized Algorithms课程类别1：专业选修课课程性质2选修授课语言3中文授课学期5学分课程学时及分配总学时讲课实验课外32248适用专业计算机科学与技术教材随机算法Rajeev Motwanl Prabhakar Raghavan 著，孙广中 黄宇 李世胜译，高等教育出版社，2008年10月第1版。授课学院计算机与软件学院先修课程程序设计基础，数据结构，算法设计后续课程机器学习课程简介课程基本定位：该课程是一门专业选修课程，本课程介绍随机算法的设计与分析的基本方法，具有一定的深度和广度，使学生对计算

2、机常用随机算法有一个全盘的了解。核心学习结果：能够运用计算思维分析问题和解决问题，培养学生的独立科研能力和理论联系实际的能力主要教学方法： 讲授法、演示法、读书指导法大纲更新时间2020年8月注：1.课程类别：选填“通识核心课/通识拓展课/通修课/学科基础课/专业主干课/专业选修课/专业实践/素质拓展”2.课程性质：选填“选修/必修”3.授课语言：选填“中文/双语/全英文或其他语种”二、课程目标序号课程目标（参考培养目标、毕业要求、课程定位）支撑毕业要求指标点1达成途径目标1通过对常用的、有代表性的随机算法的研究，让学生理解并掌握随机算法设计的基本技术，培养学生分析随机算法复杂度的初步能力，能

3、够运用随机算法知识解决各自学科的实际问题；毕业要求指标点5.2：在计算机领域复杂工程问题的建模、模拟或解决过程中，能够使用恰当的技术、软硬件及系统资源和研发工具，提高解决复杂工程问题的能力和效率；1.课堂理论授课2.课后作业3.期末考试目标2能够运用计算思维分析问题和解决问题，培养学生的独立科研能力和理论联系实际的能力，锻炼其逻辑思维能力和想象力，并使之了解当今随机算法理论的发展。毕业要求指标点12.1：了解计算机技术发展中取得重大突破的历史背景以及当前的热点问题，了解信息技术发展的前沿和趋势。1.课堂理论授课2.课后作业3.实验实操4.期末考试注：1.支撑毕业要求指标点：选填项。需要进行专业

4、认证，有毕业要求指标点可参照的课程必填，无明确毕业要求指标点可参照的可不填。三、理论教学内容章标题教学内容学时思政融入点1学生学习预期成果2教学方式3课程目标第一章概述1. 最小切算法4引入国内外为算法设计与分析的发展做出贡献的科学家及相关事迹，激发学生的科研热情和爱国情怀。理解算法的设计思想，掌握最小切算法，掌握二分平面划分的方法，掌握概率递归算法，了解Las Vegas和Monte Carlo算法，理解计算模型和复杂性类的设计思想。讲授、案例、作业12. Las Vegas 和 Monte Carlo3. 二分平面划分4. 概率递归5. 计算模型和复杂性类第二章博弈论技术1. 博弈树估值4

5、讲授经典的博弈论技术，引导学生寻找生活中的博弈问题，激发学生创新的科研精神。掌握博弈树估值算法，理解最小化最大原则，理解随机性和非均匀性问题在算法设计中的重要性。讲授、案例、作业12. 最小化最大原则3. 随机性与非均匀性第三章矩和偏差1. 占有问题4理解占有问题的实际意义，了解Markov算法和Chebyshev不等式算法，掌握随机选择的方法，理解两点采样法的具体做法，理解稳定婚姻问题和优惠券收集者问题的具体含义。讲授、案例、实验、作业12. Markov和Chebyshev不等式3. 随机选择4. 两点采样5. 稳定婚姻问题6. 优惠券收集者问题第四章概率法1. 概率法概论4掌握概率法的基

6、本概念，理解最大可满足特性，掌握扩展图的使用方法，理解条件概率法的具体使用方法讲授、案例、作业12. 最大可满足性3. 扩展图4. 重审遗忘路由5. 条件概率法第五章数据结构应用1. 基础数据结构问题4介绍我校近年来举办和参与的各级各类学科竞赛情况，鼓励学生勇于打开创新之门，同时培养学生实事求是、踏实严谨、独立思考的科学素养。回顾数据结构课程中所学的基础数据结构问题，掌握随机Treap的使用，理解跳表的含义，掌握哈希表的使用方法讲授、案例、实验、专题讨论、作业22. 随机Treap3. 跳表4. 哈希表第六章图算法应用1. 所有点对之间的最短路径问题4掌握所有点之间的最短路径问题的求解方法，理

7、解最小切问题的含义，掌握最小生成树方法。讲授、案例、实验、专题讨论、作业22. 最小切问题3. 最小生成树注：1.思政融入点：至少写3条，简述该课程教学中将思政教育内容与专业教育内容有机融合的知识点（下同）。 2.学生学习预期成果：描述学生在学完本节内容后应获得的知识、能力或素养水平（下同） 3.教学方式:包括讲授、讨论、案例、演示等，但不限于所列，根据课程实际需要列举四、实践（实验或实习）教学1编号实验或实习项目名称教学内容学时实验或实习类型2思政融入点学生学习预期成果课程目标1优惠券收集问题m为实验个数，n为优惠券的类型。研究m和收集到n种类型优惠券中每种至少一张的概率之间的关系。2设计型

8、团队协作互帮互助对离散数学中的典型优惠券收集问题有进一步的理解。12哈希表的设计哈希表的设计与构造2设计型实战精神动手能力熟悉有关哈希表的基本概念；熟悉构造哈希表的方法；掌握哈希冲突的处理方法。23所有点之间的最短路径问题最短路径问题是图论中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。2验证型实战精神动手能力对最短路径问题的解决方法进行梳理，选择一种方法对问题进行求解24最小生成树求解给定一个无方向的带权图G=（V，E），最小生成树为集合T，T是以最小代价连接V中所有顶点所用边E的最小集合。集合T中的边能形成一颗树，这是因为每个顶点都能向上找到它的一个父节点（根

9、结点除外）。2综合型创新精神科研精神对最小生成树算法进行梳理，选择一种方法对问题进行求解。2注：1.此表可用于课内实践教学环节或某门综合实践课程2.实验类型：选填”验证性/综合性/设计性”；实习类型：选填“认识实习/生产实习/毕业实习”五、课程评价（一）考核内容、考核方式与课程目标对应关系课程目标考核内容课程目标在各考核方式中占比1平时表现课程作业实验成绩期末考试1各算法的具体概念及理解算法的分析与讨论60%70%60%2算法的实现实际问题的解决40%30%100%40%合计100%100%100%100%各考核方式占总成绩权重（自行赋值）10%10%20%60%注：1. 课程目标在考核方式及

10、占比：主要根据课程目标自行设计和制定多元化考核方式，表中所列仅为参考（红色数据可删除）。但所列考核方式必须覆盖全体学生，可根据当学期具体教学情况酌情调整。2. 各考核方式占总成绩权重：根据课程实际情况对各考核方式占总成绩的权重予以赋值。（二）考核方式评分标准1课程作业评分标准课程目标评分标准（分数段划分可根据课程需要自行设计）占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）1.能深入理解各算法的具体含义，并对算法的优劣进行正确的分析能较好的理解各算法的具体含义，并对算法的优劣进行比较正确的分析能够理解各算法的具体含义，并对算法的优劣进行的分比较合理析基

11、本理解各算法的具体含义，并对算法的优劣进行基本的分析不理解各算法的具体含义，并对算法的优劣分析不够正确50%2.对所学算法能用代码进行完整实现对所学算法能用代码进行较好实现对所学算法能用代码进行基本实现对所学算法未能用代码进行完整实现对所学算法不能用代码进行实现50%2期中/期末考试评分标准（笔试类评分标准可在大纲中按以下格式予以说明，也可在通过“试卷分析表”予以说明）课程目标评分标准（分数段划分可根据课程需要自行设计）占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）1.能深入理解各算法的具体含义，并对算法的优劣进行正确的分析能较好的理解各算法的具体含

12、义，并对算法的优劣进行比较正确的分析能够理解各算法的具体含义，并对算法的优劣进行的分比较合理析基本理解各算法的具体含义，并对算法的优劣进行基本的分析不理解各算法的具体含义，并对算法的优劣分析不够正确60%2.对所学算法能用代码进行完整实现，能顺利解决现实中的具体问题对所学算法能用代码进行较好实现，能比较顺利解决现实中的具体问题对所学算法能用代码进行基本实现，能基本解决现实中的具体问题对所学算法未能用代码进行完整实现，不能顺利解决现实中的具体问题对所学算法不能用代码进行实现，不能解决现实中的具体问题40%注：考核方式和课程目标在考核方式中占比应与“（一）考核内容、考核方式与课程目标对应关系”一致。所列考核环节，除了笔试类