Download presentation
Presentation is loading. Please wait.
1
计算机问题求解 – 论题1-1 - 为什么计算机能解题
计算机问题求解 – 论题 为什么计算机能解题 2018年09月18日
2
计算机问题求解 计算机 问题求解 问题1b: 人究竟是如何解题的？ 问题1a: 计算机究竟能干什么？ 问题1：为什么计算机能帮我们解题？
3
Part I 了解计算机 Beyond formal education, normal maturation or aging itself is sadly accompanied by the monotonic dimming of one's curiosity. - Bulent Atalay
4
Amazing Machine
5
问题2： 你理解“抽象”的含义吗？如果从 解题的角度让你“极度抽象”，你 会如何想象计算机这个“黑匣子” 的内部结构呢？
6
Even More Amazing 注意：每个operation有相应的operand（1个或多个）
7
问题3：我们可以让计算机“间接地”执行什么操作？
你试试让计算机比较两个1-bit二进制数是否相等，只用前面提到的运算，如果需要，你可以使用辅助的bits, 注意：这里testing操作有两个不同的operands.
8
x y eq 问题4： Eq最终的值取决于什么？ Equality test (x,y) zero eq;
flip eq;/* equality on test x flip eq; test y flip eq; y 问题4： Eq最终的值取决于什么？ eq If x=y eq=1 Otherwise eq=0 你能将这个操作扩展到, 比如, 32位内的整数吗?
9
增加两个操作，可间接地利用判断相等的操作 实现加法
增加两个操作，可间接地利用判断相等的操作 实现加法 goto, exit x 计算两个1-bit二进制数的和 add (x,y) 1. zero z0; 2. zero z1; 3. equality test(x,y); 4. test eq goto 7 5. flip z0; /*x,y不同，和为1(01) 6. exit; 7. test x flip z1; /*x,y是1，则结果是2(10) y z1 z0 x+y 问题5： 你能说出这新增操作的关键价值吗？
10
问题6： 那么如果只允许使用原来的 三个操作，你还能完成这个 任务吗？ 没法分支，没法分情况处理。
11
x y t z1 z0 add (x,y) 1. zero z0; 2. flip z0; 3. zero z1;
4. equality test(x,y); 5. zero t 6. test eq flip t; 7. test t flip z0; 8. test t flip z1; …… (是否有可能让x=y=0时z1变为0） y 输出置为01 (t=0), 假如x,y不等，结果正确。 z1 z0 若x=y, 输出置为10 (t=1)，可能错 x+y t 我们很容易区分两加数是否相等，但确难以判断在相等的前提下是0还是1，这体现了“语言表达能力”的差别。
12
多层次抽象 用一位的加法“间接操作”可以实现普通加法操作； 加法操作又可以作为一步操作用在更复杂的“间接操作”中。
实际上现在计算机内部电路能提供的操作远不只是那几个最简单的“直接”操作。
13
内部与外部 问题7: 区分“内部与外部”对于让计算机 “什么都能干有什么意义?
14
现在你能回答“计算机究竟能做什么”了吗？
问题8： 现在你能回答“计算机究竟能做什么”了吗？ 也许可以这样回答： 计算机本身做不了什么，但在人的“指挥”下，计算机似乎什么都能做，因为“间接”有无限的“想象空间”。
15
问题9： 我们如何“指挥”？ 写程序？ 学会了“语言”就会写程序吗？
16
Problem-Solving in general
Part II Problem-Solving in general
17
问题10: 计算机能帮我们做什么? 我们如何解题? George Polya: “How to Solve It?”
Understanding the problem: “What you are given and what you are supposed to figure out” Devising a plan: “How will you attack the problem?” Carrying out the plan: Solve the problem. Looking back: check the result, and… 问题10: 计算机能帮我们做什么?
18
我们如何解题, 用计算机? 计算机如何理解问题? 如何针对计算机制定计划? 执行计划 – “计算机解题” 回头看 输入是什么? 输出是什么?
什么样的”计划”可能在计算机上实现? 什么样的形式才能让计算机知道该怎么做? 执行计划 – “计算机解题” 只有这个才真正是计算机做的! 回头看 为什么结果是正确的? 效率能提高吗?
19
问题11: 怎样才能让计算机 帮到我们?
20
一个例子 – “渡河问题” 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能驾船。
图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。 起始状态是“人狼羊菜”，结束状态是“空”。“允许状态”只有10个。 问题的解：找到一条从起始状态到结束状态的尽可能短的通路。 空 ( 成功 ) 人羊狼菜 人狼菜 人羊狼 人羊菜 狼菜 狼 菜 人羊 羊
21
计算机问题求解与数学 对问题的理解必须用严格的数学语言描述。 其前提是必须建立问题的数学模型。 可用的数学模型必须是计算机能对其进行操作的。
让计算机能理解的解题plan必须建立在严密的数学基础上。 将plan表示为计算机能执行的“指示”的语言必须建立在 严密的数学基础上。 分析计算机计算的结果必须使用数学方法： 用逻辑证明结果正确； 动用必要的数学手段分析解法的效率。
22
如何安排数据也很重要 问题12： 还记得前面问你如何将1位计算扩展成32位计 算吗，与这里有何不同？ 题解 = “算法+数据结构”
23
问题13: 你知道Google(或者百度) “背后”有什么吗？ 它为什么能找出你要的内容，而且很快？ 它为什么能将你可能最想要的放在最前面？
24
问题14: 计算机下象棋、围棋能战胜世界 冠军, 识别人的能力还比不上三 岁小儿,为什么?
25
问题15： 你对计算机的“智能”是如何理解的？又是如何期待的呢？
26
任何小方块不能旋转，但可以两两交换位置。边界两边颜色相同得1分。最高分为172。
穷举法显然不现实！ 铺砖算法 多次反复执行： 1 温度降低少许 2 随机选择要交换的两块花砖 3 如果交换后游戏得分值下降： 4 随机决定是否保留这次交换 5 保留交换的概率值随着温度值下降逐步下降 6 如果决定不保留则撤销本次交换操作
27
得分：171
28
我们最不愿意看到的前景 有“智能”的机器 Vs. 没有“智能”的人 也许，我们该区分“智能”与“智慧”。
29
算法是用计算机解题的关键 至少在可以看见的未来仍会如此
As soon as an Analytical Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will then arise – By what course of calculation can these results be arrived at by the machine in the shortest time? - Charles Babbage, 1864
30
课外作业 UD 1.2 – 1.6; 1.8 探讨用我们所介绍的3个基本操作实现加法的可能性，如果你认为不可能请给出你的论据。
采用类似渡河问题的方法解如下问题： 3个容积分别为8，5，3升的油桶，没有容量刻度，最大的桶装满油，其它两个是空的，你可以将任一桶中的油的全部或部分倒入另外的桶，但不可溢出。要分出4升油，至少要倒多少次？
Similar presentations
