events and probability

《events and probability》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、CHAPTERONEEventsandProbabilityThischapterintroducesthenotionofrandomizedalgorithmsandreviewssomebasicL"onceptsofprobabilitytheoryinthecontextofanalyzingtheperformanceofsimplerandomizedalgorithmsforverifyingalgebraicidentitiesandfindingaminimumcut-setinagraph.1.1.Application:VerifyingPolynomialIden

2、titiesComputerscansometimesmakesmistakes,dueforexampletoincorrectprogrammingorhardwarefailure.Itwouldbeusefultohavesimplewaystodouble-checktheresultsofcomputations.Forsomeproblems,wecanuserandomnesstoefficientlyverifytheL"orrectnessofanoutput.Supposewehaveaprogramthatmultipliestogethermonomials.Co

3、nsidertheprobkmofverifyingthefollowingidentity,whichmightbeoutputbyourprogram:(x+l)(x-2)(x+3)(x-4)(x+S)(x-6);1x6-7x3+25.Thereisaneasywaytoverifywhethertheidentityiscorrect:multiplytogetherthetermsontheleft-handsideandseeiftheresultingpolynomialmatchestheright-hand....ide.Inthisexample,whenwemultip

4、lyalltheconstanttermsontheleft,theresultJoesnotmatchtheconstanttermontheright,sotheidentitycannotbevalid.Moregenerally,giventwopolynomialsF(x)andG(x),wecanverifytheidentity')F(x)�G(x)byconvertingthetwopolynomialstotheircanonicalforms(2:..::�1=0c;x;);twopolynomialsareequivalentifandonlyifallthecoef

5、ficientsintheircanonicalformsareequal.Fromthispointonletusassumethat,asinourexample,F(x)isgivenasaproductF(x)=TI�1=1(x-a;)andG(x)isgiveninitscanonicalform.TransformingF(x)toitscanonicalformbyconsecutivelymultiplyingtheithmonomialwiththeproductofthefirsti-1monomialsrequiresB(d2)multiplicationsofcoe

6、fficients.Weassumein1EVENTSANDPROBABILITYwhatfollowsthateachmultiplicationcanbeperformedinconstanttime,althoughiftheproductsofthecoefficientsgrowlargethenitcouldconceivablyrequiremorethanconstanttimetoaddandmultiplynumberstogether.Sofar,wehavenotsaidanythingparticularlyinteresting.Tocheckwhetherth

7、ecomputerprogramhasmultipliedmonomialstogethercorrectly,wehavesuggestedmultiplyingthemonomialstogetheragaintochecktheresult.Ourapproachforcheckingtheprogramistowriteanotherprogramthatdoesessentiallythesamethingwe