高级算法
点此进入:学习链接(下方link因为部署需要无法直接查看)
图论/离散基础
算法分析设计
该部份比较简单,因此不做详细介绍,仅提供一个目录和部份知识点。
图灵机与P/NP/NPC
列表项中带有 未完成
前缀的问题只描述了问题,没有说明具体证明过程;带有 完成
前缀的问题描述了问题和核心解决思路,但省略了具体证明过程的;没有符号的问题同时包含了问题和具体证明过程,其中部份额外附注了核心思路。(下同)
NPC 问题证明(按照证明方法排序)
NPC 问题证明(按照证明难度排序)
以下为分级后的题目难度,可能略有出入,建议掌握所有2分及以下的题目,同时了解所有分数题目的实例形式:
难度分级按照 0-5 分评级:
- 0分:绝对无任何难度的,一般由等价问题直接归约,只需要理解相关基础概念的问题。
- 1分:非绝对无难度的,不能说一点难度没有,但也不能认为有多少难度,仅能依靠非0分的状态在坐标中定位,这种暧昧的状态被定为 1分,一般由有限步易得条件推导得到。
- 2分:有难度的最低值,但无法对其强弱进行判定,有难度的最低测度。一般是证明存在一定篇幅,但相对理解可以通过举例较为容易的理解的归约。
- 3分:很标准的难,一般是需要大段描述,且中间穿插多个定理,但推演逻辑相对单一线性,且能够通过更简单的描述理解思想的归约。
- 4分:标准之上的难,缺少可以可视化的例子,需要引入许多的符号、公式、定理,只能通过硬核的推导来结束证明。
- 5分:具有侵略性的难。目前仍然未被证明的难题。这暂时不会出现在本项目中。
该评级策略参照某定标法略做更改而来,具体链接已经找不到了。个人认为这是主观评分的一个非常棒的标准。
其他
近似算法
Reference
Contributor