南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）算法的正确性

计算机问题求解一论题2-1 -算法的正确性 2020年2月27日

计算机问题求解 – 论题2-1 - 算法的正确性 2020年2月27日

问题1： 人们似乎对于计算机 “犯错比对于人犯错更 加苛刻，这是为什么呢？

几种不同的错误 “语言错” 口很容易被语言处理软件发现，甚至自动纠正。 “语义错” 口▣合格的程序员很少会犯这类错误。 ▣解题逻辑错误 口“粗心”造成的错误。 常见（相对来说） “真正的”逻辑错误。 逻辑错误不常见，但这个是真的“伤脑筋”！

几种不同的错误 ◼ “语言错” ❑ 很容易被语言处理软件发现，甚至自动纠正。 ◼ “语义错” ❑ 合格的程序员很少会犯这类错误。 ◼ 解题逻辑错误 ❑ “粗心”造成的错误。 ◼ 常见(相对来说) ❑ “真正的”逻辑错误。 逻辑错误不常见，但这个是真的“伤脑筋”！

问题2： 书上的对文本中出现“money一词的句子计数的 例子出现了什么样的错误，你能说出它的性质吗？

Test and debugging A designer might try out an algorithm on several typical and atypical inputs and to find the error.In fact,a programmer will normally test a program on numerous inputs,sometimes called test sets,and will gradually rid it of its language errors and most of its logical errors. ■Test是一种合理的获得“正确”程序的方法吗？ 口程序是一种人工制品。既然如此，通过实验观察，应该可以得到这个“物体 ”的某些属性 How to“gradually rid it of its errors”? a Debug！

Test and debugging ◼ A designer might try out an algorithm on several typical and atypical inputs and to find the error. In fact, a programmer will normally test a program on numerous inputs, sometimes called test sets, and will gradually rid it of its language errors and most of its logical errors. ◼ Test 是一种合理的获得“正确”程序的方法吗？ ❑ 程序是一种人工制品。既然如此，通过实验观察，应该可以得到这个“物体 ”的某些属性 ◼ How to “gradually rid it of its errors”? ❑ Debug!

关于debugging的思考 a什么是debug? The process of repeatedly executing an algorithm,or running a program,with the intention of finding and eliminating errors is called debugging ■为什么我们可以依赖debug来排除错误？ 口程序运行的“再现”==》错误的“再现

关于debugging的思考 ◼ 什么是debug？ ❑ The process of repeatedly executing an algorithm, or running a program, with the intention of finding and eliminating errors is called debugging ◼ 为什么我们可以依赖debug来排除错误？ ❑ 程序运行的“再现”==》错误的“再现

Test和Debugging的局限性 Most algorithmic problems have infinite sets of legal inputs, and hence infinitely many candidate test sets,each of which has the potential of exposing a new error. Dijkstra: Program testing can be used to show the presence of bugs, but never to show their absence! 我们能够用形式系统“翻译”Dijkstral的话吗？

Test和Debugging 的局限性 Dijkstra: Program testing can be used to show the presence of bugs, but never to show their absence! 我们能够用形式系统“翻译”Dijkstra的话吗？ Most algorithmic problems have infinite sets of legal inputs, and hence infinitely many candidate test sets, each of which has the potential of exposing a new error

Infinite computation Infinite computation为什么有时也会被称为infinite loop? "以下两个例子都会形成一个infinite computation,区别在哪？ while(1)do {... for(int i=0;i==9;++)1...;i++;... ■如何规避“死循环”？ 口算法级 循环出口必达 ▣不合适的出口标准；循环体内使用控制变量；.. 口编程级 ■细心；循环控制中，少用“高级”的语言设施；

Infinite computation ◼ Infinite computation为什么有时也会被称为infinite loop？ ◼ 以下两个例子都会形成一个infinite computation，区别在哪？ ❑ while(1) do {…} ❑ for(int i=0;i==9;i++) {…;i++;…} ◼ 如何规避“死循环”？ ❑ 算法级 ◼ 循环出口必达 ❑ 不合适的出口标准；循环体内使用控制变量；…… ❑ 编程级 ◼ 细心；循环控制中，少用“高级” 的语言设施；……

Test和debug的局限性 s Debug必须以测试出的错误的可再现为前提 口只有封闭环境、确定运行，才能“再现”错误 ·开放式环境中运行的程序，debug异常困难 口分布式系统、网络平台等 ■ 确定输入，但运行时刻数据非“独占” 口非确定环境下运行的程序 ■本质上输入数据无法保证确定性 ·必须随机的算法 口程序执行存在非确定性

Test和debug的局限性 ◼ Debug 必须以测试出的错误的可再现为前提 ❑ 只有封闭环境、确定运行，才能“再现”错误 ◼ 开放式环境中运行的程序，debug异常困难 ❑ 分布式系统、网络平台等 ◼ 确定输入，但运行时刻数据非“独占” ❑ 非确定环境下运行的程序 ◼ 本质上输入数据无法保证确定性 ◼ 必须随机的算法 ❑ 程序执行存在非确定性

程序和算法正确性保障： ·自动验证： some sort of super-algorithm that ace inputs a description of a hm A that is proposed a( 当我们完成了某个算法 solves P. 的正确性证明，我们 "人工证明 test的，debug的是什 Can we ob 么？ Je correct?Is there any way in wor eformal, mathematical techniques to realize this objective?

程序和算法正确性保障： ◼ 自动验证： ❑ some sort of super-algorithm that would accept as inputs a description of an algorithmic problem P and an algorithm A that is proposed as a solution, and would determine if indeed A solves P. ◼ 人工证明： ❑ Can we ourselves prove our algorithms to be correct? Is there any way in which we can use formal, mathematical techniques to realize this objective? 当我们完成了某个算法 的正确性证明，我们 test的，debug的是什 么？