NorthChinaElectricPowerUniversity
算法
设计与分析
AlgorithmsDesign&;Analysis
华北电力大学
计算机科学与技术
SchoolofComputerScience&;TechnologyofNorthChinaElectricPowerUniversity
NorthChinaElectricPowerUniversity
Chapter1BasicConcepts&;IntroductiontoAlgorithms
1.Introduction2.HistoricalBackground3.Timecomplexity4.Spacecomplexity5.Optimalalgorithm
NorthChinaElectricPowerUniversity
§1IntroductionAlgorithm:themethodorstrategyfortheproblemsolving.Themostgeneralintuitiveideaofanalgorith
misaprocedurethatconsistsofafinitesetofinstructionswhichgivesaninputfromsomesetofpossibleinputs,enableustoobtainanoutputifsuchanoutputexistsorelseobtainingatallifthereisnooutputforthatparticularinputthroughasystematicexecutionoftheinstruction.
NorthChinaElectricPowerUniversity
Notation:
1.Thesetofpossibleinputsconsistsofallinputstowhichthealgorithmgivesanoutput.2.Werequirethatanalgorithmhaltsoneveryinput,whichimpliesthateachinstructionrequireafiniteamountoftime,andeachinputhasafinitelength.3.Wealsorequirethattheoutputofalegalinputtobeunique,thatis,thealgorithmisdeterministicinthesensethatthesamesetinstructionareexecutedwhenthealgorithmisinitiatedonaparticularinputmorethanonce.
NorthChinaElectricPowerUniversity
RemarksThedesignandanalysisofalgorithmsareoffundamentalimportanceinthefieldofcomputerscience.AsDonaldE.Knuthstated“Computerscienceisthestudyofalgorithms”.Thisshouldnotbesurprising,aseveryareaincomputersciencedependsheavilyonthedesignofefficientalgorithms.
NorthChinaElectricPowerUniversity
图灵奖设立于1966年,是美国计算机协会年是美国计算机协会是美国计算机协会(ACM:Association图灵奖设立于forComputingMachinery)在计算机技术方面所授予的最高在计算机技术方面所授予的最高奖项,被喻为计算机界的诺贝尔奖被喻为计算机界的诺贝尔奖。奖项被喻为计算机界的诺贝尔奖。年到2010年所颁发的图灵奖获得者中,约有人是由年所颁发的图灵奖获得者中,从1966年到年到年所颁发的图灵奖获得者中约有12人是由于在算法和数据结构、计算复杂性理论、于在算法和数据结构、计算复杂性理论、
程序设计以及相关领域做出杰出贡献而荣获图灵奖。领域做出杰出贡献而荣获图灵奖。
1.美国斯坦福大学计算机系终身教授美国斯坦福大学计算机系终身教授D.E.Kunth因撰写多卷巨著“Theart因撰写多卷巨著“美国斯坦福大学计算机系终身教授因撰写多卷巨著ofComputerprogramming”而于而于1974年成为最年轻的图灵奖获得者。年成为最年轻的图灵奖获得者。而于年成为最年轻的图灵奖获得者2.以色列特拉维夫大学以色列特拉维夫大学M.O.Rabin教授和英国的教授和英国的D.S.Scott教授因发表著名以色列特拉维夫大学教授和英国的教授因发表著名的计算复杂性方面的论文“的计算复杂性方面的论文“FiniteautomataandTheirDecisionproblem”荣获1976年度图灵奖。年度图灵奖。荣获年度图灵奖3.美国的美国的R.W.Floyd教授由于在算法分析和程序设计正确性证明领域做出教授由于在算法分析和程序设计正确性证明领域做出美国的开创性的
工作而荣获1978年度的图灵奖。开创性的工作而荣获年度的图灵奖。年度的图灵奖4.1980年度的图灵奖则授予在程序设计和算法方面做出突出贡献、发明著年度的图灵奖则授予在程序设计和算法方面做出突出贡献、年度的图灵奖则授予在程序设计和算法方面做出突出贡献名的Quicksort算法的英国算法的英国C.A.R.H
oare教授。教授。名的算法的英国教授5.研究计算复杂性理论和完全性
问题专家、加拿大研究计算复杂性理论和NP完全性问题专家加拿大S.A.Cook教授的论文研究计算复杂性理论和完全性问题专家、教授的论文年度图灵奖。“ThecomplexityofTheoremProvingProcedures”,荣获,荣获1982年度图灵奖。年度图灵奖