算法设计与分析

课程信息

课程名称／课程号	适用范围与修读要求
算法设计与分析 CS3186M	车辆 · 26级专业选修 · 模块选修（智能车辆）车辆 · 26级专业选修 · 模块选修（绿色动力）

展开查看

（一）中文简介本课程为海外教师主导的全英文课程。主要研究算法设计理论与分析方法。课程内容包括经典算法的深入学习，如排序和选择、最大流、匹配、计算生物算法、机器学习、随机算法、计算复杂性及不可近似性理论、蛋糕分割机制等。

来源：教务网。

1）课堂表现 10%2）家庭作业 20%3）程序设计 20%4）期末练习 50%

展开查看

根据海外教师的具体安排，采用线上线下结合的形式进行教学。下面的教学内容亦会适当调整。

2、最大流、匹配（4课时）：最大流最小割，最小费用流等网络算法

3、计算生物算法（4课时）：序列调整，motif发现，字符串匹配，稳定匹配

4、在线算法（4课时）：学习在线算法设计的基本元素、算法设计的基本技巧

5、机器学习（4课时）：基础知识，学习理论，监督学习

6、蛋糕分割等博弈问题（4课时）：介绍算法博弈论，通过切蛋糕的机制设计学习算法博弈论

7、随机算法（4课时）:基础概率方法，拉斯维加斯和蒙特卡洛方法，随机选择，奖券收集问题

8、计算复杂性及不可近似（4课时）：复杂性基础知识，多项式归约, 近似算法，不可近似性

CC98 原帖需登录访问。