哈工大大学计算机基础课件2

大学计算机基础

第三章问题求解哈尔滨工业大学计算机科学与技术学院金野1Recap1.任何信息（数值、文字、多媒体）都可被表示成0，1串。2.图灵将控制处理的规则用0和1表达,将待处理的信息及处理结果也用0和1表达,提出了图灵机模型。3.冯诺依曼根据图灵的设想构建出了冯诺依曼体系计算机，包含输入、输出、存储器、运算器和控制器。4.计算机语言的发展：机器语言->汇编语言->高级语言->以构造方式和事件驱动程序为特征的第四代程序设计语言。人们使用计算机越来越方便，所能实现的功能也越来越多越来越强大。2第3章问题求解3.1算法类问题3.2系统类问题33.1算法类问题欧几里德算法：求解两个数的最大公因子的算法（公元前300年）表述了最大公因子的求解过程表述了一个判定过程，即判定“m和n是互质的”（即除1以外，m和n没有公因子）命题的真假。4欧几里德算法语言描述：输入：正整数M和正整数N输出：M和N的最大公约数算法过程：Step1.将较大的数赋给M,较小的数赋给N;Step2.M除以N,记余数为RStep3.如果R不是0,将N的值赋给M,R的值赋给N,返回Step2;否则,最大公约数是N,输出N,算法结束5例：欧几里得算法的应用设m=56,n=32,求m、n的最大公因子。32除56余数为24；

24除32余数为8；8除24余数为0，算法结束，输出结果8。答：m、n的最大公因子为8。6欧几里得算法的伪代码描述7输入：正整数m和正整数n输出：m和n的最大公约数算法过程：Step1:M=max(m,n),n=min(m,n)Step2:R=MmodNStep3:IfR不等于0,那么M=N,N=R,GotoStep2;否则,最大公约数是N,输出N,算法结束欧几里德算法流程图8开始m<nm与n交换r=mmodnr=0m=nn=r是否否是输出n

结束控制流程图:是人们对解决问题的方法、思路或算法的一种描述。9起止/结束框判断框处理框输入/输出框连接点流向线控制结构：顺序结构：“执行A，然后执行B”10//例：顺序执行，交换M,N{

tmp=M; M=N; N=tmp;}

控制结构：分支结构：“如果P成立，那么执行A，否则执行B”，P是某些逻辑条件11//例：根据M,N大小，选择操作if(M>N){ Max=M;}else{ Max=N;}

控制结构：循环结构：控制指令的多次执行——迭代（iteration）12//例：求平均分Sum=0;//总分Num=100;//人数i=0;do{ Sum+=Score[i];//累加 i++;}while(i<100)Avg=Sum/Num;//求平均

控制结构：循环结构：控制指令的多次执行——迭代（iteration）13//例：求平均分Sum=0;//总分Num=100;//人数i=0;while(i<100){ Sum+=Score[i];//累加 i++;}Avg=Sum/Num;//求平均

控制结构：循环结构：控制指令的多次执行——迭代（iteration）14//例：求平均分Sum=0;//总分Num=100;//人数for(i=0;i<Num;i++){ Sum+=Score[i];//累加}Avg=Sum/Num;//求平均

欧几里得算法的C语言实现15int

Euclid(intm,intn){

intM=max(m,n);//被除数

intN=min(m,n);//除数

intR;//余数

do{ R=M%N;//求余数

if(R!=0)//余数不为0时设定被除数、除数。

{ M=N; N=R; } }while(R>0); returnN; }3.1算法类问题算法（Algorithm）源于数学家的名字：公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的《波斯教科书》（PersianTextbook），书中概括了进行四则算术运算的法则。163.1算法类问题算法的定义：一个有穷规则的集合，规则规定了一个解决某一特定类型问题的运算序列。算法定义了任务执行/问题求解的一系列步骤。算法的特征：有穷性：一个算法在执行有穷步之后必须结束。确定性：算法的每一个步骤必须要确切地定义，不能有歧义。输入：算法有零个或多个的输入。输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量可行性：算法中有待执行的运算和操作必须是相当基本的,可实现的.173.1算法类问题哥尼斯堡七桥问题汉诺塔问题丢番图方程可解性问题旅行商问题背包问题……183.1算法类问题算法类问题：由一个算法可以解决的问题193.1算法类问题旅行商问题（TravelingSalesmanProblem，TSP）威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。20城市之间的距离3.1算法类问题旅行商问题TSP是最有代表性的优化组合问题之一，在半导体制造、物流运输等行业有着广泛的应用TSP难于求解：2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz

的CompaqEV6Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。213.1算法类问题算法类问题求解的过程及思维方法22示例数学模型TSP问题的数学模型建立数学模型是求解算法类问题的第一步数学模型：数学模型就是为了某种目的，根据对研究对象所观察到的现象及其实践经验，用字母、数字及其它数学符号建立起来的等式或不等式以及图表、图象、框图等归结成的一套反映对象某些主要数量关系的数学公式、逻辑准则和具体算法，用来描述客观事物的特征，其内在联系和运动规律。例如:如果访问序列为ABCD，则下一个城市为A3.1算法类问题数学模型求解方法数学模型的求解可以理解为在状态空间/解空间上寻找满足约束并具有某些方面性能的特定解。求解方法：遍历搜索分治动态规划……3.1算法类问题示例TSP问题求解中的数据操纵问题输入：城市之间的距离输出：访问城市的路径中间结果：路径的距离之和、已经访问过的城市、当前的最短路径……确定数据结构问题求解中的数据组织及操纵3.1算法类问题什么是数据结构？数据结构提供了问题求解/算法的数据操纵机制数据结构：如何组织、存储和操作数据的集合数据的逻辑结构：数据之间的关系存储结构：在反映数据逻辑关系的原则下，数据在存储器中的存储方式，有顺序存储结构和链式存储结构。基本运算：(1)建立数据结构；(2)清除数据结构；(3)插入数据元素；(4)删除数据元素；(5)更新数据元素；(6)查找数据元素；(7)按序重新排列；(8)判定某个数据结构是否为空，或是否已达到最大允许的容量；(9)统计数据元素的个数等。263.1算法类问题数据结构基本数据结构：变量向量/列表/数组矩阵/表27112522254539844212801003483751612341234行列M[2,3]向量实例表实例3.1算法类问题示例TSP问题求解的数据结构城市间距离关系表D访问路径/解一维数组S路径距离之和整数变量sum循环计数器i,j,k…1432{A->D->C->B->A}3.1算法类问题确定过程控制问题求解过程中需要组织并控制操作、指令的执行的过程和顺序。29示例TSP问题求解的流程控制求解TSP问题需要控制指令、基本操作的逻辑过程/流程遍历所有的组合路径判断某条路径的距离是不是比另外一条短，并据此作出不同的处理累加一条路径的距离之和……3.1算法类问题确定算法策略求解方法：遍历贪心搜索分治动态规划……30示例所有路径组合及其长度城市之间的距离遍历：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线TSP问题的求解方法组合爆炸路径组合数目：(n-1)!20个城市，总数1.216×1017

，计算机以每秒检索1000万条路线，需386年3.1算法类问题确定算法策略可行解与最优解遍历能够获得最优解，然而，由于组合爆炸，对于较大规模的某些问题，无法在可接受的时间内获得最优解退而求其次，在可接受的时间内获得足够好的（可行）解31示例可行解最优解TSP问题的可行解与最优解3.1算法类问题城市之间的距离确定算法策略——贪心算法贪心算法“今朝有酒今朝醉”一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”32示例城市之间的距离TSP问题的贪心求解示例每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短3.1算法类问题算法的表示方法自然语言；流程图；伪代码；计算机程序设计语言等。333.1算法类问题TSP问题的贪心求解伪代码算法步骤4表示从第2个城市开始逐步选择新的城市;步骤8表示用Sum记录总路线的长度;步骤11输出问题的解。算法的核心——“贪心策略寻找下一城市”体现在算法过程的步骤(5)中，即“从所有未访问过的城市中查找距离S[i-1]最近的城市j”，然而，这一步骤如何执行还有待进一步明确。

