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

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

blank
blank
blank
 расота
blank
Mahmoud H.M. Ч Sorting: a distribution theory
Mahmoud H.M. Ч Sorting: a distribution theory

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

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

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



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


Ќазвание: Sorting: a distribution theory

јвтор: Mahmoud H.M.

јннотаци€:

A cutting-edge look at the emerging distributional theory of sorting

Research on distributions associated with sorting algorithms has grown dramatically over the last few decades, spawning many exact and limiting distributions of complexity measures for many sorting algorithms. Yet much of this information has been scattered in disparate and highly specialized sources throughout the literature. In Sorting: A Distribution Theory, leading authority Hosam Mahmoud compiles, consolidates, and clarifies the large volume of available research, providing a much-needed, comprehensive treatment of the entire emerging distributional theory of sorting.

Mahmoud carefully constructs a logical framework for the analysis of all standard sorting algorithms, focusing on the development of the probability distributions associated with the algorithms, as well as other issues in probability theory such as measures of concentration and rates of convergence. With an emphasis on narrative rather than technical explanations, this exceptionally well-written book makes new results easily accessible to a broad spectrum of readers, including computer professionals, scientists, mathematicians, and engineers. Sorting: A Distribution Theory:
* Contains introductory material on complete and partial sorting
* Explains insertion sort, quick sort, and merge sort, among other methods
* Offers verbal descriptions of the mechanics of the algorithms as well as the necessary code
* Illustrates the distribution theory of sorting using a broad array of both classical and modern techniques
* Features a variety of end-of-chapter exercises


язык: en

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

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

ed2k: ed2k stats

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

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

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

