算法导论

DesignandAnalysisofAlgorithms1.IntroductionHongweiLiSchoolofComputerScienceandEngineeringUniversityofElectronicScienceandTechnologyofChina2课程作用对象作用一般计算机用户0初级程序员/软件外包3高级程序员8研究人员/系统分析师10Welcome!Areyouthinkingaboutthesequestions?Whydoweneedtostudythiscourse?Whatshouldwelearninthecourse?Howabouttheinstructor?Isithardtopasstheexams?Whatisdifferentfromtheundergraduatecourse?NOPROBLEM1.1CourseInformation5CourseInformationLecturetimeandvenue:Time:Monday(5-6),Wednesday(7-8)Venue:B201(Qingshuihecompus)Language:Chinese+EnglishInstructor:Dr.LIHongwei(李洪伟)Email:[e-mail]:Comingsoon!6Syllabus:IntroductionBasicsofalgorithmdesign&analysisFlowsNP-CompletenessApproximationalgorithmsAdvancetopicsPracticesTextbook:J.Kleinberg，E.Tardos,Algorithmdesign，AddisonWesley，2005Reference:Cormen，Leiserson，Rivest，Stein，算法导论（第二版影印版），高等教育出版社，2007GradingScheme:Finalexam70%Practicesandothers30%CourseInformation网络流NP完备性近似算法算法高级讲座课程设计算法设计与分析基础7Advices1.Thiscourseisworthyofyourtime.Youwillbeproudofyourselfwhenyoufallinthiscourse.2.Thiscoursemaybeahighloadforyou,ifyoujustwanttogetthecredit.3.Readthelecturenotescarefully,whichwillbemorehelpfulforyouthanthetextbooks.4.MakesurethatyoucansolvetheproblemsthatIputhighlinesinthecourse.1.2Introduction9Computersv.s.TractorsWhatisthedifferencebetweenthetwomachines?v.s.Computersaremorepowerful?10ComputerProblems•ProblemsMathematicalfunctionfrominputstomatchingoutputs.•Aparticularinputmustalwaysresultinthesameoutputeverytimethefunctioniscomputed•ProblemdefinitionshouldincludeconstraintsontheresourcesthatmaybeconsumedbyanyacceptablesolutionProblem：Atasktobeperformedbycomputers11ThreeKindsofProblemsDecisionProblem(withyes-noanswers)e.g.Isthereasolutionbetterthansomegivenbound?OptimalValue/OptimalSolutione.g.Whatisthevalueofabestpossiblesolution?e.g.FindasolutionthatachievestheoptimalvalueNumericalCalculatione.g.accurateness,12Algorithms1.amethodoraprocessfollowedtosolveaproblemusingacomputer2.takestheinputofaproblemandtransformsittotheoutput3.AproblemcanhavemanyalgorithmsComputerInputsOutputsWhatisanalgorithm?ProblemAlgorithmProgram13Programsandalgorithms•Aprogramistobereadbycomputer•Analgorithmistobereadbyhumanbeing•Algorithmscanbeexpressedbypseduocodesorjustsomeshortstepsthatareeasytoreadandunderstand•Acomputerprogramisaninstance,orconcreterepresentation,foranalgorithminsomeprogramminglanguage.14GoalsofAlgorithmDesign•Wewanttousecomputerstosolveproblems--TosolveproblemsundertheresourseconstrainsTwo‘conflicting’goals:Todesignanalgorithmthatiseasytounderstand,codeanddebug.Todesignanalgorithmthatmakesefficientuseofthecomputer’sresources.15GoodAlgorithmsAlwaysExist?•Someproblemshavegoodalgorithmsandcanbesolvedquickly.Somemaynothave(wehavenotfoundgoodalgorithmsyet).•Whatshouldwedoforhardproblems?-believingthattherearesomegoodalgorithmsforthem?-believingthattheseproblemsarefundamentallydifferentfromeasyproblems?16DifferentClassesofProblems•Computationalcomplexity.Classifytheproblemsintodifferentclassesbymeasuringtheminimumresource(runningtime,space,orothers)requiredtosolvetheproblem.•人类认识世界的一个共同规则：物以类聚•Someimportantclasses:P,NP,NPC,PTAS,…17DifferentClassesofProblems•NPC:problemsthatmaynothavepolynomial-timealgorithms.•P:asolutioncanbesolvedinpolynomialtime.•ManyimportantproblemsinpracticeareNPC.NPCPNPNP=P+NPC•NP:asolutioncanbecheckedinpolynomialtime.P=NP?植物是否等同动物？18NPCProblems•Heuristicalgorithms:solvingtheproblemsbyyourfeeling.Donotknowifitisrightornot,butthealgorithmrunsfast.•ManymethodstodealwithNPCproblems:•Approximationalgorithms:thealgorithmfindsasolutionnotfarawayfromtheoptimalsolutionandrunsinpolynomialtime.•Fastexactalgorithms:effectiveexponential-timealgorithms(mustfasterthansimplesearchalgorithms).•Parameterizedalgorithms:thealgorithmiseffectivewhentheparameterissmall.1.3SomeRepresentativeProblems20IntervalSchedulingInput.Setofjobswithstarttimesandfinishtimes.Goal.Findmaximumcardinalitysubsetofmutuallycompatiblejobs(donotoverlap).Time01234567891011fgheabcdheb21WeightedIntervalSchedulingInput.Setofjobswithstarttimes,finishtimes,andweights.Goal.Findmaximumweightsubsetofmutuallycompatiblejobs.Time01234567891011201116132312202622IndependentSetInput.Graph.Goal.Findmaximumcardinalityindependentset.62517346514subsetofnodessuchthatnotwojoinedbyanedge23CompetitiveFacilityLocationInput.Graphwithweightoneachnode.Game.Twocompetingplayersalternateinselectingnodes.Notallowedtoselectanodeifanyofitsneighborshavebeenselected.Goal.Selectamaximumweightsubsetofnodes.1015155151151024RepresentativeProblemsIntervalscheduling:nlogn,greedyalgorithm.Weightedintervalscheduling:nlogn,dynamicprogrammingalgorithm.Independentset:NP-complete.Competitivefacilitylocation:PSPACE-complete.