|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Knuth D.E. — The art of computer programming (vol. 3 Sorting and Searching) |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
Minimum-comparison algorithms, for searching 413—414
Minimum-comparison algorithms, for selection 207—219
Minimum-comparison algorithms, for sorting 180—197
Minimum-phase tape sorting 311
Minimum-space algorithms, for merging 168 702
Minimum-space algorithms, for rearranging 178 617
Minimum-space algorithms, for selection 218
Minimum-space algorithms, for sorting 79—80 389
Minimum-space algorithms, for stable sorting 390
Minimum-stage tape sorting 311
Minimum-time algorithms, for merging 241
Minimum-time algorithms, for sorting 235 241
Minker, Jack 578
MinuteSort 390
Mises, Richard, Edler von 513
Misspelled names 394—395
Mitchell, Oscar Howard 69 611
MIX computer: A hypothetical machine defined in Section 1.3 vi 75 382
MIXAL: The MIX assembly language 426
MIXT tape units 318—320 330—331 358
MIXTEC disks and drums 357—358 562—563
Miyakawa, Masahiro 727
Modified external path length 502—503 511
Moebius, August Ferdinand, function  32
Moffat, Alistair 389
Molodowitch, Mariko 742
Monotonic subsequences 66 68 614
Monotonicity property 439
Monting see “Schulte Monting”
Moore School of Electrical Engineering 386
Moore, Edward Forrest 255 263 453—454
Morgenthaler, John David 713
Morris, Robert 548 738 741
Morrison, Donald Ross 498
Morse, Samuel Finley Breese, code 623
Mortenson, John Albert 684
Moser, Leo 64
Most-significant-digit-first radix sort 175—179
Motzkin, Theodor Samuel 704
Move-to-front heuristic 402—403 405—406 646
MSD: Most significant digit 175
Muir, Thomas 11
Mullin, James Kevin 573 583
Multi-attribute retrieval 395 see
Multidimensional binary search trees see “k-d trees”
Multidimensional tries see “k-d tries”
Multihead bubble sort 244—245
Multikey quicksort 389 633 728
Multilist system 561 562 578
Multinomial coefficients 23 30 32 457 735
Multiple list insertion sort 99—102 104—105 196 380 382 520
Multiple-precision constants 748—750
Multiples of an irrational number mod 1 xiv 517—518 550
Multiprecision comparison 6 136 169
Multiprocessing 267 390
Multireel files 337 342 348 356
Multiset, ordering 311
Multiset, permutations 22—35 42—44 46 66
Multiset, sum and union 597
Multiset: Analogous to a set, but elements may appear more than once 22 158 211 217 241 298 648 670 744
Multivalued logic 672
Multiway trees 453 481—491 707 see
Multiword keys 136 168
Munro, James Ian 218 435 478 533 583 655 708 734 741 742
Muntz, Richard 482 490
Muroga, Saburo 729
MUSIC 23—24
Musser, David Rea 122
Myers, Eugene Wimberly, Jr. 583
Nagler, Harry 82 347 646 648
Nakayama, Tadasi 69 612
Naor, Simeon 708
Narasimhan, Balasubramanian 707
Natural correspondence between forests and binary trees 706
Natural merge sort 160—162 167
Natural selection 259—261 263—266
nearest neighbors 563 566
Needle 1 569 572 573—574
Negative links 164 175
Neighbors of a point 563 566
Neimat, Marie-Anne Kamal 549
Nelson, Raymond John 225 226 244 245
Netto, Otto Erwin Johannes Eugen 286 592
Networks of comparators, for merging 223—226 230—232 237 239
Networks of comparators, for permutations 243—244
Networks of comparators, for selection 232—234 238
Networks of comparators, for sorting 219—247
Networks of comparators, primitive 240 668
Networks of comparators, standard 234 237—238 240 244
Networks of comparators, with minimum delay 228—229 241
Networks of workstations 267 390
Neumann, John von (Margittai Neumann Janos) 8 159 385
Newcomb, Simon 42 46
Newell, Allen 729
Newman, Donald Joseph 505
Nielsen, Jakob 511—512
Nievergelt, Jiirg 476 480 549 564
Nijenhuis, Albert 70
Nikitin, Andrei Ivanovich 351
Nitty-gritty 317—343 357—379
Nodine, Mark Howard 698
Non-messing-up theorem 90 238 669
Nondeterministic adversary 219
Norlund, Niels Erik 638
Normal deviate 69
Normal distribution, approximately 45 650
Norwegian language 520
Noshita, Kohei 213 218
Notations, index to 752—756
Novelli, Jean-Christophe 614
NOW-Sort 390
NP-complete problems 242
NSort 390
Null permutation 25 36
Number-crunching computers 175 381 389—390
Numerical instability 41
Nyberg, Christopher 390
O'Connor, Daniel J. 225
O'Neil, Patrick Eugene 489
O'Rourke, Joseph 566
Oberhettinger, Fritz 131
Oblivious algorithms 219—220
Octrees 565
Odd permutations 19 196
Odd-even merge 223—226 228 230 243 244
Odd-even transposition sort 240
Odell, Margaret K. 394
Oderfeld, Jan 518
Odlyzko, Andrew Michael 611 630 715 644
Oettinger, Anthony Gervin 491
Oldham, Jeffrey David vii
Olivie, Hendrik Johan 477
Olson, Charles A. 544
Omega network 227 236—237
One-sided height-balanced trees 480
One-tape sorting 353—356
Ones' complement notation 177
Online merge sorting 167
Open addressing 525—541 543—544 548 551—557
Open addressing, optimum 539—541 555—556
Operating systems 149 158 338
Optimization of loops 85 104—105 136 156 167 397—398 405 418 423 425 429 551 625
Optimization of tests 406
Optimum binary search trees 436—454 456—458 478
Optimum digital search trees 511
Optimum exchange sorting 196
Optimum linear arrangements 408
Optimum linear probing 532
Optimum linked trie 508
Optimum merge patterns 302—311 363—367 376—377
| Optimum open addressing 539—541 555—556
Optimum permutations 403—408
Optimum polyphase merge 274—279 286 337
Optimum searching 413 425 549
Optimum sorting 180—247
OR (bitwise or) 529
Order ideals 669
Order relations 4
Order statistics 6 44
Ordered hashing 531 741
Ordered partitions 286—287
Ordered table, searching an 398—399 409—426
Ordering of permutations 19 22 105 670
Organ-pipe order 407 452 704
Oriented trees 71 599
Orosz, Gabor 744
Orthogonal range queries 564 566
Oscillating radix sort 347
Oscillating sort 311—317 328—329 334 337 338 342 389
Overflow, arithmetic 6 519 585
Overflow, in B-trees 487—490
Overflow, in hash tables 522 525 526 529 542—543 547 551
Overmars, Markus (Mark) Hendrik 583
Own coding 339
P-way merging 166 252—254 321—324 339—343 360—373 379
Packing 721
Paging 158 378 481—482 541 547
Pagodas 152
Paige, Robert Allan 652
Painter, James Allan 256
Pairing heaps 152
Pak, Igor Markovich 70 614
Palermo, Frank Pantaleone 729
Pallo, Jean Marcel 718
Panny, Wolfgang Christian 629 630 648
Papernov, Abram Alexandrovich 91
Pappus Of Alexandria 593
Parallel processing 267 370 390 693
Parallel processing, merging 231 241
Parallel processing, searching 425
Parallel processing, sorting 113 222—223 228—229 235 390 671
Parberry, Ian 666
Pardo see “Trabb Pardo”
Pareto distribution 401 405 710
Pareto, Vilfredo 401
Parker, Ernest Tilden 8
Parkin, Thomas Randall 8
Parking problem 552 553 742
Parsimonious algorithms 391
Partial match retrieval 559—582
Partial ordering 31—32 68—69 183—184 187 216 217
Partial ordering, of permutations 19 22 105 670
Partition-exchange sort 114
Partitioning a file 113—115 123—124 128 136
Partitioning a file, into three blocks 137
Partitions of a set 653
Partitions of an integer 19—20 504 613 621 697 700
Partitions of an integer, ordered 286—287
Partitions of an integer, plane 69—70
Pasanen, Tomi Armas 649
Pass: Part of the execution of an algorithm, traversing all the data once 5 268 272
Patashnik, Oren 760
Patents vi 225 231 244 255 312 315—316 369 384—385 675 729
Paterson, Michael Stewart 152 215 230 594 655 689 736
Path length of a tree see “External path length” “Internal
Path length of a tree, minimum 192 195 361
Path length of a tree, weighted 196 337 361 438 451 458
Path length of a tree, weighted by degrees 363—367
Patricia 489 498—500 505—506 508 510—511 576 726
Patt, Yale Nance 508
Pattern matching in text 511 572 578
Patterson, David Andrew 390
Patterson, George William 386 422
Pentagonal numbers 15 19
Percentiles 136 207—219 472 see
Perfect balancing 480
Perfect distributions 268—272 276—277 286 288—289
Perfect hash functions 513 549
Perfect shuffles 237
Perfect sorters 245
Periodic sorting networks 243
Perl, Yehoshua 673 707
Permanent 660
Permutahedron 13 18 240 593
Permutation in place 79—80 178
Permutation networks 243—244
permutations 11—72 579
Permutations, 2-ordered 86—88 103 112—113 134
Permutations, cycles of 25—32 62 156 617 628 639—640 657
Permutations, enumeration of 12 22—24
Permutations, even 19 196
Permutations, factorization of 25—35
Permutations, fixed points of 62 66 617
Permutations, indexes of 16—17 21—22 32
Permutations, intercalation product of 24—35
Permutations, inverses of 13—14 18 48 53—54 74 134 596 605
Permutations, inversions of see “Inversion tables” “Inversions”
Permutations, lattice of 13 19 22 628
Permutations, matrix representations of 14 48
Permutations, of a multiset 22—35 42—44 46 66
Permutations, optimum 403—408
Permutations, partial orderings of 19 22 105 670
Permutations, pessimum 405
Permutations, readings of 47
Permutations, runs of 35—47 248 259—266 387
Permutations, signed 615
Permutations, two-line notation for 13—14 24 35 43—44 51—54 64—65
Persistent data structures 583
Perturbation trick 404
Pessimum binary search trees 457 711
Peter, Laurence Johnston, principle 143
Peterson, William Wesley 396 422 526 534 538 548
Petersson, Ola 389
Pevzner, Pavel Arkadjevich 615
Peyster, James Abercrombie de, Jr. 544
Philco 2000 computer 256
Picard, Claude Frangois 183 196 215
Ping-pong tournament 142
Pinzka, Charles Frederick 728
Pipeline computers 175 381 389—390
Pippenger, Nicholas John 215 234 549
Pitfalls 41 707 729
Pittel, Boris Gershon 713 721 728 734
PL/I language 339 532
Plane partitions 69—70
Plankalkiil 386
Plaxton, Charles Gregory 623 667
playing cards 42—44 46 169 178 370
Pliicker, Julius 745
Poblete Olivares, Patricio Vicente 646 740 741 742
Pocket sorting 343
Podderjugin, Viktor Denisowitsch 548
Pohl, Ira Sheldon 218 663
Pohlig, Stephen Carl 591
Point quadtrees 566
Poisson, Simeon Denis, distribution 555
Poisson, transform 734
Polish prefix notation 3
Pollard, John Michael 591 669 672
Polya, Gyorgy (George) 599 704
Polygons, regular 289
Polynomial arithmetic 165 520
Polynomial hashing 520 549—550
Polyphase merge sorting 268—287 297 298 300 311 325—326 333 342 346 389 425
Polyphase merge sorting, Caron variation 279—280 286—287
Polyphase merge sorting, optimum 274—279 286 337
Polyphase merge sorting, read-backward 300—302 308 328 334 338 342
Polyphase merge sorting, tape-splitting 282—285 287 298 326—327 333 338
Polyphase radix sorting 348
Pool of memory 369
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå