ALGORITHMS DESIGN TECHNIQUES AND ANALYSIS M.Mar

《ALGORITHMS DESIGN TECHNIQUES AND ANALYSIS M.Mar》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ALGORITHMSDESIGNTECHNIQUESANDANALYSISM.H.AlsuwaiyelInformation&ComputerScienceDepartmentKFUPMJuly,1999PrefaceThefieldofcomputeralgorithmshasflourishedsincetheearly1960’swhenthefirstusersofelectroniccomputersstartedtopayattentiontotheper-formanceofprograms.Thelimitedresour

2、cesofcomputersatthattimeresultedinadditionalimpetusfordevisingefficientcomputeralgorithms.Afterextensiveresearchinthisfield,numerousefficientalgorithmsfordif-ferentproblemsemerged.Thesimilaritiesamongdifferentalgorithmsforcertainclassesofproblemshaveresultedingeneralalgorith

3、mdesigntech-niques.Thisbookemphasizesmostofthesealgorithmdesigntechniquesthathaveprovedtheirutilityinthesolutiontomanyproblems.Itmaybeconsideredasanattempttocoverthemostcommontechniquesinthedesignofsequentialalgorithms.Eachtechniqueispresentedasfollows.First,thecontext

4、inwhichthattechniquecanbeapplied.Second,thespe-cialcharacteristicsofthattechniquethatsetitapart.Third,comparisonwithothertechniques,wheneverpossible;finally,andmostimportantly,illustrationofthetechniquebyapplyingittoseveralproblems.Althoughthemainthemeofthebookisalgorit

5、hmdesigntechniques,italsoemphasizestheothermajorcomponentinalgorithmicdesign:theanalysisofalgorithms.Itcoversindetailtheanalysisofmostofthealgo-rithmspresented.Chapter2coversmostofthemathematicaltoolsthatarehelpfulinanalyzingalgorithms.Chapter11isanintroductiontothefiel

6、dofcomputationalcomplexity,andChapter12coversthebasicsofestablish-inglowerboundsonthesolutionofvariousproblems.Thesechaptersareindispensableforthedesignofefficientalgorithms.Thefocusofthepresentationisonpracticalapplicationsofthedesigntechniques.Eachtechniqueisillustrate

7、dbyprovidinganadequatenum-iiiPrefaceberofalgorithmstosolvesomeproblemsthatquiteoftenariseinmanyapplicationsinscienceandengineering.Thestyleofpresentationofalgorithmsisstraightforward,andusespseudocodethatissimilartothesyntaxofstructuredprogramminglanguages,e.g.if-then-

8、else,forandwhileconstructs.ThepseudocodeissometimesintermixedwithEnglishwhenevernecessary.Describingaportionofanalgor