Purdom R.W., Brown C.A. — The analysis of algorithms :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Purdom R.W., Brown C.A. — The analysis of algorithms

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: The analysis of algorithms

Авторы: Purdom R.W., Brown C.A.

Аннотация:

The purpose of this book is to teach the tequniques needed to analyze algorithms. Students should have a background in computer science up through data structures and in mathematics through calculus. The text is organized by analysis techniques and includes a systematic and largely self-contained treatment of the mathematics needed for elementary and intermediate analysis, as well as brief guides to the sources for more advanced techniques. Each is illustrated by application to the analysis of a realistic algorithm. Explicit guidance for the use of various methods is provided. Exercises provide the student with the opportunity to apply the techniques in developing original algorithm analysis.

Язык:

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1985

Количество страниц: 540

Добавлена в каталог: 20.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Abel, Niels Henrik, power series theorem      159
Abel, Niels Henrik, summation      101
Abramowitz, Milton      136 145 339 400 454 463 496
Absolute value      38 123
Accepting state of a Turing machine      423—424
Ackermann, Wilhelm, function      392
Addition      see “Matrix addition”
Addition, Algorithm      12
Addition, integer      12
Addition, lower-bound time      411
Addition, modular arithmetic      403—408
Adjacency matrix      417
Adjacent vertices in a graph      363
Aho, Alfred V.      xv 4 16 20 25 37 40 75 83 157 212 249 282 306 313 323 388 393 395 400 403 408 421 479 495 498 499
Algebra programs      112
Alternating sum      65 195—196 146—147
Alternative hypothesis      445
Amortized cost      375
Anagrams      93—95
Analytic function      488
Ancestor, common      55
Andrews, George E.      145 499
Apostol, Tom M.      66 88 89 116 125 151 158 185 196 451 487 488 494 496
Approximately equal to      37 148
Approximation algorithm      438
Approximation, binomial theorem      160
Approximation, exponential function      160
Approximation, factorial      193—195
Approximation, harmonic number      189—190
Approximation, logarithm function      160
Approximation, power series      158—160
Approximation, range of      155—156
Approximation, Stirling's formula      193—195
Arc (edge) of a graph      362
Arithmetic, Addition      12
Arithmetic, Euclidean      16
Arithmetic, Faster Multiplication      213
Arithmetic, Integer Value      9 10
Arithmetic, Multiplication      22
Arithmetic, Strassen's Algorithm      218
Artin, Emil      98 496
Associative items      308
Associative law      60 65
Asymptotic expansion      148—199 328
Asymptotic expansion, $\Omega$ notation      155
Asymptotic expansion, $\Theta$ notation      155
Asymptotic expansion, definition      165
Asymptotic expansion, measurements      198—199 481—486
Asymptotic expansion, O notation      37—38 155
Asymptotic expansion, techniques      160—164
Atallah, Mikhail J.      414 499
Average      32 268 451 453 456
Average, time      see “Specific algorithm”
Baase, Sara      xv 20 24 25 34 37 46 54 75 83 157 216 388 400 412 495
Backtrack Estimation Algorithm      465—466
Backtracking      168—171
Backtracking, Algorithm      171
Backtracking, average time      171—180
Backtracking, estimating running time      465—477
Backwards analysis      230
Barnes, Bruce H.      303 502
Base case for proof by induction      45
Base of a number system      9
Basic event      28
Basic hypergeometric function      145
Bellman, R.      328 496
Bender, Carl M.      204 235 239 254 256 259 261 268 301 328 496
Bender, Edward A.      167 182 196 328 499
Bentley, Jon L.      95 152 212 439 499
Benton, Edward R.      301
Bernoulli, Daniel, polynomials      186
Bernoulli, James, numbers      186
Bessel, Friedrich Wilhelm, function      256
Big O      see “Asymptotics”
Bilateral function      140—141
Bin packing      438—439
Bin packing, Decreasing First Fit Algorithm      439
Bin packing, First Fit Algorithm      438
Binary branching      412
Binary computer      402
Binary Merge, Algorithm      49
Binary Merge, worst-case time      50—55
Binary search tree      279—280
Binary Search Tree Algorithm      354
Binary Search Tree Algorithm, average time      354—355
Binary Search with Equality Checking Algorithm      209—210
Binary Search, Algorithm      19 49
Binary Search, average time      311—313 315—319
Binary Search, worst-case time      19—20 200
Binary tree      279—280 315 354—355
Binary tree, balanced      306
Binary tree, number with height n      304—305
Binary tree, number with n nodes      306—308
Binary tree, threaded      284
Binomial coefficient      99
Binomial coefficient, addition formula      103
Binomial coefficient, factoring      102
Binomial coefficient, negating top index      104
Binomial coefficient, product      105
Binomial coefficient, summing on both indices      104
Binomial coefficient, summing on bottom index      100 105 461—465
Binomial coefficient, summing on top index      102
Binomial coefficient, summing products      127—130 139—146
Binomial coefficient, symmetry      102
Binomial theorem      100
Binomial tree      154
Birkhoff, Garrett      14 44 46 116 125 496
Block of code      364
Blum, Manuel      249 499
Boolean matrix multiplication      416—418
Booth, A.D.      282 499
Borosh, I.      408 499
Boundary values      137—138 200—201 203
Bounding functions      148—152 166—168 196—198 317
Bounding tails      188—195 461—465
Brainerd, Walter S.      392 440 442 495
Brandeis University      xv
Brinck, K.      291 500
Broder, Andrei Z.      101 500
Brown, Cynthia Ann      180 296 299 432 500 502
Brown, Donna J.      152 499
Brute-force approach      314—319
Buddy system      461
Bugrara, Khaled      xv
Burns, James      xv
Card deck      30
Carry propagation      403
Casoratian      257 265
Catalan, Eugene Charles, number      285 307—308
Cauchy, Augustin Louis      488
Cauchy, Augustin Louis, integral formula      490
Cauchy, Augustin Louis, residue theorem      492
Cauchy, Augustin Louis, theorem      490
Ceiling function      11
Central limit theorem      458—459
Characteristic equation      235—238 244 336—337 341
Characteristic function of a distribution      452—453
Characteristic function of a relation      41
Chebyshev, Pafnutii Lvovich, bound      462—465
checking      see “Mistake”
Chernoff, Herman, bound      462—465
Chomsky, Noam, normal form      327
Church, Alonzo, Church — Rosser property      55
Church, Alonzo, thesis      442
Clause      172
Clever approach      315—317
CLIQUE      434
Closed form      61
Cochran, William C      444 449 498
Cocke, J.      327 500

