第0章 计算思维概论.pptVIP

* 计算思维简介 * 计算思维简介 策略1：从空白图开始的策略，如果有必要就渐渐地增加砖块直到所有的房子都连接起来。这是一个好的策略；事实上，你能保证找到一种优化解决方案，如果你增加路径的时候按顺序的增加路径长度，但一旦所有的房子都连接起来之后就不再添加任何路径。不同的解决方法是通过改变添加相同长度路径的顺序而已。 策略2：将所有的路径都铺好，然后再把冗余的路径除掉。这将产生一个优化解决方法，但需要相当大的工作。  * 计算思维简介 解法1： * 计算思维简介 解法2： * 计算思维简介 问题的抽象表示 问题的一种解法 * 计算思维简介 相关知识 假设你是设计一项公共设施如电力、煤气或水等应该如何传输到一个新的社区。一个网络的点线或管道是必要连接到所有的家庭以及公共设施公司。每个家庭必须连接到网络上的一个点，但其他线路从公共设施到房子间的线路通常不是很重要的，只要线路存在就行。这个任务设计的一个使总路径最短的网络称作最小生成树。  * 计算思维简介 相关知识 最小生成树不仅在天然气和电力网络中很有用；他们帮助我们在不同应用如计算机网络、电话网、石油管道和飞机航线中解决问题，然而，正如上面所说的，你必须在考虑线路的代价的同时也考虑到线路的方便与否。这对在图表中解决其他问题诸如“旅行商问题”如何寻找在网络中访问所有的节点最短的路径第一步是很有用的。  * 计算思维简介 相关知识 最小生成树问题存在高效的算法（方法）。一个简单的最佳解决方法就是从没有任何连接开始，然后不断添加连接和增加规模，只把网络中先前没有连接的部分连接起来。这种方法之前已经提到过，但是学生们必须自己发现这种算法。这种算法在J.B.Kruskal于1956年发表之后叫做Kruskal算法。  * 计算思维简介 问题2：网络中的路由和死锁 关注焦点 解决问题的协作能力、逻辑推理的合理性、计划编制 摘要 人们在争夺稀缺资源时，筹划周密是必要的。当对资源的需求有依赖关系时(如：汽车使用公路，通过网络获取信息)，有可能出现“死锁”的情况，在任何人继续下去之前，死锁都一直存在，因此，有些人总是必须返回的。协作程序要求每人在出现“死锁”之前完成预想的结果。 专有名词 路由，死锁，信息传输  * 计算思维简介 原始问题——橙子游戏 6个小孩玩11个橙子的游戏，其中D小孩有一只手是空的。将孩子用字母做了标签，橙子也同样做了标签，一个字母对应两个橙子。孩子们穿同样标记的衣服以展现他们的字母。这些橙子被混合在一起，使字母跟对应的小孩暂时不能在一起。孩子们一手举着一个橙子。  * 计算思维简介 游戏的目标是让孩子们通过橙子，使每个孩子最终持有他们相应的橙子--如：A小孩必须持有包含A标签的橙子等等。这里有两条必须遵循的规则： (a)小孩一只手只能举一个橙子。 (b)橙子只能通过空手，然后立即传给圆中的邻居。 上图的游戏规则是：只允许C或E的小孩传橙子给D小孩。D小孩可以从C或E小孩传得橙子。  * 计算思维简介 游戏过程中，小孩们很快就会发现，如果他们“贪婪”(一旦得到自己的橙子就不放手)，那么该组可能永远无法实现其目标。强调个人不“赢”的游戏是必要的，但在该游戏中，只有当每个人都有自己的橙子，这个问题才被真正解决。  * 计算思维简介 变换与拓展 该游戏有很多可能的变化。例如： 1.尝试在更大或者更小的圆圈中玩这种游戏。 2.有其它小孩进来的变异规则。 3.在小孩间不交谈的情况下进行游戏。 4.尝试用一种不同的配置传递消息，如：所有小孩坐在一条直线上，或者对某些小孩有两个甚至更多的邻居。(如右图) 5.这个问题可以模拟出由一个人来操纵令牌，自动协作，但策略仍可加以探讨。  * 计算思维简介 相关知识 如道路系统和交通拥堵，电话和电脑系统中，路由和死锁在许多不同类型的网络是个重要的问题。工程师们花了很多时间来弄清楚如何解决这些问题，以及如何设计网络，其中的问题是容易解决的。 在许多不同类型的网络里，路由、拥塞和死锁，可成为当前令人沮丧的问题。试想一下，你最喜欢的时间，却是交通最拥挤的时间段被耗掉！在纽约市的交通街上，堵塞的情况已经出现好几次了，它变得如此的拥挤，以致出现死锁的情况：没有一个人能够开走他们的车。很多时候，许多商业部门(如银行)之所以倒闭，便是因为他们电脑的通信网络出现了死锁。设计网络，使路由简单而有效和拥塞最小化，这也是许多工程师所面临的一个困难问题。 。  * 计算思维简介 相关知识 对现代计算机更可能出现的情形是，用户在竞争使用放置在一个数据库上的数据。如果一块数据（如顾客的银行存款余额）正在更新，在更新过程中，“锁住”它是非常重要的，因为来的另外一个资源同步更新，可能导致记录存款出现