第4章 问题求解与计算思维

.,第4章问题求解与计算思维,主讲教师：郑立垠,计算机与通信工程学院计算机应用技术系,.,中国自古就有喝茶的历史习俗，有同学知道泡茶的流程吗？烧水温具置茶冲泡奉茶赏茶续水,引入,.,有一个牧羊人带着一只羊,一匹狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？,过河的方案:第一步：人和羊过河，人返回，留下羊；第二步：人和狼过河，人和羊返回，留下狼；第三步：人和菜过河，人返回，留下菜；第四步：人和羊过河。,人在解决问题时，要先对问题进行分析思考，然后确定解决问题的方法和步骤，这种解决问题的方法和步骤就称为算法。,引入,.,1、算法2、计算思维,本章内容,.,算法的由来,算法算法被誉为计算学科和计算机器的灵魂“算法”（Algorithm）一词源于：公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书（PersianTextbook），书中概括了进行四则算术运算的法则。,.,算法的定义：一个有穷规则的集合，规则规定了一个解决某一特定类型问题的运算序列。定义了任务执行/问题求解的一系列步骤。算法的特征：输入：有零个或多个的输入。输出：有一个或多个的输出。有穷性：一个算法在执行有穷步之后必须结束。确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。可行性：算法原则上能够精确地运行。,算法的定义及特征,.,算法描述,自然语言容易引起歧义，造成误解；对较复杂的问题，难以表达准确流程图直观形象，但计算机不能识别和执行程序代码用计算机能理解和执行的程序设计语言把算法表示出来，然后由计算机按照预定的算法去解决问题。,.,算法设计数学建模数据结构控制流程算法策略遍历搜索递归动态规划贪心.,算法设计,.,算法的正确性：问题求解的过程、方法算法是正确的吗？算法的输出是问题的解吗？20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中算法的效果评价：算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大？两种方法：分析方法：利用数学方法证明仿真分析方法：产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析,算法分析,.,算法的效率：时间效率和空间效率时间复杂性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。“大O记法”：基本参数n问题实例的规模把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“”，如n2+n+1=(n2)算法的空间复杂度：算法在执行过程中所占存储空间的大小。,算法效率,.,算法的复杂性,当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，计算机对于大规模问题可以处理算法的时间复杂度用一个指数函数表示，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题称为难解性问题。,算法效率,当n值增大时，各种时间复杂度存在下列关系：O(log2n)O(n)O(nlog2n)O(n2)C-B-A,示例,旅行商问题,城市之间的距离,.,问题求解中的过程控制,问题求解过程中需要组织并控制操作、指令的过程和顺序,TSP问题求解的流程控制,求解TSP问题需要控制指令、基本操作的逻辑过程/流程遍历所有的组合路径判断某条路径的距离是不是比另外一条短，并据此作出不同的处理累加一条路径的距离之和,旅行商问题,.,算法策略,可行解与最优解遍历能够获得最优解，然而，由于组合爆炸，对于较大规模的某些问题，无法在可接受的时间内获得最优解退而求其次，在可接受的时间内获得足够好的（可行）解,TSP问题的可行解与最优解,旅行商问题,.,算法策略贪心,贪心算法“今朝有酒今朝醉”一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”,TSP问题的贪心求解示例,每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短,城市之间的距离,旅行商问题,.,TSP问题贪心算法的模拟与分析,TSP问题贪心算法的正确性：直观上只需检查算法的输出结果中，每个城市出现且仅出现一次，该结果即是TSP问题的可行解，说明算法正确的求解了这些问题实例TSP问题贪心算法的效果评价：如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价；对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法结果的比较。,旅行商问题,.,TSP问题算法的效率,TSP问题遍历算法：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线组合爆炸：路径组合数目为(n-1)!时间复杂度是O(n-1)!)计算机不能处理TSP问题贪心算法：时间复杂度是O(n3)。计算机可以处理,旅行商问题,.,问题求解总结,.,1.科学与思维的含义(1)科学达尔文曾给科学下过一个定义：“科学就是整理事实，从中发现规律，作出结论”。科学一般包含：自然科学、社会科学和思维科学。(2)思维思维是高级的心理活动，是认识的高级形式。思维是人脑对现实事物概括、加工、揭露本质特征。人脑对信息的处理包括分析、抽象、综合、概括等。2.人类文明进步和科学发现的三大科学(1)理论科学、实验科学和计算科学作为科学发现三大支柱，正推动着人类文明进步和科技发展。(2)该说法已被科学文献广泛引用，并在美国得到国会听证、联邦和私人企业报告的承同。,计算思维,.,3.科学思维(1)一般而论，三种科学对应着三种思维：理论科学理论思维：理论思维又叫推理思维，以推理和演绎为特征，以数学学科为代表。实验科学实验思维：实验思维又叫实证思维，以观察和总结自然规律为特征，以物理学科为代表。计算科学计算思维：计算思维又叫构造思维，以设计和构造为特征，以计算机学科为代表。(2)科学思维的含义及重要性：一般指的是理性认识及其过程，也即经过感性阶段获得的大量材料，通过整理和改造，形成概念、判断和推理，以反映事物的本质和规律。国科发财2008197号文关于创新方法工作的若干意见认为“科学思维不仅是一切科学研究和技术发展的起点，而且始终贯穿于科学研究和技术发展的全过程，是创新的灵魂”。,计算思维,.,计算思维,计算思维(ComputationalThinking，CT)是运用计算的基础概念(FundamentalConcept)去求解问题、设计系统和理解人类行为的一种方法(Approach)。CT的本质是抽象(Abstract)和自动化(Automation)。它是如同所有人都具备“读、写、算”（简称3R）能力一样，都必须具备的思维能力。基本概念：约简、嵌入、转化、仿真、递归、并行、多维分析、类型、抽象、分解、SoC，保护、冗余、容错、纠错、系统恢复、启发式、规划、学习、调度、折衷。,.,程序设计课程中问题求解能力培养,问题表示(如何建立模型)问题求解（如何设计算法）效率（如何有效地求解）,.,寻找两个正整数的最大公约数的欧几里德算法输入：正整数M和正整数N输出：M和N的最大公约数算法过程：Step1.将较大的数赋给M,较小的数赋给N;Step2.M除以N,记余数为RStep3.如果R不是0,将N的值赋给M,R的值赋给N,返回Step2;否则,最大公约数是N,输出N,算法结束,欧几里德算法：求解两个数的最大公因子的算法（公元前300年）表述了最大公因子的求解过程表述了一个判定过程，即判定“m和n是互质的”（即除1以外，m和n没有公因子）命题的真假。,求最大公约数,.,乒乓球挑选,有13个乒乓球，其中有一个是坏的，其质量与其它球不同，请设计算法将其挑出。,建模与设计,.,解答1：步骤1：将13个球分成4,4,4,1四份，分别记为a，b，c，d组；步骤2：先比较a，b两组的轻重，若a与b一样重，取c中任意4个球与a或b比较，若都一样重，则d组为次品，若不一样重，则可知次品在c组取出的4个球中，并且可判断次品是轻还是重；若a与b不一样重，取c组与a或b进行称量对比，得出含有次品组为a组或者b组以及判断出次品是轻还是重。步骤3：从步骤2中得到含有4个球的次品组，将这4个球平分成2组称量，根据次品是轻或重得到含有次品组e，再将次品组e中2个球分别放置天平两端，根据次品轻重判断得到次品球。,乒乓球挑选,.,解答2：（1）将13个球分为三个部分，6，6,1，将6,6两部分进行称量，若平衡，则1所代表物品为次品；否则（2）（2）取一组6，将其平分为两组计为a，b；另一组6再平分为c,d；取a,b,c两两称量，若都平衡则次品在d中，转到（3）；若有一次不平衡，则次品在a,b,c之中，转到（3）（3）将三个任取两个称量，若平衡，则次品为未称量的物品；若不平衡，则转到（4）（4）若不平衡再测一次即可得次品。,乒乓球挑选,.,解答3：将13个球记为1,2,3,4,5,5,6,7,8,9,10,11,12,13。16记为A，712号记为B；步骤1：将AB组球放在天平上，若天平平衡，则次品为13号球；若不平衡，则转向步骤2；步骤2：取较轻的一组，不妨设为A,将A组重新分成两组放在天平两端，若平衡，则转向步骤3，不平衡转向步骤4；步骤3：将B组分成两组记为a,b，放在天平两端，（由步骤2值次品较重），取较重的一组，不妨设其为a，任取两个球放在天平两端，若天平平衡，则为a中的另一个球；若不平衡，则较重的为次品；步骤4：将A组分成两组，取较重的一组（三个球），任取两个放在天平两端，若平衡，则为三个中的另一个，若不平衡，则为较重的的球；,乒乓球挑选,.,解答4：步骤1：从这堆产品中任意拿出2产品，放在天平两端；步骤2：记下天平两端是否相平；相平执行步骤3；否则执行步骤5；步骤3：从天平的右端拿下产品，再从剩余产品中任意拿出一个放在右端，记下是否相平；步骤4：若相平，重复步骤3，直到不平为止，则此时右端产品为劣质；步骤5：拿下右端产品，再从剩余产品中任意拿出放在右端，若相平，则之前拿下的为劣质；否则左端为劣质,乒乓球挑选,.,两