1.1 什么是算法

  • 在数学和计算机科学中，算法/算则法为一个计算的具体步骤，常用于计算、数据处理和自动推理。

  • 算法满足的条件

    • 有穷性/终止性：有限步内必须停止
    • 确定性：每一步都是严格定义和确定的动作
    • 能行性：每一个动作都能够被精确的机械执行
    • 输入：有一个满足给定约束条件的输入
    • 输出：满足给定约束条件的结果

      1.2 计算机科学中算法的位置

  • 算法是计算机科学基础的重要主题

  • 解决一个问题的过程

    • 可计算性
    • 能行可计算
    • 算法设计与分析
    • 计算机语言实现
    • 软件系统

      1.3 算法分析引论

  • 算法正确性：对于每一个输入都终止，产生的输出都正确

  • 算法复杂性：算法对不同输入所需资源量

    • 需要时间资源的量称为时间复杂度
    • 需要空间资源的量称为空间复杂度
    • 算法复杂性依赖于算法要解决问题的规模、算法的输入和算法本身

      1.4 算法设计引论

  • 算法设计模式

    • 暴力搜索
    • 分治法
    • 图搜索与枚举：分支界限、回溯
    • 随机化方法
  • 算法实现方法
    • 递归与迭代
    • 顺序、并行与分布式
    • 确定性与非确定性
    • 近似求解与精确求解
    • 量子算法
  • 最优化算法设计方法
    • 线性规划
    • 动态规划
    • 贪心法
    • 启发式方法