算法介紹入門Introduction

算法介紹入門Introduction第一頁，共29頁。Welcome!Areyouthinkingaboutthesequestions?

Whydoweneedtostudythiscourse?

Whatshouldwelearninthecourse?

Howabouttheinstructor?

Isithardtopasstheexams?Whatisdifferentfromtheundergraduatecourse?Tobe,ornottobe

第二頁，共29頁。1.1CourseInformation第三頁，共29頁。CourseInformation

Lecturetimeandvenue:

Time:Tuesday(5-6),Thursday(9-11).ThefirstEIGHTweeksVenue:B107,Pingxueloubuilding(Qingshuihecampus)Language:

Chinese+English

Instructor:

Dr.XIAOMingyu(肖鳴宇)

Email:

Tel:

Coursepage:

Announcementsandlecturesare

releasedin:

(passwords:algorithm)

4第四頁，共29頁。Syllabus:

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，算法導(dǎo)論（影印版），高等教育出版社，2007GradingScheme:

Finalexam70%Practicesandothers30%

CourseInformation網(wǎng)絡(luò)流NP完備性和近似算法算法高級講座課程設(shè)計算法設(shè)計與分析基礎(chǔ)5第五頁，共29頁。CourseInformationDatafrom2015:

Attendedfinalexam:149(Registration:187)

考試129考查20

考試129人90分80分70分60分不及格考查

20人5246531316人通過Datafrom2014:

Attendedfinalexam:164(Registration:175)

考試137考查27

考試137人90分80分70分60分不及格考查

27人3406520918人通過6第六頁，共29頁。CourseInformationDatafromyear2012:

Attendedfinalexam:151(Registration:163)考試106考查45

考試106人90分80分70分60分不及格考查

45人6353314835人通過Datafrom2013:

Attendedfinalexam:144(Registration:163)

考試100考查44

考試100人90分80分70分60分不及格考查

44人2205717441人通過7第七頁，共29頁。CourseInformation

2015年冠軍榜(卷面分?jǐn)?shù))

第一名：94分，寇紹威，計算機(jī)軟件與理論

第二名：89分，潘睿，計算機(jī)應(yīng)用技術(shù)

第三名：87分，蔣鴻斌，計算機(jī)軟件與理論

第四名：86分，蔡騰遠(yuǎn)，計算機(jī)應(yīng)用技術(shù)

劉磊，計算機(jī)軟件與理論

2014年冠軍榜(卷面分?jǐn)?shù))

第一名：93分，王治，計算機(jī)系統(tǒng)結(jié)構(gòu)

陳均滔，計算機(jī)系統(tǒng)結(jié)構(gòu)

第三名：88分，張玖林，通信與信息系統(tǒng)

周令輝，通信與信息系統(tǒng)第五名：87分，胡海嘯，計算機(jī)軟件與理論

王飛，計算機(jī)技術(shù)

2013年冠軍：計算機(jī)軟件與理論；2012年冠軍：通信與信息系統(tǒng)

8第八頁，共29頁。CourseInformationFindyourownway2014年12月27日上午8點9第九頁，共29頁。CourseInformationAdvicestowhowantstoregisterthiscourse:

1.Thiscourseisworthyofyourtime.Youwillbeproudofyourselfwhenyoufallinthiscourse.2.Thiscoursemaybeaheavyloadforyou,ifyoudonotwanttospendtimeonit.SoDON’Tselectthiscourseifyoujustwanttogetthecredit.

3.

Readthelecturenotescarefully,whichwillbemorehelpfulforyouthanthetextbooks.

