/AdAlgo

高级算法知识详解

Primary LanguageHTML

高级算法

点此进入:学习链接(下方link因为部署需要无法直接查看)

图论/离散基础

算法分析设计

该部份比较简单,因此不做详细介绍,仅提供一个目录和部份知识点。

  • 复杂度分析
  • 分治
  • 贪心
  • 动规
    • 划分问题
  • 回溯
  • 局搜

图灵机与P/NP/NPC

NPC 问题证明(按照归约顺序排序)

列表项中带有 未完成 前缀的问题只描述了问题,没有说明具体证明过程;带有 完成 前缀的问题描述了问题和核心解决思路,但省略了具体证明过程的;没有符号的问题同时包含了问题和具体证明过程,其中部份额外附注了核心思路。(下同)


NPC 问题证明(按照证明方法排序)

NPC 问题证明(按照证明难度排序)

以下为分级后的题目难度,可能略有出入,建议掌握所有2分及以下的题目,同时了解所有分数题目的实例形式:

难度分级按照 0-5 分评级:

  • 0分:绝对无任何难度的,一般由等价问题直接归约,只需要理解相关基础概念的问题。
  • 1分:非绝对无难度的,不能说一点难度没有,但也不能认为有多少难度,仅能依靠非0分的状态在坐标中定位,这种暧昧的状态被定为 1分,一般由有限步易得条件推导得到。
  • 2分:有难度的最低值,但无法对其强弱进行判定,有难度的最低测度。一般是证明存在一定篇幅,但相对理解可以通过举例较为容易的理解的归约。
  • 3分:很标准的难,一般是需要大段描述,且中间穿插多个定理,但推演逻辑相对单一线性,且能够通过更简单的描述理解**的归约。
  • 4分:标准之上的难,缺少可以可视化的例子,需要引入许多的符号、公式、定理,只能通过硬核的推导来结束证明。
  • 5分:具有**性的难。目前仍然未被证明的难题。这暂时不会出现在本项目中。

该评级策略参照某定标法略做更改而来,具体链接已经找不到了。个人认为这是主观评分的一个非常棒的标准。

其他

近似算法

Reference

Contributor