proof

0热度

2回答

我有一个递归函数，如下所示，其中b> = 0 def multiply(a,b): if b == 0: return 0 elif b % 2 == 0: return multiply(2*a, b/2) else: return a + multiply(a, b-1) 我想知道多少倍的功能将在一个方面和b运行。谢谢。

-1热度

2回答

如何在haskell中设置归纳证明？

我需要证明 f (g xs) == g (f xs) whenver XS是INTS的有限列表。假设两个F和G型[INT] - > [INT]

0热度

1回答

解决通过替换

的方法的复发时在学习的算法和参照CLRS，我碰到 T(n) = T(n-a) + T(a) + cn ; a >= 1 and c > 0 it is Big-theta(n^2), can be easily proved by recursion tree method 我可以通过递归树的方法解决它的问题。在我的实验室与朋友们讨论时，一位朋友从不知情的地方宣布，这个问题永远无法通过替代

2热度

1回答

验证程序的等价性

优化编译器的最终目的是在程序空间中搜索等价于原始程序但速度更快的程序。这已经在实践中用于非常小的基本块：https://en.wikipedia.org/wiki/Superoptimization 听起来很难的部分是搜索空间的指数性质，但实际上它不是;最难的部分是，假设你找到了你想找的东西，你如何证明这个新的，更快的程序与原始程序真的是相同的？上次我研究过它，在某些情况下证明程序的某些属性已经

8热度

1回答

我如何让Idris自动证明两个值不相等？

我如何让Idris自动证明两个值不相等？ p : Not (Int = String) p = \Refl impossible 我该如何让Idris自动生成此证明？ auto似乎不能证明涉及Not的陈述。我的最终目标是让Idris自动证明矢量中的所有元素都是唯一的，并且两个矢量不相交。 namespace IsSet data IsSet : List t -> Type whe

0热度

2回答

证明大欧米茄功能

我试图找到N0（N不是）与n的大尺寸欧米茄函数的^ 3其中c = 2.25 （）= 3^3 - 39^2 + 360 + 20。为了证明（）是Ω（^ 3），我们需要常数0> 0，使得每个≥0的（）≥^ 3 如果c = 2.25，如何找到满足n0的最小整数？我首先想到的是在n = 1至堵塞，因为N> 0，并且如果不等式工作n = 1时将是最小的n（因此N0）。但是，对于每个n> = n0都必须满足

0热度

2回答

证明n次偶数在Agda中产生偶数

我试图在Agda 中定义1..n∈ℕ的和为n *（n + 1）/ 2，并且需要证明n * （n + 1）就是这样。证明非常简单，但似乎有一个概念我不明白，因为我是Agda的新手（虽然对数学和哈斯克尔都不熟悉），并从http://www.cse.chalmers.se/~ulfn/papers/afp08/tutorial.pdf 中得知它（指向更高级的教程比欢迎！）。 open import

2热度

1回答

共同感应，类型不匹配

我一直在尝试共同诱导类型，并决定定义自然数和向量的共同诱导版本（与他们的大小类型列表）。我确定他们和无限多的像这样： CoInductive conat : Set := | cozero : conat | cosuc : conat -> conat. CoInductive covec (A : Set) : conat -> Set := | conil : covec A co

1热度

1回答

Coq的不产生归纳假设

我得到的溶液与以下定理，如下所示： Require Import Coq.Lists.List. Import ListNotations. Inductive suffix {X : Type} : list X -> list X -> Prop := | suffix_end : forall xs, suffix xs xs | suffix_ste

-1热度

1回答

什么编程语言具有测试并发算法的具体目的？

我的一位同事编写了一个程序，证明在测试运行多个并发线程的算法试图找到可能触发不需要的条件的序列之后，某些条件将不会被满足。他使用了专为此目的而设计的计算机语言，但我不记得它的名字。为此特定目的提供哪些语言？