资源描述：
《计算机问题求解-算法在计算机科学中的地位ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机问题求解–论题1-1-为什么计算机能解题2018年09月18日计算机问题求解计算机问题求解问题1a:计算机究竟能干什么？问题1b:人究竟是如何解题的？问题1：为什么计算机能帮我们解题？PartI了解计算机Beyondformaleducation,normalmaturationoragingitselfissadlyaccompaniedbythemonotonicdimmingofone'scuriosity.-BulentAtalayAmazingMachine问题2：你理解“抽象”的含义吗？如果从解题的
2、角度让你“极度抽象”，你会如何想象计算机这个“黑匣子”的内部结构呢？EvenMoreAmazing注意：每个operation有相应的operand（1个或多个）问题3：我们可以让计算机“间接地”执行什么操作？你试试让计算机比较两个1-bit二进制数是否相等，只用前面提到的运算，如果需要，你可以使用辅助的bits,注意：这里testing操作有两个不同的operands.xyeqEqualitytest(x,y)zeroeq;flipeq;/*equalityontestxflipeq;testyflipeq;Ifx
3、=yeq=1Otherwiseeq=0你能将这个操作扩展到,比如,32位内的整数吗?问题4：Eq最终的值取决于什么？增加两个操作，可间接地利用判断相等的操作实现加法计算两个1-bit二进制数的和xyz1z0x+yadd(x,y)1.zeroz0;2.zeroz1;3.equalitytest(x,y);4.testeqgoto75.flipz0;/*x,y不同，和为1(01)6.exit;7.testxflipz1;/*x,y是1，则结果是2(10)问题5：你能说出这新增操作的关键价值吗？goto,exit问题6：那
4、么如果只允许使用原来的三个操作，你还能完成这个任务吗？没法分支，没法分情况处理。add(x,y)1.zeroz0;2.flipz0;3.zeroz1;4.equalitytest(x,y);5.zerot6.testeqflipt;7.testtflipz0;8.testtflipz1;……(是否有可能让x=y=0时z1变为0）xyz1z0tx+y输出置为01(t=0),假如x,y不等，结果正确。若x=y,输出置为10(t=1)，可能错我们很容易区分两加数是否相等，但确难以判断在相等的前提下是0还是1，这体现了“语言
5、表达能力”的差别。多层次抽象用一位的加法“间接操作”可以实现普通加法操作；加法操作又可以作为一步操作用在更复杂的“间接操作”中。实际上现在计算机内部电路能提供的操作远不只是那几个最简单的“直接”操作。内部与外部问题7:区分“内部与外部”对于让计算机“什么都能干有什么意义?问题8：现在你能回答“计算机究竟能做什么”了吗？也许可以这样回答：计算机本身做不了什么，但在人的“指挥”下，计算机似乎什么都能做，因为“间接”有无限的“想象空间”。问题9：我们如何“指挥”？写程序？学会了“语言”就会写程序吗？PartIIProble
6、m-Solvingingeneral我们如何解题?GeorgePolya:“HowtoSolveIt?”Understandingtheproblem:“Whatyouaregivenandwhatyouaresupposedtofigureout”Devisingaplan:“Howwillyouattacktheproblem?”Carryingouttheplan:Solvetheproblem.Lookingback:checktheresult,and…问题10:计算机能帮我们做什么?我们如何解题,用计算机
7、?计算机如何理解问题?输入是什么?输出是什么?如何针对计算机制定计划?什么样的”计划”可能在计算机上实现?什么样的形式才能让计算机知道该怎么做?执行计划–“计算机解题”只有这个才真正是计算机做的!回头看为什么结果是正确的?效率能提高吗?问题11:怎样才能让计算机帮到我们?一个例子–“渡河问题”问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能驾船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”
8、，结束状态是“空”。“允许状态”只有10个。问题的解：找到一条从起始状态到结束状态的尽可能短的通路。空(成功)人羊狼菜人狼菜人羊狼人羊菜狼菜狼菜人羊羊计算机问题求解与数学对问题的理解必须用严格的数学语言描述。其前提是必须建立问题的数学模型。可用的数学模型必须是计算机能对其进行操作的。让计算机能理解的解题plan必须建立在严密的数学基础上。将pl
