布尔可满足性问题
可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布尔可滿足性問題（Boolean satisfiability problem；SAT ）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多的領域皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。 直观描述 对于一个确定的逻辑电路，是否存在一种输入使得输出为真。 参见 NP-comple…
标签：#形式方法
共 24 篇文章
先决条件
在计算机编程中，先决条件或先验条件指在执行一段代码前必须成立的条件。 如果先决条件被违反了，则代码将产生未定义行为，因此其预期的工作能否履行也是未知的。不正确的先决条件还可能引发安全问题。 通常，先决条件包括在关于这段代码的文档中。有时它可通过特定的语法结构（如卫语句或断言）在代码中进行检测。 例如，阶乘只定义于自然数（大于等于零的整数）。因此计算阶乘的程序将会假定输入的值是一个整数，并且它大于等于零，这就是一个先决条件。 在面向对象编…
后置条件
在计算机编程中，后置条件指在执行一段代码后必须成立的条件或谓词。 例如，阶乘的结果应该是大于等于1的整数。 在面向对象编程中 面向对象编程中后置条件是契约式设计的一个重要组成部分。契约式设计还包括先决条件 和不变条件的概念。 被调用的子程序以后置条件来反馈给调用者。 后置条件与继承 在继承的关系中，继承了子程序的子类必须满足锲约。子类中重新定义的子程序可以加强后置条件，但不能削弱。 参见 契约式设计 卫语句 先决条件 霍尔逻辑 * 不变…
Set packing
Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一個NP-完全問題之一。 题目描述 给定一个有限集合 S 和一些 S 的子集，求问是否可以其中的 k 个子集，他们两两不相交。 形式化的定义：给定全集\mathcal{U}，和\mathcal{U}的一组子集\mathcal{S}。packing指一个集合\mathcal{C}满足\mathcal{C}\subseteq\mathcal{S}且\ma…