1验证、搜索与复杂度类
闭卷重建验证、搜索与复杂度类的对象、状态、事件、不变量与一个失败反例。
算法设计与分析 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2P、NP与NP-hard
闭卷重建P、NP与NP-hard的对象、状态、事件、不变量与一个失败反例。
3SAT与多项式归约
闭卷重建SAT与多项式归约的对象、状态、事件、不变量与一个失败反例。
4独立集、点覆盖与团
闭卷重建独立集、点覆盖与团的对象、状态、事件、不变量与一个失败反例。
5近似比与下界
闭卷重建近似比与下界的对象、状态、事件、不变量与一个失败反例。
6点覆盖二近似
闭卷重建点覆盖二近似的对象、状态、事件、不变量与一个失败反例。
7难解问题实验
闭卷重建难解问题实验的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：对P、NP与NP-hard先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为P、NP与NP-hard实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析P、NP与NP-hard时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对验证、搜索与复杂度类先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为验证、搜索与复杂度类实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析验证、搜索与复杂度类时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对独立集、点覆盖与团先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为独立集、点覆盖与团实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析独立集、点覆盖与团时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对SAT与多项式归约先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为SAT与多项式归约实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析SAT与多项式归约时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对点覆盖二近似先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为点覆盖二近似实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析点覆盖二近似时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对近似比与下界先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为近似比与下界实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析近似比与下界时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对难解问题实验先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为难解问题实验实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析难解问题实验时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。