C

算法设计与分析-教学大纲

algorithms design and analysis

Posted by xuepro on February 20, 2021

一、介绍

  • 算法:
    • 什么是算法
      算法是解决一类问题或某个计算的过程(方法),算法包含有限步可行的明确的操作。
      问题: 2个整数相加(乘)、计算圆周率、计算圆的面积、求一组数中的最大值。
      算法接受问题的输入数据、产生输出结果。
      问题实例:一类问题的一个具体问题。
      “求一组数中的最大值”的问题实例如: 5,2,3,9,4   
      
    • 算法解决问题的过程:
       设计(定义算法的操作)、
       分析(算法的正确性(正确解决问题的需求)、算法的性能(空间和时间消耗))。
      
    • 同一问题可以有不同的算法: 排序
    • 算法有什么用(哪些应用)?
      ```
      1. 是计算机学科的主干:每个计算机科学分支都以算法为核心。 operating systems and compiles:进程调度、词法分析 networking:如路由算法、搜索引擎 machine learning and AI:各种机器学习算法如神经网络层、随机森林、支持向量机、智能算法 cryptography: 密码算法、数论算法 computational biology:动态规划、机器学习 computer Graphics: 计算几何、光照渲染、流体仿真、动画、
      2. 算法非常有用: 计算速度取决于硬件和算法。 深度学习/现代人工智能、电子商务/自媒体平台的推荐算法、算法决定思维(算法喂料洗脑)。
      3. 算法有趣: 创造性的数学活动,有趣也有挑战,有挑战才激动人心。如 a^n、大整数乘法 ```
  • 算法设计:技术(设计模式)、艺术(创造性思维)
    • 算法设计的策略(模式、技术):

      1. 穷举法(迭代法): 列举所有可能情况。求最大值、n!、a^n、斐波拉契数列、平面点集的最近点对。
      2. 贪婪法: 找零钱、图的Dijsktra最短路径算法
      3. 分治法: 大问题分解成小问题(Divid),解决小问题(Conqour)、组合小问题解为大问题的解(Combine)
        • n!、斐波拉契数列、汉诺塔、大整数相乘、a^n、选择排序、冒泡排序、快速排序、归并排序
      4. 动态规划:
    • 算法的表示(描述):自然语言、伪代码

  • 算法分析
    • 时间复杂度:最好、最坏、平均
    • 空间复杂度
  • 渐进分析
    • 渐进符号: $O,\Omega,\Theta,o,\omega$
    • 递推方程: 迭代展开、递归树、主定理、假设验证(数学归纳法)。
    • P和NP:算法复杂度和问题复杂度,P问题和NP问题

二、分治递归

  1. 分治法:
    • 思想、分类、算法描述、性能分析
    • 选最大与最小:分组、分治递归
  2. 二分查找、归并排序、汉诺塔
  3. 幂乘算法及其应用
  4. 整数乘、矩阵乘:减少子问题的数量
  5. 快速排序
  6. 选择问题(第k个)
  7. 最大子序列和(最大字段和)
  8. 最近点对
  9. 棋盘覆盖
  10. 循环赛日程表

三、动态规划法

  1. 动态规划 Fibonacci数列、
  2. 序列比对
  3. 矩阵链乘法
  4. 加权区间调度(weighted interval Scheduling)
  5. 背包问题
  6. 最长公共子序列
  7. 最大子序列和(最大字段和)
  8. 凸三角形最有剖分
  9. 最优二叉搜索树
  10. 图像压缩

四、贪婪法

  1. 活动选择/区间调度(activity selection/Interval Scheduling)
  2. 找零钱
  3. 分数背包问题
  4. 断点选择
  5. 哈夫曼编码
  6. 任务调度(task Scheduling)
  7. Dijkstra最短路径算法
  8. 最小生成树

五、回溯法与分支定界

  1. 回溯法
  2. 图的着色
  3. 分支定界
  4. 最大团问题
  5. 旅行售货员问题

六、网络流算法

  1. 二部图匹配
  2. 最大最小切

七、随机算法

  1. 数值随机化算法
  2. 舍伍德算法
  3. 拉斯维加斯算法
  4. 蒙特卡洛算法

支付宝打赏 微信打赏

您的打赏是对我最大的鼓励!