算法证明

1. RSA算法的证明

分两种情况考虑，
1.m,n互素的时候。要证明c^d≡m (molo n)。在上面一步中 再加一步，读者应该就更好理解了。由欧拉定理退出XXXX，然后下面还有一步。m^kφ（n）≡1 modn 最后一步应该是写成m^(kφ（n）+1)≡1 mod n.然后你应该就知道c^d≡m (molo n)。
2.这步中的p-1其实就是φ（p），你先算m^kφ（n）≡1 modn 然后再φ（p），结果还是1啊。
另外，你看的是不是电子档的应用密码学的？建议你去看实体书，那个上面写的很详细。不会像这个那么简略，很多都不能理解

2. 算法分析证明题

程序设计里的时间复杂度？
就是同阶无穷大那个算法，lim(n->+inf,18n^2+4n+2014/n^2)=18 成立
这里只要不是无穷大就成立(inf=无穷大)
同理2,3
二：lim(n->+inf,log 3 n/log 100 n)=lim(n->+inf,ln n/ln n)*(ln 100/ln 3)=(ln 100/ln 3)不是无穷大所以成立

3. 算法证明

显然是错的
比如说，有个问题是寻找某个数列中最大数所在的位置
一种算法可以是从前向后找，返回找到的第一个
一种算法可以是从后向前找，返回找到的第一个
还有算法可以是等分成两段，递归地使用上面的第一种（或者第二种）方法找，最后合并
还可以按奇偶性分类

诸如此类，可以有多种算法
如果输入数据是0,1,2,0,1,2，输出是3，上面的算法至少有两种会产生这个输出，但显然合理的输出既可以是3也可以是6，并不唯一

4. 离散数学等值算法证明，第一，第三问

（1）
(p∧q)∨(p∧¬q)
⇔p∧（q∨¬q）分配率
⇔p∧TRUE
⇔p

（2）
¬(p↔q)
⇔¬((p→q)∧(q→p)) 变成 合取析取
⇔¬((¬p∨q)∧(¬q∨p)) 变成 合取析取
⇔¬((¬p∨(p∧q))∧(¬q∨(p∧q))) 吸收率 反过来用
⇔¬((¬p∧¬q)∨(p∧q)) 分配率 把上式中(p∧q)看成一个整体来处理
⇔¬(¬p∧¬q)∧¬(p∧q) 德摩根定律
⇔(p∨q)∧¬(p∧q) 德摩根定律

5. 有关DES算法的一道证明题

证明：DES算法的加密算法和解密算法是完全一样的，所不同的是密钥以相反的顺序依次加入到轮函数中。

DES算法的加密流程如下：
（1）生成子密钥
首先，将64比特的密钥（实际有效位数只有56比特）进行置换，得到56比特的密钥串；
然后，将56比特的串分为两个28比特的子串，经过16轮的循环左移以及合并置换，生成16个子密钥，记为K1K2K3...K16；
（2）加密
首先，将64比特的明文W做初始置换，得到结果IP（W）；
将结果分成两个32比特的子串，记为L0和R0，所以L0R0=IP（W）；
然后，根据L0、R0以及K1，求得L1和R1，具体如下：
L1=R0，即L1跟R0完全相同；
R1=P(S(E(R0)^K1))^L0，其中：
E(R0)表示对R0做扩展置换；
E(R0)^K1表示上一步的结果与K1做异或运算；
S(E(R0)^K1)表示上一步的结果做S-box运算；
P(S(E(R0)^K1))表示上一步的结果做置换；
P(S(E(R0)^K1))^L0表示上一步的结果与L0做异或运算。
以上的过程就是一次轮函数。如此，再由L1、R1以及K2，求得L2R2。以此类推，经过16次轮函数的迭代即可求得L16R16。
最后，把L16R16交换顺序，得到R16L16，再经过一次逆置换FP(R16L16),可以得到64比特的密文C,所以C=FP（R16L16）。

