正确性 (计算机科学)

✍ dations ◷ 2025-04-26 12:45:35 #理论计算机科学

在理论计算机科学中,算法的正确性(英语:correctness)是指一个算法在程序规范下被认定为正确的判定。其中,正确(英语:functional correctness)针对输入输出的行为(例如:对每一个输入,算法都能给出预期的输出)。

人们将正确性分为两类。一类被称为部分正确性(英语:partial correctness),它要求在算法返回结果时这一结果是正确的;另一类被称为完全正确性(英语:total correctness),它在部分正确性的基础之上还要求算法必须能够结束。由于对于停机问题没有通用的解决方案,因此判定完全正确性的断言有着更多需要深层次研究的地方。终止的证明是指一类数学证明,因为完全正确性需要证明一个算法会终止,所以它在程序的形式验证中起着至关重要的作用。

例如考虑这样一个问题:依次搜索整数列1, 2, 3, …来看是否存在某个特定现象——比如说存在一个奇数为完全数。对于这个问题而言,我们很容易写出一个部分正确的程序(直接对于每个数字做长除法判定其是否完全)。然而如果我们想证明这个程序是完全正确的,那就相当于我们在断言一个在数论里目前还未知的结论。

在算法和程序规范都是基于形式化来给出时,对正确性的证明应当为一个数学证明。然而我们并不期待能够给出特定机器上实现的特定程序的正确性断言,因为那样将需要考虑诸如内存限制在内的更多问题。

证明论中有一个结论柯里-霍华德同构。这一结论认为:任意一个在构造性逻辑下的功能正确性的证明都对应了一个λ演算程序。这种转换证明的方式被称为(英文:program extraction)。

霍尔逻辑是一个具体的能够严密验证程序正确性的形式系统。它用一系列的公理来定义程序语言的语义,从而通过称之为霍尔三元组的断言来验证程序的正确性。

软件测试是指验证一个程序或系统的某些属性或能力来判断它是否达到预期目的的行为。尽管软件测试在软件质量方面起着至关重要的作用,并且被程序员和测试员们广泛采用,但由于人们对软件的认识十分有限,它仍旧是一个艰深的领域。软件测试的最大难点在于如何控制其复杂性:我们没有办法在一个合理的复杂度内完整地测试一个程序。测试不只是调试。测试的目的包括但不限于确保软件质量、验证其正确性和估算其稳定性。我们对测试的定义也可以更加一般化,其中正确性测试和稳定性测试是两个最大的研究领域。软件测试是预算、时间和软件质量的一个平衡。

相关

  • 分离焦虑症分离焦虑症(SAD)是一种焦虑症,其中个体对于从家庭或个人对个体具有强烈情感依恋(例如父母,看护者,重要的其他或兄弟姐妹)的分离经历过度焦虑。通常在6-7个月至3岁之间的婴儿和小孩
  • 李约瑟中国科学技术史《中国科学技术史》(英语:Science and Civilisation in China)乃李约瑟研究所李约瑟博士和国际学者们所编著的一套关于中国的科学技术历史的著作。李约瑟在书中列出中国人的发
  • 咖啡牛奶咖啡牛奶(Coffee milk)是一种混合咖啡糖浆及牛奶的饮料,以类似巧克力牛奶的制作方式调制而成,它也是美国罗德岛州的官方饮料。咖啡糖浆则是一种加糖后的咖啡浓缩液体,将咖啡渣透
  • 军屯军屯是指驻屯的军队,利用驻屯军队就地耕种土地。军屯是“寓兵于农”的政策。郑成功论军屯为:“夫定国之术,在于强兵足食,秦人以急农兼天下,孝武以屯田定西域,此先代之良式也”。汉
  • 菖蒲菖蒲(学名:Acorus calamus),也叫做白菖蒲、藏菖蒲,古名蒖、䒢,是一种菖蒲科的水生草本植物。菖蒲分布很广,整个温带基本都能找到它,中国各地也都有分布。菖蒲可以提取芳香油;端午节有
  • 海鸥鸻形目(学名:Charadriiformes)在生物分类学上是鸟纲中的一个目,包括鸻、鹬、鸥等。
  • 韩国茶文化参数所指定的目标页面不存在,建议更正成存在页面或直接建立下列一个页面(建立前请先搜寻是否有合适的存在页面可以取代):韩国茶文化泛指韩国的制茶、饮茶的文化。韩国的茶叶最初
  • 私人飞行执照私人飞行执照(英语:Private Pilot Licence,简称PPL,美国称之为Private Pilot Certificate)是一种执照,持有人可以以机长身份、不受雇用的形式驾驶私人航空器进行飞行活动。由该国
  • 亚米德·阿包达勒亚米德·阿包达勒(荷兰语:Ahmed Aboutaleb,柏柏尔语:ⴰⵃⵎⴻⴷ ⴰⴱⵓⵟⴰⵍⴻⴱ,阿拉伯语:أحمد أبو طالب‎,1961年8月29日-)是荷兰工党(PvdA)政治人物,现任鹿特丹市长。他
  • 陈东 (宋朝)陈东(1086年-1127年),字少阳,镇江丹阳人,宋朝政治人物。生于北宋元祐元年(1086年),十七岁(1103年)入学,徽宗政和三年(1113年)入太学。宣和七年(1125年)十月二十七日上书请诛蔡京、王黼、童贯