(1)S[I]=1;(2)Sum=0;(3)初始化距离数组D[N,N];(4)I=2;(5)从所有未访问过的城市中查找距离S[I-1]最近的城市j;(6)S[I]=j;(7)I=I+1;(8)Sum=Sum+D[S[I-2],j];(9)如果I<=N，转步骤(5)，否则，转步骤(10);(10)Sum=Sum+D[1,j]；(11)逐个输出S[N]中的全部元素;(12)输出Sum。3.1算法类问题将步骤(5)进一步细化，得到如下的过程：从所有未访问过的城市中查找距离S[I-1]最近的城市jDtemp用于在遍历时，保存当前最小的距离。而j存储该城市。K遍历每一个即将可能要访问到的城市，因此，其初始值为2.（A是始点，已被访问了）。L表示访问过的城市。在K确定的前提下，利用L的变化，考察每个已经访问过的S[L]，是否与K相同，即K是否被访问过。一旦确定K被访问过，即S[L]=K，则将K更新为下一个，如果K+1>n，则意味着处理完毕，否则利用更新过的K重新处理。外循环，K变化内循环，L变化TSP问题的贪心求解伪代码3.1算法类问题算法的流程图描述36示例TSP问题贪心算法的流程图3.1算法类问题算法的程序描述——算法的实现程序是算法的一种机器相容（Compatible）的表示程序是利用计算机程序设计语言对算法描述的结果程序可在计算机上执行程序设计语言：C、Java、…程序设计过程：编辑编译链接执行373.1算法类问题算法的程序描述38示例TSP问题贪心算法程序算法的模拟与分析算法的正确性：问题求解的过程、方法——算法是正确的吗？算法的输出是问题的解吗？20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中算法的效果评价：算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大？两种方法：理论分析方法：利用数学方法证明。严格有效但困难。仿真分析方法：产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析。易实现但不能保证永远正确。393.1算法类问题TSP问题贪心算法的模拟与分析TSP问题贪心算法的正确性：直观上只需检查算法的输出结果中，每个城市出现且仅出现一次，该结果即是TSP问题的可行解，说明算法正确的求解了这些问题实例TSP问题贪心算法的效果评价：如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价，对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法结果的比较。403.1算法类问题算法的复杂度算法的复杂度：时间复杂度和空间复杂度时间复杂度：在问题规模增大时，算法的执行时间的增长。“大O记法”：算法处理的数据规模为n。算法的复杂度表示为n的函数。例：O(1),O(n),O(n^2),O(a^n)等等.算法的空间复杂度：算法在执行过程中所占存储空间随问题规模的增长。413.1算法类问题42示例TSP问题算法的复杂性TSP问题遍历算法：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线组合爆炸：路径组合数目为(n-1)!时间复杂度是O((n-1)!)TSP问题贪心算法：时间复杂度是O(n3)。3.1算法类问题算法的复杂性当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，计算机对于大规模问题可以处理。例如，TSP问题的贪心算法算法的时间复杂度用一个指数函数表示，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题称为难解型问题或NP问题。例如，TSP问题的遍历算法433.1算法类问题计算复杂性理论：所有可以在多项式时间内求解的问题称为P类问题所有在多项式时间内能够用不确定的算法解决的问题称为NP类问题，P⊆NP。Openproblem:P=NP?美国克雷数学研究所百万大奖难题443.1算法类问题3.1算法类问题小结453.2系统类问题*系统类问题是指那些不能由单一算法解决的，而必须构建一个系统来解决的问题。例如：卫星导航系统、机器人系统、企业生产管理系统、计算机操作系统等。463.2系统类问题*系统的概念：系统是指由相互联系、相互作用的若干元素构成的，具有特定功能的统一整体。一个大系统往往是复杂的，通常可划分为一系列较小的系统，称为子系统。系统的特性：系统是有结构的：系统内各组成部分（元素和子系统）之间相互联系、相互作用的框架。系统是处于环境之中的：所谓环境是指一个系统之外的一切与它有联系的事物组成的集合。系统要发挥它应有的作用，达到应有的目标，系统自身一定要适应环境的要求。473.2系统类问题系统的特性：系统是有功能的：所谓功能是指系统行为所引起的、有利于环境中某些事物乃至整个环境存在与发展的作用。系统是有行为的：所谓行为是指系统相对于它的环境所表现出来的一切变化，行为属于系统自身的变化，同时又反映环境对系统的影响和作用。系统是有状态的：所谓状态是指系统的那些可以观察和识别的形态特征。状态一般可以用系统的定量特征来表示，如温度T、体积V等。483.2系统类问题49卫星导航系统操作系统机器人系统系统类问题与系统科学50物料需求管理问题系统类问题与系统科学解决系统类问题需要采用系统科学方法：系统科学是以系统为研究和应用对象的一门科学，诞生于20世纪40年代。系统科学的崛起被认为是20世纪现代科学的两个重大突破性成就之一。系统科学是探索系统的存在方式和运动变化规律的学问，是对系统本质的理性认识，是人们认识客观世界的一个知识体系。系统科学方法是用系统的观点来认识和处理问题的各种方法的总称。计算学科中的结构化方法、面向对象方法都沿用了系统科学的思想方法。51系统类问题与系统科学（系统科学）解决系统类问题遵循的原则：整体性原则：非还原性是指系统的整体具有但还原为部分便不存在的特性——“涌现性”非加和性是指整体不能完全等于各部分之和——“贝塔朗菲定律”研究系统时，应从整体出发，立足于整体来分析其部分以及部分之间的关系，进而达到对系统整体的更深刻的理解。整体优化原则：运用各种有效方法，从系统多种目标或多种可能的途径中选择最优系统、最优方案、最优功能、最优运动状态，达到整体优化的目的。52系统类问题与系统科学（系统科学）解决系统类问题遵循的原则：动态原则：系统总是动态的，永远处于运动变化之中。研究系统时，应从动态的角度去研究系统发展的各个阶段，以准确把握其发展过程及未来趋势。模型化原则根据系统模型说明的原因和真实系统提供的依据，提出以模型代替真实系统进行模拟实验，达到认识真实系统特性和规律性的方法。模型化方法是系统科学的基本方法，主要采用符号模型，包括概念模型、逻辑模型、数学模型等。基于计算机的模型（Computer-BasedModel），计算思维（Computationalthinking），建立基于计算机的模型，利用计算手段研究和解决系统类问题。53系统类问题求解过程及思维方法54业务模型与业务建模系统类问题求解的第一步——业务建模/问题域建模系统类问题是复杂问题，解决该问题的前提是正确的理解问题，把握系统的目标、结构、行为等，并将其描述出来运用系统科学的模型化原则这一过程称为——业务建模/问题域建模获得的结果——业务模型55业务模型与业务建模模型与建模的概念模型是对某一真实系统（如卫星导航系统、企业）的目标、结构、行为的抽象描述。模型的内容：识别概念识别概念间的关系…表达（可视化/形式化）建模的根本原则——抽象：把握系统的本质内容，而忽略与系统当前目标无关的内容，它是一种基本的认知过程和思维方式。56业务模型与业务建模业务建模/问题域建模的内容业务过程模型组织模型信息模型….业务模型的作用：理解区分命名表达57业务模型与业务建模58示例物料需求管理问题的业务模型概念及关系：产品结构：描述了产品的构成关系，即产品各零部件之间的父子构成关系，一个父件由多少单位的子件构成。提前期和期量标准：提前期描述了由零件制造、产品装配或材料采购所需的时间，当所有构成子件完成后制造出父件的周期即为提前期。期量标准是依据产品结构模型和提前期信息，为产品建立时间坐标上的产品结构。业务模型与业务建模59示例物料需求管理问题的业务模型概念：独立需求物项：企业可以独立对外销售的物料，其需求数量一般由市场决定，不依赖于其他物料的需求。相关需求物项：为了制造独立需求物项而制造或采购的物项，例如木板是为了制造桌子而采购的，其需求数量是依赖于其他(独立或相关)物料需求数量而计算出来的。库存：为了某些目的存储在仓库中的物项，库存量因入库而增加，因出库而减少。在途：物项已经投产尚未完工或已经采购尚未到货的数量，将在未来某一时间完工可用或到货。计划产出量：预计将于某一时段产出某种物项的数量。计划投入量：预计将于某一时段投入某种物项的数量。业务模型与业务建模60示例物料需求计算过程的实例：物料需求管理问题的业务模型业务模型与业务建模61示例问题的核心模型----物料需求计算模型物料需求管理问题的业务模型业务模型与业务建模62示例物料需求管理问题的求解：核心算法及软件系统算法系统软件模型系统类问题求解第二步：软件模型系统类问题的求解需要构建一个系统人：用户/使用者硬件：计算机、网络软件：基础软件：操作系统、数据库管理系统应用软件：面向特定系统类问题求解的软件应用软件的构建是系统类问题求解的核心软件是复杂的智力产品，需运用系统科学方法、工程方法获取——软件工程业务模型（问题域模型）→软件模型→软件系统（解）63软件模型64软件模型与软件开发过程软件模型软件系统系统模块类函数变量调用/事件对象/实例数据库表…65软件模型软件模型/软件建模用例模型功能模型结构模型行为模型数据模型…66软件模型67示例物料需求管理系统的软件模型模块划分及功能分解模型分解原则：先总体、后局部的思想原则，自顶向下、分层解决。模块化原则：将系统分解成具有特定功能的若干模块，从而完成系统指定的各项功能。软件模型68示例物料需求管理系统的软件模型结构模型（类图）基本构造法则：区分对象及其属性；区分整体对象及其组成部分；形成并区分不同对象的类。抽象：强调一个对象和其他对象相区别的本质特性。封装：封装是对抽象元素的划分过程，抽象由结构和行为组成，封装用来分离抽象的原始接口和它的执行。类之间的静态联系：继承，聚合，关联物料类数据方法类图表示法软件模型69示例物料需求管理系统的软件模型结构模型（类图）软件模型70示例物料需求管理系统的软件模型动态/行为模型：表征运行时的对象交互/消息传递/接口调用软件实现系统类问题求解第三步：软件实现软件模型必须被实现为软件系统，才能够实际被用户使用，解决系统类问题软件实现：利用程序设计语言将软件模型转换为可运行的软件模块/系统模块→系统模块实现的内容用户界面程序业务处理程序数据的持久化存储程序模块实现程序必须进行测试—模块/单元测试：模块接口测试，局部数据结构测试，路径测试，错误处理测试，边界测试71软件实现系统实现的概念：将多个模块组装成一个完整的系统系统实现的内容：选择合适的体系结构并建立系统底层框架；

