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

问题求解 论题1.1：计算机为什么能解题？ 2019年10月 2022/12/14

单击此处编辑母版标题样式 2019年10月 2022/12/14 1 问题求解 论题1.1：计算机为什么能解题？

Computers are amazing machines Navigation fly aircraft and spaceships Entertainment Industry provide diverse entertainment such as control power stations and computer games or computerized chemical plants music Communication Business route and control millions of help companies to make telephone calls in networks 自 decisions Mathematics Medical perform immensely complicated and involved mathematical sophisticated medical procedures computations Law 2022/12/14 serve lawyers and judges 2

Entertainment provide diverse entertainment such as computer games or computerized music Mathematics perform immensely complicated and involved mathematical computations Communication route and control millions of telephone calls in networks Industry control power stations and chemical plants Medical sophisticated medical procedures Business help companies to make decisions Navigation fly aircraft and spaceships Law 2022/12/14 serve lawyers and judges 2 Computers are amazing machines

What is Computer? Volume of Bits Even the most sophisticated computer is really only a large,well-organized volume of bits. if this hit Operations fip this bit zero this bit is I.flip this bit 0101 0101 0101 if this b翊 It can normally carry out only a p邮如 zero this bit is1,明 this bit 0100 0101 small number of extremely 0100 simple operations on them,e.g., 01101 0100 1101 zeroing,flipping,and testing Flipping Zeroing Testing 2022/12/14

2022/12/14 3 What is Computer? Even the most sophisticated computer is really only a large, well-organized volume of bits. Volume of Bits It can normally carry out only a small number of extremely simple operations on them, e.g., zeroing, flipping, and testing Operations

It's amazing!Isn't it? if this bit flip this bit zero this bit is 1.flip this bit 01011 0101川 0101川 Computer is if this bit flip this bit zero this bit is 1.flip not that this bit 01001 01001 0101山 SMART!!! 01101 01001 11011 Flipping Zeroing Testing

2022/12/14 4 It’s amazing! Isn’t it? Computer is not that SMART!!!

What is Computer? if this bit X flip this bit zero this bit is 1.flip this bit 0101 01011 01011 if this bit How to flip this bit zero this bit is I.flip this bit check the 01001 01001 01011 equality of eq 01101 01001 H01 two bits？ If x=y eq=1 Otherwise eq=0 Flipping Zeroing Testing 5

2022/12/14 5 What is Computer? How to check the equality of two bits?

What is Computer? Equality test(x,y) zero eq; How to flip eq;产equality on check the test x flip eq; equality of test y flip eq;equality on only tum twice two bits？ Can you extend it to check the equality of two 32-bit binary numbers? Assume,X =x31,x30,..,x,Y=y31,y30,...,yo

2022/12/14 6 What is Computer? How to check the equality of two bits? Assume, 𝑋 = 𝑥31, 𝑥30, … , 𝑥0 , 𝑌 = 𝑦31, 𝑦30, … , 𝑦0 Can you extend it to check the equality of two 32-bit binary numbers?

Another "complicated"example Operations allowed to use add(x,y) How to flip,zero,test 1.zero z0 calculate exit,goto 2.zero z1 3.equality test(x,y) the sum of X 4.test eq goto 7 5.flip z0 two 1-bit 6.exit 1， binary 7.zero t 8.flip t number 9.equality test(x,t) 10.test eq flip z1

2022/12/14 7 Another “complicated” example How to calculate the sum of two 1-bit binary number ? flip, zero, test exit, goto Operations allowed to use 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

Another "complicated"example add(x,y) X2X1 How to 1.zero z0 2.zero z1 y2 y1 calculate 3.equality test(x,y) the sum of 4.test eq goto 7 Z2 Z1 Zo 5.flip z0 two 2-bit 6.exit binary 7.zero t YES 8.flip t numbers? 9.equality test(x,t) WE 10.test eq flip z1 CAN

2022/12/14 8 Another “complicated” example How to calculate the sum of two 2-bit binary numbers? 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 𝑥1 𝑦1 𝑥2 𝑦2 𝑧2 𝑧1 𝑧0

Encapsulation Abstraction flip zero test goto exit “Atomic” operations Equality test (x.y) zero eq; add(x,y) can be flip eq;equality on 1.zero z0 test x flip eq; 2.zero z1 combined to test y flip eq;equality on only tum twice 3.equality test(x,y） 4.test eq goto 7 5.flip z0 generate 6.exit 7.zero t “Compound' 8.flip t 2-bitAdd(x,y) 9.equality test(x,t) operations! 10.test eq flip z1 9

2022/12/14 9 Encapsulation + Abstraction “Atomic” operations can be combined to generate “Compound” operations! 2-bitAdd(x,y) flip zero test goto exit …

Encapsulation Abstraction Compound Operations “Atomic” Provide higher functional abstractions operations can be Encapsulate underlying details of implemented by lower operations combined to generate Can be directly used as atomic “Compound' operations operations! Can be further combined to provide new higher compound operations/functions

2022/12/14 10 Encapsulation + Abstraction “Atomic” operations can be combined to generate “Compound” operations! • Provide higher functional abstractions • Encapsulate underlying details of implemented by lower operations • Can be directly used as atomic operations • Can be further combined to provide new higher compound operations/functions Compound Operations