√лавна€    Ex Libris     ниги    ∆урналы    —татьи    —ерии     аталог    Wanted    «агрузка    ’удЋит    —правка    ѕоиск по индексам    ѕоиск    ‘орум   
blank
јвторизаци€

       
blank
ѕоиск по указател€м

blank
blank
blank
 расота
blank
Mitzenmacher M., Upfal E. Ч Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Mitzenmacher M., Upfal E. Ч Probability and Computing: Randomized Algorithms and Probabilistic Analysis



ќбсудите книгу на научном форуме



Ќашли опечатку?
¬ыделите ее мышкой и нажмите Ctrl+Enter


Ќазвание: 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.


язык: en

–убрика: ћатематика/

—татус предметного указател€: √отов указатель с номерами страниц

ed2k: ed2k stats

√од издани€: 2005

 оличество страниц: 368

ƒобавлена в каталог: 27.10.2010

ќперации: ѕоложить на полку | —копировать ссылку дл€ форума | —копировать ID
blank
ѕредметный указатель
$(\varepsilon,\delta)$-approximation      253 254
$\varepsilon$-uniform sample      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, $M/M/\infty$      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
1 2
blank
–еклама
blank
blank
HR
@Mail.ru
       © Ёлектронна€ библиотека попечительского совета мехмата ћ√”, 2004-2020
Ёлектронна€ библиотека мехмата ћ√” | Valid HTML 4.01! | Valid CSS! ќ проекте