算法设计与分析

课程编码：180086085404P2004H 英文名称：Algorithm Design and Analysis 课时：60 学分：3.00 课程属性：专业核心课 主讲教师：马丙鹏

本课程为计算机技术专业硕士的核心课程。本课程讲授算法设计的基本思想、设计策略与技巧，算法的复杂性分析技术。主要内容有分治算法、贪心算法、动态规划算法、回溯算法、分枝限界算法、线性规划算法、网络流算法、NP难问题、近似算法及其概率算法等经典算法等。
通过本课程的学习，希望学生能掌握常用经典算法的基本设计思想和策略，能够将实际问题抽象成算法问题，分析与界定问题的难度，设计求解算法；掌握算法的复杂性分析技术；了解算法与分析前沿研究领域，了解最新研究成果。为选课学生建立良好的算法理论概念模型，培养学生解决实际问题的能力。

离散数学基础知识，数据结构基础知识，程序设计语言C/C++

第一章 算法引论 马丙鹏
第1节 算法的定义 1.0学时
第2节 复杂性分析初步 1.0学时
第3节 递归 1.0学时
第二章 图与遍历算法 马丙鹏
第1节 图的基本概念和性质 1.0学时
第2节 图上遍历算法 1.5学时
第3节 双连通与网络可靠性 1.5学时
第三章 分治算法 马丙鹏
第1节 一般方法 1.0学时
第2节 二分检索 1.0学时
第3节 找最大和最小元素 1.0学时
第4节 归并排序 1.0学时
第5节 快速排序 1.0学时
第6节 选择问题 1.0学时
第7节 斯特拉森矩阵乘法 1.0学时
第四章 贪心算法 马丙鹏
第1节 一般方法 1.0学时
第2节 背包问题 1.0学时
第3节 带有限期的作业排序 1.0学时
第4节 最优归并模式 1.0学时
第5节 最小生成树 1.0学时
第6节 单源点最短路径 1.0学时
第五章 动态规划算法 马丙鹏
第1节 一般方法 1.0学时
第2节 多段图问题 1.0学时
第3节 每对结点之间的最短路径 1.0学时
第4节 最优二分检索树 1.0学时
第5节 0/1背包问题 1.0学时
第6节 可靠性设计 1.0学时
第7节 货郎担问题 1.0学时
第8节 流水线调度问题 1.0学时
第六章 回溯法 马丙鹏
第1节 一般方法 1.0学时
第2节 8-皇后问题 1.5学时
第3节 子集和数问题 1.5学时
第4节 图的着色问题 1.0学时
第5节 0/1背包问题 1.0学时
第七章 分枝-限界算法 马丙鹏
第1节 一般方法 1.0学时
第2节 LC-检索 1.0学时
第3节 15-谜问题 0.5学时
第4节 LC-检索(续) 1.0学时
第5节 分枝-限界算法 1.0学时
第6节 0/1背包问题 1.0学时
第7节 货郎担问题 0.5学时
第八章 蛮力法 马丙鹏
第1节 概述 0.5学时
第2节 串匹配问题 1.5学时
第九章 计算复杂性分析 马丙鹏
第1节 复杂性分类 1.0学时
第2节 P 类问题和 NP 类问题 1.0学时
第3节 NP 完全问题 1.0学时
第十章 近似算法 马丙鹏
第1节 概述 0.5学时
第2节 图问题中的近似算法 0.5学时
第3节 组合问题中的近似算法 1.0学时
第十一章 概率算法 马丙鹏
第1节 概述 1.0学时
第2节 舍伍德型概率算法 1.0学时
第3节 拉斯维加斯型概率算法 1.0学时
第4节 蒙特卡罗型概率算法 1.0学时
第十二章 线性规划 马丙鹏
第1节 数学模型 1.0学时
第2节 图解法 1.0学时
第3节 标准型 1.0学时
第4节 基本概念 1.0学时
第5节 单纯形法 1.0学时
第十三章 最大流 马丙鹏
第1节 基本概念 0.5学时
第2节 Ford-Fulkerson标号算法 1.0学时
第3节 割集与割量 1.0学时
第4节 最小费用流 1.0学时
第5节 最大流应用举例 0.5学时

马丙鹏，中国科学院大学，计算机科学与技术学院，教授，博士生导师。2009年在中国科学院计算技术研究所获工学博士学位。2009年9月至2013年3月期间任教于华中科技大学计算机科学与技术学院，2011年至2012年期间在法国卡昂诺曼底大学从事博士后研究。主要研究方向包括模式识别理论与应用、计算机视觉、人工智能和机器学习，尤其关注人体身份再识别、行人检测、行人跟踪、人脸识别和头部姿态估计等方面的研究。先后在包括IEEE T-PAMI、IEEE T-IP、CVPR和ICCV等本领域权威国际期刊与会议上发表学术论文80余篇，谷歌学术引用4000次。作为第一完成人荣获2018年中国计算机学会科学技术奖自然科学二等奖，指导研究生获得ICME2018白金最佳论文奖，ECCV2018行人检测竞赛冠军。中国计算机学会高级会员，青年计算机科技论坛(YOCSEF)学术委员,青年工作委员会委员。