爱问 爱问共享资料 爱问分类

算法都能给出数学证明吗

首页

算法都能给出数学证明吗


        

Myron龙

查看TA的回答:

提交回答

全部答案

    2018-05-15 04:22:31
  • 不能,算数只是人类发明的方便生活的东西,纯属人类的假象

    Bonnie...

    2018-05-15 04:22:31

  • 2018-05-15 04:22:31
  • 任何算法的正确性,都需要得到证明。
    只有得到证明,才能保证结果的正确性。
    只有得到证明,才能够使用。
    可见,任何算法都已经得到了证明。

    Joanna...

    2018-05-15 04:22:31

  • 2018-05-15 04:22:31
  •   作者:facetothefate
    链接:https://www。zhihu。com/question/59671403/answer/173617873
    来源:知乎
    著作权归作者所有。
      商业转载请联系作者获得授权,非商业转载请注明出处。
    从题目表述来看, 这里是在问是不是每个程序的正确性是可以证明的。如果从工程的角度来说,明确的回答,不是。为什么呢?过于复杂的程序系统进行正确性证明是非常难的,不同于科研论文中对于某一算法精确的描述,确定的输入输出,这涉及到大量的不同的call path,不同的子系统互相调用。
      这就是为什么我们有个东西叫做测试。如果你去过几家大公司呆过,就会明白只要测试写的好,代码就是写的稀烂,也是可以保证正常工作的。大部分程序只有有限的输入,很多时候,我们不需要证明,只要将每一个结果测试一下就好了。这样对于该程序,至少在需要的一个测试集里,是正确的。
      对于工程来说,这样就足够了。但是你问这个程序能不能被证明正确性呢,其实也是可以的,只是从工程的角度来说,这就是在浪费时间,我们的系统,只要满足设计要求即可,并不需要得到一个广泛的,一般性的解。举个例子:比如我们要写一个 1的程序,要求的输入集是确定的1~5整数,那么对于这个问题其实以下两个程序是都是正确的:intplus_one_1(intn){returnn 1;}intplus_one_2(intn){switch(n){case1:return2;case2:return3;case3:return4;case4:return5;case5:return6;default:return-1;}}显然对于plus_one_1 可以有一个普遍性的正确性证明,但是对于plus_one_2只能保证在测试集[1,5]的正确性,然而如果实际问题是我们只有[1,5]的输入,那么对于这两个程序都是正确的。
      因此,再设计程序的时候,只要明确了输入范围,明确了测试集,那么就算你的code写的稀烂如plus_one_2又有什么关系呢,反正可以得到符合设计的正确结果。而且这里没有任何的形式化证明,我们只是把每个输入试了一下看看对还是不对罢了。当系统足够复杂的时候,系统里的逻辑就会慢慢变成一个又一个if去把当初没有cover的测试集去cover,这就是当今很多大型系统的德行,所谓的business logic很多就是在做这个按情况分类,比如1,5给这个函数,6,10给那个函数,听起来很蠢,但是当系统足够复杂的时候,能把这些情况按照一定条件分类就已经非常不容易了。
      最后,算法是什么呢,对于图灵机来说,它就是一个图灵机的状态转移矩阵,我们要做的就是在几个初始状态和几个终结状态之间这样一个状态转移矩阵。如果你懂状态机,就会更加理解为什么测试是行之有效的正确性保证的手段了。因此,很多时候不是算法不能证明正确性,而是实际的工程是不会那么做的,现代的软件工程是测试驱动的,测试就是正确性的保证。
      

    恋爱一点都不...

    2018-05-15 04:22:31

类似问题

换一换
  • 数学 相关知识

  • 教育培训
  • 教育考试

相关推荐

正在加载...

爱问推荐

  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200

热点检索

  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200
返回
顶部
帮助 意见
反馈
关注
爱问

关注爱问微信公众号,开启知识之旅,随时随地了解最新资讯。

确定举报此问题

举报原因(必选):