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

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

blank
blank
blank
 расота
blank
Alon N., Spenser J. Ч The probabilistic method
Alon N., Spenser J. Ч The probabilistic method

„итать книгу
бесплатно

—качать книгу с нашего сайта нельз€

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



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


Ќазвание: The probabilistic method

јвторы: Alon N., Spenser J.

јннотаци€:

One of the most powerful and popular tools used in combinatorics is the probabilistic method. Describes current algorithmic techniques, applying both the classical method and the modern tools it uses. Along with a detailed description of the techniques used in probabilistic arguments, it includes basic methods which utilize expectation and variance plus recent applications of martingales and correlation inequalities. Examines discrepancy and random graphs and covers such topics as theoretical computer science, computational geometry, derandomization of randomized algorithms and more. A study of various topics using successful probabilistic techniques is included along with an Open Problems Appendix by Paul Erd?s, the founder of the probabilistic method.


язык: en

–убрика: ћатематика/јлгебра/ омбинаторика/

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

ed2k: ed2k stats

»здание: Second edition

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

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

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

ќперации: ѕоложить на полку | —копировать ссылку дл€ форума | —копировать ID
blank
ѕредметный указатель
$\epsilon$-net      220 222Ч223
$\epsilon$-sample      222Ч223 225 253
Agarwal      226
Ahlswede      81Ч83 85 87
Aho      2
Ajtai      137 140 185 259 272Ч273
Akiyama      69
Algorithm      2Ч3 5Чvii 20 31Ч32 74Ч75 77 126 133Ч134 138 141Ч142 239Ч240 249Ч251
Algorithm, derandomization      vii
Algorithm, deterministic      75 257Ч258
Algorithm, greedy      20 30 34 36
Algorithm, Monte-Carlo      141
Algorithm, nonadaptive or on-line      239
Algorithm, primality testing      141
Algorithm, probabilistic or randomized      3 31 34 36 74Ч75 141 249 254
Algorithm, Rabin      141
Alon      5 9 14 36 60 70 78 99 101 104 135 137Ч138 140 142 192 219 226 254 256Ч257 272Ч273
Andreev      191 195
Antichain      197Ч198
Arboricity, di-linear      70
Arboricity, linear, conjecture      69Ч71
Arboricity, linear, of a graph      69Ч70
Automorphism      46 50 150 157
Azuma      95Ч96 98 100 103 108Ч109
Babai      254 256 278
Baik      110
Barany      211 217Ч218
Beck      7 30 32 74Ч75 201 209
Bernstein      113
Binomial distribution      35Ч36 72 113 166 188 220 232 265 270
Binomial random variable      72 113 124 188 220 224
Block design      54
Blum      185
Bollobas      8 52 97 155 160 278
Bonferroni      120
Boppana      117 192 201
Borel      125Ч128
Borel Ч Cantelli lemma      125Ч128
Bregman      22 60Ч61
Brun      119Ч120
BrunТs Sieve      119Ч120
Cantelli      125Ч128
Cauchy      135 139Ч140 148
Cayley      137Ч138
Cayley graph      137
Chain      198
Chain, Markov      162
Chain, rigid      176Ч177
Chazelle      226
Chebyschev      41Ч42 44Ч45 53 55Ч57 113 117 150 224
Chernoff      245 263
Chervonenkis      221Ч222
Chromatic number      38 94 97 112 130 160 245 271 276
Chung      140 142 242 244 275 278
Chvatal      259
Circuit      180 183Ч185 188Ч191 193Ч194 276
Circuit, binary      184Ч185 191Ч192 196
Circuit, boolean      196
Circuit, bounded depth      185 189 196
Circuit, complexity      vii 183Ч185 192
Circuit, monotone      191Ч193
Circuit, subcircuit      188
CLIQUE      184 191
Clique in a graph      47 51Ч52 92 97Ч98 110 133Ч134
Clique, function      184 191Ч192
Clique, number      51 100 158Ч160
Code, binary BCH      255
Coding scheme      232Ч233
Cohen      140
Coloring      1Ч3 6Ч7 15Ч17 25Ч27 65Ч66 69 71Ч72 75 77 99 130 194 199Ч204 208 239Ч240 249Ч250 254 256
Coloring hypergraph      75
Coloring, random      1Ч3 16Ч17 25Ч26 66Ч67 72 78
Compactness      66Ч67 69
Conjecture, Danzer and Grunbaum      216
Conjecture, Daykin and Erdos      9
Conjecture, Erdos      260 277
Conjecture, Erdos and Hanani      37 54 278
Conjecture, Erdos and Szekeres      278
Conjecture, Hadamard      208
Conjecture, Heilbronn      28
Conjecture, linear arboricity      69Ч71
Conjecture, Mine      22 60
Conjecture, Ramanujan      139
Conjecture, Rival and Sands      88
Conjecture, Simonovits and Sos      244
Conjecture, Szele      14 60
Convex body      29 106Ч107 215 218 222 229
Covariance      42 44
Covering      54
Covering number      53
Covering of $R^d$      68Ч69
Covering of $R^d$, decomposable      68
Covering of $R^d$, non-decomposable      68
Covering of a graph      69
Covering of a hypergraph      54Ч55 58
Crossing number      259Ч260
Cut      5Ч6
CYCLE      38
Danzer      216
Daykin      9 81Ч83 85 87
De la Vega      134
Deift      110
Density of $R^d$ packing      230
Density of a graph      47Ч49
Density of a set      277
Density of linear expanders      137
Dependency      121
Dependency, digraph      64Ч65 67 70 72Ч73 128
Dependency, graph      67 75
Dependency, superdependency digraph      128
Deviation, large      43 95 122Ч125 129 166 263 269
Deviation, large, inequality      95
Deviation, standard      41Ч42 72 113 129 162 201 220 264
Discrepancy      viiЧviii 199Ч200 208 225Ч226 228 239
Discrepancy of a set      200
Discrepancy, hereditary      204Ч205
Discrepancy, linear      204
Disjoint family      68 122
Disjoint family, maximal      122
Disjoint, cliques      97
Disjoint, pairs      9
Disjoint, pairwise      8 12 70 77
distribution      3 15 19 45 87 93 95Ч96 110 155Ч156 161Ч162
Distribution, binomial      35Ч36 72 113 166 188 220 232 265 270
Distribution, normal      19 42 44Ч55 102 209 267Ч269 271 276
Distribution, Poisson      35Ч36 115 123Ч124 127 162 166 269Ч270
Distribution, uniform      9 59 66 70 72Ч73 78 106 141 195 215 217Ч218 226
Dominating set      4Ч6 178
Doob      95
Double jump      161
Dudley      222
Edge connectivity      5Ч6 88 171
Ehrenfeucht      172
Ehrenfeucht game      172
Eichler      138Ч139
Eigenvalue      137
Eigenvalue of a graph      143
Eigenvalue of a matrix      138
Eigenvalue of a regular graph      137Ч140 142
Eigenvalue of a symmetric matrix      137Ч141 143
Eigenvector of a symmetric matrix      137Ч141
Elekes      260
entropy      201Ч203 231 240 242 245
Entropy of a random variable      240
Entropy, binary      240
Entropy, conditional      240
Entropy, function      viii 130 232 240
Erdos      1Ч3 6 8Ч9 12 16 28 30 37Ч38 41 44 49 52 54 58 64 66Ч68 73 126Ч127 130 133Ч134 155Ч156 161 216Ч217 250 260Ч261 275Ч281
Erdos-Ko-Rado theorem      12
Euclidean distance      106
Euclidean norm      17 21 59 207
Euclidean space      68 216 218 222 243
Euler      279
Exoo      69
Expander      137Ч138 149
Expander, explicit construction      137 142
Expander, linear      137
Expander, linear, density      137
Expectation      vii 16Ч17 21 33 41 45 58Ч59 72 85 93 96 102 113 146 168 188 224 264 272Ч273
Expectation, conditional      33 93Ч95 102 235 273
Expectation, linearity of      4Ч5 13 16 19 23 26Ч27 29 36 43 47 49 56 103Ч104 121 156 181 197 200 212 235Ч236 247 250 273
Explicit construction      133Ч134 136 138 235 257 273
Explicit construction, expander      142
Explicit construction, linear expander      137
Explicit construction, Ramsey graph      133Ч134
Explicit construction, tournament      4 136
Fagin      171
Fiala      209
Fishburn      88
Forest      69 245
Forest, linear      69
Forest, linear, directed      70Ч71 73
Forest, star      245
Fortuin      81 85
Frankl      9 54 134 136 142 219 242 244
Function, boolean      116 183Ч185 189 191Ч192 194Ч195 219
Furedi      217Ч218 54 216Ч217
Furst      185
Giant component      161 165Ч168 170
Ginibre      81 85
Glebskii      171
Goldreich      257
Graham      26 136 142 242 244 278
Graph, balanced      47Ч49 157
Graph, balanced, strictly      47Ч48 50 157Ч158 168
Graph, Cayley      138
Graph, Cayley, explicit construction      137
Graph, girth      38Ч39 71Ч72 276
Graph, girth, directed      71Ч72
Graph, independent set      27 37Ч38 70Ч71 76Ч77 91 125 130 133Ч134 161 180 272Ч273 276
Graph, planar      81 88 259
Graph, quasi-random      142Ч143 148
Graph, Ramsey, explicit construction      134
Graph, random      155
Greenberg      211
Group, abelian      8Ч9
Group, code      233
Group, cyclic      9
Group, factor      138
Group, matrices      137Ч138
Group, subgroup      233
Group, symmetric      95
Grunbaum      216
hadamard      207Ч208
Hajnal      278
Halberstam      126
Hall      71 208
Hamiltonian, graph      81 88
Hamiltonian, path      14 21 60
Hamming metric      103 106 202 232
Hanani      37 54 58 278
Harary      69
Hardy      25 42 45
Harper      104
Harris      81
Hastad      185 195 257
Haussler      221 223 225Ч226
Heilbronn      28
Hoffman      278
Holder      107
Hopcroft      2
Hypergraph      6 37 57 65 68 110
Hypergraph, 2-coloring      75
Hypergraph, covering      54Ч55 58
Hypergraph, induced      55 58
Hypergraph, property B      6 30 33 65 276
Hypergraph, regular      66
Hypergraph, subhypergraph      69
Hypergraph, uniform      6 10 20 30 34 37 54Ч55 58
Igusa      138
Inclusion-exclusion      119Ч120
Independent set in a Euclidean space      218
Independent set in a graph      27 37Ч38 70Ч71 76Ч77 91 125 130 133Ч134 161 180 272Ч273 276
Inequality      7 10 26 31 45 61 65 69 72Ч73 76 82Ч83 85Ч88 90 95 99 102 104 107 117Ч118 128 136Ч140 149Ч150 161 186 194Ч195 209 216 222 224Ч225 247 250Ч253 263Ч264 266Ч268 271
Inequality, Azuma      95Ч96 98 100 103 108Ч109
Inequality, Bonferroni      120
Inequality, Cauchy Ч Schwarz      135 139Ч140 148
Inequality, Chebyschev      41Ч42 44Ч45 53 55Ч57 113 117 224
Inequality, correlation      vii 81 86 88 118
Inequality, FKG      81 84Ч90 186
Inequality, Han      245
Inequality, Holder      107
Inequality, isoperimetric      95 104
Inequality, Janson      87 115Ч116 120Ч121 123 128 157Ч158 160
Inequality, Janson, extended      110 117 160
Inequality, Jensen      240Ч241 266
Inequality, Kraft      11
Inequality, Kraft-McMillan      11
Inequality, large deviation      95
Inequality, Markov      264 266
Inequality, martingale      vii 95 101 111
Inequality, Talagrand      105 108Ч109
Itai      254 256
Janson      87 110 115Ч117 120Ч121 123 128Ч129 157Ч158 160 168
Jensen      240Ч241 266
Joffe      254
Johansson      110
Join      83 89 166
Join-irreducible      83Ч84
Kac      44 276
Kahn      54
Karchmer      185
Karp      165 253
Kasteleyn      81 85
Katchalski      217Ч218
Katona      12
Khrapchenko      195
Kim      36 68 101 104 110Ч111 273
Kleitman      9 81 86Ч87 202 211 242
KleitmanТs lemma      86
Knuth      168
Ko      12
Kogan      171
Kolountzakis      126
Komlos      28 29 137 140 223 272Ч273
Konig      71
Krivelevich      99
Laplace      117 129
Laplace transform      117 129
Latin transversal      73
Lattice      29 83 89 230
Lattice, distributive      83Ч85 89
Lattice, sublattice      83
Liagonkii      171
Linear extensions      88
Linear extensions of partially ordered set      88 90
Linial      78
Lipschitz      96Ч101 103Ч104 108Ч110
Lipschitz condition      96Ч100 103Ч104
Lipschitz function      108
Log-supermodular      84Ч87 90
Lookahead strategy      176
Loomis      243
Lovasz      2 26Ч27 64 66 128 204
Lovasz local lemma      2 26Ч27 63Ч74 77Ч78 128
Lubotzky      138 142
Luczak      99 168
Mac Williams      255
Mani      68
Mani-Levitska      68
1 2
blank
–еклама
blank
blank
HR
@Mail.ru
       © Ёлектронна€ библиотека попечительского совета мехмата ћ√”, 2004-2018
Ёлектронна€ библиотека мехмата ћ√” | Valid HTML 4.01! | Valid CSS! ќ проекте