计算机科学导论-计算思维程序实践 课件 第1、2讲-从小白鼠验毒到数据传输校验-初识计算思维、从数学和计算机看方程求解-最基本的计算思维枚举-计算-验证

第1讲从小白鼠验毒到数据传输校验

—初识计算思维哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣什么是计算思维？计算机，仅仅是这样的吗？计算机不仅仅是编程，还有计算思维。计算思维是人们普适的思维方式思维有多远，决定你能走多远有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时内就会死亡，问：至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒？测试一下你的思维…一个示例【问题】小白鼠验毒问题？012997有毒998999111110011111111001101111100101000000001000000000010000000000【求解】小白鼠验毒问题之求解一个示例00000101001110010111011100011011013位23=8个2位22=4个1位21=2个9位29=512个10位210=1024个这里用到了递推，也是计算思维012997有毒998999111110011111111001101111100101000000001000000000010000000000B9B8B7B6B5B4B3B2B1B0M9M8M7M6M5M4M3M2M1M0B9=1B8=1B7=1B6=1B5=1B4=1B3=1B2=1B1=1B0=11000瓶水分给10只小白鼠喝，分配原则是：如一瓶水的Bi位为1，则给Mi小白鼠喝一口；哪些小白鼠死掉了?死掉为1，不死为0：M9M8M7M6M5M4M3M2M1M0=1111100101有什么启示吗?【求解】小白鼠验毒问题之求解一个示例难度：【0和1的多种语义的组合应用】小白鼠“喝”与“不喝”与小白鼠“死”与“活”，水的“有毒”与“无毒”不同的两种状态都可表达为0和1---小白鼠-“死”与“活”；---小白鼠对某瓶水-“喝”与“不喝”；---水“有毒”与“无毒”用0/1编码串表示不同的含义---000010---对应第(000010的十进制)瓶水---000010---第i位对应第i只小白鼠，1喝0不喝；---000010---第i位对应第i只小白鼠，死1

活0

；000010多种不同的含义统一在一个01串中，可无缝隙实现含义转换多种不同的含义均用01串表达计算思维理解的关键点示例背后的思维0和1

---1000瓶分为A1组500瓶,B1组500瓶---500瓶分为A2组250瓶,B2组250瓶---250瓶分为A3组125瓶,B3组125瓶------2瓶分为A10组1瓶，B10组1瓶二分法思维示例背后的思维二分法ABCDE二分法为什么不行呢？二分法-串行使用小白鼠---1只能区分2瓶，2只能区分4瓶，…,n只能区分2n瓶二分法与二进制思维二分法-并行使用小白鼠---“组合”识别水瓶，n位编码能区分出2n瓶的某一瓶示例背后的思维二进制与并行二分法串行-并行也是计算思维用二进制编码作并行划分也是计算思维过程化思维---水瓶十进制编号(所有)

二进制编码

分配给小白鼠喝(第i位对应第i只小白鼠，1喝0不喝)

小白鼠死与活

再形成二进制编码(第i位对应第i只小白鼠，死1活0)

十进制编号(有毒编号的水瓶)。符号变换与逻辑推理---由小白鼠的死活用计算的手段推断第几瓶水有毒---符号变换：十进制变换为二进制，二进制再变换为十进制。过程化与符号变换思维示例背后的思维符号变换与过程化【计算思维】是运用计算科学的基础概念去求解问题、设计系统和理解人类行为。From周以真，前卡耐基.梅隆大学计算机系系主任教授、前微软公司高级副总裁、前美国国家科学基金会助理局长。她在世界范围内推动了计算思维教育，尤其强调在大学低年级以及中学阶段进行计算思维教育，她认为到21世纪中叶计算思维能力是人人都应具备的一种基本能力。计算思维是一种科学与工程思维，是未来可以转化为创新的思维计算思维是关于计算方法与计算系统的思维（包括设计、构造和应用）、是一种大思维而非小技巧计算思维不仅仅是程序思维、算法思维和问题求解思维（这些可被认为是计算+思维），而是覆盖计算+思维、互联网+思维、大数据思维和人工智能+思维等相对完整的计算思维内容体系怎样创新？且看下例什么是计算思维？【思维】什么是计算思维？·“偶校验规则”--使传输前和传输后相关位1的个数始终为偶数--偶数个1相加和为0；奇数个1相加和为1010110100010101001传输1001101110110111判断数据传输过程是否有错误发生？问题：数据传输的检错与纠错。【应用】通讯数据校验问题及其求解示例思维的价值7654321P4=D7+D6+D5+D4---编号的第3位为1P2=D7+D6+D3+D2---编号的第2位为1P1=D7+D5+D3+D1---编号的第1位为11101001111P4’P2’P1’1101101数据111110101100

