Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Mahmoud H.M. — Evolution of random search trees
Mahmoud H.M. — Evolution of random search trees

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

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

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



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


Название: Evolution of random search trees

Автор: Mahmoud H.M.

Аннотация:

While several excellent books have been written on algorithms and their analysis, remarkably few have been dedicated to the probabilistic analysis of algorithms. This graduate text/professional reference fills that gap and brings together material that is scattered over tens of publications. Its unifying theme is the study of some classes of random search trees suitable for use as data structures with a behavior of random growth that is almost as good as balanced trees.


Язык: en

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1992

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

Добавлена в каталог: 20.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Absolute integrability      21 85 88
Additive random variable      110 120—121 134—136
Address      52
Adjacency matrix      52
Alphabet      185 208
Analytic continuation      16 225 275—276 282
Arora, S.      82
ASCII      59 208
Asymmetric trie      216 218 250 257
Asymptotic equivalence      8
Average      35
AVL tree      vii
B tree      vii
Baeza-Yates' data structure      106 109 134
Baeza-Yates, R.      vii 119
Barndorff-Nielsen, O.      69
Base function      18—19
Bead      65
Bell-shaped curve      238
Bender, E.      14
Bentley, J.      178 181
Bernoulli model      215
Bernoulli model, biased      216—218 239
Bernoulli model, generalized      216—219 244 247
Bernoulli model, unbiased      216—218 239
Bernoulli random variable      197
Bernoulli trial      32
beta function      34
Big oh      7
Biggins, J.      92
Billingsley, P.      86
Binary search      105—107 145 158—160
Birth      92—93 173
Birth, first      92—93 98
Birth, last      102
Borel — Cantelli lemma      51 290
Branching factor      53
Branching process      160 173
Branching random walk      92
Breiman, L.      91
Brink      67—68 70
Brink's transformation      70
Brown, G.      76 79 82
Bucket      214 240 244 247—248 256
Bucket trie      214 219 240 244 247—248 250 256
Buffer      105
C programming language      52
Calculus of finite differences      275
Cantelli, F.      see Borel — Cantelli lemma
Cartesian product      180
Cartography      177
Catalan number      12
Cauchy — Saalschuetz identity      23 29 243
Cauchy's classical integration formula      14 26 233—235 276
Cauchy's criterion      97
Central limit theorem      40—41
Central limit theorem, Lindeberg — Levy      40
Central limit theorem, Lyapunov's      41 77
Characteristic equation      112 150
Characteristic equation, roots of      110 112—113 122 136 138
Characteristic function      36 198 235 238
Characteristic function of the standard normal distribution      40—41 234 239
Characteristic polynomial      110
Chebychev's inequality      47—48 272
Chernoffs bounding technique      198—199
Chi-square $(\chi^2)$ distribution      34
Child      6
Circuit      3
Circuit, directed circuit      3
Coffman, Jr., E.      241 260
Collating sequence      59 208
Compact domain      220 229
Complement of a graph      4
Complete binary tree      91 158 160—161 205 256 280 290
Complete m-ary tree      143 166 171—172 176 205 245 248 256
Component      3
composite key      177
Computational biochemistry      214
Conditional expectation      36
Conditional probability      30
Connected component      3
Connected graph      3
Continuous distribution      33
Continuous random variable      33
Convergence      42
Convergence in $L^2$      90
Convergence in distribution      39
Convergence in law      39
Convergence in probability      42
Convergence in quadratic mean      90
Convergence, almost-sure      42
Convergence, probabilistic      42
Convergence, strong      43
Convergence, weak      42
Convolution      40 95 198
Correlation      160
Correlation coefficient      38
Covariance      38
Cover      220
Cramer's rule      121
Crump — Mode birth process      93
Culberson, J.      vii
Cut      192
Cut, k-dimensional      192
Cylinder      105
Cylinder, finite dimensional      90
Darboux's method      16 115 123—124 137 141
De La Briandais, R.      208
De-Poissonization      217 247
Degree      1
density      33
Density, beta      34
Density, chi-square $(\chi^2)$      34
Density, exponential      34
Density, gamma      34
Density, normal      34
Density, uniform      33
Dent, W.      82
Dependent events      31
Devroye's tree of random variables      161 164 204
Devroye, L.      92—93 99 102 115—116 160—161 167 171 175—176 186 190 194 205 216 247—248 256
Digital search      207
Digraph      2
Directed circuit      3
Directed graph      2
Directed tree      6
Dirichlet condition      20
Dirichlet generating function      17
Discrete probability distribution      31—33
Discrete probability distribution, Bernoulli      32
Discrete probability distribution, binomial      32
Discrete probability distribution, discrete uniform      31
Discrete probability distribution, geometric      32
Discrete probability distribution, hypergeometric      32
Discrete probability distribution, multinomial      38
Discrete probability distribution, negative binomial      32
Discrete probability distribution, Poisson      33
Discrete random variable      31
Disk      52 105 108
Distribution function      33
Distribution function, joint      37
DNA      214
Dominated convergence      238
Doubly exponential distribution      214 248 256.
Dynamic allocation      52
EDGE      1
Endmarker      208
Endpoint      1
Equivalence class      254
Equivalence relation      254
Euler's classical identities      264 268—269
Euler's constant      10
Euler's differential equation      112 136
Euler's representation of a complex number      21
Eve, J.      241 260
Event      30
Expectation      35
Expected value      34
Extended tree      54
External node      54
External path length      83 134
Extreme value distribution      245—246 248 256—257
Extreme value distribution, discretized version      246 248 256—257 274
Extreme value distribution, mixture of      274—275 283—284.
Fagin, R.      247
Fenner, T.      67
Fibonacci number      16
Finkel, R.      178
Fixed length key      213 260
Fixed point      85
Flajolet, P.      186 190 247—248 275 277 280—281 284
Forest      6
Forward difference      286
Fourier series      10 20
Fourier transform      18 36
Fourier's integral formula      21
Fredkin, E.      208
Fundamental strip      19 23—24 221—223 243—244
Gamma function      16
Generating function      11
Generating function, bivariate      111
Generating function, Dirichlet      17
Generating function, exponential      13
Generating function, kernel of      13
Generating function, moment      35
Generating function, ordinary      13
Generating function, probability      36
Generating function, semiexponential      14
Gonnet, G.      186 190
Graph      1
Graph, empty      1
Graph, order of      6
Graph, simple directed      2
Graph, simple undirected      1
Graphics      177
Guibas, L.      215
Hammersley, J.      92
hard disk      105
Harmonic number      10
Harmonic sum      18—19 243
Hashing      260
Heaviside's unit step function      143 198
Hennequin, P.      143
Hibbard, T.      75 110
Hypercube      39 180 182 192—193 205
Hyperplane      148 177
I'Hopital's rule      280
Incidence matrix      52
Indegree      2
Independent events      30
Inequality      47—48
Inequality, Chebychev's      47—48 272
Inequality, Kolmogorov's      48 91 96
Inequality, Markov's      47 49 102 168 291
Integral transform      18
Integral transform, kernel of      18
Internal node      54
Internal path length      82 134
Internal-node polynomial      270—271 282
Inversion formula      20
Inversion formula for the Fourier transform      22
Inversion formula for the Laplace transform      21
Isolated vertex      3
Jacquet, P.      215 219 221 223 227 234 239—241 245
Joint distribution function      37
Joint probability function      37
Jointly continuous random variables      37
Jonassen, A.      vii
k-d tree      177 181—182 184—186
Kemp, R.      63
Kernel function      13—14 17
Kesten, H.      92
Kingman's tree of random variables      93 164
Kingman, J.      92—93 98 163—166 172—173
Kirschenhofer, P.      244—245 284
Knott, G.      71
Knuth's recurrence      91
Knuth, D.      vii 55 83 119 160 219 240 243—244 246 269—270 277 283
Kolmogorov's inequality      48 91 96
Kolmogorov, A.      48 91 96
Konheim, A.      265 267 270 277
Labeled tree      13 53
Laforest, L.      186 190 194
Laplace transform      18 35
Large deviation inequalities      99—102
Large deviation inequalities for longest path length      99
Large deviation inequalities for shortest path length      102
Leaf      6
Leaf polynomial      259 264—265 267—268 270—271 282
Lebesgue measure      216
Levy, P.      40—41
Lexicographic ordering      59
Lexicographic relation      178—179 183
Limiting distribution      40
Limiting random variable      90—91
Lindeberg, J.      40—41
Linear search      29 160
Linked list      106
Little oh      8
Loizou, G.      67
Louchard, G.      80—81 282 284
Lyapunov, A.      41
Lynch, W.      72 74 116
m-ary, digital search      260
m-ary, search tree      103
m-ary, tree      53
m-ary, trie      208
Maclaurin series      28—29
Mahmoud, H.      82 114—116 119 128 133 135 147 160
Mainframe      52 133
Marginal, density      38
Marginal, probability function      38
Markov's inequality      47 49 102 168 291
Martingale      85—90
Martingale, convergence theorem      85—86 90
Mass function      31
McMillan, B.      269
Mean      35
Measuring string      215
Mellin transform      18
Memory      52
Memory, external      105 108—109
Memory, internal      103 105—107 109
Memoryless property      34 95
Meromorphic continuation (extension)      276—277
Mixture of distributions      272 274—275 283—284
Mode, C.      see Crump — Mode birth process
moment      35
Moment, factorial      35
Moment, generating function      35
Moment, second central      35
Multidimensional binary tree      181
Multidimensional data      177
Multinomial coefficient      39
Multivariate distribution      37
Multivariate distribution, bivariate normal      39
Multivariate distribution, multinomial      38
Multivariate distribution, multivariate normal      39
Multivariate distribution, uniform      39
Munro, I.      vii
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2018
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте