Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
Mahmoud H.M. — Sorting: a distribution theory
Îáñóäèòå êíèãó íà íàó÷íîì ôîðóìå Íàøëè îïå÷àòêó?
Íàçâàíèå: Sorting: a distribution theoryÀâòîð: Mahmoud H.M. Àííîòàöèÿ: A cutting-edge look at the emerging distributional theory of sorting
ßçûê: Ðóáðèêà: 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
Ðåêëàìà
|
|
Î ïðîåêòå