Ãëàâíàÿ    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-2024
Ýëåêòðîííàÿ áèáëèîòåêà ìåõìàòà ÌÃÓ | Valid HTML 4.01! | Valid CSS! Î ïðîåêòå