建立菜单管理器，即建立系统的功能菜单，给用户以功能入口；提供系统级的功能和基础设施，如安全和权限控制、统一的界面风格控制、统一的数据访问等；模块/构件的装载，包括将模块/构件装载到框架上，与菜单关联起来等；将模块/构件组装为完整的过程以支持完整的问题求解等。模块组装成系统后要进行整体测试——系统测试72软件实现73示例物料需求管理系统的软件实现库存管理模块业务处理程序库存管理模块用户界面软件实现74示例物料需求管理系统的功能菜单和框架物料需求管理系统的软件实现系统的部署与运行75系统类问题求解的第四步：系统的部署与运行系统的部署与运行系统部署与运行：数据+软件系统+使用在企业构建系统运行的必要环境，铺设网络、搭建硬件、软件平台。部署软件系统到企业：在数据库中建立数据库、表、视图等；在客户机、应用服务器上安装（物料需求管理）系统的客户机部分或服务器部分，取决于软件系统的体系结构选择；对系统进行测试。系统配置：设置系统的用户（计划员、库管员等）、设置用户的权限（即可以使用的软件功能和数据）等。对系统进行必要的初始化：将企业中的所有物项编码、清查库房中的物项数量，并将这些数据输入到系统中，作为系统运行的起点。76系统的部署与运行系统部署与运行：数据+软件系统+使用系统的试运行/试应用：尝试性的利用系统来解决问题，支持业务工作，例如计算物项的需求、对物项计划作出安排等，在此过程中，系统的运行、系统所产生的输出需要由用户检验其正确性，必要时对系统进行调整。系统的运行和应用：如系统通过了试运行/试应用，则系统开始正式应用，企业信任该系统的解决问题的能力，并依赖系统支持其业务工作和问题求解。当然，某些错误可能会在运行期出现，此时再进行系统的维护和完善。77系统的部署与运行78示例物料需求管理系统的部署与运行系统角色与权限配置系统的部署与运行79示例物料需求管理系统的体系结构选择客户机/服务器结构浏览器/服务器结构用户界面+业务逻辑数据用户界面+业务逻辑数据3.2系统类问题高级话题：系统的结构性与演化为什么系统的结构会变化，会演化？早期的软件实现技术是从零开始，利用某种程序设计语言实现模块或系统的所有部分，如用户界面、业务处理、数据的持久化存储等。缺点：程序员需要考虑硬件平台、操作系统平台的特性等诸多因素。实现难度大，对程序员的要求高，实现周期长，成本高。随着技术的发展和反复的开发，逐渐形成了对某类问题的有效解决方案，并形成了支持该问题的系统和工具问题逐渐分离为与特定应用有关的部分和与特定应用无关的共性技术及工具，导致了软件实现模式和体系结构的发展和演化。803.2系统类问题81示例早期的程序员在实现时需要自己设计、定义数据的逻辑结构、数据的存储形式/结构，还需要考虑硬件平台、操作系统平台的特性等。随着技术的发展和反复的开发，逐渐形成了关系数据库理论，并形成了关系数据库管理系统等工具数据持久化存储问题逐渐分离为与特定应用有关的部分（如物料需求管理系统中的特定数据内容及格式）和与特定应用无关的共性技术及工具（如关系数据库及关系数据库管理系统），导致了软件实现模式和体系结构的发展和演化。系统结构演化举例——数据持久化存储问题系统的结构性与演化软件模式的概念：“每个模式描述了那些在我们的环境中反复发生的问题，然后描述了该问题的解决方案的核心，从而使得你可以重复利用该方案”。模式关注于某种特定的解决方案，这种方案在处理一个或多个反复发生的问题时是通用而有效的。模式的一个关键特征是他们根植于实践，你可以通过观察人如何做事、事物如何工作而获得“解决方案的核心”。模式广泛存在于软件的分析、设计、实现等过程和领域中，应该有针对性的选择软件模式，以更好、更快地解决软件系统问题。软件模式影响了软件的结构，促进了软件结构的演化。82系统的结构性与演化软件体系结构：问题：随着软件系统的规模和复杂性不断增加，系统的全局结构的设计和规划变得比算法的选择以及数据结构的设计更加重要。全局组织结构、全局控制结构、通信和同步、数据存取的协议、设计元素的功能、设计元素的组合、物理分布、规模和性能、设计方案的选择等。软件体系结构的概念：包括构成系统的设计元素的描述、设计元素的交互、设计元素组合的模式，以及在这些模式中的约束。软件体系结构的重要性：为系统设计一个合适的体系结构是系统取得长远的成功的关键因素。83系统的结构性与演化