算法设计与分析(第2版)郑宗汉第1章

算法设计与分析,什么是算法？,2,算法组成（1）问题（2）规则（3）结果,算法是解某一问题的一组有穷规则的集合。算法是把输入转换成输出的一个计算序列。,课程概述,计算机系统中的任何软件，都是按一个个特定的算法来予以实现的。算法性能的好坏，直接决定了所实现软件性能的优劣。如何判定一个算法的性能、用什么方法来设计算法、所设计的算法需要多少运行时间、多少存储空间，在实现一个软件时，这些都是必须要予以解决的。因此，算法设计与分析是计算机科学与技术的一个核心问题，也是大学计算机专业本科生及研究生的一门重要的专业基础课程。,3,课程内容,第一部分(1-2章)：基本概念和常用数学工具(6学时)第二部分(3-11章)：基本理论和技术，包括排序、递归、分治、贪婪法、动态规划、回溯法、分支与限界、随机算法、图和网络问题(30学时)第三部分：复习考试(4学时),4,教材与参考书,教材：郑宗汉、郑晓明：算法设计与分析，清华大学出版社，第2版，2011年7月参考书：算法导论(原书第3版)，ThomasH.Cormen，CharlesE.Leiserson,RonaldL.Rivest,liffordStein,殷建平等译,机械工业出版社,第1版，2013年7月,5,References,ThomasH.Cormen,CharlesE.Leiserson,andRonaldL.Rivest.IntroductiontoAlgorithms,TheMITPress,第二版,2002.卢开澄.计算机算法导引（第二版）。清华大学出版社，2006.王晓东.计算机算法设计与分析，电子工业出版社，2001。D.E.Knuth等.ArtoftheComputerProgramming,Vol.3,Addison-Wesley,1973.A.V.Aho,J.D.Ullman等.TheDesignandAnalysisofComputerAlgorithms.Addison-Wesley,1974.A.V.Aho,J.D.Ullman等.DataStructuresandAlgorithms.Addison-Wesley,1983.4.S.Baase.ComputerAlgorithms:IntroductiontoDesignandAnalysis.Addison-Wesley,secondedition,1988.E.HorowitzandSartajSahni.FundamentalsofComputerAlgorithms.ComputerSciencePress,1978,6,Journals,IEEETransactionsonElectronicComputersIEEETransactionsonSoftwareEngineeringIEEETransactionsonDataandKnowledgeEngineeringActaInformaticaSIAMJournalonComputingJournalofComputerandSystemSciencesCommunicationoftheACMJournaloftheACMBITInformationandControlACMComputingSurveysMathematicsofComputationInformationProcessingLettersTheoreticalComputerScience,7,Conferences,AnnualACMSymposiumonTheoryofComputingAnnualIEEESymposiumonFoundationsofComputerScienceACMAnnualComputerScienceConferenceAnnualSymposiumonComputationalGeometryACMSymposiumonParallelAlgorithmsandArchitectures,8,学习要求,深刻理解每一类算法的思想及其实现能熟练运用所学知识解决实际问题培养提高计算思维能力,9,考核方式,HomeworkandReading:20%FinalExam(WrittenTest):80%,10,11,第1章算法的基本概念1.1引言1.1.1算法的定义和特性1.1.2算法的设计和复杂性分析,1.1.1算法的定义和特性,定义：算法是把输入转换成输出的一个计算序列。特性：（1）输入（2）输出（3）有限性（4）确定性（5）可行性,12,设计：欧几里德算法,13,输入：输出：第一步:第二步:第三步:第四步:,正整数m和nm和n的最大公约数求余数rm%nifr=0?yes终止(n为答案)no执行第三步。mn,nr,返回第一步。,1.1.1算法的定义和特性,最大公约数问题：求两个正整数m和n的最大公约数,输入：一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。算法的输入是从特定的对象集合中抽取的。算法中有两个输入m、n，就是从正整数集合中抽取的。,输出：一个算法有一个或多个输出，这些输出与输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。算法中的输出是输入m、n的最大公约数。,有限性：算法在执行有限步之后必须终止。算法（欧几里德算法）中，对输入的任意正整数m、n，将m除以n的余数赋予r之后，再通过r赋予n，从而使n值变小。如此往复进行，最终或者使r为0，或者使n递减为1。这两种情况，都最终使r=0，而使算法终止。,确定性：算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。例如，在算法的第3行中，如果m、n是无理数，那么，m除以n的余数就没有一个明确的界定。确定性的准则意味着必须确保在执行第3行时，m和n的值都是正整数。算法规定了m、n都是正整数，从而保证了后续各个步骤中都能确定地执行。,可行性：算法中所有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。算法中整除、判断、赋值等等运算都是可行的。因为整数可以用有限的方式表示。如果所涉及的数值必须由展开成无穷小数的实数来精确地完成，则这些运算就不是可行的了。,注意：有限性的限制是不够的。一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。,特性：（1）输入（2）输出（3）有限性（4）确定性（5）可行性,14,1.1引言1.1.1算法的定义和特性1.1.2算法的设计和复杂性分析,1.1.2算法的设计和复杂性分析,过程,15,例1百鸡问题：公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。令a为公鸡数，为b母鸡数，c为小鸡数，则：（1.1.1）（1.1.2）（1.1.3）,16,1.1.2算法的设计和复杂性分析,1.voidchicken_question(intn,int6.17.,百鸡问题的穷举法,输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s,17,分析发现：只能买到n/5只公鸡，n/3只母鸡，将算法进行改进。,1.1.2算法的设计和复杂性分析,输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s,1.voidchicken_question_2(intn,int15.16.,百鸡问题的穷举法改进,18,1.1.2算法的设计和复杂性分析,例2货郎担问题：售货员到若干个城市去售货，每个城市仅经过一次，最后回到出发点。已知各个城市之间的距离，求一个总路程最短的路线。,19,最短路径的哈密尔顿回路问题，数据结构是无向加权图G=，V是顶点集合，E是距离集合。,1.1.2算法的设计和复杂性分析,货郎担问题的穷举法算法,输入：城市个数n，费用(距离)矩阵c输出：旅行路线t，最小费用min,1.voidsalesman_problem(intn,float14.15.,n!,20,1.1.2算法的设计和复杂性分析,货郎担问题的执行时间和问题规模的关系,（假定循环体每执行一次，需要1s时间）,21,1.1.2算法的设计和复杂性分析,思考,从百鸡问题的穷举法改进，可以得到什么启示？从货郎担问题的穷举算法时间消耗和问题规模的关系，可以得到什么启示？什么是一个有效的算法？如何判断某个算法更加有效？,22,说明了改