Week 1Introduction to Formal Methods & Program Correctness
### 📖 核心知识点：形式化方法与程序正确性导论 课程介绍为什么需要形式化方法来保证软件正确性。学习 Formal Specification 和 Formal Verification 的基本概念。回顾命题逻辑 (Propositional Logic) 和谓词逻辑 (Predicate Logic) 的基础知识，这是后续所有形式化推理的数学基础。 - **核心概念/公式**: Partial Correctness vs Total Correctness、Formal Specification 的目标、逻辑连接词 (∧, ∨, ¬, →, ↔)、全称量词 ∀ 和存在量词 ∃ ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 8h（Lecture 2h + Applied Class 1h + 自学 5h） 🎯 **考试关联**: Final Exam (50%) 的逻辑推理部分基于本周的逻辑基础。 🧪 **Tutorial/Lab**: 练习命题逻辑和谓词逻辑的基本推导，复习数学证明的常用技巧。 📌 **作业关联**: Assignment 1 需要用到逻辑推理基础，本周必须打好基础。 ⚠️ **易错点**: 蕴含 (→) 当前件为假时整个蕴含为真，这与直觉相悖；全称量词的否定变成存在量词 ¬∀x.P(x) ≡ ∃x.¬P(x)。 （数据来源：2025 S1 UQ Course Profile + GitHub Formal-Methods-Courses，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第1周生成 5 道练习题并给出解题步骤
Week 2Hoare Logic & Hoare Triples
### 📖 核心知识点：霍尔逻辑与霍尔三元组 学习 Hoare Logic 的核心框架。掌握 Hoare Triple {P} S {Q} 的含义：如果 Precondition P 成立，执行语句 S 后，Postcondition Q 成立。学习 Assignment Axiom、Sequence Rule、Conditional Rule 等基本推理规则。 - **核心概念/公式**: Hoare Triple {P} S {Q}、Assignment Axiom {P[x/E]} x:=E {P}、Sequence Rule、Conditional Rule: {P∧B} S1 {Q}, {P∧¬B} S2 {Q} ⊢ {P} if B then S1 else S2 {Q} ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 6h） 🎯 **考试关联**: Hoare Triple 的推导是 Final Exam 的核心考点，通常占 20-30%。必须能手工推导。 🧪 **Tutorial/Lab**: 练习用 Assignment Axiom 和 Sequence Rule 推导简单程序的正确性。 📌 **作业关联**: Assignment 1 的主体内容围绕 Hoare Logic 推导。 ⚠️ **易错点**: Assignment Axiom 的替换方向是"向后推导" (backward reasoning)，不是"向前执行"；Precondition 的 Strengthening 和 Postcondition 的 Weakening 方向容易搞反。 （数据来源：2025 S1 UQ Course Profile + AssignmentChef 参考，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第2周生成 5 道练习题并给出解题步骤
Week 3Weakest Precondition Calculus
### 📖 核心知识点：最弱前条件演算 学习 Weakest Precondition (WP) 的概念——对于给定的程序 S 和后条件 Q，WP(S,Q) 是使 {P} S {Q} 成立的最弱（最宽松的）前条件。掌握 WP 对各种语句的计算规则：赋值、顺序、条件分支。理解 WP 在程序验证中的自动化优势。 - **核心概念/公式**: wp(x:=E, Q) = Q[x/E]、wp(S1;S2, Q) = wp(S1, wp(S2,Q))、wp(if B then S1 else S2, Q) = (B→wp(S1,Q)) ∧ (¬B→wp(S2,Q)) ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 7h）🔥 高压周 🎯 **考试关联**: WP 计算是 Final Exam 的高频考题。需要熟练计算各种语句组合的 WP。 🧪 **Tutorial/Lab**: Week 3 Exercises（Haskell 编程练习）— 用 Haskell 实现 WP 的自动计算。 📌 **作业关联**: Assignment 1 需要用 WP 推导验证程序正确性。 ⚠️ **易错点**: WP 计算的替换方向和 Hoare Axiom 一致（向后推导）；条件语句的 WP 需要两个分支的 WP 取合取；嵌套条件的 WP 计算容易在替换时出错。 （数据来源：2025 S1 UQ Course Profile + AssignmentChef Week 3 Exercises，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第3周生成 5 道练习题并给出解题步骤
Week 4Loop Invariants & While-Loop Verification
### 📖 核心知识点：循环不变量与While循环验证 学习如何验证含循环的程序。掌握 Loop Invariant (循环不变量) 的概念和寻找方法。学习 While Rule: {P∧B} S {P} ⊢ {P} while B do S {P∧¬B}。理解 Loop Invariant 需要满足的四个条件：Initialization, Maintenance, Termination, 和 Postcondition Implication。 - **核心概念/公式**: While Rule、Loop Invariant 的四个验证条件、wp(while B do S, Q) 需要用户提供 invariant ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 7h）🔥 高压周 🎯 **考试关联**: Loop Invariant 的寻找和验证是 Final Exam 的最难考点之一。需要大量练习。 🧪 **Tutorial/Lab**: Week 4 Exercises — 为经典算法（求和、阶乘、线性搜索）找到 Loop Invariant 并完成形式化证明。 📌 **作业关联**: Assignment 1 的核心挑战题通常涉及 Loop Invariant。 ⚠️ **易错点**: Loop Invariant 太强（导致无法证明 Initialization）或太弱（无法推出 Postcondition）；忘记 Invariant 在循环退出时要蕴含 Postcondition 且 Guard 为假。 （数据来源：2025 S1 UQ Course Profile + AssignmentChef Week 4 Exercises，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第4周生成 5 道练习题并给出解题步骤
Week 5Termination & Total Correctness
### 📖 核心知识点：终止性与完全正确性 从 Partial Correctness 扩展到 Total Correctness，证明程序不仅结果正确，而且一定会终止。学习 Variant (Bound Function / Ranking Function) 的概念——一个每次循环迭代严格递减且有下界的表达式。掌握 Total Correctness Rule: [P∧B∧t=z] S [P∧t0 保证终止、Total Correctness = Partial Correctness + Termination ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 6h） 🎯 **考试关联**: Termination proof 是 Final Exam 的常考内容。需要能同时提供 Invariant 和 Variant。 🧪 **Tutorial/Lab**: 为含循环的程序同时找到 Loop Invariant（正确性）和 Variant（终止性），完成 Total Correctness 证明。 📌 **作业关联**: Assignment 1 可能要求 Total Correctness 证明。 ⚠️ **易错点**: Variant 必须是整数值（不能是实数）；Variant 只需要在循环体内严格递减，不需要全局递减；嵌套循环需要分别证明内外层的终止性。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第5周生成 5 道练习题并给出解题步骤
Week 6Arrays & Data Structure Verification
### 📖 核心知识点：数组与数据结构验证 学习如何形式化验证操作数组和数据结构的程序。掌握 Array Assignment 的 Hoare 规则和 WP 计算。学习 Quantified Loop Invariants（含全称/存在量词的不变量）来表达数组属性（如排序、搜索、分区）。 - **核心概念/公式**: Array Update: a[i]:=E 的 WP 规则、Quantified Invariant: ∀j. 0≤j<i → a[j]≤a[j+1]（排序不变量示例）、Frame Condition: 数组未修改部分的保持 ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 7h）🔥 高压周 🎯 **考试关联**: 数组相关的 Loop Invariant 推导是 Final Exam 高难度题目的常见来源。 🧪 **Tutorial/Lab**: 验证 Binary Search、Insertion Sort 等经典算法的正确性。 📌 **作业关联**: Assignment 1 截止在即，可能包含数组验证题目。 ⚠️ **易错点**: 数组下标的边界条件 (off-by-one)；Quantified Invariant 中量词的范围写错；忘记 Frame Condition（证明数组未被修改的部分仍保持原值）。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第6周生成 5 道练习题并给出解题步骤
Week 7Refinement Calculus Introduction
### 📖 核心知识点：精化演算导论 学习 Refinement Calculus — 从抽象规约 (Abstract Specification) 系统地推导出可执行程序的方法。掌握 Specification Statement [P, Q] 的含义和精化关系 (⊑)。学习精化规则：Sequential Composition Refinement、Assignment Introduction、Conditional Introduction。 - **核心概念/公式**: Specification Statement [P, Q]、Refinement 关系 S1 ⊑ S2 (S2 至少与 S1 一样好)、Monotonicity of Refinement ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 6h） 🎯 **考试关联**: Refinement 的概念和基本规则是 Final Exam 的考查内容。 🧪 **Tutorial/Lab**: 从简单规约出发，用精化规则一步步推导出可执行程序。 📌 **作业关联**: Assignment 2 可能涉及 Refinement Calculus 的应用。 ⚠️ **易错点**: Refinement 是单向关系，S1⊑S2 不意味着 S2⊑S1；精化过程中引入的实现细节必须满足原始规约的所有约束。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第7周生成 5 道练习题并给出解题步骤
Week 8Dafny Verification Tool
### 📖 核心知识点：Dafny自动化验证工具 学习 Dafny — 微软开发的程序验证语言和工具。掌握 Dafny 的语法：method、function、predicate、requires/ensures (前/后条件)、invariant、decreases (终止度量)。学习如何将手工证明转换为 Dafny 自动验证。 - **核心概念/公式**: Dafny method 的 requires/ensures 子句、loop invariant 声明语法、decreases 子句用于终止证明、ghost variables 的辅助证明作用 ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 7h） 🎯 **考试关联**: Dafny 语法和验证方法在 Final Exam 中可能出现代码阅读题。 🧪 **Tutorial/Lab**: 在 Dafny 中实现并验证之前手工证明过的算法（求和、搜索、排序）。 📌 **作业关联**: Assignment 2 要求使用 Dafny 完成自动化验证。 ⚠️ **易错点**: Dafny 的 ensures 和 requires 关键字拼写错误不会报语法错但验证会失败；invariant 不够强导致 Dafny 无法自动证明；忘记 decreases 子句导致终止性证明失败。 （数据来源：2025 S1 UQ Course Profile + GitHub Formal-Methods-Courses，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第8周生成 5 道练习题并给出解题步骤
Week 9Recursive Programs & Structural Induction
### 📖 核心知识点：递归程序与结构归纳法 学习递归程序的形式化验证方法。掌握 Structural Induction 在递归数据结构（链表、树）上的应用。学习递归函数的 Pre/Post Condition 规约和终止性证明（递归参数严格递减）。 - **核心概念/公式**: Structural Induction: Base Case + Inductive Step、递归函数的 decreases 子句必须在每次递归调用时严格减小 ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 6h） 🎯 **考试关联**: 递归程序验证和结构归纳是 Final Exam 的可能考点。 🧪 **Tutorial/Lab**: 在 Dafny 中验证递归算法（如 Fibonacci、Tree Traversal、Merge Sort）。 📌 **作业关联**: Assignment 2 可能包含递归程序验证。 ⚠️ **易错点**: 结构归纳的归纳假设应用范围搞错；递归函数的终止度量需要选择合适的"大小"概念（如列表长度、树高度）；Dafny 的 function 和 method 的区别（function 是纯函数，不能有副作用）。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第9周生成 5 道练习题并给出解题步骤
Week 10Abstract Data Types & Object Invariants
### 📖 核心知识点：抽象数据类型与对象不变量 学习如何形式化规约 Abstract Data Types (ADT)。掌握 Object Invariant (类不变量) 的概念——对象在每个公开方法调用前后都必须满足的属性。学习 Representation Invariant 和 Abstraction Function 的定义方法。 - **核心概念/公式**: Class Invariant: 每个 public method 的 implicit pre/post condition、Representation Invariant: 内部数据结构的合法性条件、Abstraction Function: concrete → abstract 的映射 ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 6h） 🎯 **考试关联**: ADT 规约和 Object Invariant 的理解在 Final Exam 中可能出现。 🧪 **Tutorial/Lab**: 在 Dafny 中定义带 Invariant 的 Class（如 Stack、Queue、Priority Queue），验证所有方法保持不变量。 📌 **作业关联**: Assignment 2 的高级部分。 ⚠️ **易错点**: Object Invariant 在构造函数结束时必须成立（不是在构造过程中）；Abstraction Function 不是一对一映射（多个 concrete 状态可以映射到同一个 abstract 状态）。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第10周生成 5 道练习题并给出解题步骤
Week 11Advanced Verification Techniques
### 📖 核心知识点：高级验证技术 学习更高级的程序验证技术：Ghost Code（辅助证明的幽灵代码）、Lemma Functions（辅助引理）、Automated vs Interactive Theorem Proving 的比较。了解形式化验证在工业界的实际应用案例（如 seL4 微内核、CompCert 编译器）。 - **核心概念/公式**: Ghost Variables/Methods: 只在验证时存在，编译后消除、Lemma: 可调用的已证明命题、SMT Solver (Z3) 的工作原理简介 ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 6h） 🎯 **考试关联**: 高级验证概念和工业应用案例可能在 Final Exam 中作为分析题出现。 🧪 **Tutorial/Lab**: 使用 Ghost Code 和 Lemma 完成复杂数据结构的验证。 📌 **作业关联**: Assignment 2 截止提交。 ⚠️ **易错点**: Ghost Code 不能影响程序的实际执行路径（只能出现在 assert/invariant 中）；过度依赖 SMT Solver 而不理解证明原理会在需要手动引导时卡住。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第11周生成 5 道练习题并给出解题步骤
Week 12Course Review & Exam Preparation
### 📖 核心知识点：课程总复习与考试准备 课程整体回顾，串联从 Hoare Logic → Weakest Precondition → Loop Invariants → Termination → Refinement → Dafny 的完整知识链。重点复习考试高频题型：Hoare Triple 推导、WP 计算、Loop Invariant 寻找、Dafny 代码分析。 - **核心概念/公式**: 全课程知识地图、各推理规则的速查表、常见算法的标准 Loop Invariant 模板 ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 7h）📝 复习周 🎯 **考试关联**: Final Exam (50%) 覆盖全部内容。重点：Hoare Logic 推导 (30%)、Loop Invariant (20%)、Dafny (20%)、Refinement (15%)、基础概念 (15%)。 🧪 **Tutorial/Lab**: 最后一次 Applied Class，做往年真题模拟和疑难点答疑。 📌 **作业关联**: 所有作业已截止，专注备考。 ⚠️ **易错点**: 考试时间紧张，需要提前练习手写推导的速度；Hoare Logic 和 WP 两种方法可以互换使用，选择更简洁的方式；考试不允许使用计算器和电子设备。 （数据来源：2025 S1 UQ Course Profile，CSSE3100）
LecturesLectureswillbeusedtointroducenewcoursecontent.
💡 学习提示
• 总结 Lectures Lectures will be used to introduce new course content. 的核心概念与适用场景
• 为第12周生成 5 道练习题并给出解题步骤
