सामग्री पर जाएँ
The Lumenary
स्नातकोत्तर प्रथम वर्षComputationनियोजित

Formal methods

Mathematical methods for specifying and verifying software and hardware: operational and denotational semantics, Hoare logic, model checking, type soundness, and proof assistants for verified programs.

math.comp.formal-methods

इस विषय तक पहुँचने के लिए आवश्यक सब कुछ दिखाएँ

इस विषय का पाठ अभी लिखा नहीं गया है। नीचे दी गई रूपरेखा पाठ्यक्रम-मानचित्र का हिस्सा है और इसकी समीक्षा नहीं हुई है।

इस पर आधारित

First-order logicThe λ-calculusAlgorithm design and analysis

21 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)

आप सीखेंगे

  • Give an operational semantics for a small imperative language and prove properties by induction on derivations.
  • Verify programs with Hoare triples and loop invariants.
  • Model-check finite-state systems against temporal-logic specifications.

परिभाषा

  • A Hoare triple {P} C {Q} asserts that if P holds before command C runs and C terminates, then Q holds afterwards.
  • Model checking algorithmically decides whether a finite model satisfies a temporal-logic formula.
  • A type system is sound if well-typed programs cannot reach a stuck state (progress and preservation).

प्रमेय

  • Hoare logic is sound, and it is relatively complete for suitable languages (Cook).
  • CTL model checking can be done in time linear in the product of the sizes of the model and the formula.
  • By Rice's theorem, verifying arbitrary properties of arbitrary programs cannot be fully automated.

आम भ्रांतियाँ

  • Thinking a verified program is correct in every sense; it is correct relative to its specification and its trusted base.
  • Believing partial correctness implies termination.

वैकल्पिक खोजें

अधिगम पथ

आगे पढ़ने के लिए

  • Glynn Winskel, The Formal Semantics of Programming Languages (1993)
  • Michael Huth and Mark Ryan, Logic in Computer Science
  • Christel Baier and Joost-Pieter Katoen, Principles of Model Checking (2008)