Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
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
ßçûê:
Ðóáðèêà: Computer science /Àëãîðèòìû /
Ñòàòóñ ïðåäìåòíîãî óêàçàòåëÿ: Ãîòîâ óêàçàòåëü ñ íîìåðàìè ñòðàíèö
ed2k: ed2k stats
Ãîä èçäàíèÿ: 2000
Êîëè÷åñòâî ñòðàíèö: 396
Äîáàâëåíà â êàòàëîã: 19.11.2005
Îïåðàöèè: Ïîëîæèòü íà ïîëêó |
Ñêîïèðîâàòü ññûëêó äëÿ ôîðóìà | Ñêîïèðîâàòü ID
Ïðåäìåòíûé óêàçàòåëü
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
Ðåêëàìà