Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
Mitzenmacher M., Upfal E. — Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Îáñóäèòå êíèãó íà íàó÷íîì ôîðóìå Íàøëè îïå÷àòêó?
Íàçâàíèå: Probability and Computing: Randomized Algorithms and Probabilistic AnalysisÀâòîðû: Mitzenmacher M., Upfal E. Àííîòàöèÿ: Assuming only an elementary background in discrete mathematics, this textbook is an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It includes random sampling, expectations, Markov's and Chevyshev's inequalities, Chernoff bounds, balls and bins models, the probabilistic method, Markov chains, MCMC, martingales, entropy, and other topics. The book is designed to accompany a one- or two-semester course for graduate students in computer science and applied mathematics.
ßçûê: Ðóáðèêà: Ìàòåìàòèêà /Ñòàòóñ ïðåäìåòíîãî óêàçàòåëÿ: Ãîòîâ óêàçàòåëü ñ íîìåðàìè ñòðàíèö ed2k: ed2k stats Ãîä èçäàíèÿ: 2005Êîëè÷åñòâî ñòðàíèö: 368Äîáàâëåíà â êàòàëîã: 27.10.2010Îïåðàöèè: Ïîëîæèòü íà ïîëêó |
Ñêîïèðîâàòü ññûëêó äëÿ ôîðóìà | Ñêîïèðîâàòü ID
Ïðåäìåòíûé óêàçàòåëü
253 254 259 2-SAT 156 2-SAT, algorithm 156—159 3-SAT 159 3-SAT, algorithm 161 =P 255 Arithmetic coding 250 Azuma — Hoeffding inequality 303 Balanced allocation 336—345 Ballot Theorem 299 Balls and bins model 92—104 Balls and bins with feedback 199—201 Bayes' law 10 Bernoulli random variable 25 Bernoulli random variable, expectation 25 Bernoulli random variable, variance 48 Bernoulli trials 63 Binary erasure channel 251 Binary symmetric channel 238 Binomial coefficients, bounds 228—229 Binomial distribution 25 161 Binomial identity 26 Binomial random variable 25 29 Binomial random variable, expectation 26 Binomial random variable, variance 48 Binomial theorem 48 228 Birthday paradox 90—92 Bit-fixing routing algorithm 74 79 80 88 Bloom filter 109—111 329 Branching process 30 Bubblesort 41 58 94 Bucket sort 93—94 Buffon's needle 267 Burst errors 171 Butterfly, routing algorithm 80 Butterfly, wrapped 78 Chain hashing 106—107 Channel 238 Channel, binary symmetric 238 Chebyshev's inequality 48—49 56 134 Chebyshev's inequality, pairwise independent variables 318—329 Chernoff bound 63 61—83 Chernoff bound, geometric random variables 85 Chernoff bound, Poisson random variable 97 Chernoff bound, Poisson trials 63—67 85 Chernoff bound, sum of {-1, +1} random variables 69—71 Chernoff bound, weighted sum of Poisson trials 86 Compression 234—237 Compression function 235 Conditional density function 193 Conditional entropy 246 Conditional expectation 26 26—30 131—133 181 Conditional expectation inequality 136—138 Conditional expectation, random variable 28 Conditional probability 6 27 140 159 192 Confidence interval 68 319 Connectivity algorithm 176 Convex function 24 Count-min filter 329—332 Count-min filter, conservative update 332 Coupling 274 271—289 Coupon collector's problem 32—33 50 104—106 117 Coupon collector's problem, expectation 33 Coupon collector's problem, variance 52 Covariance 46 135 318 Cuts 316—327 Data stream model 329 Decoding function 238 Delay sequence 81 Density function 189 Density function, conditional 193 Dependency graph 139 Derandomization 126 Derandomization, conditional expectations 131—133 Derandomization, pairwise independence 316—327 Discrete probability space see “Probability space discrete” Discrete random variable see “”Randum variable discrete” Distribution function 189 Distribution function, joint distribution 191 DNF formula 255 DNF formula, approximating the number of satisfying assignment 255—259 Doob martingale 296 Dynamic resource allocation 345 Edge exposure martingale 296 Edge-disjoint paths 141 Embedded Markov chain 210 Encoding function 238 entropy 225 225—245 Entropy function, binary 226 Event 3 Event, set notation 3 Event, simple 3 Expectation 21 20—26 128—131 Expectation, Bernoulli random variable 25 Expectation, binomial random variable 26 Expectation, conditional see “Conditional expectation” Expectation, continuous random variable 190 Expectation, coupon collector's problem 33 Expectation, exponential random variable 197 Expectation, geometric random variable 31 Expectation, linearity of see “Linearity of expectations” Expectation, Poisson random variable 96 Expectation, product of random variables 46 Expectation, uniform random variable 194 Exponential distribution 196 205 Exponential distribution, density 197 Exponential distribution, distribution function 196 Exponential distribution, memoryless property 197 Exponential distribution, minimum 198 Exponential random variable 196 Exponential random variable, expectation 197 Exponential random variable, variance 197 Extracting random bits 230—234 Extraction function 230 248 Factorial bounds 93 102 151 Fully polynomial almost uniform sampler (FPAUS) 259 259—263 Fully polynomial randomized approximation scheme (FPRAS ) 254 257—263 267 Gambler's ruin 166—167 298 Geometric distribution 30 62 Geometric random variable 30 62 Geometric random variable, expectation 31 Geometric random variable, memoryless property 30 Geometric random variable, variance 50 girth 134 Hamiltonian cycle 113 Hamiltonian cycle, algorithm 115 Harmonic number 33 Hashing 106—112 344—345 Hashing, fingerprint 108 Hashing, perfect hashing 326—328 Hashing, universal hash functions 321—328 Heavy hitters 332 Heavy hitters, algorithm 328 Hypercube 73 Hypercube, routing algorithm 75 Inclusion-Exclusion Principle 4 16 Independence 6 21 191 Independence, k-wise 315 Independence, mutual 6 21 138 314 Independence, pairwise 315 Independent set 133—134 Independent set, approximate counting 259 Independent set, sampling 277—278 286—289 Indicator random variable 25 26 Jensen's inequality 23—24 k-SAT 142—146 156 Kraft inequality 249 Large cuts 129—130 Las Vegas algorithm 57 128 130 Law of total probability 9 Leader election 112 Linear insertion sort 41 94 Linearity of expectations 22 26 Little's result 216 Lovasz local lemma 138—148 Lovasz local lemma, explicit constructions 142 Lovasz local lemma, general case 146 148 Lovasz local lemma, symmetric version 139—141 Marginal distribution function 191 Markov chain 153 153—210 Markov chain Monte Carlo method 263—265 Markov chain, aperiodic 165 Markov chain, communicating states 164 Markov chain, coupling 274 271—289 Markov chain, directed graph representation 155 Markov chain, embedded 210 Markov chain, equilibrium distribution 167 Markov chain, ergodic 166 Markov chain, irreducible 164 Markov chain, Markov property 154 Markov chain, memoryless property 154 Markov chain, mixing time 274 Markov chain, null recurrent 165 Markov chain, path coupling 286—289 Markov chain, periodic 165 Markov chain, positive recurrent 165 Markov chain, rapidly mixing 274 Markov chain, recurrent 164 Markov chain, skeleton 210 Markov chain, state 153 Markov chain, stationary distribution 167 167—172 Markov chain, time-reversible 172 183 264 266 Markov chain, transient 164 Markov chain, transition matrix 154 Markov chain, transition probability 154 Markov chain, transition probability, n-step 154 Markov processes 210 Markov's inequality 44—45 Martingale 295 295—308 Martingale, Azuma — Hoeffding inequality 303 Martingale, edge exposure 296 Martingale, stopping theorem 29s Martingale, vertex exposure 297 Maximum Cut 131—133 Maximum SATISFIABILITY 130—131 Median algorithm 52—57 Memoryless property 30 197 Metropolis scheme 265 Min-cut algorithm 12—14 Minimum cut-set 12 Moment generating function 61 61—63 Moment generating function, Poisson distribution 97 Moments 45 Monte Carlo algorithm 57 128 335 Monte Carlo method 252—266 Negative binomial random variable 40 Order statistics 207 Order statistics, uniform random variables 208 packet routing 72—83 Packet routing, hypercube 75 Packet routing, wrapped butterfly 80 Pairwise independence 315 Pairwise independence, constructions 315—328 Pairwise independence, sampling 319—321 Parrondo's paradox 177 PASTA principle 215 Perfect hashing 326—328 Permutation 41 Poisson approximation 99—105 111 Poisson distribution 95 202 Poisson distribution, moment generating function 97 Poisson process 202 201—209 Poisson process, combining 205—207 Poisson process, interarrival distribution 204 Poisson process, splitting 205—207 Poisson random variable 63 95 Poisson random variable, Chernoff bound 97 Poisson random variable, expectation 96 Poisson random variable, sums 96 Poisson trial 63 Prefix code 234 249 Principle of Deferred Decisions 9 116 Priority queue 224 Probabilistic method 126—148 242 Probabilistic method, counting argument 126—128 Probabilistic method, expectation argument 128—131 Probabilistic method, Lovasz local lemma 138—148 Probabilistic method, sample and modify 133—134 Probabilistic method, second moment method 134—136 Probability function 3 Probability space 3 Probability space, discrete 3 Queues 173—174 212—228 Queues, 216—228 Queues, M/M/1 213—226 Queues, M/M/1/K 216 Queues, notation 212 Quicksort 34—38 Quicksort, pivot 34 Random graphs 112—123 296 Random graphs, threshold function 135 135—138 Random variable 20 20—26 Random variable, continuous 189 188—193 Random variable, discrete 20 Random walk 174 174—177 Random walk, cover time 176 Random walk, stationary distribution 175 Randomized routing 72—83 Randomized routing, hypercube 75 Randomized routing, wrapped butterfly 80 Reservoir sampling 40 S-t connectivity algorithm 176 Sample space 3 Sampling 5 Sampling, pairwise independence 319—321 Sampling, with replacement 5 Sampling, without replacement 5 Satisfiability 130 142—146 Second moment method 134—136 Set balancing 71 Set membership problem 108 Shannon's Theorem 237—245 Skeleton Markov chain 210 Standard deviation 45 Stationary distribution 179 210 Stationary distribution, continuous time Markov processes 210—222 Stirling's formula 162 246 Stochastic counting process 201 Stochastic process 153 Stopping time 297 297—300 Symmetry breaking 111—122 Uniform distribution 193 208 Uniform distribution, conditional probability 194 Uniform distribution, density function 194 Uniform distribution, distribution function 194 Uniform random variable 193 Uniform random variable, expectation 194 Uniform random variable, variance 194 Union bound 4 52 127 Universal hash functions 321 321—328 Variance 45 Variance, Bernoulli random variable 48 Variance, binomial random variable 48 Variance, continuous random variable 190 Variance, exponential random variable 197 Variance, geometric random variable 50 Variance, sum 46 Variance, sum of pairwise independent variables 318 Variance, uniform random variable 194
Ðåêëàìà
-approximation 
-uniform sample 
|
|
Î ïðîåêòå