南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）为什么计算机能解题（陶先平）

计算机问题求解 论题1.1：计算机为什么能解题？ 2019年10月8

计算机问题求解 论题1.1：计算机为什么能解题？ 2019年10月8

Computers are amazing machines. They seem to be able to do anything.They fly aircraft and spaceships,and control power stations and hazardous chemical plants.Companies can no longer be run without them,and a growing number of sophisticated medical procedures cannot be performed in their absence.They serve lawyers and judges who seek judicial precedents in scores of documented trials,and help scientists in performing immensely complicated and involved mathematical computations. They route and control millions of telephone calls in networks that span continents.They execute tasks with enormous precision-from map reading and typesetting to graphical picture processing and integrated circuit design.They can relieve us of many boring chores,such as keeping a meticulous track of home expenses,and at the same time provide us with diverse entertainment such as computer games or computerized music.Moreover,the computers of today are hard at work helping design the even more powerful computers of tomorrow

Computers are amazing machines. • They seem to be able to do anything. They fly aircraft and spaceships, and control power stations and hazardous chemical plants. Companies can no longer be run without them, and a growing number of sophisticated medical procedures cannot be performed in their absence. They serve lawyers and judges who seek judicial precedents in scores of documented trials, and help scientists in performing immensely complicated and involved mathematical computations. • They route and control millions of telephone calls in networks that span continents. They execute tasks with enormous precision—from map reading and typesetting to graphical picture processing and integrated circuit design. They can relieve us of many boring chores, such as keeping a meticulous track of home expenses, and at the same time provide us with diverse entertainment such as computer games or computerized music. Moreover, the computers of today are hard at work helping design the even more powerful computers of tomorrow

实际上，计算机是什么？ .even the most sophisticated computer is really only a large,well-organized volume of bits,and moreover it can normally carry out only a small number of extremely simple operations on them,such as zeroing, flipping,and testing

实际上，计算机是什么？ •even the most sophisticated computer is really only a large, well-organized volume of bits, and moreover it can normally carry out only a small number of extremely simple operations on them, such as zeroing, flipping, and testing

计算机其实很笨！ if this bit flip this bit zero this bit is 1,flip this bit 01011 01011 01011 if this bit flip this bit zero this bit is I,flip this bit 01001 01001 01011 01101 01001 11011 Flipping Zeroing Testing

计算机其实很笨！

但是，计算机确实很神奇！ 问题1：你 X 能仅仅用这 Equality test(x,y) 三个基本操 zero eq; 作，完成右 flip eq;equality on test x flip eq; 边图中给出 eq test y flip eq;equality on only tumn twice 的问题吗？ If x=y eq=1 Otherwise ec 问题2： 你能将这个操作扩展到， 比如，32位内的整数吗？

但是，计算机确实很神奇！ 问题1：你 能仅仅用这 三个基本操 作，完成右 边图中给出 的问题吗？ 问题2:

一个稍微复杂的例子 ·计算两个1bit的二进制数的和（增加exit和goto操作） add(x,y) 1.zero zO 问题3： 2.zero z1 3.equality test(x,y) 如果只用zero、flip、test 4.test eq goto 7 exit、goto操作，能完成 5.flip zO 这个任务吗？ 6.exit z1z0 7.zero t 8.flip t 9.equality test(x,t) 10.test eq flip z1

一个稍微复杂的例子 • 计算两个1bit的二进制数的和(增加exit和goto操作) add(x,y) 1. zero z0 2. zero z1 3. equality test(x,y) 4. test eq goto 7 5. flip z0 6. exit 7. zero t 8. flip t 9.equality test(x,t) 10. test eq flip z1 问题3： 如果只用zero、flip、test exit、goto操作，能完成 这个任务吗？

一段等价的汇编和高级语言程序 /-计算|x-y川的c代码 ∥----汇编代码--- int absdiff(int x,int y) moMl8(%ebp),%edx;取x的值 moM12(%ebp),%eax;取y的值 cmpl%eax,%edx;比较x和y的值 if (x<y) j1.L3 ;如果y<x转到.L3 subl%eax,%edx;计算y-x return y X; mol%edx,%eax;返▣值 else jmp .L5 ;跳转到.L5 .L3: y<X return x -y; subl%edx,%eax;计算xy } .L5: ;完成

一段等价的汇编和高级语言程序 //--计算|x-y|的C代码- int absdiff(int x, int y) { if (x < y) return y - x; else return x - y; } //----------汇编代码---------- movl 8(%ebp),%edx ; 取x的值 movl 12(%ebp),%eax ; 取y的值 cmpl %eax,%edx ;比较x和y的值 jl .L3 ;如果y<x 转到.L3 subl %eax,%edx ; 计算y-x movl %edx,%eax ; 返回值 jmp .L5 ; 跳转到.L5 .L3: ;y<x subl %edx,%eax ;计算x-y .L5: ; 完成

封装+抽象 ·用最原子的操作封装成更“高级”的操作 ·用三个基本操作可以实现“相等”操作 ·用“相等”操作可以实现一位的加法操作 ·用一位的加法“间接操作”可以实现普通加法 ·a:=x+y 实际上，现代计算机内部电路能提供的“原子”操作远不止这5个基 本操作 不同的原子操作=不同的计算机 实际上，我们在编写程序时使用“封装”的高级操作可以“随心所欲” 不同级别的语言、不同级别的软件库

封装+抽象 • 用最原子的操作封装成更“高级”的操作 • 用三个基本操作可以实现“相等”操作 • 用“相等”操作可以实现一位的加法操作 • 用一位的加法“间接操作”可以实现普通加法 • a:= x + y 实际上，现代计算机内部电路能提供的“原子”操作远不止这5个基 本操作 不同的原子操作 == 不同的计算机 实际上，我们在编写程序时使用“封装”的高级操作可以“随心所欲” 不同级别的语言、不同级别的软件库

尽管计算机几乎无所不能，但本质上都是： It is the bits that"sense"the external stimuli arriving from the outside world via buttons,levers,keys on a keyboard,electronic communication lines,and even microphones and cameras.It is the bits that"decide" how to react to these stimuli and respond accordingly by directing other stimuli to the outside via displays,screens,printers,loudspeakers,beepers,levers,and cranks. 那么，计算机从哪里得到‘sense’和‘decide’能力的？ 计算机最终会成为人的“主人”吗？

尽管计算机几乎无所不能，但本质上都是： 那么，计算机从哪里得到‘sense’和‘decide’能力的？ 计算机最终会成为人的“主人”吗？

关于问题的广义理解 ·求解3x=6和求解ax=b的区别 ·“哪个x能够满足3x=6”:问题的实例 ·在给定任意的a,b时，哪个x能够满足ax=b:问题！ ·计算机解题： ·解一般的题 什么叫“解一般的题”？ ·20万份报纸从印刷厂用50辆汽车，分发到100个小镇的1000个零 售点。如何安排运输？

关于问题的广义理解 • 求解3x=6和求解ax=b的区别 • “哪个x能够满足3x=6”:问题的实例 • 在给定任意的a,b时，哪个x能够满足ax=b：问题！ • 计算机解题： • 解一般的题 什么叫“解一般的题” ？ • 20万份报纸从印刷厂用50辆汽车，分发到100个小镇的1000个零 售点。如何安排运输？