图灵在1936年就指出，图灵机并不是什么都能计算。最著名的例子就是停机问题，即没有计算机能通过查看一段代码就知道自己是会永远执行下去还是会最终停止。——摘自《可能与不可能的边界：P/NP问题趣史》　　我们都见过计算机屏幕上出现一个代表忙碌的小沙漏，不知道这是代表计算机死机了，还是在进行长时间的计...

1.复数我们把形如a+bi的数称为复数，其中a称为实部，b称为虚部，i称为虚数单位，a，b∈R.在复平面内，任何一个复数都可以表示为r(cosθ+isinθ)的形式，其中，θ叫做该复数的辐角，即该复数在复平面内与实数轴的夹角，r为该复数的模.2.棣莫弗定理对于复数Z1，Z2...

证明：实对称阵属于不同特征值的的特征向量是正交的.设Ap=mp,Aq=nq,其中A是实对称矩阵,m,n为其不同的特征值,p,q分别为其对应得特征向量.　　则　　p1(Aq)=p1(nq)=np1q　　　　　(p1A)q=(p1A1)q=(AP)1q=(mp)1q=mp1q　　因为　p1(Aq)=(p1A)q　　上两式作...

一，问题介绍最近一直在看贪心算法的正确性证明（如何证明贪心算法获得的解一定是最优解），感觉“剪枝”技巧用得比较多。再看了下《算法导论》中贪心算法一章里面的一个练习---找换硬币问题。这个问题对于某些面值的硬币是有最优解的，故记录下其中的一些证明思路。考虑用最少的硬币数来找n分钱的问题，假设每个硬...

一，部分背包问题介绍首先介绍下0-1背包问题。假设一共有N件物品，第i件物品的价值为Vi，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，请问：他应该选择哪些物品？0-1背包问题的特点是：对于某件（更适合的说法是：某类）物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在...

转自:https://blog.csdn.net/liangzhaoyang1/article/details/51602926  设G是所有边权均不相同的无向联通图。证明一：首先，易证图G中权值最小的边一定是最小生成树中的边。(否则最小生成树加上权值最小的边后构成一个环，去掉环中任意一条非此边则形...