课程介绍

 

　　Thiscourseteachesacalculusthatenablesprecisequantitativepredictionsoflargecombinatorialstructures.Inaddition,thiscoursecoversgeneratingfunctionsandrealasymptoticsandthenintroducesthesymbolicmethodinthecontextofapplicationsintheanalysisofalgorithmsandbasicstructuressuchaspermutations,trees,strings,words,andmappings.

 

　　课程目录

 

　　1Orientation

 

　　1.1BriefHistory

 

　　1.2AnalysisofAlgorithms

 

　　1.3Context

 

　　1.4AnalyticCombinatorics

 

　　2AnalysisofAlgorithms

 

　　2.1HistoryandMotivation

 

　　2.2ScientificApproach

 

　　2.3Example-Quicksort

 

　　2.4Resources

 

　　3Recurrences

 

　　3.1ComputingValues

 

　　3.2Telescoping

 

　　3.3TypesofRecurrences

 

　　3.4Mergesort

 

　　3.5MasterTheorem

 

　　4GeneratingFunctions

 

　　4.1CountingwithGeneratingFunctions

 

　　4.2ExponentialGeneratingFunctions

 

　　4.3CatalanNumbers

 

　　4.4SolvingRecurrences

 

　　4.5OrdinaryGeneratingFunctions

 

　　5Asymptotics

 

　　5.1StandardScale

 

　　5.2ManipulatingExpansions

 

　　5.3AsymptoticsofFiniteSums

 

　　5.4BivariateAsymptotics

 

　　6AnalyticCombinatorics

 

　　6.1TheSymbolicMethod

 

　　6.2LabelledObjects

 

　　6.3CoefficientAsymptotics

 

　　6.4Perspective

 

　　7Trees

 

　　7.1TreesandForests

 

　　7.2BinarySearchTrees

 

　　7.3PathLength

 

　　7.4OtherTypesofTrees

 

　　8Permutations

 

　　8.1Basics

 

　　8.2SetsofCycles

 

　　8.3Left-Right-Minima

 

　　8.4OtherParameters

 

　　8.5BGFsandDistributions

 

　　9StringsandTries

 

　　9.1BitstringswithRestrictions

 

　　9.2Languages

 

　　9.3Tries

 

　　9.4TrieParameters

 

　　9.5Exercises

 

　　10WordsandMappings

 

　　10.1Words

 

　　10.2BirthdayProblem

 

　　10.3CouponCollectorProblem

 

　　10.4HashTables

 

　　10.5Mappings

 

　　10.6Exercises