算法设计与分析第2版郑宗汉.pptx

算法设计与分析什么是算法？2o算法组成算法组成n（1）问题）问题n（2）规则）规则n（3）结果）结果o算法是解某一问题的一组算法是解某一问题的一组有穷有穷规则的集合。规则的集合。o算法是把算法是把输入输入转换成转换成输出输出的一个计算序列。的一个计算序列。课程概述o计算机系统中的任何软件，都是按一个个特定的算法来计算机系统中的任何软件，都是按一个个特定的算法来予以实现的。算法性能的好坏，直接决定了所实现软件予以实现的。算法性能的好坏，直接决定了所实现软件性能的优劣。性能的优劣。o如何判定一个算法的性能、用什么方法来设计算法、所如何判定一个算法的性能、用什么方法来设计算法、所设计的算法需要多少运行时间、多少存储空间，在实现设计的算法需要多少运行时间、多少存储空间，在实现一个软件时，这些都是必须一个软件时，这些都是必须要要予以解决的。予以解决的。o因此，算法设计与分析是计算机科学与技术的一个核心因此，算法设计与分析是计算机科学与技术的一个核心问题，也是大学计算机专业本科生及研究生的一门重要问题，也是大学计算机专业本科生及研究生的一门重要的专业基础课程。的专业基础课程。3课程内容o第一部分第一部分(1-2章章)：基本概念和常用数学工具基本概念和常用数学工具(6学时学时)o第第二二部部分分(3-11章章)：基基本本理理论论和和技技术术，包包括括排排序序、递递归归、分分治治、贪贪婪婪法法、动动态态规规划划、回回溯溯法法、分分支支与与限限界界、随随机算法、图和网络问题机算法、图和网络问题 (30学时学时)o第三部分：第三部分：复习考试复习考试(4学时学时)4教材与参考书o教教材材：郑郑宗宗汉汉、郑郑晓晓明明：算算法法设设计计与与分分析析，清清华华大大学学出版社，出版社，第第2版，版，2011年年7月月o参参考考书书：算算法法导导论论(原原书书第第3版版)，ThomasH.Cormen，CharlesE.Leiserson,RonaldL.Rivest,liffordStein,殷殷建建平平等等译译,机机械械工工业业出出版版社社,第第1版版，2013年年7月月5References11.ThomasThomasH.H.Cormen,Cormen,CharlesCharlesE.E.Leiserson,Leiserson,andandRonaldRonaldL.L.Rivest.Rivest.IntroductiontoAlgorithms,TheMITPress,IntroductiontoAlgorithms,TheMITPress,第二版第二版第二版第二版,2002.,2002.2.2.2.2.卢开澄卢开澄卢开澄卢开澄.计算机算法导引（第二版）。清华大学出版社，计算机算法导引（第二版）。清华大学出版社，计算机算法导引（第二版）。清华大学出版社，计算机算法导引（第二版清华大学出版社，2006.2006.3.3.3.3.王晓东王晓东王晓东王晓东.计算机算法设计与分析，电子工业出版社，计算机算法设计与分析，电子工业出版社，计算机算法设计与分析，电子工业出版社，计算机算法设计与分析，电子工业出版社，20012001。4.4.D.D.E.E.KnuthKnuth等等等等.ArtArtofofthetheComputerComputerProgramming,Programming,Vol.Vol.3,3,Addison-Addison-Wesley,1973.Wesley,1973.5.5.A.A.V.V.Aho,Aho,J.J.D.D.UllmanUllman等等等等.TheTheDesignDesignandandAnalysisAnalysisofofComputerComputerAlgorithms.Addison-Wesley,1974.Algorithms.Addison-Wesley,1974.6.6.A.A.V.V.Aho,Aho,J.J.D.D.UllmanUllman等等等等.DataData StructuresStructures andand Algorithms.Algorithms.Addison-Wesley,1983.4.Addison-Wesley,1983.4.7.7.S.S.Baase.Baase.ComputerComputer Algorithms:Algorithms:IntroductionIntroduction toto DesignDesign andandAnalysis.Addison-Wesley,secondedition,1988.Analysis.Addison-Wesley,secondedition,1988.8.8.E.E.HorowitzHorowitz andand SartajSartaj Sahni.Sahni.FundamentalsFundamentals ofof ComputerComputerAlgorithms.ComputerSciencePress,1978Algorithms.ComputerSciencePress,19786Journals1.1.IEEETransactionsonElectronicComputersIEEETransactionsonElectronicComputers2.2.IEEETransactionsonSoftwareEngineeringIEEETransactionsonSoftwareEngineering3.3.IEEETransactionsonDataandKnowledgeEngineeringIEEETransactionsonDataandKnowledgeEngineering4.4.ActaInformaticaActaInformatica5.5.SIAMJournalonComputingSIAMJournalonComputing6.6.JournalofComputerandSystemSciencesJournalofComputerandSystemSciences7.7.CommunicationoftheACMCommunicationoftheACM8.8.JournaloftheACMJournaloftheACM9.9.BITBIT10.10.InformationandControlInformationandControl11.11.ACMComputingSurveysACMComputingSurveys12.12.MathematicsofComputationMathematicsofComputation13.13.InformationProcessingLettersInformationProcessingLetters14.14.TheoreticalComputerScienceTheoreticalComputerScience7Conferences1.1.AnnualACMSymposiumonTheoryofComputingAnnualACMSymposiumonTheoryofComputing2.2.AnnualIEEESymposiumonFoundationsofComputerScienceAnnualIEEESymposiumonFoundationsofComputerScience3.3.ACMAnnualComputerScienceConferenceACMAnnualComputerScienceConference4.4.AnnualSymposiumonComputationalGeometryAnnualSymposiumonComputationalGeometry5.5.ACMSymposiumonParallelAlgorithmsandArchitecturesACMSymposiumonParallelAlgorithmsandArchitectures8学习要求o深刻理解每一类算法的思想及其实现深刻理解每一类算法的思想及其实现o能熟练运用所学知识解决实际问题能熟练运用所学知识解决实际问题o培养提高计算思维能力培养提高计算思维能力9考核方式ooHomeworkandReading:20%HomeworkandReading:20%ooFinalExam(WrittenTest):80%FinalExam(WrittenTest):80%1011第第1章章 算法的基本概念算法的基本概念o1.1引言引言n1.1.1算法的定义和特性算法的定义和特性n1.1.2算法的设计和复杂性分析算法的设计和复杂性分析1.1.1 算法的定义和特性o定义：算法是把定义：算法是把输入输入转换成转换成输出输出的一个计算序列。的一个计算序列。o特性：特性：n（1）输入）输入n（2）输出）输出n（3）有限性）有限性n（4）确定性）确定性n（5）可行性）可行性12o设计：设计：o欧几里德算法欧几里德算法13输入：输入：输出：输出：第一步第一步:第二步第二步:第三步第三步:第四步第四步:正整数正整数m和和nm和和n的最大公约数的最大公约数求余数求余数rm%nifr=0?yes终止终止(n为答案为答案)no执行第三步。执行第三步。mn,nr,返回第一步。返回第一步。1.1.1算法的定义和特性算法的定义和特性最大公约数问题：求两个正整数m和n的最大公约数输入输入：一一个个算算法法有有0 0个个或或多多个个输输入入，它它是是由由外外部部提提供供的的，作作为为算算法法开开始始执执行行前前的的初初始始值值，或或初初始始状状态。态。算算法法的的输输入入是是从从特特定定的的对对象象集集合合中中抽抽取取的的。算算法法中中有有两两个个输输入入m m、n n，就就是是从从正正整整数数集集合合中中抽取的。抽取的。输出输出：一一个个算算法法有有一一个个或或多多个个输输出出，这这些些输输出出与与输输入入有有特特定定的的关关系系，实实际际上上是是输输入入的的某某种种函函数数。不不同同取取值值的的输输入入，产产生生不不同同结结果果的输出。的输出。算算法法中中的的输输出出是是输输入入m m、n n的的最最大公约数。大公约数。有限性有限性：算算法法在在执执行行有有限限步步之之后后必必须须终终止。止。算算法法（欧欧几几里里德德算算法法）中中，对对输输入入的的任任意意正正整整数数m m、n n，将将m m除除以以n n的的余余数数赋赋予予r r之之后后，再再通通过过r r赋赋予予n n，从从而而使使n n值值变变小小。如如此此往往复复进进行行，最最终终或或者者使使r r为为0 0，或或者者使使n n递递减减为为1 1。这这两两种种情情况况，都最终使都最终使r=0r=0，而使算法终止。，而使算法终止。确定性确定性：算算法法的的每每一一个个步步骤骤，都都有有精精确确的的定定义义。要要执执行行的的每每一一个个动动作作都是清晰的、无歧义的。都是清晰的、无歧义的。例例如如，在在算算法法的的第第3 3行行中中，如如果果m m、n n是是无无理理数数，那那么么，m m除除以以n n的的余余数数就就没没有有一一个个明明确确的的界界定定。确确定定性性的的准准则则意意味味着着必必须须确确保保在在执执行行第第3 3行行时时，m m和和n n的的值值都都是是正整数。正整数。算算法法规规定定了了m m、n n都都是是正正整整数数，从从而而保保证证了了后后续续各各个个步步骤骤中中都都能确定地执行。能确定地执行。可行性可行性：算算法法中中所所有有待待实实现现的的运运算算，都都是是基基本本的的运运算算。原原则则上上可可以以由由人人们们用用纸纸和和笔笔，在在有有限限的的时时间间里精确地完成。里精确地完成。算算法法中中整整除除、判判断断、赋赋值值等等等等运运算算都都是是可可行行的的。因因为为整整数数可可以用有限的方式表示。以用有限的方式表示。如如果果所所涉涉及及的的数数值值必必须须由由展展开开成成无无穷穷小小数数的的实实数数来来精精确确地地完完成成，则则这这些些运运算算就就不不是是可可行行的的了。了。注意：注意：有限性的限制是不够的。有限性的限制是不够的。一个实用的算法，不仅要求步骤一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所有限，同时要求运行这些步骤所花费的时间是人们可以接受的。花费的时间是人们可以接受的。特性：特性：（1）输入）输入（2）输出）输出（3）有限性）有限性（4）确定性）确定性（5）可行性）可行性14o1.1引言引言n1.1.1算法的定义和特性算法的定义和特性n1.1.2算法的设计和复杂性分析算法的设计和复杂性分析1.1.2 算法的设计和复杂性分析o过程过程15理解问题算法表示算法分析算法实现o例例1百鸡问题：百鸡问题：n公鸡每只公鸡每只5元、母鸡每只元、母鸡每只3元、小鸡元、小鸡3只只1元，用元，用100元钱元钱买买100只鸡，求公鸡、母鸡、小鸡的只数。只鸡，求公鸡、母鸡、小鸡的只数。n令令a为公鸡数，为公鸡数，为为b母鸡数，母鸡数，c 为小鸡数，则：为小鸡数，则：（1.1.1）（1.1.2）（1.1.3）161.1.2算法的设计和复杂性分析算法的设计和复杂性分析1.voidchicken_question(intn,int&k,intg,intm,ints)2.3.inta,b,c;4.k=0;5.for(a=0;a=n;a+)6.for(b=0;b=n;b+)7.for(c=0;c=n;c+)8.if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0)9.gk=a;10.mk=b;11.sk=c;12.k+;13.14.15.16.17.百鸡问题的穷举法o输入：所购买的输入：所购买的3种鸡的总数目种鸡的总数目no输出：满足问题的解的数目输出：满足问题的解的数目k,公鸡公鸡,母鸡母鸡,小鸡的只数小鸡的只数g,m,s17分析发现：只能买到分析发现：只能买到n/5只公鸡，只公鸡，n/3只母鸡，将只母鸡，将算法进行改进。算法进行改进。1.1.2算法的设计和复杂性分析算法的设计和复杂性分析o输入：所购买的输入：所购买的3种鸡的总数目种鸡的总数目no输出：满足问题的解的数目输出：满足问题的解的数目k,公鸡公鸡,母鸡母鸡,小鸡的只数小鸡的只数g,m,s1.voidchicken_question_2(intn,int&k,intg,intm,ints)2.3.inta,b,c;4.k=0;5.i=n/5;6.j=n/3;7.for(a=0;a=i;a+)8.for(b=0;b=j;b+)9.c=na-b;/原来为原来为for(c=0;c=n;c+)10.if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0)11.gk=a;12.mk=b;13.sk=c;14.k+;15.16.百鸡问题的穷举法改进181.1.2算法的设计和复杂性分析算法的设计和复杂性分析o例例2货郎担问题：货郎担问题：n售货员到若干个城市去售货，每个城市仅经过一次，最售货员到若干个城市去售货，每个城市仅经过一次，最后回到出发点。已知各个城市之间的距离，求一个总路后回到出发点。已知各个城市之间的距离，求一个总路程最短的路线。程最短的路线。19n最短路径的哈密尔顿回路问最短路径的哈密尔顿回路问题，数据结构是无向加权图题，数据结构是无向加权图G=，V是顶点集合，是顶点集合，E是距离集合。是距离集合。1.1.2算法的设计和复杂性分析算法的设计和复杂性分析货郎担问题的穷举法算法o输入输入：城市个数：城市个数n，费用，费用(距离距离)矩阵矩阵co输出输出：旅行路线：旅行路线t，最小费用，最小费用min1.voidsalesman_problem(intn,float&min,intt,floatc)2.3.intpni=1;4.floatcost;5.min=MAX_FLOAT_NUM;6.while(i=n!)7.产生产生n个城市的第个城市的第i个排列于个排列于p;8.cost=路线路线p的费用；的费用；9.if(costmin)10.把数组把数组p的内容复制到数组的内容复制到数组t；11.min=cost;12.13.i+;14.15.n!201.1.2算法的设计和复杂性分析算法的设计和复杂性分析货郎担问题的执行时间和问题规模的关系（假定假定循环体循环体每执行一次，需要每执行一次，需要1s时间时间）211.1.2算法的设计和复杂性分析算法的设计和复杂性分析思考o从百鸡问题的穷举法改进，可以得到什么启示？从百鸡问题的穷举法改进，可以得到什么启示？o从货郎担问题的穷举算法时间消耗和问题规模的关系，从货郎担问题的穷举算法时间消耗和问题规模的关系，可以得到什么启示？可以得到什么启示？o什么是一个有效的算法？如何判断某个算法更加有效？什么是一个有效的算法？如何判断某个算法更加有效？22说说明明了了改改进进算算法法的的设设计计方方法法对对提提高高算算法法性性能能是是非非常常重要的。重要的。说说明明了了穷穷举举法法对对于于一一个个不不太太大大的的（货货郎郎担担问问题题），都都是是行行不不通的。通的。如如果果一一个个问问题题有有2个个算算法法，如如何何知知道道这这一一个个算算法法比比另另一一个个算算法法更更有有效效？涉涉及及下次课的时间、空间复杂性分析。下次课的时间、空间复杂性分析。1.1.2算法的设计和复杂性分析算法的设计和复杂性分析小结o算法的定义和特征算法的定义和特征o算法的设计和复杂性分析算法的设计和复杂性分析23作业o查阅有关算法的研究动态，了解本节所列出的部分查阅有关算法的研究动态，了解本节所列出的部分参考书目、期刊和会议。参考书目、期刊和会议。24