高级算法设计与分析(徐小华) 2021秋  课程号:COMP7102P01
2021秋  课程号:COMP7102P01
(暂无评价)
(暂无评价)
  • 课程难度:你猜
  • 作业多少:你猜
  • 给分好坏:你猜
  • 收获大小:你猜
选课类别:基础 教学类型:理论课
课程类别:研究生课程 开课单位:计算机科学与技术系
课程层次:博士   学分:3.0
课程主页:暂无(如果你知道,劳烦告诉我们!)
简介 最后更新:

本课程主要包括随机算法、近似算法、在线算法三部分。

  1. 随机算法:通过设计各种随机采样等方法解决计算机领域的复杂的算法、优化问题,如均匀采样、自适性采样方法,包括相关的理论分析、概率证明、算法设计等。包括:
    1. 随机图模型与算法
    2. 马尔可夫链与随机游走理论
    3. 蒙特卡洛算法,近似采样,以及近似计数理论
    4. 平衡分配理论与算法
  2. 近似算法:主要针对现实世界大部分NP-hard问题,通过各种算法设计上的技巧,将问题目标简化成可以在多项式时间内解决的优化问题,进而分析解的近似比,结合随机算法,讨论达到近似比的成功概率等问题。包括:
    1. 最小费用最大流问题的近似算法
    2. 度量空间、欧式空间的旅行商问题近似算法
    3. 高维几何优化算法,随机投影、体积估计、近邻查询等
    4. 线性规划、二次规划、半正定规划等优化问题的解法
    5. APX-hard, Exponential Time Hypothesis, 通信复杂度,细粒度复杂度等近似复杂度理论
  3. 在线算法:主要针对数据没有预先存储在内存里,而是通过在线数据流的形式输入的情况。在线算法主要考虑设计动态数据结构,实现快速更新,减少对存储空间的需求,同时保证结果的准确性。一部分在线算法需要的算法设计技巧也包含在随机算法和近似算法里。包括:
    1. 在线paging问题及相关算法
    2. k-server问题及相关算法
    3. 多臂老虎机问题及相关算法
    4. ski rental问题及相关算法

还没有评论耶!放着我来!

徐小华

教师主页: 戳这里

其他老师的「高级算法设计与分析」课

徐小华, 陈雪 5.0 (3) 2024秋 2023秋...

徐小华老师的其他课

计算机程序设计A 8.7 (6) 2021秋
计算机程序设计A 8.8 (4) 2023秋 2022秋...
算法设计与分析 7.8 (8) 2023秋
算法设计与分析 7.7 (7) 2023秋
高级算法设计与分析 5.0 (3) 2024秋 2023秋...
计算机程序设计B 1.0 (1) 2022秋