算法设计与分析电子科技大学肖明宇研究生课件

DesignandAnalysisofAlgorithms1.IntroductionMingyuXIAOSchoolofComputerScienceandEngineeringUniversityofElectronicScienceandTechnologyofChinaWelcome!Areyouthinkingaboutthesequestions?Whydoweneedtostudythiscourse?Whatshouldwelearninthecourse?Howabouttheinstructor?Isithardtopasstheexams?Whatisdifferentfromtheundergraduatecourse?NOPROBLEM1.1CourseInformation4CourseInformationLecturetimeandvenue:Time:Wednesday(5-6),Friday(1-2).ThefirsttenweeksVenue:B208(Qingshuihecampus)Language:Chinese+EnglishInstructor:Dr.XIAOMingyu(肖鸣宇)Email:[e-mail]:153-97626165Coursepage:Announcementsandlecturesarereleasedin:[e-mail](passwords:algorithm)2008@HongKong5Syllabus:Introduction(2hours)Basicsofalgorithmdesign&analysis(8hours)Flows(4hours)NP-CompletenessandAppro.alg.(10hours)Advancetopics(12hours)Practices(4hours)Textbook:J.Kleinberg，E.Tardos,Algorithmdesign，AddisonWesley，2005Reference:Cormen，Leiserson，Rivest，Stein，算法导论（影印版），高等教育出版社，2007GradingScheme:Finalexam70%Practicesandothers30%CourseInformation网络流NP完备性和近似算法算法高级讲座课程设计算法设计与分析基础6CourseInformationDatafromlastyear:Attendedfinalexam:144(Registration:163)考试100考查44考试100人90分80分70分60分不及格考查44人2205717441人通过Datafromyear2012:Attendedfinalexam:151(Registration:163)考试106考查45考试106人90分80分70分60分不及格考查45人6353314835人通过7CourseInformation2012年冠军榜第一名：95分，郭思奇，电子与通信（应用型硕士）第二名：93分，肖燕霞，计算机应用技术第三名：92分，牛攀，计算机系统结构廖军，计算机应用技术第五名：91分，计算机软件与理论第六名：90分，计算机应用技术2013年冠军榜第一名：90分，周志惠，计算机软件与理论周佼，计算机应用技术第三名：87分，姜晓，计算机应用技术第四名：86分，甘茂然，计算机系统结构王浩，信息与通信工程（考查）8CourseInformationAdvicestowhowantstoregisterthiscourse:1.Thiscourseisworthyofyourtime.Youwillbeproudofyourselfwhenyoufallinthiscourse.2.Thiscoursemaybeaheavyloadforyou,ifyoudonotwanttospendtimeonit.SoDON’Tselectthiscourseifyoujustwanttogetthecredit.3.Readthelecturenotescarefully,whichwillbemorehelpfulforyouthanthetextbooks.4.MakesurethatyoucansolvetheproblemsthatIputhighlinesinthecourse.5.Insomeinterviewsofjobhunting,youmayfindthetechniquesinthecourseuseful.1.2Introduction10Computersv.s.TractorsWhatisthedifferencebetweenthetwomachines?v.s.Computersaremorepowerful?11ComputerProblems•ProblemsMathematicalfunctionfrominputstomatchingoutputs.•Aparticularinputmustalwaysresultinthesameoutputeverytimethefunctioniscomputed•ProblemdefinitionshouldincludeconstraintsontheresourcesthatmaybeconsumedbyanyacceptablesolutionProblem：Atasktobeperformedbycomputers12ThreeKindsofProblemsDecisionProblem(withyes-noanswers)e.g.Isthereasolutionbetterthansomegivenbound?OptimalValue/OptimalSolutione.g.Whatisthevalueofabestpossiblesolution?e.g.FindasolutionthatachievestheoptimalvalueNumericalCalculatione.g.Solvinganequationgroup13Algorithms1.amethodoraprocessfollowedtosolveaproblemusingacomputer2.takestheinputofaproblemandtransformsittotheoutput3.AproblemcanhavemanyalgorithmsComputerInputsOutputsWhatisanalgorithm?ProblemAlgorithmProgram14Programsandalgorithms•Aprogramistobereadbycomputer•Analgorithmistobereadbyhumanbeing•Algorithmscanbeexpressedbypseduocodesorjustsomeshortstepsthatareeasytoreadandunderstand•Acomputerprogramisaninstance,orconcreterepresentation,foranalgorithminsomeprogramminglanguage.15GoalsofAlgorithmDesign•Wewanttousecomputestosolveproblems--TosolveproblemsundertherecourseconstrainsTwo‘conflicting’goals:Todesignanalgorithmthatiseasytounderstand,codeanddebug.Todesignanalgorithmthatmakesefficientuseofthecomputer’sresources.16GoodAlgorithmsAlwaysExist?•Someproblemshavegoodalgorithmsandcanbesolvedquickly.Somemaynothave(wehavenotfoundgoodalgorithmsyet).•Whatshouldwedoforhardproblems?-believingthattherearesomegoodalgorithmsforthem?-believingthattheseproblemsarefundamentallydifferentfromeasyproblems?17DifferentClassesofProblems•Computationalcomplexity.Classifytheproblemsintodifferentclassesbymeasuringtheminimumresource(runningtime,space,orothers)requiredtosolvetheproblem.•人类认识世界的一个共同规则：物以类聚•Someimportantclasses:P,NP,NPC,PTAS,…18DifferentClassesofProblems•NPC:problemsthatmaynothavepolynomial-timealgorithms.•P:asolutioncanbesolvedinpolynomialtime.•ManyimportantproblemsinpracticeareNPC.NPCPNPNP=P+NPC•NP:asolutioncanbecheckedinpolynomialtime.P=NP?植物是否等同动物？19NPCProblems•Heuristicalgorithms:solvingtheproblemsbyyourfeeling.Donotknowifitisrightornot,butthealgorithmrunsfast.•ManymethodstodealwithNPCproblems:•Approximationalgorithms:thealgorithmfindsasolutionnotfarawayfromtheoptimalsolutionandrunsinpolynomialtime.•Fastexactalgorithms:effectiveexponential-timealgorithms(mustfasterthansimplesearchalgorithms).•Parameterizedalgorithms:thealgorithmiseffectivewhentheparameterissmall.1.3SomeRepresentativeProblems21IntervalSchedulingInput.Setofjobswithstarttimesandfinishtimes.Goal.Findmaximumcardinalitysubsetofmutuallycompatiblejobs(donotoverlap).Time01234567891011fgheabcdheb22WeightedIntervalSchedulingInput.Setofjobswithstarttimes,finishtimes,andweights.Goal.Findmaximumweightsubsetofmutuallycompatiblejobs.Time01234567891011201116132312202623BipartiteMatchingInput.Bipartitegraph.Goal.Findmaximumcardinalitymatching.C152AE3BD424IndependentSetInput.Graph.Goal.Findmaximumcardinalityi