|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Kept R. — Fundamentals of the Average Case Analysis of Particular Algorithms |
|
|
|
| Предметный указатель |
(d,e,u)-random walk 60—72
(d,e,u)-random walk , (1,0,1)-random walk 64 69 71 83 87 101 107 115 121 134
(d,e,u)-random walk , (1,0,2)-random walk 87
(d,e,u)-random walk , (1,1,1)-random walk 63 68 70 77
(d,e,u)-random walk , (2,0,1)-random walk 87
(d,e,u)-random walk , (2,0,2)-random walk 86
(d,e,u)-random walk , (d,0,u)-random walk 71 77 97
(K,i)-tree 167 169
Acyclic graph 12
Adjacent vertices 12
Alternating permutation 48 91
Ancestor of a node 81
Approximant of a continued fraction 74 107 108 110 111
Balanced 2, 3-tree 100
Batcher, Kenneth Edward 183
Bell number 121 213
Bell polynomial 26 214
Bernoulli number 30 49 137 143 212 213
Bernoulli polynomial 30 212 215
Binary reflected code 188 see
Binomial coefficient 209 A
Bounded random walk 50 75 86—91 121
Brother of a node 81
Canonical cycle notation of a permutation 28
Catalan number 48 76 77 92 93 99 103 109 121 126 182
Cauchy's formula 62 63 110 208
Cauchy's residue theorem 141
Characteristic equation 60 207
Characteristic power series 55 205
Chebyshev inequality 4 205
Chebyshev polynomial of the second kind 61 76 107 115—118 125 216
Chomsky-normal form 111
Closed history 86—91 114 115 118
Closed path 12
Closed random walk 72—80 83 86—91 107 114 115 134
Code 130
Comparator module 183 190
Complete tree 81 152 201
Configuration 132 161
Connected digraph 14
Connected graph 12
Content of a file 86
Context-free grammar 55—57 111—113 205
Context-free grammar, linear 114 127 128 205
Context-free grammar, proper 205 A
Continued fraction 74 79 107 108 110 115
Continued fraction, terminating 74
Cumulative distribution function 4 7 148 149 170 204
Cycle in a digraph 14
Cycle indicator 31—34 46
Cycle notation of a permutation 27
Cycle of a permutation 28 47 96
Darboux-method 96
Data-type 84—92 114—120 128
de Bruijn, Nicolaas Govert 137
Degree path length 125
Density of a language 128
Deque 86 115 116 118 119
Deque, input-restricted 87 128 131 158—160
Deque, output-restricted 87 128
Derangement 34 46 47 91
Derivable word 56 205
Derivation tree 102 111 127
Descendant of a node 81
DICTIONARY 90 115 117 118 121 129
Digraph (directed graph) 13
Digraph (directed graph), connected 14
Digraph (directed graph), rooted 14
Digraph (directed graph), simple 13
Digraph (directed graph), strongly connected 14
Dirichlet convolution 141 207
Dirichlet series 141 146 155 193 207
Double fall of a permutation 48
Double rise of a permutation 48
Dycklanguage 70 173—183 201 203
Empty word 205 A
Euler number 49 95 120 212
Euler polynomial 214 A
Euler's constant 23 25 26 29 30 143 144 156 158 199—201 219
Euler's summation formula 199 208
Eulerian number 35 37 39 41 47 210—212
Eulerian polynomial 4 35 36 214
Evaluation of a tree 132 133 150 152
Evaluation of an expression 132
Exchange 183 185 186 188—192 198 200
Expected value 3 7 29 30 37 41 42 45 105 110 136 144 155 175 178 179 182 191—200 204
Expression 130—132
Extended binary tree 81 125
External path length 124
Fall of a permutation 34
Fall of a sequence 47
Father of a node 81
Feasible history 86—91
Fibonacci number 128
Final node 13
Formal power series 32 55 205
Fourier series 9 196 198 200 202
Fundamental matrix 16
Gamma-function 96 141—143 156—158 180 200—202 219
Gamma-function method 137 146 155 193 194 202 203
Generalized harmonic number 25 29 30 211
Generalized Laguerre polynomial 47 217
Generated language 205 A
Generating function 206 A
Generating function, exponential 92—100 206
Generating function, ordinary 32 92—100 206
Generating function, probability 23 204
Generating function, structure 113
Graph 12
Graph notation of a permutation 26
Graph, acyclic 12
Graph, connected 12
Graph, directed 13
Graph, simple 12
Harmonic number 211 A
Height of a random walk 50 107
Height of a tree 81 101 106 107 125 144 203
Height of a tree of order r 81 83 125
Hermite polynomial 115 117 118 216
history 86—91 114—116 118 128
History, closed 86—91 114 115 118
History, feasible 86—91
Hurwitz zeta function 194 197 198 220
Identity permutation 26
In-degree of a node 13
Increasing subsequence of a permutation 47
initial node 13
Input-restricted deque 87 128 131 158—160
Instruction 131
Interior node 81
Intermediate variables 131—134
Internal path length 124
Inversion of a permutation 42 122
Inversion table 43
Involution 49 91
k-permutation 47
K-permutation, 2-permutation 96
Key 86
l'Hospital's rule 61
Labelled tree 82 98 100 111 123 151
Lagrange — Buermann formula 67 104
Laguerre polynomial 47 78 79 115—118 217
| Laurent series 143 207
Leaf of a tree 81
Left-to-right maxima of a permutation 28
Legendre polynomial 122 125 217
Length of a cycle 29 47 96
Length of a random walk 50
Length of a run 34 122
Level of a node 81 83
Level of a segment 50
Level-order of nodes 82
Linear context-free grammar 114 127 128 205
Linear list 88 115—118 120 129
Linear notation of a permutation 27
Linear recurrence 56 60 207
Lipschitz condition 199
Major diagonal 188 202
Matrix notation of a permutation 27
Maximal deviation of a random walk 50 69 70 83 86—91 121
Maximal span of a random walk 50
Maximum size of a stack 83 111 127 149 178
Mean 3 7 29 30 37 41 42 45 105 110 136 144 155 175 178 179 182 191—200 204 see
Meixner polynomial 115 116 118 218
Mellin transform 141 146 155
Moment about the origin 3 7 24—26 29 30 35—37 40 45 135 136 144 146 154 155 204
Monotonously labelled tree 98 126
Motzkin number 77 123
Multiset 12 51
Murphy's formula 122 125 217
Negative peak of a permutation 48
Network for sorting 183
Non-negative random walk 50 72—80 86—91 107 114 115 128 134
Nonterminal 111 205
Odd-even merge 183—186 190—192 198 200
Ordered tree 81—85 98—111 123 157 159
Oriented cycle 14
Oriented path 13
Oscillation of a function 199
Out-degree of a node 13
Pair of brackets 173
Partial fraction expansion 61
Path 12
Pattern of a permutation 48
Permutation 26 91 122
Permutation group 26 31—34
Permutation matrix 27
Permutation, 2-ordered permutation 122 183 185 188 190 191 198 200
Permutation, 2-permutation 96
Permutation, alternating 48 91
Permutation, k-permutation 47
Plane tree 82
Poisson — Charlier polynomial 115 117 118 218
Positive peak of a permutation 48
Post-order of nodes 82 111 132 160
Pre-order of nodes 82
Prefix of the Dycklanguage 70
Priority queue 89 115 116 118 120 129
probability distribution 14
Probability generating function 23 204
Production system 56 111 205
PROGRAM 131
Program, k-program 131
Proper context-free grammar 205 A
Psi-function 143 219
Q-nomial coefficient 209 A
QUEUE 87 128
R-tree (R-tuply rooted tree) 81 125
Random algorithm 14
Random path 15
Random walk 50 122 154 see walk"
Random walk, bounded 50 75 86—91 121
Random walk, closed 72—80 83 86—91 107 114 115 134
Random walk, non-negative 50 83 86—91 107 114 115 128 134
Random walk, simple 50 121 122
Random walk, weighted 51 86—91 114—117 128
Reduction of a tree 131 148—150 158 159 202
register 130 132 134 152
Residue 95 156 157 207
Riemann zeta function 141—143 155—158 180 201—202 220
Rise of a permutation 34
Root of a tree 81
Rooted digraph 14
Run of a permutation 34 122
Secant number 49
Segment of a random walk 50
Simple digraph 13
Simple graph 12
Simple linear list 128
Simple oriented path 14
Simple path 12
Simple random algorithm 14—19
Simple random walk 50 121 122
Simply generated family of trees 122—124
Size of a history 86—91 115—118
Son of a node 81
STACK 86 115 118 119 131 132 148 149 168 169 174
Stack size 111
Standard deviation 204 A
Standard Gray code 188 192 194 202
Standard notation of a permutation 26
Stirling inversion 211 A
Stirling number of the first kind 23 29 210
Stirling number of the second kind 24 36 40 211
Stirling's formula 93 96 100 137 219
Strongly connected digraph 14
Structure generating function 113
Substitution scheme 55 102 106 205
Subtree 81
Succession of a permutation 47
Symbol table 90 115 117 118 120 129
Symmetric group 26 32—38 42—45 122
Syntax tree 130 132
Tangent number 49
Terminal 111 205
Terminating continued fraction 74
Theta-relation 149
TREE 81
Tree, (k,i)- 167 169
Tree, balanced 2 3 100
Tree, complete 81 152 201
Tree, derivation 111 127
Tree, extended binary 81 125
Tree, labelled 82 98 100 111 123 151
Tree, monotonously labelled 98 126
Tree, ordered 82—85 98—111 123 157 159
Tree, plane 82
Tree, r-tree 81 125
Tree, syntax 130 132
Tree, t-ary 81 98 106 123
Tree, unlabelled 82
Tree, unordered 81 100 123
Trinomial coefficient 63 68—71 209
Turing machine 2—9 201
Two-way-one-counter automaton 176—183
Type of a permutation 31
Type of a segment 50
Unambiguous scheme 55 102 106 205
Uniform set of random walks 52 73 128
Unlabelled tree 82
Unordered tree 81 100 123
Value of a variable 131
Variance 25 29 30 37 45 147 148 204
Weight of a set of random walks 52 86—91
Weighted random walk 51 86—91 114—117 128
|
|
|
| Реклама |
|
|
|
|
|
О проекте