Cohen, Daniel I.A.      46 101 130 147 221 308 351 497
Cohen, Norman H.      360 500
Coin      28 444 464
Coin flipping      108—109 463
Colin, A. J. T.      282 499
Combination      99
Commutative law      60 65
Commutative operator      68
Complete predicate      55
Complex analysis      487—494
Complex conjugate      125
Complex number      123
Component of a graph      363
Conditional probability      30
Configuration of a Turning machine      424
Confluent relation      55
Congruent      12—15 42 400—409
Conjunction (logical and)      170 172
Conjunctive normal form      180
Connected graph      364
constant time      2
Continuous function      40
Contour integral      489 '
Conventions, power      100
Conventions, product      90
Conventions, running time      10
Conventions, Stirling numbers      132
Conventions, summation      66 114
Convergent      165
Convergent, absolute      65 159
Convolution      269 282 306 393—395
Convolution, cyclic      394
Cook, Stephen A.      334 430 432 500
Cook, Stephen A., Theorem      427
Coppersmith, D.      410 500
Correlation coefficient      34
Covariance      34
Cramer, Grabriel, rule      116
Cramer, Harald      458
Credit analysis      375 393
Cross, Anne Elizabeth      xv
Cubic sum      64 70
Cummings, Larry J.      101 499
Cumulative probability      81
Cycle of a graph      363
Cycle of a graph, directed      363
Cycle of a graph, fundamental set      370—374
Cycle of a graph, simple      363
Cycle of a permutation      93 254
Daniel, Cuthbert      480 497
Darboux, Jean Gaston      328
Data analysis      459—461
Davis, Martin      440 500
De Bruijn, N. G.      40 157 182 196 198 497
de Fermat, Pierre, prime      405
de L'Hopital, Guillaume Francois Antoine, rule      40
Decision table      301
Decision table, number of      301—306
Decreasing First Fit Algorithm      439
Decreasing function      149 184
Decreasing power      71 91 132
Degree of a vertex      362
Delete Algorithm      482
Delta function      103
Demers, A.      438 439 501
Density function      451 (see “Distribution function”)
Density function, normal      454
Density function, rectangular      459
Derangement      147 264
Derivative      150 488
Derivative, of a sum      89
Descendant, common      55
destructive testing      152—154
Determinant      116
Deterministic      425
Diagonal triangulation      308
Diagonalization      441
Diamond lemma      55
dictionary order      44
Die      28
Difference equation      204 (see “Recurrence equation”)
Differential equation      204
Differential equation, first order linear      255
Differential equation, general $n^{th}$ order      255
Differential equation, partial      346
Differential equation, steady-state solution      240—241 343—344
Directed multigraph      363
Discrete distribution      451
Discrete linear systems      335
Disjunction (logical or)      172
Distribute Algorithm (for Merge Sort)      229
Distribution function      444 451—453
Distribution function, nasty      459—400
Distributive law      114
diverge      65
Divide and conquer      238 243—250
Divide and conquer, algorithms      200 210 243
Divide and conquer, recurrence      210—212 243—250 309—314
Dot dot dot notation      58
Dot product      394
Dreyfus, S. E.      328 496
Dwork, Cynthia      334 500
Dynamic programming      320—321
Dynamic programming, blind bottom-up      321—324
Dynamic programming, blind top-down      321—323
Early, J.C      479 502
Edge Flow Graph Algorithm      368
Edge of a graph      361
Edge of a graph, negative      37
Edge of a graph, positive      371
Eight-queens      169—172
Elliott, Douglas F.      400 497
Ellipsis notation      58
Eppinger, Jeffrey L.      483 500
Epstein, George      xv
EQUIVALENCE      42
Equivalence class      42
Equivalence class, algorithm      385—388
Equivalence class, worst-case time      388—392
Equivalent programs      303
Erlang, A. K.      242
Error      see also “Mistake”
Error notation      155
Error term      302
Error term, rounding up      339
Error, numerical      304
Error, relative      193
Error, timing      5
Essential singularity      491
Estimator      456
Euclid      15
Euclidean algorithm      16 359
Euclidean Algorithm, worst-case time      20
Euler, Leonhard, $\phi$ function      147
Euler, Leonhard, constant      189—190
Euler, Leonhard, general summation formula      186—188
Euler, Leonhard, number      353
Euler, Leonhard,recurrence equation      261
Euler, Leonhard,summation formula      184—186
Event      444
Event, basic      28
Event, independent      29 456
Event, mutually exclusive      29
Expected value      see “Average”
EXPONENT      17 125
Exponent, laws of      17
Exponential generating function      292—293
Exponential sum      64 76
Exponential time      2—3 422
External path length      280

1 2 3 4

О проекте