关闭

关闭

封号提示

内容

首页 [具体数学].Concrete.Math.pdf

[具体数学].Concrete.Math.pdf

[具体数学].Concrete.Math.pdf

上传者: 至尊小寳 2013-10-11 评分 4.5 0 74 10 337 暂无简介 简介 举报

简介:本文档为《[具体数学].Concrete.Mathpdf》,可适用于高等教育领域,主题内容包含CONCRETEMATHEMATICSDedicatedtoLeonhardEuler(l)CONCRETEMATHEMATICSDedicated符等。

CONCRETEMATHEMATICSDedicatedtoLeonhardEuler(l)CONCRETEMATHEMATICSDedicatedtoLeonhardEuler(l)CONCRETEMATHEMATICSRonaldLGrahamATTBellLaboratoriesDonaldEKnuthStanfordUniversityOrenPatashnikStanfordUniversityAADDISONWESLEYPUBLISHINGCOMPANYReading,MassachusettsMenloPark,CaliforniaNewYorkDonMills,OntarioWokingham,EnglandAmsterdamBonnSydneySingaporeTokyoMadridSanJuanLibraryofCongressCataloginginPublicationDataGraham,RonaldLewis,Concretemathematics:afoundationforcomputerscienceRonaldLGraham,DonaldEKnuth,OrenPatashnikxiii,pcmBibliography:pIncludesindexISBNoMathematicsElectronicdataprocessingMathematicsIKnuth,DonaldErvin,IIPatashnik,Oren,IIITitleQACdcCIPSixthprinting,withcorrections,OctoberCopyrightbyAddisonWesleyPublishingCompanyAllrightsreservedNopartofthispublicationmaybereproduced,storedinaretrievalsystemortransmitted,inanyformorbyanymeans,electronic,mechanical,photocopying,recording,orotherwise,withoutthepriorwrittenpermissionofthepublisherPrintedintheUnitedStatesofAmericaPublishedsimultaneouslyinCanadaFGHIJKHAPreface“Aodience,level,andtreatmentadescriptionofsuchmattersiswhatprefacesaresupposedtobeabout”PRHalmos“Peopledoacquirealittlebriefauthoritybyequippingthemselveswithjargon:theycanpontificateandairasuperficialexpertiseButwhatweshouldaskofeducatedmathematiciansisnotwhattheycanspeechifyabout,norevenwhattheyknowabouttheexistingcorpusofmathematicalknowledge,butratherwhatcantheynowdowiththeirlearningandwhethertheycanactuallysolvemathematicalproblemsarisinginpracticeInshort,welookfordeedsnotwords”JHammersleyTHISBOOKISBASEDonacourseofthesamenamethathasbeentaughtannuallyatStanfordUniversitysinceAboutfiftystudentshavetakeniteachyearjuniorsandseniors,butmostlygraduatestudentsandalumnioftheseclasseshavebeguntospawnsimilarcourseselsewhereThusthetimeseemsripetopresentthematerialtoawideraudience(includingsophomores)ItwasadarkandstormydecadewhenConcreteMathematicswasbornLongheldvalueswereconstantlybeingquestionedduringthoseturbulentyearscollegecampuseswerehotbedsofcontroversyThecollegecurriculumitselfwaschallenged,andmathematicsdidnotescapescrutinyJohnHammersleyhadjustwrittenathoughtprovokingarticle“Ontheenfeeblementofmathematicalskillsby‘ModernMathematics’andbysimilarsoftintellectualtrashinschoolsanduniversities”otherworriedmathematiciansevenasked,“Canmathematicsbesaved”OneofthepresentauthorshadembarkedonaseriesofbookscalledTheArtofComputerProgramming,andinwritingthefirstvolumehe(DEK)hadfoundthatthereweremathematicaltoolsmissingfromhisrepertoirethemathematicsheneededforathorough,wellgroundedunderstandingofcomputerprogramswasquitedifferentfromwhathe’dlearnedasamathematicsmajorincollegeSoheintroducedanewcourse,teachingwhathewishedsomebodyhadtaughthimThecoursetitle“ConcreteMathematics”wasoriginallyintendedasanantidoteto“AbstractMathematics,”sinceconcreteclassicalresultswererapidlybeingsweptoutofthemodernmathematicalcurriculumbyanewwaveofabstractideaspopularlycalledthe“NewMath!’Abstractmathematicsisawonderfulsubject,andthere’snothingwrongwithit:It’sbeautiful,general,andusefulButitsadherentshadbecomedeludedthattherestofmathematicswasinferiorandnolongerworthyofattentionThegoalofgeneralizationhadbecomesofashionablethatagenerationofmathematicianshadbecomeunabletorelishbeautyintheparticular,toenjoythechallengeofsolvingquantitativeproblems,ortoappreciatethevalueoftechniqueAbstractmathematicswasbecominginbredandlosingtouchwithrealitymathematicaleducationneededaconcretecounterweightinordertorestoreahealthybalanceWhenDEKtaughtConcreteMathematicsatStanfordforthefirsttime,heexplainedthesomewhatstrangetitlebysayingthatitwashisattemptVviPREFACEtoteachamathcoursethatwashardinsteadofsoftHeannouncedthat,contrarytotheexpectationsofsomeofhiscolleagues,hewasnotgoingtoteachtheTheoryofAggregates,norStone’sEmbeddingTheorem,noreventheStoneTechcompactification(Severalstudentsfromthecivilengineeringdepartmentgotupandquietlylefttheroom)AlthoughConcreteMathematicsbeganasareactionagainstothertrends,themainreasonsforitsexistencewerepositiveinsteadofnegativeAndasthecoursecontinueditspopularplaceinthecurriculum,itssubjectmatter“solidified”andprovedtobevaluableinavarietyofnewapplicationsMeanwhile,independentconfirmationfortheappropriatenessofthenamecamefromanotherdirection,whenZAMelzakpublishedtwovolumesentitledCompaniontoConcreteMathematicsThematerialofconcretemathematicsmayseematfirsttobeadisparatebagoftricks,butpracticemakesitintoadisciplinedsetoftoolsIndeed,thetechniqueshaveanunderlyingunityandastrongappealformanypeopleWhenanotheroneoftheauthors(RLG)firsttaughtthecoursein,thestudentshadsuchfunthattheydecidedtoholdaclassreunionayearlaterButwhatexactlyisConcreteMathematicsItisablendofcontinuousanddiSCRETEmathematicsMoreconcretely,itisthecontrolledmanipulationofmathematicalformulas,usingacollectionoftechniquesforsolvingproblemsOnceyou,thereader,havelearnedthematerialinthisbook,allyouwillneedisacoolhead,alargesheetofpaper,andfairlydecenthandwritinginordertoevaluatehorrendouslookingsums,tosolvecomplexrecurrencerelations,andtodiscoversubtlepatternsindataYouwillbesofluentinalgebraictechniquesthatyouwilloftenfinditeasiertoobtainexactresultsthantosettleforapproximateanswersthatarevalidonlyinalimitingsenseThemajortopicstreatedinthisbookincludesums,recurrences,elementarynumbertheory,binomialcoefficients,generatingfunctions,discreteprobability,andasymptoticmethodsTheemphasisisonmanipulativetechniqueratherthanonexistencetheoremsorcombinatorialreasoningthegoalisforeachreadertobecomeasfamiliarwithdiscreteoperations(likethegreatestintegerfunctionandfinitesummation)asastudentofcalculusisfamiliarwithcontinuousoperations(liketheabsolutevaluefunctionandinfiniteintegration)Noticethatthislistoftopicsisquitedifferentfromwhatisusuallytaughtnowadaysinundergraduatecoursesentitled“DiscreteMathematics!’Thereforethesubjectneedsadistinctivename,and“ConcreteMathematics”hasprovedtobeassuitableasanyotherTheoriginaltextbookforStanford’scourseonconcretemathematicswasthe“MathematicalPreliminaries”sectioninTheArtofComputerProgrammingButthepresentationinthosepagesisquiteterse,soanotherauthor(OP)wasinspiredtodraftalengthysetofsupplementarynotesThe“Theheartofmathematicsconsistsofconcreteexamplesandconcreteproblems”PRHalmos“ltisdownrightsinfultoteachtheabstractbeforetheconcrete”ZAMelzakConcreteMathematicsisabridgetoabstractmathematics“Theadvancedreaderwhoskipspartsthatappeartooelementarymaymissmorethanthelessadvancedreaderwhoskipspartsthatappeartoocomplex”GPdlya(We’renotboldenoughtotryDistinuousMathematics)‘Iaconcretelifepreserverthrowntostudentssinkinginaseaofabstraction”WGottschalkMathgraffiti:Kilroywasn’tHaarFreethegroupNukethekernelPowertothenN=ljP=NPIhaveonlyamarginalinterestinthissubjectThiswasthemostenjoyablecourseI’veeverhadButitmightbenicetosummarizethematerialasyougoalongPREFACEviipresentbookisanoutgrowthofthosenotesitisanexpansionof,andamoreleisurelyintroductionto,thematerialofMathematicalPreliminariesSomeofthemoreadvancedpartshavebeenomittedontheotherhand,severaltopicsnotfoundtherehavebeenincludedheresothatthestorywillbecompleteTheauthorshaveenjoyedputtingthisbooktogetherbecausethesubjectbegantojellandtotakeonalifeofitsownbeforeoureyesthisbookalmostseemedtowriteitselfMoreover,thesomewhatunconventionalapproacheswehaveadoptedinseveralplaceshaveseemedtofittogethersowell,aftertheseyearsofexperience,thatwecan’thelpfeelingthatthisbookisakindofmanifestoaboutourfavoritewaytodomathematicsSowethinkthebookhasturnedouttobeataleofmathematicalbeautyandsurprise,andwehopethatourreaderswillshareatleastEofthepleasurewehadwhilewritingitSincethisbookwasborninauniversitysetting,wehavetriedtocapturethespiritofacontemporaryclassroombyadoptinganinformalstyleSomepeoplethinkthatmathematicsisaseriousbusinessthatmustalwaysbecoldanddrybutwethinkmathematicsisfun,andwearen’tashamedtoadmitthefactWhyshouldastrictboundarylinebedrawnbetweenworkandplayConcretemathematicsisfullofappealingpatternsthemanipulationsarenotalwayseasy,buttheanswerscanbeastonishinglyattractiveThejoysandsorrowsofmathematicalworkarereflectedexplicitlyinthisbookbecausetheyarepartofourlivesStudentsalwaysknowbetterthantheirteachers,sowehaveaskedthefirststudentsofthismaterialtocontributetheirfrankopinions,as“grafhti”inthemarginsSomeofthesemarginalmarkingsaremerelycorny,someareprofoundsomeofthemwarnaboutambiguitiesorobscurities,othersaretypicalcommentsmadebywiseguysinthebackrowsomearepositive,somearenegative,somearezeroButtheyallarerealindicationsoffeelingsthatshouldmakethetextmaterialeasiertoassimilate(TheinspirationforsuchmarginalnotescomesfromastudenthandbookentitledApproachingStanford,wheretheofficialuniversitylineiscounterbalancedbytheremarksofoutgoingstudentsForexample,Stanfordsays,“ThereareafewthingsyoucannotmissinthisamorphousshapewhichisStanford”themarginsays,“Amorphouswhattheh***doesthatmeanTypicalofthepseudointellectualismaroundhere”Stanford:“Thereisnoendtothepotentialofagroupofstudentslivingtogether”Grafhto:“Stanforddormsarelikezooswithoutakeeper“)Themarginsalsoincludedirectquotationsfromfamousmathematiciansofpastgenerations,givingtheactualwordsinwhichtheyannouncedsomeoftheirfundamentaldiscoveriesSomehowitseemsappropriatetomixthewordsofLeibniz,Euler,Gauss,andotherswiththoseofthepeoplewhowillbecontinuingtheworkMathematicsisanongoingendeavorforpeopleeverywheremanystrandsarebeingwovenintoonerichfabricviiiPREFACEThisbookcontainsmorethanexercises,dividedintosixcategories:Isee:WarmupsareexercisesthatEVERYREADERshouldtrytodowhenfirstConcretemathematitsmeanSdri,,inpreadingthematerialBasicsareexercisestodevelopfactsthatarebestlearnedbytryingone’sownderivationratherthanbyreadingsomebodyelse’s,HomeworkexercisesareproblemsintendedtodeepenanunderstandingofmaterialinthecurrentchapterExamproblemstypicallyinvolveideasfromtwoormorechapterssimultaneouslytheyaregenerallyintendedforuseintakehomeexams(notforinclassexamsundertimepressure)BonusproblemsgobeyondwhatanaveragestudentofconcretemathematicsisexpectedtohandlewhiletakingacoursebasedonthisbooktheyextendthetextininterestingwaysThehomeworkwastoughbutIlearnedalotItwaswortheveryhourTakehomeexamsarevitalkeepthemExamswereharderthanthehomeworkledmetoexoectResearchproblemsmayormaynotbehumanlysolvable,buttheonespresentedhereseemtobeworthatry(withouttimepressure)AnswerstoalltheexercisesappearinAppendixA,oftenwithadditionalinformationaboutrelatedresults(Ofcourse,the“answers”toresearchproblemsareincompletebuteveninthesecases,partialresultsorhintsaregiventhatmightprovetobehelpful)Readersareencouragedtolookattheanswers,especiallytheanswerstothewarmupproblems,butonlyAFTERmakingaseriousattempttosolvetheproblemwithoutpeekingWehavetriedinAppendixCtogivepropercredittothesourcesofeachexercise,sinceagreatdealofcreativityandorluckoftengoesintothedesignofaninstructiveproblemMathematicianshaveunfortunatelydevelopedatraditionofborrowingexerciseswithoutanyacknowledgmentwebelievethattheoppositetradition,practicedforexamplebybooksandmagazinesaboutchess(wherenames,dates,andlocationsoforiginalchessproblemsareroutinelyspecified)isfarsuperiorHowever,wehavenotbeenabletopindownthesourcesofmanyproblemsthathavebecomepartofthefolkloreIfanyreaderknowstheoriginofanexerciseforwhichourcitationismissingorinaccurate,wewouldbegladtolearnthedetailssothatwecancorrecttheomissioninsubsequenteditionsofthisbookThetypefaceusedformathematicsthroughoutthisbookisanewdesignbyHermannZapf,commissionedbytheAmericanMathematicalSocietyanddevelopedwiththehelpofacommitteethatincludedBBeeton,RPBoas,LKDurst,DEKnuth,PMurdock,RSPalais,PRenz,ESwanson,SBWhidden,andWBWoolfTheunderlyingphilosophyofZapf’sdesignistocapturetheflavorofmathematicsasitmightbewrittenbyamathematicianwithexcellenthandwritingAhandwrittenratherthanmechanicalstyleisappropriatebecausepeoplegenerallycreatemathematicswithpen,pencil,Cheatersmaypassthiscoursebyjustcopyingtheanswers,butthey’reonlycheatingthemselvesDifficultexamsdon’ttakeintoaccountstudentswhohaveotherclassestoprepareforI’munaccustomedtothisfaceDearprof:Thanksfor()thepuns,()thesubjectmatterdon’tseehowwhatI’velearnedwilleverhelpmeIbadalotoftroubleinthisclass,butIknowitsharpenedmymathskillsandmythinkingskillswouldadvisethecasualstudenttostayawayfromthiscoursePREFACEixorchalk(Forexample,oneofthetrademarksofthenewdesignisthesymbolforzero,‘’,whichisslightlypointedatthetopbecauseahandwrittenzerorarelyclosestogethersmoothlywhenthecurvereturnstoitsstartingpoint)Thelettersareupright,notitalic,sothatsubscripts,superscripts,andaccentsaremoreeasilyfittedwithordinarysymbolsThisnewtypefamilyhasbeennamedAMEuler,afterthegreatSwissmathematicianLeonhardEuler()whodiscoveredsomuchofmathematicsasweknowittodayThealphabetsincludeEulerText(AaBbCcthroughXxYyZz),EulerFraktur(accthroughQ’$lu,),andEulerScriptCapitals(A’BethroughXyZ),aswellasEulerGreek(AOLBfirythroughXXY’J,nw)andspecialsymbolssuchaspandKWeareespeciallypleasedtobeabletoinauguratetheEulerfamilyoftypefacesinthisbook,becauseLeonhardEuler’sspirittrulylivesoneverypage:ConcretemathematicsisEulerianmathematicsTheauthorsareextremelygratefultoAndreiBroder,ErnstMayr,AndrewYao,andFrancesYao,whocontributedgreatlytothisbookduringtheyearsthattheytaughtConcreteMathematicsatStanfordFurthermoreweofferthankstotheteachingassistantswhocreativelytranscribedwhattookplaceinclasseachyearandwhohelpedtodesigntheexaminationquestionstheirnamesarelistedinAppendixCThisbook,whichisessentiallyacompendiumofsixteenyears’worthoflecturenotes,wouldhavebeenimpossiblewithouttheirfirstrateworkManyotherpeoplehavehelpedtomakethisbookarealityForexample,wewishtocommendthestudentsatBrown,Columbia,CUNY,Princeton,Rice,andStanfordwhocontributedthechoicegraffitiandhelpedtodebugourfirstdraftsOurcontactsatAddisonWesleywereespeciallyefficientandhelpfulinparticular,wewishtothankourpublisher(PeterGordon),productionsupervisor(BetteAaronson),designer(RoyBrown),andcopyeditor(LynDupre)TheNationalScienceFoundationandtheOfficeofNavalResearchhavegiveninvaluablesupportCherylGrahamwastremendouslyhelpfulaswepreparedtheindexAndaboveall,wewishtothankourwives(Fan,Jill,andAmy)fortheirpatience,support,encouragement,andideasWehavetriedtoproduceaperfectbook,butweareimperfectauthorsThereforewesolicithelpincorrectinganymistakesthatwe’vemadeArewardof$willgratefullybepaidtothefirstfinderofanyerror,whetheritismathematical,historical,ortypographicalMurrayHill,NewJerseyRLGandStanford,CaliforniaDEKMayOPANoteonNotationSOMEOFTHESYMBOLISMinthisbookhasnot(yet)becomestandardHereisalistofnotationsthatmightbeunfamiliartoreaderswhohavelearnedsimilarmaterialfromotherbooks,togetherwiththepagenumberswherethesenotationsareexplained:Notationlnxkxlogxxxxmody{xlxf(x)xx:f(x)xXIXiiniiRzJzH,H’X’nf'"'(z)XNamenaturallogarithm:log,xbinarylogarithm:log,xcommonlogarithm:log,xfloor:max{nn<x,integern}ceiling:min{nnx,integern}remainder:xylxyfractionalpart:xmodindefinitesummationPagedefinitesummationfallingfactorialpower:x!(xn)!risingfactorialpower:T(xn)(x)subfactorial:n!O!n!l!()“n!n!realpart:x,if=xiyimaginarypart:y,if=xiyharmonicnumber:lngeneralizedharmonicnumber:lxnxmthderivativeoffatzIfyoudon’tunderstandwhatthexdenotesatthebottomofthispage,tryaskingyourLatinprofessorinsteadofyourmathprofessornnln{ImnmnPrestressedconcretemathematicsiscon(i>>mCretemathematicsthat’sprecededby(‘h)babewilderinglistofnotationsK(al,,a,)F#Aiz”lf(z)lam=nlmnlImnlmlnANOTEONNOTATIONxiStirlingcyclenumber(the“firstkind”)Stirlingsubsetnumber(the“secondkind”)EuleriannumberSecondorderEuleriannumberradixnotationforz,“=,akbkcontinuantpolynomialhypergeometricfunctioncardinality:numberofelementsinthesetAcoefficientofzninf()closedinterval:theset{xx(}ifm=n,otherwise*ifmdividesn,otherwise*ifmexactlydividesn,otherwise*ifmisrelativelyprimeton,otherwise**Ingeneral,ifSisanystatementthatcanbetrueorfalse,thebracketednotationSstandsforifSistrue,otherwiseThroughoutthistext,weusesinglequotemarks(‘‘)todelimittextasitiswritten,doublequotemarks(““)foraphraseasitisspokenThus,Also‘nonstring’isthestringofletters‘string’issometimescalleda“s

类似资料

编辑推荐

摩西十诫(中英文).pdf

红楼梦诗词曲赋鉴赏_蔡义江.pdf

36【东方编译所译丛】植物的欲望:植.pdf

宠物狗训练秘籍.pdf

本雅明:历史哲学论纲.doc

职业精品

精彩专题

上传我的资料

精选资料

热门资料排行换一换

  • [黄帝内经.素问2.汉英对照].…

  • 巴鲁克自传.pdf

  • 有限元法基本原理和数值方法_清华…

  • 唐代_道僧格_研究.pdf

  • 怪诞心理学.pdf

  • [吕氏春秋1.汉英对照].翟江月…

  • 朱棣:一个人的战斗.pdf

  • 文人发牢骚.pdf

  • 宋朝官民的为商之道.pdf

  • 资料评价:

    / 640
    所需积分:1 立即下载

    意见
    反馈

    返回
    顶部