以下代码是Idris:
natAssociative : (a : Nat) -> (b : Nat) -> (c : Nat) -> (a + b) + c = a + (b + c)
natAssociative Z b c = the (b + c = b + c) refl
natAssociative (S k) b c = replace {P=\x => S (k + b) + c = S x} (natAssociative k b c) refl
我正在艰难地将其转化为无形.我尝试了一些不同的编码,但我认为这是最有希望的开始:
import scalaz.Leibniz._
import shapeless.{ HNil, Nat, Succ, Poly3 }
import shapeless.Nat._
import shapeless.ops.nat._
object natAssociative extends …我想知道是否存在任何继续证明算法正确性的规则/方案？例如,我们在自然数上定义了一个函数$ F $,定义如下:
function F(n,k)
begin
if k=0 then return 1
else if (n mod 2 = 0) and (k mod 2 = 1) then return 0
else return F(n div 2, k div 2);
end;
其中$ n\\ text {div}\2 =\left\lfloor\frac {n} {2}\right\rfloor $
任务是证明$ F(n,k)=\begin {cases} 1\Leftrightarrow {n\choose k}\\ text {mod}\2 = 1\0\text {otherwise}\end {cases} $
它看起来并不复杂(我错了吗？),但我不知道这种证据应该如何构建.我非常感谢你的帮助.
我有一个我似乎无法弄清楚的面试问题.给定大小为N的阵列,找到大小为k的子集,使得子集中的元素彼此相距最远.换句话说,最大化元素之间的最小成对距离.
Example:
Array = [1,2,6,10]
k = 3
answer = [1,6,10]
强力方式需要找到大小为k的所有子集,这些子集在运行时是指数的.
我的一个想法是从数组中均匀分布值.我的意思是
这是基于元素应尽可能均匀分布的直觉.我不知道如何证明它有效/无效.如果有人知道如何或有更好的算法,请分享.谢谢!
假设长度为n的列表L 在列表J中交织,长度为n + 1.我们想知道,对于J的每个元素,L的哪个邻居是更大的.下面的函数需L作为其输入,并产生一个列表K,也长度的 n + 1个,使得我个钾元素是所期望的邻居我个J.的元件
aux [] prev acc = prev:acc
aux (hd:tl) prev acc = aux tl hd ((max hd prev):acc)
expand row = reverse (aux row 0 [])
我可以非正式地向自己证明,这个函数(我最初在Ocaml中写的)的结果长度比输入的长度大.但我跳到Haskell(一种新语言),因为我有兴趣通过类型系统证明这个不变量.在前面的答案的帮助下,我能够得到以下内容:
{-# LANGUAGE GADTs, TypeOperators, TypeFamilies #-}
data Z
data S n
type family (:+:) a b :: *
type instance (:+:) Z n = n
type instance (:+:) (S m) n = S (m :+: n) …最初由Launchbury和Peyton Jones设计的ST monad允许Haskell程序员编写命令式代码(使用可变变量,数组等),同时获得该代码的纯接口.
更具体地说,入口点函数的多态类型
runST :: (forall s. ST s a) -> a
确保ST包含计算的所有副作用,并且结果值是纯的.
这是否经过严格(甚至正式)证明？
多线程算法特别难以设计/调试/证明.Dekker的算法是设计正确的同步算法有多么困难的一个主要例子.Tanenbaum的现代操作系统在其IPC部分中充满了示例.有没有人有这方面的好参考(书籍,文章)？谢谢!
我遇到了一个常见的编程访谈问题:给定一个无符号整数列表,找到一个在列表中出现奇数次的整数.例如,如果给出列表:
{2,3,5,2,5,5,3}
解决方案将是整数5,因为它在列表中出现3次而其他整数出现偶数次.
我的原始解决方案包括设置一个排序数组,然后迭代数组:对于每个奇数元素,我会添加整数,而对于每个偶数元素,我会减去; 结束总和是解决方案,因为其他整数将取消.
但是,我发现只需在每个元素上执行XOR就可以实现更高效的解决方案 - 您甚至不需要排序数组!也就是说:
2^3^5^2^5^5^3 = 5
我从Discrete Structures类回忆起,我认为Associate Property适用于XOR操作,这就是为什么这个解决方案有效:
a^a = 0
和:
a^a^a = a
虽然我记得Associative Property适用于XOR,但是我很难找到特定于XOR的这个属性的逻辑证明(因特网上的大多数逻辑证据似乎更侧重于AND和OR操作).有谁知道为什么关联属性适用于XOR操作？
我怀疑它涉及包含AND和/或OR的XOR身份.
嗨,大家好我想比较2个算法,并认为我可以尝试为他们写一个证明!(我的数学很糟糕因此问题)
通常在去年的数学课上我们会遇到类似的问题
证明:(2r + 3)= n(n + 4)
那么我会做所需的4个阶段并在最后得到答案
我被困的地方是证明prims和Kruskals - 我怎样才能将这些算法变成上面的数学形式所以我可以继续证明
注意:我不是要求别人为我回答 - 只是帮我把它放到一个我可以自己去的地方
谢谢
我正在撰写关于依赖类型有用性的本科论文.我正在尝试构造一个容器,只能构造成一个排序列表,以便它被证明按构造排序:
import Data.So
mutual
data SortedList : (a : Type) -> {ord : Ord a) -> Type where
SNil : SortedList a
SMore : (ord : Ord a) => (el: a) -> (xs : SortedList a) -> So (canPrepend el xs) -> SortedList a
canPrepend : Ord a => a -> SortedList a -> Bool
canPrepend el SNil = True
canPrepend el (SMore x xs prf) = el <= x
SMore 需要运行时证明,前置元素小于或等于排序列表中的最小(第一)元素.
为了排序未排序的列表,我创建了一个函数sinsert,它接受一个排序列表并插入一个元素并返回一个排序列表:
sinsert : (ord : Ord …我只是开始玩idris和定理证明一般.我可以在互联网上关注大多数基本事实证据的例子,所以我想尝试一些我自己的任意事物.所以,我想为map的以下基本属性编写一个证明术语:
map : (a -> b) -> List a -> List b
prf : map id = id
直觉上,我可以想象证明应该如何工作:获取任意列表l并分析map id l的可能性.如果l是空的,那很明显; 当l非空时,它基于函数应用程序保持相等的概念.所以,我可以这样做:
prf' : (l : List a) -> map id l = id l
这就像一个所有声明.如何将其转化为所涉及功能相等的证明？