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

计算机问题求解一论题2-1 ~算法的正确性 2018年3月7日

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

As discussed in Chapter 1,an algorithmic problem can be concisely divided into two parts: 1.a specification of the set of legal inputs;and 2.the relationship between the inputs and the desired outputs. 这段话和我们今天的主题什么关系？

这段话和我们今天的主题什么关系？

Reverse a string: reverse(“ajjSdt8")=“8td$ja” head(aii$dt8")=“a” and; tail(“ajjSdt8")=“ij$dt8 Also,we use the special symbol"."for string concatenation,or attachment.Thus: “aj$dt8”.“tdd9tr”=“ajjSdta8tdd9tr

Reverse a string:

start 问题： Input:a string of symbol S; X←S: Output:the reverse image of S. Y←-A 算法： 如右图 NO YES X=∧？ Y←head(X).Y stop X←-tail(X)

问题: Input: a string of symbol S; Output: the reverse image of S. 算法： 如右图

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

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

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

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

Test and debugging A designer might try out an algorithm on several typical and atypical inputs and do not 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. 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

Test and debugging ◼ A designer might try out an algorithm on several typical and atypical inputs and do not 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. ◼ 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

Debugging的局限性 As someone once put it,testing and debugging can not be used to demonstrate the absence of errors in software,only their presence. “someone”believed to be Dijkstra: Program testing can be used to show the presence of bugs, but never to show their absence! 我们能够用形式系统为Dijkstra的话证实吗？

Debugging 的局限性 “someone” believed to be Dijkstra: Program testing can be used to show the presence of bugs, but never to show their absence! 我们能够用形式系统为Dijkstra的话证实吗？ As someone once put it, testing and debugging can not be used to demonstrate the absence of errors in software, only their presence

关于debugging的思考 ▣为什么我们可以： -The process of repeatedly executing an algorithm,or running a program,with the intention of finding and eliminating errors is called debugging?

关于debugging的思考 ◼为什么我们可以： ◼ The process of repeatedly executing an algorithm, or running a program, with the intention of finding and eliminating errors is called debugging？