UChicago Notes - Discrete Mathematics

《UChicago Notes - Discrete Mathematics》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DiscreteMathematicsLectureNotesIncompletePreliminaryVersionInstructor:LaszloBabaiLastrevision:June22,2003Lastupdate:October24,2003Copyrightc2003byLaszloBabaiAllrightsreserved.Contents1Logic11.1Quantiernotation..................................11.2Problems...................................

2、....12AsymptoticNotation52.1Limitofsequence...................................62.2AsymptoticEqualityandInequality........................62.3Little-ohnotation...................................92.4Big-Oh,Omega,Thetanotation(O,,).....................102.5PrimeNumbers............................

3、........112.6Partitions.......................................122.7Problems.......................................133ConvexFunctionsandJensen'sInequality154BasicNumberTheory194.1IntroductoryProblems:g.c.d.,congruences,multiplicativeinverse,ChineseRe-mainderTheorem,Fermat'sLittleTheorem.........

4、...........194.2Gcd,congruences...................................254.3ArithmeticFunctions.................................274.4PrimeNumbers....................................314.5QuadraticResidues..................................344.6Latticesanddiophantineapproximation......................3

5、5iiiivCONTENTS5Counting375.1Binomialcoecients.................................375.2Recurrences,generatingfunctions..........................406GraphsandDigraphs436.1GraphTheoryTerminology.............................436.2DigraphTerminology.................................567FiniteProbabilitySp

6、aces637.1FiniteProbabilitySpacesandEvents........................637.2RandomVariablesandExpectedValue.......................687.3StandarddeviationandChebyshev'sInequality..................707.4Independenceofrandomvariables.........................717.5Cherno'sBound.............................

7、......747.6Problems.......................................778FiniteMarkovChains798.2Problems.......................................89Lastupdate:October24,2003ListofFigures3.1Denitionofconvexity................................166.