《高级算法设计》课程教学大纲

《高级算法设计与分析》课程教学大纲课程中文名称:高级算法设计课程英文名称：Advancedalgorithmdesignandanalysis课程类别：通开课课程学分数：2课程学时数：32授课对象：计算机和网络安全专业硕士研究生一．课程性质《高级算法设计》是计算机专业和网络安全专业硕士研究生的一门学科通开课。二、教学目的与要求本课程是对本科课程《算法设计与分析》的扩展和提高，其是支撑网络空间安全一级学科的基础课程。算法是计算机最核心的内容，计算机科学也被称为算法科学。通过本科学习，学生已经掌握了分治、动态规划、回溯等基本算法，本课程在这些算法的基础上进一步培养学生的算法设计和分析能力，培养学生“时间高效和空间高效地”解决实际问题思维习惯和动手能力，进一步提高学生的算法修养。本课程详细讲授了线性规划、NP完全性理论、近似算法、随机算法和启发式算法等方面的相关知识，同时通过对各种算法的设计分析，使硕士研究生掌握各种算法原理的同时理解算法的设计思想，为将来学习加密算法、安全协议、人工智能算法打下基础，同时能够在这些领域设计新的算法，实现理论与实践的统一。三．教学内容本课程由七大部分组成：（一）线性规划(6学时)1.基本概念2.标准型和松弛型3.图解法4.单纯形法和单纯形表5.对偶：对偶推导、性质，矩阵博弈和对偶6.原始-对偶算法7.整数规划及其解法（二）高级图算法(5学时)1．最大流问题2.图的中心性算法3.社群发现算法（三）NP完全性问题(5学时)1．NP完全理论的基本概念2.难解问题与易解问题、判定问题3.NP类与P类4.几个NP完全问题:顶点覆盖、哈密顿回路与货郎问题、恰好覆盖、子集和、0-1背包、整数线性规划等（四）近似算法(4学时)1．近似算法的设计思想及分析方法2.旅行商问题的近似解法3.集合覆盖的近似解法4.斯坦纳最小树近似解法（五）随机算法(4学时)1．随机算法概述和基本思想2.随机快速排序、选择3.最小圆覆盖4.懒惰选择(LazySelect)5.最小割（六）在线算法(4学时)1.在线算法基本概念与竞争度分析2.确定性在线算法3.随机在线算法（七）启发式算法(4学时)1.蚁群算法2.遗传算法3.模拟退火4.Tabu搜索四.教学计划（包含每个课时的授课内容等）授课内容授课课时（一）线性规划6（二）高级图算法5（三）NP完全性问题5（四）近似算法4（五）随机算法4（六）在线算法4（七）启发式算法4五.课程重点和难点课程的重要知识点包括：1）线性规划的模型建立和求解，线性模型是高级算法，如近似算法、随机算法、在线算法用到的工具；2）高级图算法中图中心性算法，其是图神经网络的基础；3）NPC问题的证明，其是算法问题分类的基础；4）近似算法中采用对偶方法求解近似解；5）随机算法中的最小割问题，其在图中有着重要的作用；6）在线算法中的姚极小极大原理，其是衡量最优在线算法的重要工具。课程的难点包括：1）线性规划的对偶问题；2）图算法的社群划分问题；3）NPC问题的证明；4）近似算法和在线算法的近似度和竞争度分析；5）随机算法的算法的概率分析。六．教学方法本课程主要采用教师讲授、课堂讨论、学生自学、课堂练习及期末考试相结合的方法，灵活运用多种教学手段，如MOOC课程（B站）、多媒体辅助教学、课堂互动教学等，同时注重知识传授上的整体性和连贯性，让学生能够从该课程的应用领域，逐渐了解到知识点，最后深入到该领域的知识体系，通过课堂练习和讨论，提高学生的积极性，引导学生进行自主学习，提高学生对该研究领域的学习兴趣。七．考核方式期末考试+大作业（报告）。八.适用对象（说明此课程的开课对象是硕士或是博士等）开课对象：计算机和网络安全专