第 1 週 9/6 Introduction: Reasoning about Programs; Fundamentals: Propositional and…
- User
第 1 週 9/6 Introduction: Reasoning about Programs; Fundamentals: Propositional and First-Order Logics 第 2 週 9/13 Fundamentals: Propositional and First-Order Logics 第 3 週 9/20 Fundamentals: Propositional and First-Order Logics 第 4 週 9/27 Verification Tools: Coq 第 5 週 10/4 Verification Tools: Coq 第 6 週 10/11 Sequential Programs: Hoare Logic (I) 第 7 週 10/18 Sequential Programs: Hoare Logic (I) 第 8 週 10/25 Predicate Transformers 第 9 週 11/1 Procedures: Hoare Logic (II) 第 10 週 11/8 Verification Tools: Frama-C + Plugins 第 11 週 11/15 NTU Anniversary, no class meeting 第 12 週 11/22 Verification Tools: Frama-C + Plugins 第 13 週 11/29 Concurrent, Reactive Systems: Owicki-Gries Method 第 14 週 12/6 Concurrent, Reactive Systems: UNITY and Linear Temporal Logic 第 15 週 12/13 Selected Topics: Modular/Compositional Reasoning
從以上課表整理出我會學會那些技術與相關應用
- Assistant
根據你提供的課表,這門課主要聚焦在程式正確性驗證(program verification)的理論與工具,將涵蓋邏輯基礎、形式化方法,以及實際驗證工具的使用。以下是你將學會的技術分類與應用方向整理:
✅ 一、邏輯基礎(9/6~9/20) 主題:
命題邏輯(Propositional Logic)
一階邏輯(First-Order Logic, FOL)
你會學到的技能:
使用形式邏輯表示與推理程式的性質(例如:條件、迴圈不變式、資料結構性質)
轉換程式語句為邏輯語句,進而進行形式推理與驗證
應用場景:
程式分析與靜態檢查工具的邏輯推理核心
自動定理證明與 SMT 求解器的使用背景(Z3、CVC4)
✅ 二、程式驗證工具:Coq(9/27~10/4) 主題:
Coq 定理證明器
你會學到的技能:
使用 Coq 表示數學定義、引理與定理
編寫證明腳本(tactic-based proof)
建立與驗證小型程式的正確性(甚至是遞迴定義)
應用場景:
認證演算法與資料結構(如:排序演算法正確性)
編譯器驗證(如 CompCert)
數學定理形式化(如四色定理、Feit–Thompson)
✅ 三、順序程式驗證:Hoare Logic(10/11~11/1) 主題:
Hoare 三元組(Hoare Triples):{P} C {Q}
程序與副程序驗證(Procedures, Local Variables)
Predicate Transformers(如:WP、SP)
你會學到的技能:
為命令式程式撰寫前後條件
推導 loop invariant,並驗證其正確性
使用 weakest precondition 形式化導出條件
應用場景:
對迴圈與分支語句進行正確性推理
實作靜態分析器與自動驗證工具的理論基礎
✅ 四、驗證工具:Frama-C 與 Plugins(11/8~11/22) 主題:
Frama-C 靜態分析平台
使用 ACSL 撰寫程式規格
搭配插件(如 WP, EVA, Value Analysis)分析 C 程式
你會學到的技能:
將 C 程式加上形式規格(pre/post conditions, loop invariants)
使用自動或半自動方式驗證程式的行為是否符合規格
分析可能的錯誤(例如:記憶體錯誤、未初始化、越界等)
應用場景:
嵌入式系統開發中的安全性驗證
航太、醫療等關鍵領域的高信賴軟體開發
✅ 五、並行與反應式系統的邏輯(11/29~12/6) 主題:
Owicki-Gries 方法:處理共享變數的並行驗證
UNITY 與線性時序邏輯(LTL)
你會學到的技能:
對多執行緒或並行程式進行干擾分析與正確性驗證
使用 LTL 描述反應式系統的時間性質(如:安全性、活性)
應用場景:
並行系統的形式驗證(如 mutex、deadlock-freedom)
通訊協定與分散式系統驗證(如 cache coherence、Paxos)
✅ 六、模組化與組合性推理(12/13) 主題:
Modular Reasoning(模組化推理)
Compositional Reasoning(組合性推理)
你會學到的技能:
分割複雜系統為小模組,單獨驗證後再合成
使用抽象規格與合約(contract)管理模組邊界
應用場景:
大型系統開發中逐步驗證各部分模組
實踐資訊隱藏與抽象資料型態驗證
📌 總結:你將學到的核心技術與工具 領域技術/工具應用形式邏輯Propositional / First-Order Logic理解與撰寫程式邏輯性質定理證明Coq定理與程式的互動式證明程式驗證邏輯Hoare Logic, WP, SP驗證循環、條件、函式正確性工具Frama-C + Plugins驗證 C 程式符合形式規格並行推理Owicki-Gries, UNITY, LTL驗證多執行緒與反應式行為模組化推理Modular Reasoning管理大型程式驗證複雜度 如果你未來有興趣往安全關鍵系統、形式驗證、或程式語言設計發展,這門課的內容非常紮實且實用。 如果你希望我幫你整理成學習計畫或筆記模板,也可以告訴我。