《0501战德臣《大学计算机计算思维导论》大学计算机第7讲算法程序与计算系统之灵魂.ppt》由会员分享，可在线阅读，更多相关《0501战德臣《大学计算机计算思维导论》大学计算机第7讲算法程序与计算系统之灵魂.ppt（62页珍藏版）》请在三一办公上搜索。
1、算法与算法类问题求解,Research Center on Intelligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员,符号化,计算化,再语义化,程序化,执行化,算法的结果,机器级程序-机器指令,运算器和控制器(CPU)-执行,算法,产生,用0/1编码：指令和数据,存储器：0/1存与取,0/1化,信号化,存储,高级语言程序,编译,执行化,汇编语言程序,程序执行,汇编,程序执行,算法与算法类问题求解(1)为什么算法很重要呢?
2、,“是否会编程序”，本质上是“能否想出求解问题的算法”，其次才是将算法用计算机可以识别的形式书写出来,算法-计算机与软件的灵魂。“算法”(Algorithm)一词源于数学家的名字：公元825年，阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的波斯教科书(Persian Textbook)，书中概括了进行四则算术运算的计算规则。算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。,算法与算法类问题求解(2)什么是算法?,如音乐乐谱、太极拳谱等都可看作广义的算法,有穷性：一个算法在执行有穷步规则之后必须结束。确定性：算法的
3、每一个步骤必须要确切地定义，不得有歧义性。输入：算法有零个或多个的输入。输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成)，并能在有限时间内完成。,算法,算法与算法类问题求解(3)什么是计算学科中的算法?,基本运算：除法、赋值、逻辑判断,典型的“重复/循环”与“迭代”,寻找两个正整数的最大公约数的欧几里德算法输入：正整数M和正整数N输出：M和N的最大公约数(设MN)算法步骤：Step 1.M除以N,记余数为RStep 2.如果R不是0，将N的值赋给M,R的值赋给N,返回Step 1;否则,最大公约数是N,输出
4、N,算法结束。,哥尼斯堡七桥问题：“寻找走遍这7座桥且只许走过每座桥一次最后又回到原出发点的路径”“对给定的任意一个河道图与任意多座桥判定可能不可能每座桥恰好走过一次?”。梵天塔问题：有三根柱子，梵天将64个直径大小不一的金盘子按照从大到小的顺序依次套放在第一根柱子上形成一座金塔，要求每次只能移动一个盘子，盘子只能在三根柱子上来回移动不能放在他处，在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上。其他如：背包问题，丢番图方程可解性问题；,算法与算法类问题求解(4)你知道一些典型的算法类问题吗?,算法类问题：由一个算法可以解决的问题,寻找一个(唯一的)方法(算法)以解决同一类型的无穷多个
5、单个问题系列的问题,TSP问题(Traveling Salesman Problem，旅行商问题)，威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出TSP问题TSP问题：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。TSP是最有代表性的组合优化问题之一，在半导体制造(线路规划)、物流运输(路径规划)等行业有着广泛的应用。,城市之间的距离,算法与算法类问题求解(5)你知道TSP问题吗?,算法类问题示例,问题抽象及数学建模：将问题抽象
6、为一个数学问题，并给出求解该数学问题的算法模型。算法策略设计算法的数据结构和控制结构设计：将数学模型转换为可由计算机自动计算的算法。算法的实现：用程序设计语言编写算法实现的程序。算法的分析：分析算法的正确性和复杂性，判断能行性！,算法与算法类问题求解(6)你知道算法类问题求解的一般步骤吗?,算法类问题求解框架,数学建模与算法策略设计-算法思想,Research Center on Intelligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教
7、学指导委员会委员,算法类问题求解的第一步就是要数学建模。数学建模是用数学语言描述实际现象的过程，即建立数学模型的过程。数学模型是对实际问题的一种数学表述，是关于部分现实世界为某种目的的一个抽象的简化的数学结构。,数学建模与算法策略设计-算法思想(1)为什么说数学建模对于算法很重要?,将现实世界的问题抽象成数学模型，就可能发现问题的本质及其能否求解，甚至找到求解该问题的方法和算法。,哥尼斯堡七桥问题被抽象成一个“图(Graph)”-由节点和边所构成的一种结构，-依据“图”，可发现该问题所蕴含的许多性质：“连通-两个节点间有路径相连接”“回路-从一个节点出发最后又回到该节点的一条路径”“可达-从一
8、个节点出发能够到达另一个节点”“经过图中每边一次且仅一次的回路”“经过图中每个节点一次且仅一次的回路”什么情况下有解，什么情况下无解？,数学建模与算法策略设计-算法思想(1)为什么说数学建模对于算法很重要?,如果能抽象成数学模型，则可将一个具体问题的求解，推广为一类问题的求解！,TSP问题的数学模型,数学建模与算法策略设计-算法思想(2)数学建模要做到怎样?,算法策略设计-算法思想,当数学建模完成后，就要设计算法的策略或者说问题求解的策略。求解TSP的遍历算法：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线。出现的问题是：组合爆炸路径组合数目：(n-1)!20个城
9、市，遍历总数1.2161017计算机以每秒检索1000万条路线的计算速度，需386年。,所有路径组合及其长度,城市之间的距离,数学建模与算法策略设计-算法思想(3)算法思想或者算法策略对问题求解有什么影响?,TSP问题的难解性：随着城市数量的上升，TSP问题的“遍历”方法计算量剧增，计算资源将难以承受。2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。,An optimal TSP tour through Germanys
10、15 largest cities.It is the shortest among 43 589 145 600 possible tours visiting each city exactly once.,数学建模与算法策略设计-算法思想(3)算法思想或者算法策略对问题求解有什么影响?,TSP问题，有没有其他求解算法呢？最优解 vs.可行解不同的算法设计策略：遍历、搜索算法分治算法贪心算法动态规划算法,数学建模与算法策略设计-算法思想(4)有哪些算法策略?,贪心算法是一种算法策略，或者说问题求解的策略。基本思想“今朝有酒今朝醉”。一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪
11、心”。TSP问题的贪心算法求解思想从某一个城市开始，每次选择一个城市，直到所有城市都被走完。每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短。,城市之间的距离,数学建模与算法策略设计-算法思想(5)为什么称为“贪心算法”?,基本目标:理解算法类问题求解框架,数学建模与算法策略设计-算法思想(6)小结?,算法思想的精确表达-算法的数据结构设计(I),Research Center on Intelligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.
12、博士生导师教育部大学计算机课程教学指导委员会委员,算法思想的精确表达-算法的数据结构设计(I)(1)算法设计包括什么?,算法的数据结构设计-问题或算法相关的数据之间的逻辑关系及存储关系的设计 算法的控制结构设计-算法的计算规则或计算步骤设计,如何构造和表达处理的规则，以便能够按规则逐步计算出结果?,如何将数学模型中的数据转为计算机可以存储和处理的数据？,数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。,算法思想的精确表达-算法的数据结构设计(I)(2)什么是数据结构?,反映逻辑语义关系,为便于计算系统处理,变量与存储单元,算法思想的精确表达-算法的数据结
13、构设计(I)(3)变量和存储单元之间的关系?,变量及其存储,“变量”与“指针变量”,算法思想的精确表达-算法的数据结构设计(I)(4)指针是什么?,变量及其存储,“变量”与“变量类型”及其存储,算法思想的精确表达-算法的数据结构设计(I)(5)变量为什么需要声明类型?,变量及其存储,向量或列表是有序数据的集合型变量，向量中的每一个元素都属于同一个数据类型，用一个统一的向量名和下标来唯一的确定向量中的元素。在程序设计语言中，又称为数组。向量名通常表示该向量的起始存储地址，而向量下标表示所指向元素相对于起始存储地址的偏移位置。,向量实例,向量存储实例,n=4;Sum=0;For J=0 to n
14、Step 1Sum=Sum+mark J;Next JAvg=Sum/(n+1);,算法思想的精确表达-算法的数据结构设计(I)(6)如何控制读取向量/数组型变量的不同元素?,多元素变量及其存储,多元素变量使得程序可通过下标来操作多元素变量中的每一个元素,编写求上述数组中值的平均值的程序,矩阵或表是按行按列组织数据的集合型变量，通常是一个二维向量，可表示为如M2,3或M23形式，即用符号名加两个下标来唯一确定表中的一个元素，前一下标为行序号，后一下标为列序号。系统会自动将其转换为对应的存储地址，找到相应的存储单元。在程序设计语言中，矩阵或表是一个多维数组变量。,1,2,3,4,1,2,3,4,
15、行,列,M2,3,表实例,Sum=0;For I=1 to 4 Step 1 For J=1 to 4 Step 1 Sum=Sum+MIJ;Next J Next I Avg=Sum/16;,算法思想的精确表达-算法的数据结构设计(I)(7)如何控制读取向量/数组型变量的不同元素?,多元素变量及其存储,逻辑上是二维的按行、列下标来操作一个元素,如M2,3或M23；物理上仍旧是一维存储的，由“表起始地址+(行下标-1)*列数+列下标”。这种转换可由系统自动完成，程序中只需按下标操作即可，即如M23,算法思想的精确表达-算法的数据结构设计(II),Research Center on Intel
16、ligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员,算法思想的精确表达-算法的数据结构设计(II)(1)数据结构示例?,典型的数据结构-“树”“树”的存储结构:一个存储单元存储“数据元素”；一个存储单元存储“指针”，指示数据元素之间的逻辑关系,150,120,160,数据的逻辑结构,数据的存储结构,50,30,70,100,数据元素,对应数据元素的指针指向该元素的父元素,150,120,160,50,30,70,100,数据
17、的逻辑结构,数据的存储结构,存储结构中，通过指针的变化,不改变数据元素的存储,但却改变了数据元素之间的逻辑关系,算法思想的精确表达-算法的数据结构设计(II)(1)数据结构示例?,120,150,120,160,50,30,70,100,数据元素,对应数据元素的左指针指向该元素的左侧子结点,对应数据元素的右指针指向该元素的右侧子结点,算法思想的精确表达-算法的数据结构设计(II)(2)同样的逻辑结构可以有不同的存储结构吗?,“树”的另一种存储结构,用两个指针表达数据之间的逻辑关系，一个指向其左数据元素，一个指向其右数据元素。,数据的逻辑结构,数据的存储结构,数据结构不同，数据之间的操作方法也是
18、不同的,150,120,160,50,30,70,100,算法思想的精确表达-算法的数据结构设计(II)(2)同样的逻辑结构可以有不同的存储结构吗?,数据的逻辑结构,150,120,160,50,30,70,100,数据的逻辑结构,110,Null,动手练习一下,数据结构设计就是针对选定的算法策略，设计其相应的数据结构及其运算规则。不同的算法可能有不同的数据结构及其运算规则！,城市映射为编号:A-1,B-2,C-3,D-4城市间距离关系:表或二维数组D，用Dij或Di,j来确定欲处理的每一个元素访问路径/解:一维数组S，用Sj来确定每一个元素,A-D-C-B-A,S,S1 S2 S3 S4,D
19、,D23,算法设计-算法思想的精确表达(II)(3)一个问题中应该设计哪些数据结构?,TSP问题的数据结构设计,基本目标:理解算法类问题求解框架,算法思想的精确表达-算法的数据结构设计(II)(4)小结?,Research Center on Intelligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员,算法思想的精确表达-算法的控制结构设计(I),算法思想的精确表达-算法的控制结构设计(I)(1)算法设计包括什么?,算法的
20、数据结构设计-问题或算法相关的数据之间的逻辑关系及存储关系的设计 算法的控制结构设计-算法的计算规则或计算步骤设计,如何构造和表达处理的规则，以便能够按规则逐步计算出结果?,如何将数学模型中的数据转为计算机可以存储和处理的数据？,顺序结构：“执行A，然后执行B”，是按顺序执行一条条规则的一种结构。分支结构：“如果Q成立，那么执行A，否则执行B”，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则的一种结构。循环结构：控制指令或规则的多次执行的一种结构-迭代(iteration)循环结构又分为有界循环结构和条件循环结构。有界循环：“执行A指令N次”，其中N是一个整数。条件循环：某些时候称为无界循
21、环，“重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。,算法与程序的基本控制结构,算法思想的精确表达-算法的控制结构设计(I)(2)怎样表达算法的步骤呢?,流程图的基本表示符号矩形框：表示一组顺序执行的规则或者程序语句。菱形框：表示条件判断，并根据判断结果执行不同的分支。圆形框：表示算法或程序的开始或结束。箭头线：表示算法或程序的走向。,算法与程序构造的表达方法：程序流程图,算法思想的精确表达-算法的控制结构设计(I)(3)怎样绘制算法或程序流程图?,三种控制结构的流程图表示方法示意,算法思想的精确表达-算法的控制结构设计(I)(4)不同结构的流程图示例?,算法与程序构造的
22、表达方法：程序流程图,循环结构的两种情况的流程图表示方法示意,算法与程序构造的表达方法：程序流程图,算法思想的精确表达-算法的控制结构设计(I)(4)不同结构的流程图示例?,欧几里德算法流程图,算法思想的精确表达-算法的控制结构设计(I)(5)算法流程图示例?,算法与程序构造的表达方法：程序流程图,步骤描述法，即用人们日常使用的语言和数学语言描述算法的步骤。例如：sum=1+2+3+4+n求和问题的算法描述Start of the algorithm(算法开始)(1)输入N的值；(2)设 i 的值为1；sum的值为0；(3)如果 i=N，则执行第(4)步，否则转到第(7)步执行；(4)计算 s
23、um+i，并将结果赋给sum；(5)计算 i+1，并将结果赋给i;(6)返回到第3步继续执行；(7)输出sum的结果。End of the algorithm(算法结束),算法思想的精确表达-算法的控制结构设计(I)(6)自然语言表述算法有什么问题?,算法与程序构造的表达方法：步骤描述法,自然语言表示的算法容易出现二义性、不确定性等问题,Research Center on Intelligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导
24、委员会委员,算法思想的精确表达-算法的控制结构设计(II),求解TSP问题的遍历算法遍历所有的组合路径；累加一条路径的距离之和；判断某条路径的距离是不是比当前最短路径距离短；如果是，则用新路径取代当前最短路径，并记录其距离；直到所有路径比较完毕；,开始,结束,否,是,将该路径记录为当前最短路径，并用其距离值更新当前最短距离,是,否,算法思想的精确表达-算法的控制结构设计(II)(1)具体算法-TSP的遍历算法的控制结构如何设计?,将思想/策略转变为“步骤”,步骤描述法表示的求解TSP问题的贪心算法城市用数字编号来表示,1,2,N任何两个城市的距离记录在数组Di,j中依次访问过的城市编号被记录在
25、S1,S2,SN中,即第i 次访问的城市记录在Si中。Step(1)：从第1个城市开始访问起，将城市编号1赋值给S1。Step(6)：第I次访问的城市为城市j，其距第I-1次访问城市的距离最短。,算法思想的精确表达-算法的控制结构设计(II)(2)具体算法-TSP问题的贪心算法的控制结构如何设计?,Start of the Algorithm(1)S1=1;(2)Sum=0;(3)初始化距离数组DN,N;(4)I=2;(5)从所有未访问过的城市中查找距离SI-1最近的城市j;(6)SI=j;(7)I=I+1;(8)Sum=Sum+Dtemp;(9)如果I=N，转步骤(5)，否则，转步骤(10)
26、;(11)Sum=Sum+D1,j；(12)逐个输出SN中的全部元素;(13)输出Sum。End of the Algorithm,步骤描述法表示的求解TSP问题的贪心算法(Cont.)前述第5步“从所有未访问过的城市中查找距离SI-1最近的城市j”还是不够明确，需要进一步细化,(5.1)K=2;(5.2)将Dtemp设为一个大数(比所有两个城市之间的距离都大)(5.3)L=1；(5.4)如果SL=K，转步骤5.8；/该城市已出现过，跳过(5.5)L=L+1；(5.6)如果LI，转5.4；(5.7)如果DK,SI-1Dtemp,则j=K;DtempDK,SI-1；(5.8)K=K+1;(5.9
27、)如果K=N，转步骤5.3。,算法思想的精确表达-算法的控制结构设计(II)(2)具体算法-TSP问题的贪心算法的控制结构如何设计?,流程图表示的求解TSP问题的贪心算法,算法思想的精确表达-算法的控制结构设计(II)(3)具体算法-TSP问题的贪心算法的算法流程图?,算法思想解读计算学科的学生不仅能够设计算法，而且会描述和表达算法，更要能读懂算法。,算法思想的精确表达-算法的控制结构设计(II)(4)你能够读懂流程图吗?,基本目标:理解算法类问题求解框架,算法思想的精确表达-算法的控制结构设计(II)(5)小结?,Research Center on Intelligent Computin
28、g for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员,算法的实现-程序设计,算法的实现,程序是算法的一种机器相容(Compatible)的表示，是利用计算机程序设计语言对算法描述的结果，是可以在计算机上执行的算法。,算法的实现-程序设计(1)算法实现要选定计算机语言，你知道吗?,程序设计过程：编辑源程序编译链接执行。,一套书写程序的语法规则,计算机语言程序设计环境：编辑、编译、连接、调试、运行一体化平台,S,S0 S1 S2 S3,K从1,n-1是城市的编
29、号I是至今已访问过的城市数S0至SI-1中存储的是已访问过的城市的编号,算法的实现-程序设计(2)你能用某一种计算机语言书写出TSP问题贪心算法的程序吗?,main()/前面已为 K 和 I 赋过值L=0;Found=0;do if(SL=K)Found=1;break;else L=L+1;while(LI);/L从1到I循环 if Found=0/城市K未出现过 else/城市K出现过.,判断城市K是否是已访问过的城市,S,S0 S1 S2 S3,K从1,n-1是城市的编号I是至今已访问过的城市数SI-1中存储的是当前访问过的城市编号，要找第I个程序,算法的实现-程序设计(2)你能用某一种
30、计算机语言书写出TSP问题贪心算法的程序吗?,main()K=1;Dtemp=10000;do/K从1到n-1循环 L=0;Found=0;do if(SL=K)Found=1;break;else L=L+1;while(LI);/L从1到I循环if(Found=0,寻找下一个未访问过的城市j,且其距当前访问城市SI-1距离最短,DKSI-1为城市K距当前访问过的城市的距离,TSP问题贪心算法程序实例,算法的实现,算法的实现-程序设计(2)你能用某一种计算机语言书写出TSP问题贪心算法的程序吗?,基本目标:理解算法类问题求解框架,算法的实现-程序设计(5)小结?,Research Cente
31、r on Intelligent Computing for Enterprises&Services,Harbin Institute of Technology,战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员,算法分析与计算复杂性,算法的模拟与分析算法的正确性问题：问题求解的过程、方法算法是正确的吗？算法的输出是问题的解吗？20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中算法的效果评价：算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大？两种评价方法：证明方法：利用数学方法证明；仿真分析方法：产生或选取大量的、具有代表
32、性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析。,算法分析与计算复杂性(1)算法是正确的吗?,算法是正确的吗?,算法获得的解是最优的吗?,TSP问题贪心算法的模拟与分析TSP问题贪心算法的正确性评价：直观上只需检查算法的输出结果中，每个城市出现且仅出现一次，该结果即是TSP问题的可行解，说明算法正确地求解了这些问题实例TSP问题贪心算法的效果评价：如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价；对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算
33、法结果的比较。,算法分析与计算复杂性(1)算法是正确的吗?,另一个问题：算法是能够执行的吗？算法的复杂性分析算法的效率：时间效率和空间效率时间复杂性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。“大O记法”：基本参数 n问题实例的规模把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“”，如n2+n+1=(n2)。算法的空间复杂度：算法在执行过程中所占存储空间的大小。,算法分析与计算复杂性(2)算法的计算时间有多长?,算法获得结果的时间有多长?,算法分析与计算复杂性(2)算法的计算时
34、间有多长?,算法复杂性分析示例,sum=0；（1次）for(i=1;i=n;i+)（n次）for(j=1;j=n;j+)（n2次）sum+；（n2次）解：T(n)=2n2+n+1=O(n2),主要关注点：循环的层数,TSP问题算法的复杂性分析TSP问题遍历算法的复杂性：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线组合爆炸：路径组合数目为(n-1)!时间复杂度是O(n-1)!)TSP问题贪心算法的复杂性：一个关于n的三重循环。时间复杂度是O(n3)。,算法分析与计算复杂性(2)算法的计算时间有多长?,n,n2,n3,算法分析与计算复杂性(3)O(n3),O(n!)
35、和O(3n)差别有多大?,20！=1.2161017203=8000,O(n3)与O(3n)的差别，O(n!)与O(n3)的差别,难解性问题当算法的时间复杂度的表示函数是一个多项式时，如O(n2)时，则计算机对于大规模问题是可以处理的，即可解的。例如，TSP问题的贪心算法 O(n3)。当算法的时间复杂度是用指数函数表示时，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题被称为难解性问题。例如，TSP问题的遍历算法。计算复杂性理论所有可以在多项式时间内求解的问题称为P类问题所有在多项式时间内可以验证的问题称为NP类问题，PNP。Open problem:P=NP?美国克雷数学研究所百万大奖难题。,算法分析与计算复杂性(4)可解性与难解性问题?,基本目标:理解算法类问题求解框架,算法分析与计算复杂性(5)小结?,算法-程序与计算系统之灵魂：总结?,
