|
|
Авторизация |
|
|
Поиск по указателям |
|
|
|
|
|
|
|
|
|
|
Purdom R.W., Brown C.A. — The analysis of algorithms |
|
|
Предметный указатель |
External variance 476
F Algorithm (Fibonacci numbers) 224
Factorial 91 (see also “Gamma function”)
Factorial, Stirling's approximation 193—195
Fast Algorithm (multiplying series of matrices) 324
Fast Fourier Transform 393
Fast Pattern Match Algorithm 377
Faster Algorithm (multiplying series of matrices) 324
Faster Multiplication Algorithm 213
Feller, William 31 109 242 255 271 344 497
FFT Algorithm (fast Fourier transform) 399
Fibonacci numbers, F 224
Fibonacci, Leonardo, numbers 221 230
Fibonacci, Leonardo, properties 224—226
File comparison 323
Find (set) Algorithm 386
Find with Collapsing Algorithm 388
First Fit algorithm 438
Fisz, Marek 31 255 344 444 449 453 457 458 459 497
Floor function 11
Flow graph 364
Flow multigraph 366
Floyd, Robert W. 25 249 499 500
Foo, N.Y. 291 500
Ford, Lester 497
Formal power series 221
Fort, Tomlinson 268 497
Fourier transform, FFT 399
Fourier transform, RFFT 396
Fourier, Jean Baptiste Joseph, all integer 400—403
Fourier, Jean Baptiste Joseph, FFT Algorithm (fast Fourier transform) 399
Fourier, Jean Baptiste Joseph, RFFT Algorithm (recursive fast Fourier transform) 396
Fourier, Jean Baptiste Joseph, transform 393
Fractional part 11
Fraenkel, A.S. 408 499
Function notation for a recurrence 201
Function of a complex variable 488
Fundamental set of cycles 371
Gadget 435
Gale, David 487 497
game playing 447—449
Gamma function 96—98
Garey, Michael R. 430 432 434 437 438 439 495 501
Gauss, Carl Friedrich 26 140 478
Gauss, Carl Friedrich, generalization of the binomial theorem 356
Gaussian binomial coefficient 356
General solution of a recurrence equation 201 203 346
Generating function 130 219—234 306—308 328
Generating function, composition 270
Generating function, exponential 292—293
Generating function, indexed 345
Generating function, multidimensional 345
Generating function, probability 268—271
Generating function, product 269 282—283
Geometric series (exponential sums) 76
Goldberg, Allen 296 299 500
Goldberg, Jack L. 337 497
Goldberg, Karl 136
Gonnet, G.H. 32 495
Good, I.J. 400 500
Gosper, R. William, Jr. 145 205 500
Goulden, Ian P. 221 497
Graham, Susan L. 327 438 439 501
Grammar 325 479
Graph 361
Graph, directed 362
Graph, Edge Flow Graph 368
Graph, Recursive Transitive Closure 420
Graph, Shortest Path 24
Graph, spanning tree 364
Graph, undirected 362 385
Greatest common divisor 15
Green, George, theorem 488
Greene, Daniel H. 66 69 80 130 157 182 198 204 235 238 239 263 278 298 301 306 317 319 328 459 495
grouping data 448
GTE Laboratories xv
guessing 317
Guessing module 425
Hadley, G. 487 497
Haken, Dorothea 212 499
Halting problem 440
Hamiltonian circuit 434
Han, Moon Sung xv
Hansen, Wilfred J. 20 37 54 75 83 121 282 388 498
Harmonic number 167 189—190 192 282
Harrison, Michael A. 327 500
Hashing with Chaining Algorithm 118
Hashing, coalesced 121
Hashing, nonrepeating random 95
Hashing, nonrepeating random (average time) 95—96 109—112
Hashing, random 77
Hashing, random (average time) 77 191—192
Hashing, random (variance) 84
Hashing, with chaining (average time) 118 120—121
Hashing, with chaining (variance) 119
Haynsworth, Emilie 136
Heacox, Harry C 453 500
Heap 82
Heap, Algorithm 82
Heapsort Algorithm 82
Height of a tree 153
Hermite polynomials 293
Heuristic 437
Hibbard, Thomas N. 282 500
Hilbert, David 440
Hoare, C. A. R. 500 75
Hopcroft, John E. xv 4 16 20 25 37 40 75 83 157 212 249 282 313 323 388 393 395 400 403 408 410 421 495 498 500
Horner, William George, Algorithm 7
Horowitz, Ellis 4 16 20 25 37 40 54 75 83 121 157 180 388 495
Hu, T.C 180 323 487 495 497 498 501
Huet, Gerard 56 501
Hwang, F. K. 54 501
Hypergeometric function 139—146
Hypothesis testing 445—449
Ian Munro xv
Imaginary part 123
Implicit data structure 82
In-degree 362
Inclusion and exclusion 146—147 196
Increasing function 149 183
Increasing path 127
Increasing power 71 91 139
Independent events 29 456
Independent set of a graph 434
Independent set of equations 372
Index notation for a recurrence see “Sequence notation for a recurrence”
Indiana University xv
Induction, proof by 45 57 98 107 137 201 221 248 309 311 346
Infinite chain 43
Infinite descending chain 43
Infinite processor model 254
Infinite sum 65
Inorder Algorithm 385
Inorder Successor Algorithm 284
Inorder tree traversal 283
Insert (into a search tree) Algorithm 280
insertion sort algorithm 35
Insertion Sort Algorithm, average time 36—37
Instantaneous description of a Turing Machine 424
INTEGER 9
Integer addition see “Addition”
Integer matrix multiplication 416
Integer Value Algorithm 9 10
Integer vector 116
Integral, of a sum 89
Integral, Reimann 450
Integral, Stieltjes 450
Integration by parts 165
Intermediate predicate 170 173
Internal path length 280
| Internal variance 476
Invariant condition 7 19
Inverse 16
inversion 381
Involution 254
Is (a member of a set) Algorithm 386
Jackson, David M. 221 497
James, Glenn 497
Johnson, David S. 430 432 434 437 438 439 495 499 501
Johnson, Richard E. 88 151 497
Jolley, L.B.W. 63 497
Kaplansky, Irving 351
Karatsuba, A. 213 501
Karp, Richard M. 271 434 437 501
Karr, Michael 67 87 145 205 274 276 501
Kasami, T. 327 501
Kelly, T.L. 454 463
Key of a record 412
Kiokemeister, Fred L. 88 151 497
Kirchhoff, Gustav Robert, law 366 371
Kleinrock, Leonard 465 497
Knopp, Konrad 66 89 160 188 190 191 195 196 497
Knott, G.D. 483 501
Knuth, Donald E. xv 6 10 12—14 16 18 20 23 34 37 40 44 46 54 63 65 66 67 69 75 78 80 83 92 95 98 101 109 116 121 126 130 132 136 182 185 188 190 195 198 204 213 221 223 226 227 235 238 239 245 246 249 263 271 273 278 279 282 283 293 298 301 306 308 313 317 319 328 342 344 347 353 355 369 374 379 388 395 408 412 414 459 468 481 495 496 501 502
Kosaraju, S. Rao xv 414 499
Kronecker, Leopold, delta function 103
Lah, I. 353 50S
Lah, I., numbers 353
Lambda calculus 55
Landweber, Lawrence H. 392 440 442 495
Language 325 424
Laurent, Paul Matthieu Hermann, expansion 491
Lawler, Eugene 366 496
Least squares 477—481
Left child 279
Left shell node 285
Legendre, Adrien Marie, polynomial 256
Leighton, Tom 439 499
Levy, P. 458
Lewis, Harry R. 392 440 442 496
Lexicographic order 43
LIMIT 39
Lin, Shen 54 500
Lindeberg, J.W. 458
Linear algebra 408
linear combination 116 203
Linear equations 407
Linear programming 411 487
linear search algorithm 64
Linear sum 25 70
Linear time 2 8
Linearly independent solutions 257
Lisp programming language 360
Literal 172
Liu, C.L. 347 351 497
Locally confluent 55
Log convex 98
Logarithm 2 17—18
Logarithm, laws of 17
Logarithmic time 2
logical AND 170 172
Logical not 172
Logical or 172 331 417—418
Loop in a flow graph 363
Lower bound 395 409
Lower bound, adversary 413
Lower bound, information theoretic 411—412
Lower bound, input-output 411
Lower bound, tight 409
Lower bound, time see “Specific algorithm”
LR(1) 479
Lueker, George S. 204 209 439 501
Lynch, William C 355 502
Mac Lane, Saunders 14 44 46 116 125 496
MACSYMA symbolic algebra system 112
Magnitude of a complex number 123
Markov, Andrei Andrecvich, chain 343
Markov, Andrei Andrecvich, hound 461 465
Matching algorithm 319
Matiyasevich, Y. 440 501
Matrix 21 417
Matrix addition 21
Matrix addition, Algorithm 21 365
Matrix addition, triangular 27
Matrix multiplication 71 407 411 416
Matrix multiplication, Algorithm 23
Matrix multiplication, series of 320 324
Matrix multiplication, Strassen's algorithm 218 410
Matrix multiplication, triangular 71
Matrix, Matrix Addition 21 365
Matrix, Matrix Multiplication 23
Matrix, Series Matrix Multiplication 322
Matrix, Series Matrix Multiplication: Fast(i,y) 324
Matrix, Series Matrix Multiplication: Faster 324
Matrix, Series Matrix Multiplication: Slow 323
Matrix, Triangular Matrix Addition 27
Maximum Algorithm 136
Maximum Algorithm, average time 136—139 190 272
Maximum flow problem 422
Mc Geoch, Catherine Cole 439 499
McClellan, Michael T. 408 502
McCormick 487 498
Mean see “Average”
Measurements 196
Median 245
Median, worst-case time 246—250
Merge sort algorithm 227
Merge Sort Algorithm, Polyphase 231
Merge, Algorithm 228
Merge, lower-bound time 413—415
Mersenne, Marin, prime 405
Metzer, John R. 303 502
Milne-Thomson, Louis Melville 69 80 145 204 235 238 253 259 261 498
Minimum cut problem 422
Minimum extension of a relation 41 368
Minimum-cost search tree 328
Minton, Barry M. 145 502
Mistakes (avoiding) 26 63 112 138 163 166 198 201 203 220 221 290 316
Mod operation 11
Modular arithmetic 13—17 400—408
Modular arithmetic, radix conversion 406
MODULO 12 17
Monier, Louis 502
Montgomery, Douglas C. 480 498
Moore, Edward F. 366 502
Morris, J.H. (Jr.) 379 501
Morris, Robert 78 96 502
Move forward algorithms 379—385
Move to Front Algorithm 380
Multigraph 363
Multinomial coefficient 131
Multinomial theorem 131
Multiple sums 112
Multiplication 403 (see also “Matrix multiplication” “Strassen's “Faster
Multiplication, Algorithm 22 212
Multiplication, integer 212 395
Multiplication, modular arithmetic 403
Multiplication, polynomials 395
Multiplication, time analysis 312
Mutually exclusive 29
Nan, Dana S. 447 448 502
National Science Foundation xv
Natural logarithm 18
Negation (logical not) 172
nested loops 20
Newman, M. 135
Noble, Ben 116 408 498
Node (vertex) of a graph 362
Noether, Amalie Emmy 43
Noetherian 43
|
|
|
Реклама |
|
|
|