|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Knuth D.E. — The art of computer programming (vol. 3 Sorting and Searching) |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
Shell, Donald Lewis 83 93 279
Shellsort 83—95 98 102—105 111 148 380 382 389 669 698
Shepp, Lawrence Alan 611
Sherman, Philip Martin 492
Shields, Paul Calvin 728
Shift-register device 407
Shifted tableaux 67
Shockley, William Bradford 668
Sholmov, Leonid Ivanovich 351
Shrairman, Ruth 152
Shrikhande, Sharadchandra Shankar 745
Shuffle network 227 236—237
Shuffling 7 237
Sideways addition 235 643 644 717
Siegel, Alan Richard 708 742
Siegel, Shelby 623
Sifting 80 see
Siftup 70 145—146 153—154 157
Signed permutations 615
Signed-magnitude notation 177
Silicon Graphics 0rigin2000 390
Silver, Roland Lazarus 591
Silverstein, Craig Daryl 152
Simon, Istvan Gusztav 642
Simulation 351—353
Singer, Theodore 279
Single hashing 556—557
Single rotation 461 464 477
Singleton, Richard Collom 99 115 122 136 572 581
Sinking sort 80 106 see
Skew heaps 152
Skip lists 478
Slagle, James Robert 704
SLB (shift left rAX binary) 516 529
Sleator, Daniel Dominic Kaplan 152 403 478 583 718
Sloane, Neil James Alexander 479
Slupecki, Jerzy 209
Smallest-in-first-out see “Priority queues”
Smith, Alan Jay 168 695
Smith, Alfred Emanuel 392
Smith, Cyril Stanley 593
Smith, Wayne Earl 405 407
Snow job 255—256 260—261 263—266
Sobel, Milton 212 215 216 217 218
Sobel, Sheldon 311 316
Software 387—390
Solitaire (patience) 42—44 46
Sort generators 338—339 387—388
Sorting (into order) 1—391 see “Internal “Address “Enumeration “Exchange “Insertion “Merge “Radix “Selection
Sorting, adaptive 389
Sorting, by counting 75—80
Sorting, by distribution 168—179
Sorting, by exchanging 105—138
Sorting, by insertion 73 80—105 222
Sorting, by merging 98 158—168
Sorting, by reversals 72
Sorting, by selection 138—158
Sorting, history 251 383—390 421
Sorting, in O(N) steps 5 102 176—179 196 616
Sorting, into unusual orders 7—8
Sorting, methods see “Binary insertion sort” “Bitonic “Bubble “Cocktail-shaker “Comparison “Distribution “Heapsort” “Interval “List “List “Median-of-three “Merge rt” “Merge “Multiple “Natural “Odd-even “Pratt “Quicksort” “Radix “Radix “Radix “Samplesort” “Shellsort” “Straight “StRaight “Straight “Tree “Tree “Two-way Merge
Sorting, networks for 219—247
Sorting, optimum 180—247
Sorting, parallel 113 222—223 228—229 235 390 671
Sorting, punched cards 169—170 175 383—385 694
Sorting, related to searching, v 2 393—394 409 660
Sorting, stable 4—5 24 37—38 79 102 134 155 167 347 390 584 615
Sorting, topological 9 31—32 62 66—67 187 216 393 593
Sorting, two-line arrays 34
Sorting, variable-length strings 177 178 489 633
Sorting, with one tape 353—356
Sorting, with two tapes 348—353 356
Sos, Vera Turan Paine 518 747
SOUNDEX 394—395
Spacings 458
Sparse arrays 721—722
Speedup see “Loop optimization”
Spelling correction 394 573
Sperner, Emanuel, lemma 744
Splay trees 478
Splitting a balanced tree 474—475 480
Sprugnoli, Renzo 513
Spruth, Wilhelm Gustav Bernhard 538 555
Spuler, David Andrew 711
SRB (shift right rAX binary) 125—126 134 411
Stable sorting 4—5 24. 79 102 134 155 167 347 390 584 615
stacks 21 60 114—117 122 123—125 135 148 156 168 177 299 310 350 473
Stacy, Edney Webb 704
Staeel-Holstein, Anne Louise Germaine Necker, Baronne de 589
Standard networks of comparators 234 237—238 240 244
Stanfel, Larry Eugene 457
Stanley, Richard Peter 69 600 607 670 671
Stasevich, Grigory Vladomirovich 91
Stasko, John Thomas 152
Static table searching 393 409—426 436—458 492—496 507—508 513—515
Stearns, Richard Edwin 351 356
Steiner triple systems 576—577 580—581 745
Steiner, Jacob 745
Steinhaus, Hugo Dyonizy 186 209 422 518
Stepdowns 160 262
Stevenson, David 671
Stirling, James, approximation 63 129 182 197
Stirling, James, numbers 45 175 455 602 653 679 739 754
Stockmeyer, Paul Kelly 202
Stone, Harold Stuart 237 425
Stop/start time 319—320 331 342
Stoyanovskii, Alexander Vasil'evich 70 614
Straight insertion sort 80—82 96 102 105 110 116—117 127 140 148 163 222—223 380 382 385 386 390 676
Straight merge sort 162—163 167 183 193 387
Straight selection sort 110 139—140 148 155—156 381 382 387 390
Stratified trees 152
Straus, Ernst Gabor 704
Strings: Ordered subsequences 248 see
Strings: Sequences of items 22 27—28 72 248 494
Strings: Sequences of items, recurrence relations for 274—275 284 287 308
Strings: Sequences of items, sorting 177 178 489 633
Striping 342 370—373 378 379 389 698
Strong, Hovey Raymond, Jr. 549
strongly 310—311 345 348
Strongly T-fifo trees 310—311 345 348
Successful searches 392 396 550 532
Sue, Jeffrey Yen 693
Suel, Torsten 623 667
Sugito, Yoshio 727
Sum of uniform deviates 47
Summation factor 120
Sun SPARCstation 780
Superblock striping 370 371 379
Superfactorials 612
Superimposed coding 570—573 579
Surnames, encoding 394—395
Sussenguth, Edward Henry, Jr. 496
Swierczkowski, Stanislaw Slawomir 518
Swift, Jonathan vii
Sylvester, James Joseph 622
Symbol table algorithms 3 426—435 455 496—512 520—558
Symmetric binary B-trees 477
Symmetric functions 239 608—609
Symmetric group 48 see
Symmetric order: Left subtree, then root, then right subtree 412 427 658
Symvonis, Antonios 702
SyncSort 369 371 699
Szekeres, George 66
Szemeredi, Endre 228 549 673 740
Szpankowski, Wojciech 726 727 728
T-fifo trees 310—311
T-lifo trees 305—310 346 348
Tableaux 47—72 240 670—671
Tables 392
Tables, of numerical quantities 748—751
| Tag sorting see “Keysorting”
Tail inequalities 379 636
Tainiter, Melvin 740
Takacs, Lajos 744
Talagrand, Michel 611
Tamaki, Jeanne Keiko 454
Tamari, Dov 718
Tamminen, Markku 176—177 179
Tan, Kok Chye 457 711
Tangent numbers 602 610—611
Tanner, Robert Michael 660
Tanny, Stephen Michael 606
Tape searching 403—407
Tape splitting 281—287
Tape splitting, polyphase merge 282—285 287 298 326—327 333 338
tapes see “Magnetic tapes”
Tardiness 407
Tarjan, Robert Endre 152 214 215 403 477 478 549 583 590 615 649 652 713 718 722
Tarter, Michael Ernest 99
Tarui, Jun 230
Telephone directories 409 561 573
Tengbergen, Cornelia van Ebbenhorst 744
Tennis tournaments 207—208 216
Terabyte sorting 390
Ternary comparison trees 194
Ternary heaps 157
Ternary trees for tries 512
Terquem, Olry 591
Tertiary clustering 554
Testing several conditions 406
Teuhola, Jukka Ilmari 649
Text searching 511 572 578
Theory meets practice 318
Thiel, Larry Henry 578
Thimbleby, Harold William 627
Thimonier, Loys 703
Thorup, Mikkel 181
Thrall, Robert McDowell 60 67
Threaded trees 267 454—455 464 708
Three-distance theorem 518 550
Three-way radix quicksort see “Multikey quicksort”
Thue, Axel 422 494
Thue, trees 426
Thumb indexes 419 492
Thurston, William Paul 718
Tichy, Robert Franz 644
Tie-breaking trick 404
Ting, Tze Ching 261
Tobacco 72
Togetherness 2
Tomlinson, Robert L.,Jr. 623
Topological sorting 9 31—32 62 66—67 187 216 393 593
Total displacement 22 102
Total order 4
Total variance 735 742
Touchard, Jacques 653
Tournament 141—142 207—212 216 253—254
Townsend, Gregg Marshall 549
Trabb Pardo, Luis Isidoro 645 702
tracks 357 482
Trading tails 64
Transitive Law 4—5 18—19 182 207 456
Transpose of a matrix 6—7 14 567 617
Transposition sorting see “Exchange sorting”
Treadway, Jennifer Ann 595
Treaps, vii 478
Tree function T(z) 713 740
Tree hashing 553
Tree insertion sort 98 389 431 453 675
Tree network of processors 267
Tree representation of algorithms see “Decision trees”
Tree representation of distribution patterns 344—345 348
Tree representation of merge patterns 303—306 309—311 363—364 377
Tree search 427—431 482 546—547 547
Tree search, generalized 490
Tree selection sort 141—144 167 183 210 217 388 664
Tree traversal 138 427 431
Trees 1
Treesort see “Tree selection sort” “Heapsort”
Tribolet, Charles Siegfried 623
Trichotomy Law 4—5
Tricomi, Francesco Giacomo Filippo 131
Trie memory see “Tries”
Trie search 492—496 500—502 508—509
Tries 492—496 507—509 512
Tries, binary 500—502
Tries, compressed 507 722
Tries, generalized 576
Tries, multidimensional 576
Tries, optimum 508
Tries, represented as forests 494—496 508 512
Tries, represented as ternary trees 512
Tripartitioning 633 635
Triple systems 576—577 580—581 745
Triply linked trees 158 475
Trotter, William Thomas 658
Trousse, Jean-Michel 746
Truesdell, Leon Edgar 384
Truncated octahedron 13 18
Trybula, Stanislaw 186
Tucker, Alan Curtiss 454
Tumble instruction 82
Turba, Thomas Norbert 496
Turing, Alan Mathison 583
Turing, machine 676
Turski, Wladyslaw 513
Twain, Mark (Clemens, Samuel Langhorne) 747
Twin heaps 645
Twin primes 529
Two's complement notation 177
Two-line notation for permutations 13—14 24 35 43—44 51—54 64—65
Two-tape sorting 348—353 356
Two-way branching 425 457
Two-way insertion sort 83 98
Two-way merging 158—159 166 248 370 379 386
Ullman, Jeffrey David 476 539—540 652
UltraSPARC computer 390
Underflow during deletions 720
Uniform binary search 414—416 423
Uniform distribution 6 16 20 47 127 606
Uniform probing 530 534—535 548 555—557
Uniform sorting 245—246
Unimodal function 417
UNIVAC I computer 386—387 738
UNIVAC III computer 688
UNIVAC LARC computer 2
Universal hashing 519 557—558
UNIX operating system 122
Unreliable comparisons 702
Unsuccessful searches 392 396 531 572
Unusual correspondence 27
Updating a file 166 370
Uzgalis, Robert 482 490
Vallee, Brigitte 728
van der Pool, Jan Albertus 739
van Ebbenhorst Tengbergen, Cornelia 744
van Emde Boas, Peter 152
van Emden, Maarten Herman 128 633 638
van Leeuwen, Jan 645
van Leeuwen, Marcus Aurelius Augustinus 611
van Lint, Jacobus Hendricus 729 747
Van Valkenburg, Mac Elwyn 8
Van Voorhis, David Curtis 228—229 240
van Wijngaarden, Adriaan 8
Vandermonde, Alexandre Theophile 8
Vandermonde, determinant 59 610 729
Variable-length code 452—453
Variable-length keys, searching for 429 487 490 496 519 556 557 720
Variable-length records 266 339 403
Variable-length strings, sorting 177 178 489 633
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå