关闭

关闭

封号提示

内容

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

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

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

上传者: 至尊小寳 2013-10-11 评分1 评论0 下载29 收藏0 阅读量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

类似资料

编辑推荐

工程质量安全管理制度.doc

WORD2007教程1849220819.doc

数字描红&#40;左半格&#41;.doc

《金匮要略》试题及答案.doc

平面设计PS-CS4教案.doc

职业精品

精彩专题

房地产评估师考试指南

房地产估价师考试备战已经开始,为了方便考生进行全面备考,小编特别对房估考生如何进行报考、备考提出了建议,并对重点预习知识、考试大纲与笔记画重点。房地产估价师职业前景可是大好,做好考试准备,事半功倍。

用户评论

0/200
    暂无评论
上传我的资料

精选资料

热门资料排行换一换

  • 李俨钱宝琮科学史全集 第06卷.…

  • 李俨钱宝琮科学史全集 第05卷.…

  • 李俨钱宝琮科学史全集 第03卷.…

  • 李俨钱宝琮科学史全集 第02卷.…

  • 伪满秘档:关于东北抗日联军的资料…

  • 国民党1937.pdf

  • 装配钳工.pdf

  • 奉系军事.pdf

  • 徐恩曾:回忆国民党中统 .pdf

  • 资料评价:

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

    意见
    反馈

    返回
    顶部