我们知道，DES的解密只需将16个子密钥以相反的顺序加入到轮函数中，重复加密的步骤即可。 现在我们要证明DES加密和解密的算法是完全一样，只是子密钥使用的顺序相反。也就是说，我们要证明密文经过子密钥顺序相反的加密之后可以得到明文。
DES算法的解密流程如下：
（1）生成子密钥
解密的时候使用的子密钥与加密时的顺序相反，记为K16K15...K2K1；
（2）解密
首先，将64比特的密文C做初始置换IP（C），
由于C=FP（R16L16），所以IP（C）=IP（FP（R16L16））=R16L16，因此得到的结果为R16L16。
将结果分成两个32比特的子串，也就是R16和L16。
然后，对其进行轮函数运算，结果记为XY，具体如下：
X=L16，
Y=P(S(E(L16)^K16))^R16。
从加密的过程中，我们知道，
L16=R15,
R16=P(S(E(R15)^K16))^L15，
因此，Y=P(S(E(L16)^K16))^P(S(E(R15)^K16))^L15。
由于L16=R15，所以P(S(E(L16)^K16))=P(S(E(R15)^K16))，
所以P(S(E(L16)^K16))^P(S(E(R15)^K16))=，
因为^L15=L15，
所以Y=P(S(E(L16)^K16))^P(S(E(R15)^K16))^L15=L15。
由此可知，R16L16经过一次轮函数之后，得到的结果是R15L15。
如此，在对R15L15做轮函数运算，得到R14L14。以此类推，经过16次轮函数的迭代，得到R0L0。
最后，把R0L0交换顺序，得到L0R0，再经过一次逆置换FP（L0R0）=FP（IP（W））=W，就得到了明文W。
综上所述，DES算法的加密算法和解密算法是完全一样的，所不同的是密钥以相反的顺序依次加入到轮函数中。

6. SPFA算法的原理及证明

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra算法等便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
定理：只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。
期望时间复杂度：O(me)， 其中m为所有顶点进队的平均次数，可以证明m一般小于等于2：“算法编程后实际运算情况表明m一般没有超过2n.事实上顶点入队次数m是一个不容易事先分析出来的数,但它确是一个随图的不同而略有不同的常数.所谓常数,就是与e无关,与n也无关,仅与边的权值分布有关.一旦图确定,权值确定,原点确定,m就是一个确定的常数.所以SPFA算法复杂度为O(e).证毕.（SPFA的论文）不过，这个证明是非常不严谨甚至错误的，事实上在bellman算法的论文中已有这方面的内容，所以国际上一般不承认SPFA算法。
对SPFA的一个很直观的理解就是由无权图的BFS转化而来。在无权图中，BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。一个解决方法是放弃数组，此时所需时间自然就是指数级的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。
SPFA算法有两个优化策略SLF和LLL——SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾； LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。

7. 证明分治算法要对什么性质展开证明

(1)设一函数intcount(intb,inte,intx),可求出A[b,e]中x的出现频度,则:intcount(intb,inte,intx){if(b==e){returnA[b]==x);}else{returncount(b,(b+e)/2,x)+count((b+e)/2+1,e,x);}}复杂度O(n),具体地n次比较,n-1次加法运算.(2)直接从第1个往后选,选到满为止.复杂度O(n)证明:假设此方法得出的解不是最优解,则:设所选物品为1~k,必然存在一个n(n>k),用这个物品代替原所选物品物品时,能取得更优的解值.但由条件可知,位置大于k的物品重量必然比小于k的物品大,所以至少要替换掉1个;而它的值却小于原物品中的任何一个.所以假设不成立.按"直接从第1个往后选,选到满为止"的方法选取,得出的解就是最优解.

8. 算法设计与分析 证明n!＝Θ（n^n）

n!/(n^n)=(1/n)(2/n)……(n/n)<=1/n，当n趋向无穷时，趋于0,所以n！=o（n^n）

9. 贪心算法的证明方法

贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
----------------------------------------------
其实归纳起来也就一个类。其他的都是分支

10. 求Kruskal算法正确性证明b

证明：令G为任何一个与Kruskal算法产生的树F不同的树。考虑构造F的过程。令e为第一次选的一条不属于G的边。如果我们将e加入G，我们会得到一个圈C。这个圈不完全包含在F里面，因此在C中有一条不属于F的边f。如果我们将e加入G并删除f，我们就得到了一个新的树H。

我们想要证明H不比G贵。这意味着e不比f贵。用反证法。假设f比e便宜。

现在考虑这样一个问题：为什么Kruskal算法选择了f而不是e呢？唯一的原因只可能是f被排除了，即f与加入e之前被选入F的边会形成一个圈。但是所有这些已经被选的边都是G的边，因为e为第一次选的一条不属于G的边。又f本身属于G，所以G就包含了一个圈，这是不可能的（G是树）。这个矛盾证明了H不比G贵。

因此我们可以用H来代替G，而且H比G更接近F（即H与F有更多相同的边）。如果H不是F，重复以上步骤，我们得到一系列与H越来越接近的不比G贵的树。这个过程迟早会以F终结，这就证明了F不比G贵。

Kruskal算法的正确性也就得证。