标签: proof-of-correctness

我试图更全面地了解动态规划中最优子结构属性的使用，但我对为什么我们必须证明问题的任何最优解都包含子问题的最优解感到盲目。

证明问题的某些最佳解决方案具有此属性，然后用它来证明，由于我们的递归算法构建的解决方案至少与最佳解决方案一样好，因此它本身就是最佳的，这还不够吗？换句话说，我无法在我们的算法的正确性论证中发现我们需要所有最优解包含子问题的最优解。

澄清：

CLRS 对最优子结构的定义是：“如果问题的任何最优解都包含子问题的最优解，则该问题表现出最优子结构”。

为什么说“如果问题的某些最优解包含子问题的最优解，则问题表现出最优子结构”还不够？

我是lambda演算的新手,并努力证明以下内容.

SKK和II是等效的.

哪里

S = lambda xyz.xz(yz)K = lambda xy.x I = lambda xx

我尝试通过打开它来测试减少SKK,但无处可去,它变得凌乱.不要认为SKK可以在不扩展S,K的情况下进一步减少.

我需要证明以下选择排序代码（在Haskell中）始终在排序：

import Data.List (minimum, delete)

ssort :: Ord t => [t] -> [t]
ssort [] = []
ssort xs = let { x = minimum xs } in  x : ssort (delete x xs)

我们可以假设我们有一个名为“ sorted ” 的函数，该函数检查列表何时排序。

用结构归纳法证明的语句：sorted（ssort xs）

我尝试了以下操作，但无法完成证明。您能帮我完成证明吗？

基本情况：xs = []

sorted（ssort xs）=

sorted（ssort []]）=

排序（[]]

正确，因为sorted（[]）总是被排序

归纳步骤

IH（归纳假设）=排序（ssort xs）

显示：排序（排序y＃xs）

情况I：x = y =最小值

sorted（sort y＃xs）=

sorted（let {x = x中的最小值（y＃xs）}：ssort（删除x（y＃xs）））=（根据定义）

sorted（let {y = y中的最小值（y＃xs）}：ssort（删除y（y＃xs）））=（通过替换）

sorted（y：ssort（删除y（y＃xs）））=

sorted（y：ssort（xs））=（按删除定义）

排序（y：ssort（xs））

通过IH，我们知道sort（xs）已排序，y也是最小值，因此它排在第一位

情况二：y不是最小值

sorted（sort y＃xs）=

sorted（let {x …

我想证明我对 multi-paxos 的实现是正确的。是否有任何有效的示例供我测试？或者可以有其他一些方法来说服其他人我的实施是正确的。

我试图找到一些包含示例的论文，但大多数论文只是指定了算法。

In Haskell, find is designed to evaluate as a Maybe, because when scanning a list for an element matching a predicate, it could fail. However, consider the following:

factorize n | isPrime n = [n]\n            | otherwise = m : factorize (n `div` m)\n            where m = find ((==0) . (n `mod`)) [2..]\n

find here will clearly find a value in every case, assuming we\xe2\x80\x99re only hitting integers greater than 2. If a number is not prime, then …

手动或由计算机代数系统执行的符号计算可能是错误的或仅在某些假设下成立。一个经典的例子是sqrt(x^2) == x，一般情况下，这不是真的，但如果x是实数且非负，则它确实成立。

是否有使用证明助手/检查器（例如 Coq、Isabelle、HOL、Metamath 或其他）来证明符号计算的正确性的示例？我特别对微积分和线性代数示例感兴趣，例如求解定积分或不定积分、微分方程和矩阵方程。

更新： 更具体地说，了解是否有微积分和线性代数方面的本科作业示例可以正式解决（可能在证明助理的帮助下），以便解决方案可以通过自动验证证明检查器。这里有一个非常简单的精益作业示例。

Haskell 经常被吹捧为进行证明的语言。（在他们开始推荐 Agda、Idris 或 Coq 之前）。但是，这段代码没有潜在问题还是我对这个概念的理解错误？

x :: Int -> Int
x n
 | x == 0 = error "Error"
 | otherwise = n + 1

据我了解，这对于检查证明不太好（因为Int这里不强制返回。）
有没有办法解决这个问题？

据我了解，上述其他语言都避免了这种情况。[1] 我不明白怎么办。仅仅是因为更严格的类型系统还是该语言提供的其他一些保证？

到目前为止，我已经仔细查看了语言文档，但什么也没找到。

[1] = https://www.reddit.com/r/haskell/comments/9toh6b/comment/e8y4gzi/?utm_source=share&utm_medium=web2x&context=3