算法分析与理论第一课笔记

课程介绍

算法的研究目标

• 第一层次
  • 算法设计技术
  • 算法分析方法
• 第二层次
  • 问题计算复杂度分析
• 第三层次
  • 计算复杂性理论
    • 关注更宏观层面
    • 关注问题的难度
    • 计算复杂性边界

讲授主要内容（按章）（斜体为线上学习）

• 算法分析基础
• 动态规划法
• 回溯法
• 分支限界法
• 计算复杂性理论
• 近似算法
• 概率算法

参考书目

• 📷️
• （算法圣经）《Introduction to Algorithm (3rd Ed)》
• ⭐️（算法圣经）《算法导论（第三版）》
• 《算法设计与分析（第5版）》
• 选择一个就可以

教学目的

• 算法设计方法与理论，知识体系
• 计算复杂性分析能力
• 独立设计和分析算法的理论基础

教学方式

• 线上学习
  • 学堂在线
    • 算法分析基础（部分）
    • 动态规划法
    • 回溯法
    • 分支限界法
    • 近似算法
  • 雨课堂
• 线下

考核方式

^3d75f5

• 平时成绩40%
  • 雨课堂视频等50%
  • 考勤（雨课堂）50%
  • 课堂讨论40%
• 期末大作业60%

课堂讨论要求

1. 分组与时间节点：6-7人一组；第10周末提供分组名单与选题（腾讯文档填写），第12周开始讨论；
2. 选一种算法（见以下PPT）进行学习；
3. 学习内容：算法基本思想、适用场景、优缺点、解决案例、实验与结果分析、对比等；
4. 讨论时间与内容：每组10分钟左右，以PPT形式展示分工与学习内容；
5. 第14周末提交讨论的文档，包括PPT以及文档材料、源码、分工情况。

• 算法的对比
  • 纵向
  • 横向

各种算法（课堂讨论选择算法时参考）

• 深度强化学习算法
• 元学习（含元强化学习）算法
• 群智能优化算法
• 经典机器学习算法（至少要了解吧，不能说没听说啊）
• 各种降维算法

一些Q&A

经典算法与新兴算法的关联

• 分治法与深度神经网络
  • 思想
    • 分解为子问题、最终合并
  • 关联
  • 应用
    • 利用将神经网络任务分为多个部分，并行处理
• 动态规划与深度神经网络
  • 思想
  • 关联
  • 应用
• 贪心法与深度神经网络
  • 关联
    • 模型压缩
    • 特征选择
• 回溯法与…
• 分支限界法与…

深度强化学习算法

概念

• 深度学习
• 强化学习
• 深度强化学习
  • 深度学习的感知能力
  • 强化学习的决策能力

各类深度强化学习算法

分类

• 基于模型（Model-based methods）
  • 给定模型
  • 学习模型
• 无模型模型（Model-free methods）
  • 基于价值
  • 基于策略

典型算法

• DQN
• AC

应用