Главная    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-2019
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте