是否存在总是需要有限时间的两个(确定性)有限状态机的等价性的一般证明？也就是说,给定两个FSM,你能证明给定相同的输入它们总是产生相同的输出而不需要实际执行FSM(可能是非终止的吗？).如果确实存在这样的证据,那么时间复杂度是多少？
在big-O表示法中O((log n)^k) = O(log n),k某些常量(例如,循环的对数),是真的吗？
我的教授告诉我,这种说法是正确的,但是他说这将在课程的后期证明.我想知道你们中是否有人能证明其有效性,或者有一个链接我可以确认是否属实.
在浏览维基百科的排序算法列表时,我注意到没有稳定的比较排序具有O(n*log(n))(最坏情况)时间复杂度和O(1)(最坏情况)空间复杂度.这肯定看起来像理论界限,但我找不到更多关于它的信息.
如何证明这一点？
注意:我知道O(n*log(n))比较排序的最坏情况时间复杂度的下限.
我可以清楚地看到,N ^ 2受到c2 ^ N的限制,但我如何通过使用big-O的形式定义来证明它.我可以通过MI简单地证明这一点
这是我的尝试..根据定义,对于任何n> n0,存在一个常数C,其中f(n)<= Cg(n)其中f(n)= n ^ 2且g(n)= 2 ^ n
我应该记录到两边并解决C？
还有一个关于斐波纳契序列的问题,我想解决递归关系.
int fib(int n){
if(n<=1) return n;
else return fib(n-1) + fib(n-2);
等式是......
T(n) = T(n-1)+T(n-2)+C // where c is for the adding operationT(n) = T(n-2) + 2T(n-3) + T(n-4) + 3c 还有一个
T(n) = T(n-3) + 3T(n-4) + 3T(n-5) + T(n-6) + 6c然后我开始迷失形成一般方程式我的模式有点像帕斯卡三角形？
t(n) = t(n-i) + aT(n-i-1) + bT(n-i-2) + ... + kT(n-i-i) + C 根据代数定律的思考,我想知道在比特操作领域是否存在任何官方指导线,类似于代数.
代数例子
a - b =/= b - a
让我们a = 7和b = 5
a - b = 2 b - a = -2让我们a = 10和b = 3
a - b = 7b - a = -7因此if a > b,b - a将是负面的等价物a - b.因此,我们可以说
|a - b| = |b - a|.
其中|x|表示绝对值x.
按位示例
a | b =/= a …
我很难理解感应如何与一些不变量一起用来证明算法的正确性.也就是说,如何找到不变量,何时使用归纳假设 - 特别是二元搜索？我还没有找到直观的回复,所以我希望有人可以在这里阐述一下这个话题.
我设法将目标减少到了
(fun x0 : PSR => me (x x0)) = x
我知道这reflexivity会有效,但出于教学原因,我宁愿继续减少它.
me是一个身份功能,所以unfold me简化它
(fun x0 : PSR => x x0) = x
这只是一个将函数应用于x虚拟变量的匿名函数x0,所以你可以说两边都只是函数x.如果可能的话,我想在双方达成相同的表达方式.
大多数证明助手都是具有依赖类型的函数式编程语言.他们可以证明程序/算法.相反,我感兴趣的是最适合数学的证明助手,而且只有(例如微积分).你能推荐一个吗？我听说过Mizar,但我不喜欢源代码已关闭,但如果最好是数学,我会使用它.Agda和Idris等新语言如何适用于数学证明？
Codility,第14课,任务TieRopes(https://codility.com/demo/take-sample-test/tie_ropes).简而言之,问题是将A正整数列表划分为具有至少总和的(连续)子列表的最大数量K.
我只想出一个贪婪的解决方案,因为这就是课程的名称.它通过了所有测试,但我不知道为什么它是一个最佳解决方案(如果它是最佳的).
int solution(int K, vector<int> &A) {
int sum = 0, count = 0;
for (int a : A)
{
sum += a;
if (sum >= K)
{
++count;
sum = 0;
}
}
return count;
}
有人可以告诉我这个解决方案是否以及为何最佳？
我有这些类型的家庭：
type family xs ++ ys where
'[] ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)
type family Drop n xs where
Drop O xs = xs
Drop (S n) (_ : xs) = Drop n xs
type family Length xs where
Length '[] = O
Length (x : xs) = S (Length xs)
在某些时候，GHC 想要证明
forall a. Drop (Length a) (a ++ c) ~ c
我曾经把它推到一些构造函数的上下文中。
我如何普遍证明这个属性？