算法验证

默认只展示每周独有的知识重点；节奏、考核、Tutorial 和避坑信息按需展开。

1. 1

   形式化验证导论

   📖核心知识点：软件/硬件验证的动机——为什么测试不够？**形式化方法**的分类——模型检测（Model Checking）、定理证明（Theorem Proving）、抽象解释（Abstract Interpretation）。时序逻辑基础——命题逻辑回顾、Kripke 结构。⏰本周节奏：概念导入周，理解验证的意义与挑战。🎯考试关联：形式化方法分类与适用场景是基础考题。🧪Tutorial/Lab：安装 NuSMV/SPIN 等模型检测工具。📌作业关联：Assignment 1——模型检测。⚠️易错点：混淆验证（Verification）与确认（Validation）；低估状态空间爆炸问题的严重性。

2. 2

   线性时序逻辑 (LTL)

   📖核心知识点：**LTL (Linear Temporal Logic)**——时序算子 G（全局）、F（最终）、X（下一步）、U（直到）。LTL 公式的语义——在无穷迹（Infinite Trace）上的满足关系。常见性质的 LTL 表达——安全性（Safety: G¬bad）、活性（Liveness: GF good）、公平性（Fairness）。⏰本周节奏：LTL 是模型检测的理论基础。🎯考试关联：LTL 公式编写与语义判定是必考题（约 15 分）。🧪Tutorial/Lab：将自然语言性质翻译为 LTL 公式。📌作业关联：Assignment 1——LTL 建模。⚠️易错点：混淆 FG p 与 GF p 的含义；Safety vs Liveness 的分类判断错误。

3. 3

   计算树逻辑 (CTL)

   📖核心知识点：**CTL (Computation Tree Logic)**——路径量词 A（所有路径）、E（存在路径）+ 时序算子组合。CTL vs LTL 的表达力对比——CTL 无法表达某些 LTL 性质，反之亦然。CTL* 作为统一框架。CTL 模型检测算法——标记算法（Labeling Algorithm）的 O(|φ|·|S|·|R|) 复杂度。⏰本周节奏：深入理解分支时间逻辑。🎯考试关联：CTL 公式判定与模型检测算法执行是高频考题。🧪Tutorial/Lab：手动执行 CTL 标记算法。📌作业关联：Assignment 1——CTL 模型检测。⚠️易错点：CTL 中 AG 与 EG 的语义混淆；CTL 模型检测中不动点计算的终止条件。

4. 4

   模型检测实践

   📖核心知识点：**符号模型检测**——使用 BDD（Binary Decision Diagram）紧凑表示状态集。OBDD 的变量顺序对大小的影响。有界模型检测（BMC）——将验证转化为 SAT 问题。工具实践——NuSMV/SPIN 的使用。⏰本周节奏：从理论到工具实操。🎯考试关联：BDD 与 BMC 的原理是期末考试内容。🧪Tutorial/Lab：使用 NuSMV 验证互斥协议。📌作业关联：Assignment 1——工具实操。⚠️易错点：BDD 变量顺序选择不当导致爆炸；BMC 的完备性局限（只能发现有界反例）。

5. 5

   抽象解释

   📖核心知识点：**抽象解释 (Abstract Interpretation)** 框架——具体域与抽象域之间的 Galois 连接。常见抽象域——区间域（Interval Domain）、八边形域（Octagon Domain）、多面体域（Polyhedra Domain）。不动点计算与加宽算子（Widening）。抽象解释的安全性保证——Over-Approximation。⏰本周节奏：理论密度高，需仔细消化。🎯考试关联：抽象解释原理与区间分析是期末重点。🧪Tutorial/Lab：手动执行区间抽象分析。📌作业关联：Assignment 2——抽象解释。⚠️易错点：混淆 Over-Approximation 与 Under-Approximation；Widening 导致精度严重损失。

6. 6

   灵活性周 (Flex Week)

   📖核心知识点：无新内容。复习时序逻辑、模型检测、抽象解释的核心概念。完善 Assignment。⏰本周节奏：80% 作业，20% 复习。🎯考试关联：前 5 周约占期末 50%。🧪Tutorial/Lab：答疑。📌作业关联：Assignment 截止。⚠️易错点：工具使用中的语法错误导致验证结果不正确。

7. 7

   定理证明基础

   📖核心知识点：**交互式定理证明**——Isabelle/HOL、Coq 的基本概念。归纳证明（Induction）在程序验证中的应用。Hoare Logic——前置条件、后置条件、循环不变式。程序正确性的部分正确性（Partial Correctness）vs 完全正确性（Total Correctness）。⏰本周节奏：从自动化方法转向半自动化方法。🎯考试关联：Hoare Logic 推导是期末常考题型。🧪Tutorial/Lab：使用 Hoare Logic 证明简单程序的正确性。📌作业关联：Assignment 2——程序验证。⚠️易错点：循环不变式选择不当导致证明失败；混淆部分正确性与完全正确性的终止要求。

8. 8

   SAT/SMT 求解

   📖核心知识点：**SAT 问题**——布尔可满足性。DPLL 算法与 CDCL（Conflict-Driven Clause Learning）。**SMT (Satisfiability Modulo Theories)**——在理论（整数算术、数组、位向量）上的可满足性。Z3 求解器的使用。SAT/SMT 在验证中的应用——BMC、符号执行。⏰本周节奏：理解现代验证工具的核心引擎。🎯考试关联：DPLL 算法执行与 SMT 应用是可能的考题。🧪Tutorial/Lab：使用 Z3 编码并求解验证问题。📌作业关联：Assignment 2。⚠️易错点：CDCL 中学习子句的推导过程理解不透；SMT 理论组合的 Nelson-Oppen 方法。

9. 9

   并发系统验证

   📖核心知识点：并发程序的挑战——数据竞争、死锁、活锁。偏序归约（Partial Order Reduction）——减少状态空间探索。进程代数——CSP/CCS 的基本概念。SPIN 模型检测器与 Promela 建模语言的深入应用。⏰本周节奏：将验证技术应用于并发场景。🎯考试关联：并发系统的性质验证是可能的论述题。🧪Tutorial/Lab：使用 SPIN 验证并发协议（如 Dining Philosophers）。📌作业关联：Assignment 2 扩展。⚠️易错点：并发交错语义导致状态空间指数增长；偏序归约的适用条件限制。

10. 10

    前沿主题与总复习

    📖核心知识点：Runtime Verification——在运行时监控系统行为。形式化验证在工业界的应用——AWS（s2n-tls）、Intel（处理器验证）、航空航天（DO-178C）。AI 系统的验证挑战——神经网络验证。课程全景回顾。⏰本周节奏：总复习，整理验证技术体系。🎯考试关联：期末覆盖全部 10 周。🧪Tutorial/Lab：Mock Exam 与答疑。📌作业关联：所有作业已提交。⚠️易错点：只记工具用法不理解底层理论；忽略验证方法的局限性（不完备性、可扩展性）。