4.MakesurethatyoucansolvetheproblemsthatIputhighlinesinthecourse.5.Insomeinterviewsofjobhunting,youmayfindthetechniquesinthecourseuseful.10第十頁，共29頁。1.2Introduction第十一頁，共29頁。Computersv.s.TractorsWhatisthedifferencebetweenthetwomachines?v.s.Computersaremorepowerful?12第十二頁，共29頁。ComputerProblemsProblemsMathematicalfunctionfrominputstomatchingoutputs.AparticularinputmustalwaysresultinthesameoutputeverytimethefunctioniscomputedProblemdefinitionshouldincludeconstraintsontheresourcesthatmaybeconsumedbyanyacceptablesolutionProblem：Atasktobeperformedbycomputers13第十三頁，共29頁。ThreeKindsofProblemsDecisionProblem(withyes-noanswers)e.g.Isthereasolutionbetterthansomegivenbound?OptimalValue/OptimalSolutione.g.Whatisthevalueofabestpossiblesolution?e.g.FindasolutionthatachievestheoptimalvalueNumericalCalculation

e.g.Solvinganequationgroup14第十四頁，共29頁。Algorithms1.amethodoraprocessfollowedtosolveaproblemusingacomputer

2.takestheinputofaproblemandtransformsittotheoutput

3.AproblemcanhavemanyalgorithmsComputerInputsOutputsWhatisanalgorithm?ProblemAlgorithmProgram15第十五頁，共29頁。ProgramsandalgorithmsAprogramistobereadbycomputerAnalgorithmistobereadbyhumanbeingAlgorithmscanbeexpressedbypseduocodesorjustsomeshortstepsthatareeasytoreadandunderstandAcomputerprogramisaninstance,orconcreterepresentation,foranalgorithminsomeprogramminglanguage.

16第十六頁，共29頁。GoalsofAlgorithmDesignWewanttousecomputestosolveproblems

--TosolveproblemsundertherecourseconstrainsTwo‘conflicting’goals:Todesignanalgorithmthatiseasytounderstand,codeanddebug.Todesignanalgorithmthatmakesefficientuseofthecomputer’sresources.

17第十七頁，共29頁。GoodAlgorithmsAlwaysExist?Someproblemshavegoodalgorithmsandcanbesolvedquickly.Somemaynothave(wehavenotfoundgoodalgorithmsyet).Whatshouldwedoforhardproblems?

-believingthattherearesomegoodalgorithmsforthem?

-believingthattheseproblemsarefundamentallydifferentfromeasyproblems?18第十八頁，共29頁。DifferentClassesofProblemsComputationalcomplexity.

Classifytheproblemsintodifferentclassesbymeasuringtheminimumresource(runningtime,space,orothers)requiredtosolvetheproblem.人類認(rèn)識世界的一個共同規(guī)則：物以類聚Someimportantclasses:P,NP,NPC,PTAS,…19第十九頁，共29頁。DifferentClassesofProblemsNPC:problemsthatmaynothavepolynomial-timealgorithms.P:asolutioncanbesolvedinpolynomialtime.ManyimportantproblemsinpracticeareNPC.NPCPNPNP:asolutioncanbecheckedinpolynomialtime.P=NP?植物是否等同動物？20第二十頁，共29頁。NPCProblemsHeuristicalgorithms:solvingtheproblemsbyyourfeeling.Donotknowifitisrightornot,butthealgorithmrunsfast.ManymethodstodealwithNPCproblems:Approximationalgorithms:thealgorithmfindsasolutionnotfarawayfromtheoptimalsolutionandrunsinpolynomialtime.Fastexactalgorithms:effectiveexponential-timealgorithms(mustfasterthansimplesearchalgorithms).Parameterizedalgorithms:thealgorithmiseffectivewhentheparameterissmall.21第二十一頁，共29頁。1.3SomeRepresentativeProblems第二十二頁，共29頁。IntervalSchedulingInput.Setofjobswithstarttimesandfinishtimes.Goal.Findmaximumcardinalitysubsetofmutuallycompatiblejobs(donotoverlap).Time01234567891011fgheabcdheb23第二十三頁，共29頁。WeightedIntervalSchedulingInput.Setofjobswithstarttimes,finishtimes,andweights.Goal.Findmaximumweightsubsetofmutuallycompatiblejobs.Time01234567891011201116132312202624第二十四頁，共29頁。BipartiteMatchingInput.Bipartitegraph.Goal.Findmaximum

cardinalitymatching.C152AE3BD425第二十五頁，共29頁。Independ