计算思维引导陶先平南京大学计算机软件研究所我们用计算机干什么-走向物理世界与虚拟世界的无缝连接.pptx

计算思维引导陶先平南京大学计算机软件研究所

我们用计算机干什么？走向物理世界与虚拟世界的无缝连接抽象物理世界虚拟世界

数据抽象数据抽象解释核心概念：信息形态、信息组织、存储、检索与利用

相应的逆过程就是解码。Representinformationasbitpatterns怎么把一段文字“放到”计算机里？你怎么知道计算机里一段二进制串表达的就是王国维的“三境界”？

RepresentTextEachofthedifferentsymbolsAuniquebitpattern

ASCII码每个人的电脑里都有不少.txt文件。什么文件是.txt文件？

加法计算不便，而加法是计算机中计算的最根本操作：2+（-2）不能直接得到0000；符号位无法直接参与运算；补码101101是十进制的多少？Representintegers

RepresentImages如果你用放大镜去看这个画的真迹，你必定会看到画布上密布着有色调、灰度的“点”。正是这样的宏观上连续的点，构成了我们的“画”或者叫图像那我们该如何将这幅画“存”到计算机中？

Pixelandbitmap

RepresentSound按照我们处理图像数字化的方法，你会如何思考这个问题？

一个例子–“渡河问题”问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能驾船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”，结束状态是“空”。“允许状态”只有10个。问题的解：找到一条从起始状态到结束状态的尽可能短的通路。空(成功)人羊狼菜人狼菜人羊菜人羊狼 人羊狼菜狼菜羊

问题编码上述关系可以用一个布尔矩阵表示：它也可以表示成一个“数”：1000000000111000000010100000000110……或者，也可以表示成符号串：16#28#2#6#3#768#384#320#112#32在编码世界中，一切皆有可能！So,wejustneedto……人羊狼菜人狼菜人羊狼空狼菜空人羊

因为报告时间问题，建议最多挑一个去讲，其它的跳过。问题抽象问题抽象算法算法是计算思维的核心概念:方法层:算法表示层:编程实现层:机器这差不多也就是计算机科学的主要内容了

定找假币---何谓“计算思维”？给你70个外观完全一样的金币,但是你知道其中有一个是假币,其重量比真币轻。给你一架没有砝码的天平，你可以在天平两边摆任意多个金币，比较他们的轻重。请设计一种方法，通过若干次称量，确哪一个是假币。

我们为什么会这样思考来找到最快的方法？第一种方案:解空间：所有可能的假币位置构成的集合第二种方案:几乎每次压缩空间到一半几乎每次压缩空间到三分之一√

如何表达我们的这个思想？写个程序！ProcedureFindIt(n){币ifn=1{假币；程序结束；}ifn=2{称量中天平上翘起的是假币；程序结束；}//有多于两个硬币将硬币分为几乎数量相同的三堆n1,n2,n3；称量其中数量相同的两堆；if两堆不同重{FindIt(n1);}elseFindIt(n3);}//从n个硬币中找出一个较轻的假//只有两个硬币//其中必定有两堆数量相同//不妨假设n1=n2//不妨假设n1堆轻

到此为止，这个问题我们解决了吗？No！我们还应该至少回答这些问题：你能证明你的解法是正确的吗？你能证明你的解法是最优的吗？你能证明你的程序没有错误吗？2/24/2021

再一个互动游戏：统计到场人数：0，所有人都站起来，每个人都握有一个数字：11，每两个人组成一组，将手中数字相加，并记住。其中一人坐下；2，重复第一步，直到教室中只有一人；3，最后一人，大声报出数字；

这个游戏，给了我们什么启发？

空间压缩1，依然是压缩”问题”空间：N压缩到n-1==》n压缩到n/2三人或者四人或者……都是一种可能的选择，只要一次统计能够被“简单”完成 2，如果每次分组（两人组）后，组内的统计、累计都可以在组内完成，那么：我就只需要完成分组、同步和最后数据的收集工作每个小组，可以并行完成组内工作每个小组都是一个小型计算机系统N个人，如果小组规模是m，那么我只需要进行约logmn次的分组、同步工作我是一个管理了多个可并行运行的计算机系统的“并行计算机系统”多核系统是一个典型案例分治法+并行处理：极大提高了问题求解的效率

如何表达我们的解题过程呢？假设我们有p+1个处理器(0,…,p),其中第0号是master，其它是slaveParallelProcedurecount(n){if(I’mthemaster){将n个数据分为p份：n1,n2,…,npfor(i