ќперации: ѕоложить на полку | —копировать ссылку дл€ форума | —копировать ID
blank
ѕредметный указатель
Adversary      26 27 36 126
Adversary argument      26Ч29 36
Aldous, D.      62
Alternating sum      75
Analytic continuation      62 99
Andrews, D.      3
Arratia, R.      62
ASCII      90
Asymptotic integration      55
Australian median-of-three algorithm      205
Barbour, A.      161
Base function      57
Base of number system      260; see УRadixФ
Bent, S.      30
Berry Ч Esseen bound      92 94
beta function      75 114
Bickel, P.      3
Binary search      83Ч84 95 101Ч102 227 230 287
Bit      260
Blum, M.      25 294 297
Brown, R.      107
Brownian bridge      109 103 106Ч112
Brownian bridge, absolute      112
Brownian bridge, standard      109
Brownian motion      109 106Ч108
Brownian motion, incremental      107Ч109
Bubble sort      129Ч131
Bubble sort, pass of      129
Bucket sorting      250
Bucket sorting, principle of      250
Bucketing      251
Bucketing, digital      259
Carlsson, S.      219
Carroll, L.      26
Cartesian product      7
Cauchy Ч Riemann conditions      55
Cauchy Ч Saalschuetz Gamma function      59
CauchyТs residue theorem      55 58 64 74Ч76 257
Chambers      166 177
Chao, C.      50
ChebyshevТs inequality      51 136 196
Chernoff, H.      196
Closing the box method      58
Coefficient transfer      279
Collating sequence      90
Comparable elements      7
Constant phase path      55
Continuity theorem      369
Contraction mapping      159
Convolution      121 167 188 239 268Ч269 301
Cramer, M.      242
Cumulants      159
Curran, J.      128
CYCLE      43 46
Cycle representation      46 47Ч48
Cycle representation, canonical      46 47Ч48
de Bruijn, N.      135 264
De-Poissonization      61
De-Poissonization, cone of      63
De-Poissonization, lemma      64 265
Delange, H.      81 247 249
Demuth, H.      25
Devroye, L.      18
Difference, backward      70
Difference, forward      70
Difference, martingale      51
Dirichlet generating function      70
Dirichlet transform      see УTransformФ
Disorder      284
Distributive selection      270Ч271 273
Distributive sort      251
Divide and conquer      5 220 148 304
DNA      260Ч261
Doberkat, E.      94
Dobosiewicz, W.      138 250 256 281
Dor, D.      25 30Ч31
Einstein, A.      107
Empirical distribution function      106 112Ч113
Esseen, X.      see УBerry Ч Esseen boundФ
EulerТs constant      61 264
EulerТs differential equation      202
External path length      13
Fibonacci search      86
Fixed point      159
Flajolet, P.      70 73 235 238 242 244 247 256 266 268 274 279Ч280
Floyd, R.      25 212 214 216Ч219 294 297
Foata, D.      43 47
Ford Ч Johnson algorithm      286Ч289 291Ч293
Fourier expansion      235 238 264
Fourier transform      see УTransformФ
Fractal      247
Frank, R.      124
Frazer, W.      207Ч209
Frobenius Number      124 126Ч128
Gamma function      60 266
Gamma function method      264 (see also УClosing the box methodФ)
Gastwirth, J.      3
Gaussian law      86Ч87 100Ч102 115 300
Generator sequence      124 125 127
Geometrization      61
Golin, M.      70 73 235 238 242 244 247
Goncharov, V.      43 48
Gonnet, G.      62Ч63 219 253Ч254
Grabner, P.      61
Grand average      167
Grand distribution      167Ч168
Grand variance      167
Gries, D.      83Ч84 87
Hadian, A.      291
Hadjicostas, P.      159
Hampel, F.      3
Harmonic number      42 368
Harmonic sum      57 59
Hash function      251 281 283
Hash table      250
Hashing      250 272 283 305
Hashing with linear probing      84
Hayward, R.      159
Heap      213 212
Heap construction      214Ч217
Heap sorting      217Ч218
Heap, conceptual      213
Hennequin, P.      159
Hibbard, T.      124
Hoare, C.      148 155 166Ч167 170 172 177 208 294
Holst, L.      62 161
Huber, P.      3
Hunt, D.      123
Hwang Ч Lin merging algorithm      221 228Ч230 293
Hwang, F.      see УHwang Ч Lin merging algorithmФ
Hwang, H.      81 298Ч300 302
Incerpi, J.      124
Incomparable elements      7
Indegree      11
Infinitely divisible distribution      175 167 176Ч177
Information theory      23
Insertion sort      83Ч84
Insertion sort, binary      95
Insertion sort, jump      101
Insertion sort, linear      88Ч94 103Ч105 119
Insertion sort, randomized      102
Internal path length      13
Interpolation select      271Ч274 282
Interpolation sort      253Ч255
inversion      44 45Ч46 91 127 132 284 299Ч301
Jacobian      110
Jacquet, P.      62 64 81 256 266 268 274 280
Janson, S.      161
John, J.      30
Johnson, B.      113
Johnson, S.      see УFord Ч Johnson algorithmФ
Kac, M.      61
Key      4
Killeen, T.      113
Kirschenhofer, P.      172 205
Kislitsyn, S.      29 33 35
Knuth, D.      23 118Ч119 123 125 133 135 157 170 209 264 289 292
KolmogorovТs canonical representation      177
Landau, L.      367
Laplace, P.      see УTransformФ
Law of Large Numbers      51 136 369
Law of Large Numbers, strong      106Ч107 369
Lazarus, R.      124
Lebesgue measure      159
Lebesgue Ч Stieltjes integration      46
Lent, J.      15 87 182 187 196
Lin, S.      see УHwang Ч Lin merging algorithmФ
LindebergТs central limit theorem      88
LindebergТs condition      43 45 88 370 371
LindebergТs conditional      51 372
Linear search      86
Linear search, backward      86
Linear search, forward      86
Louchard, G.      118 121
LyapunovТs condition      242Ч243 377
Mahmoud, H.      15 43 87 166 172Ч174 176 182 187 190 195Ч196 256 264 266 268 274 280 289 292
Manacher, G.      286 293
Mannila, H.      302
Maple      156
Martinez, C.      205 372
Martingale      49Ч52 372
Martingale central limit theorem      50Ч52 372
Martingale convergence theorem      158 372
Martingale difference      51 372
Martingale transform      50
Martingale, conditional variance in      51Ч52 372
Martingalization      49Ч50
Master Mind      27Ч29
Mathematica      156
McDiarmid, C.      159
McKellar, A.      207Ч209
Mellin Ч Perron formula      67
Mellin, H.      see УTransformФ
Melville, R.      83Ч84 87
Merge sort      220Ч222
Merge sort, bottom-up      243Ч245
Merge sort, top-down      220
Merging, binary      227Ч228 230 293
Merging, Hwang Ч Lin      228Ч230
Merging, linear      222Ч224
Meyer, R.      36
Modarres, R.      166 172Ч174 176 195Ч196
Moment generating function      53
Moment generating function, bivariate      54
Moment generating function, super      54 261Ч262
MQS tree      178
Munro, I.      62Ч63 219
Object-Oriented Programming      309
Odlyzko, A.      279
Oracle      27
Order      7
Order statistic      1
Order statistic, median      3
Order statistic, quantile      3
Order statistic, quartile      3
Order statistic, tertile      3
Order, partial      7
Order, total      7
Outdegree      11
Outlier      178
Panholzer, A.      190Ч191
Panny, W.      94 244 247Ч248
Papernov, A.      124 128
Partial order      7
Partial order, chain of      8
Partial order, induced      20
Partially ordered set      7
Pascal, programming language      86 90
PascalТs identity      240
Paterson, M.      25
Path of maximal sons      216 218Ч219
Permutation      2
Permutation, random      15 37 105 150Ч151 206 225 255 283 301
Perron, O.      see УMellin Ч Perron formulaФ
Pippenger, N.      25
Pivot      149
Plaxton, C.      124
Poblete, P.      62 256
PochhammerТs symbol      181
Poisson compound law      275
Poissonization      61 263
Poissonized average      264Ч265
Poissonized cost      263
Poonen, B.      124 127
POSET      7
Pratt, V.      25 125 127 294 297
Presortedness      284
Presortedness, measure of      284
Presorting      298
Probability integral transform      112 117
Probe sequence      85 95
Prodinger, H.      172 180 182 190Ч191 205 244 247Ч248
Pseudocode      6
Quantile scheme      206 211
Query      18
Quick sort tree      152 178
RADIX      260
Radix sort      259Ч261
Radix, binary      260
Radix, decimal      260
Radix, hexadecimal      260
Radix, octal      260
Rais, B.      62 81
Ramanujan, S.      135
random number generation      285
Random number generation, pseudo-      285
Random walk      107
Random walk, symmetric      107
Randomization      285
Randomized QUICK SORT      285
Rank      37
Rank, absolute      37
Rank, sequential      37
Rate of convergence      86 266
Rayleigh distribution      133
Record      41Ч43 46Ч48 141
Regnier, M.      62 157 256 266 268 274 280
Relation      7
Relation from      7
Relation on      7
Relation, antisymmetric      7
Relation, reflexive      7
Relation, transitive      7
Rice method      75 74Ч76
Rice, S.      74
Riemann, B.      see УCauchy Ч Riemann conditionsФ
Rivest, R.      25 294 297
Roesler, U.      159 164 168 194 204
Rogers, W.      3
Run      48 49Ч52 284
Saalschuetz, L.      see УCauchy Ч Saalschuetz Gamma functionФ
Saddle point      55 64 67 257 281
Saddle point method      257
Schaffer, R.      219
Schoenhage, A.      25
Schreier, J.      34Ч35
Search strategy      84
Sedgewick, R.      124 170 194 204 219 259
Selection      2
Selection, fixed      166
1 2
blank
–еклама
blank
blank
HR
@Mail.ru
       © Ёлектронна€ библиотека попечительского совета мехмата ћ√”, 2004-2018
Ёлектронна€ библиотека мехмата ћ√” | Valid HTML 4.01! | Valid CSS! ќ проекте