资源描述：
《lecture 23 advanced topics (cont.)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYYY).License:Crea
2、tiveCommonsAttribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Transcript
3、–Lecture23OK,goodmorning.Sotoday,we'regoingtocontinueourexplorationofmultithreadedalgorithms.Lasttimewetalkedaboutsomeaspectsofscheduling,andalittlebitaboutlinguisticstodescribeamultithreadedcompetition.Andtoday,we'regoingtoactuallydealwithsomealgorithms.So,we'regoingtostartoutwitharea
4、llysimple,actually,what'sfunaboutthis,actually,isthateverythingI'mgoingtoteachyoutodayIcouldhavetaughtyouinweektwo,OK,becausebasicallyit'sjusttakingthedivideandconquerhammer,andjustsmashingproblemafterproblemwithit.OK,andso,actuallynextweek'slecturesoncaching,alsoverysimilar.So,everybo
5、dyshouldboneupontheirmastertheoremandsubstitutionmethodsforoccurrences,andsoforthbecausethat'sourgoingtobedoing.Andofcourse,allthestuffwillbeonthefinal.Solet'sstartwithmatrixmultiplication.Andwe'lldonbyn.So,ourproblemistodoCequalsAtimesB.Andthewaywe'lldothatisusingdivideandconquer,aswe
6、sawbefore,althoughwe'renotgoingtouseStrassen'smethod.OK,we'lljustusetheordinarything,andI'llleaveStrassen'sasanexercise.So,theideaiswe'regoingtolookatmatrixmultiplicationintermsofannbynmatrix,intermsofnover2bynover2matrices.So,IpartitionCintofourblocks,andlikewisewithAandB.OK,andwemult
7、iplythoseout,andthatgivesusthefollowing.MakesureIgetallmyindicesright.OK,soitgivesusthesumofthesetwonbynmatrices.OK,soforexample,ifImultiplythefirstrowbythefirstcolumn,I'mputtingthefirstterm,A_1-1timesB_1-1inthismatrix,inthesecondone,A_1-2timesB_2-1getsplacedhere.So,whenIsumthem,ands
