Skip to content
TheChatArchiveThe Chat Archive
ChatGPT (model unspecified)· OpenAIHugging Face ShareLM (browser-extension contributions)

第 1 週 9/6 Introduction: Reasoning about Programs; Fundamentals: Propositional and…

  1. 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

    從以上課表整理出我會學會那些技術與相關應用

  2. 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管理大型程式驗證複雜度 如果你未來有興趣往安全關鍵系統、形式驗證、或程式語言設計發展,這門課的內容非常紮實且實用。 如果你希望我幫你整理成學習計畫或筆記模板,也可以告訴我。