011

010

001数据位二进制编号D7D6D5D4D3D2D1P4P2P1数据位校验位1101101111传输P4’=D7+D6+D5+D4+P4P2’=D7+D6+D3+D2+P2P1’=D7+D5+D3+D1+P1小白鼠“喝”与“不喝”小白鼠“死”与“活”11

1110【应用】通讯数据校验问题及其求解示例思维的价值传输7654321P4=D7+D6+D5+D4---编号的第3位为1P2=D7+D6+D3+D2---编号的第2位为1P1=D7+D5+D3+D1---编号的第1位为11001101111P4’P2’P1’1101101101数据111110101100011010

001数据位二进制编号D7D6D5D4D3

D2D1P4P2P1数据位校验位1101101111P4’=D7+D6+D5+D4+P4P2’=D7+D6+D3+D2+P2P1’=D7+D5+D3+D1+P1小白鼠“喝”与“不喝”小白鼠“死”与“活”111换一位出错是否能判断？【应用】通讯数据校验问题及其求解示例思维的价值传输传输P8=编号的第4位为1的位相加=D11+D10+D9=0P4=编号的第3位为1的位相加=D7+D6+D5=0P2=编号的第2位为1的位相加=D11+D10+D7+D6+D3=1P1=编号的第1位为1的位相加=D11+D9+D7+D5+D3=110001100111P8’P4’P2’P1’101011001100111

P8’=D11+D10+D9+P8=1P4’=D7+D6+D5+P4=0P2’=D11+D10+D7+D6+D3+P2=1P1’=D11+D9+D7+D5+D3+P1=0小白鼠“喝”与“不喝”小白鼠“死”与“活”如果校验位出错怎么办？

23

22

21

20

111098

7654

3

2

1D11D10D9P8

D7D6D5P4

D3P2

P11011101010011000011101100101010000110010000111001101111P8’=D11+D10+D9+P8=0P4’=D7+D6+D5+P4=1P2’=D11+D10+D7+D6+D3+P2=0P1’=D11+D9+D7+D5+D3+P1=0【应用】通讯数据校验问题及其求解示例思维的价值小白鼠验毒问题检错与纠错问题---如果7瓶水中有2瓶有毒，则需几只小白鼠，才能确定是哪2瓶有毒？---如果7位二进制位传输过程中有2位出差错，则需几位校验位才能判断是哪2位有差错？编码效率问题？01324567 x%3=0 x%3=1x%3=2x/3=0 001

001(0)001010

(1)001100

(2)x/3=1 010

001

(3)

010010

(4)

010100

(5)x/3=2

100

001

(6)

100010

(7)

计算vs.检错/纠错

计算机/通讯领域重要的发明【应用】通讯数据校验问题及其求解示例思维的价值图灵奖获得者理查德·汉明【汉明码/海明码】学而有用学而有索趣味故事

思维挖掘

价值再现

对比联想

计算与专业融合学而有趣学而有思什么是计算思维？【小结】从示例中，你学到了什么？第2讲从数学和计算机看方程求解

—最基本的计算思维：枚举-计算-验证哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣求ax2+bx+c=0的根怎样求解一元二次方程？人计算与机器计算人计算与机器计算在思维上什么差异？例如：求ax2+bx+c=0的根人-计算机器-计算(1)从-n到n，产生x的每一个整数值；(2)将其依次代入到方程中计算;(3)如果其值使方程式成立，则即为其解；否则不是

利用上述公式计算得到x值怎样求解一元二次方程？人计算与机器计算人-计算一条规则可能很复杂,但计算量却可能很小人需要知道具体的计算规则特定规则，只能求:a1x2+a2x=c机器-计算每条规则可能很简单,但计算量却很大机器也可以采用人所使用的计算规则一般性的规则，可以求任意:a1x1b1+a2x2b2+…+anxnbn=c枚举-计算-验证蛮干思维怎样求解一元二次方程？人计算与机器自动计算的差别人快速获得结果的方法为什么规则要简单？复杂规则怎么办--重复运用简单规则人设计规则-人计算获得结果人设计规则-机器自动计算获得结果机器是如何自动计算的机器自动计算用符号型指令表达规则算法（计算规则）用01编码的指令表达规则用函数/积木块表达规则用语句表达规则机器程序如何执行？CPU(中央处理单元)和存储器(内存/主存)执行程序—芯片级，机器相关各种应用高级语言程序—独立于具体机器高级语言程序如何执行？高端智能机械互联网+高端机械(群)组合-重复表达上，是组合简单规则形成复杂规则执行上，是重复执行简单规则来完成复杂规则无人机例如：求ax2+bx+c=0的根人-计算机器-计算(1)从-n到n，产生x的每一个整数值；(2)将其依次代入到方程中计算;(3)如果其值使方程式成立，则即为其解；否则不是

利用上述公式计算得到x值机器-难于计算(1)在实数空间内，以δ为步长，产生x的每一个数值；(2)将其依次代入到方程中计算;(3)如果其值使方程式成立，则即为其解；否则不是。注意：δ可以是0.1，0.01，…，0.000001，…步长越小，求解精度越高，但计算量也越大。机器能在有限时间内完成计算吗？枚举-计算-验证蛮干

优化可求解与难求解机器一定能计算出结果吗？最基本的计算思维：枚举-计算-验证人快速获得结果的方法算法与算法复杂性x一定是整数解吗？0<=x<=20

0<=y<=33

0<=z=100-x-y0<=x<=100

0<=y<=100

0<=z<=100其他示例最基本的计算思维：枚举-计算-验证【示例1】公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，问：用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各能买多少只？设公鸡x

只，母鸡y

只，小鸡z

只，方程式组：

5x+3y+z/3=100

x+y+z=100

0<=x<=100

0<=y<=100

0<=z<=100优化算法：减少无效计算量基本算法：枚举-计算-验证其他示例最基本的计算思维：枚举-计算-验证【示例2】123456789给出一个排列来，使得前n位组成的整数能被n整除(n=1,2,3,…,9)。A*108+B*107+C*106+D*105+E*104+F*103+G*102+H*101+I*100（1）A%1=0；(2)

（A*101+B*100）%2=0；(3)（A*102+B*101+C*100）%3=0（4）…;(5)(A*104+B*103+C*102+D*101+E*100)%5=0;(6)…;(7)…;(8)…;（9）%9=0A到I取其中之一{1，2，3，4，5，6，7，8，9}优化算法：减少无效计算量基本算法：枚举-计算-验证A-I,任意组成一个排列：不重复计算并依次检查条件(1)-(9)哪些排列是没有意义的,是不需要计算和验证。(1)前5位组成的数能被5整除，第5位只能是5。(2)前2、4、6、8位组成的数能被2、4、6、8整除，则第2、4、6、8位只能是偶数，所以第1、3、7、9位只能是奇数。A={1,3,7,9},B={2,4,6,8},C={1,3,7,9},D={2,4,6,8},E=5,F={2,4,6,8},G={1,