|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Knuth D.E. — The art of computer programming (vol. 3 Sorting and Searching) |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
Pool, Jan Albertus van der 739
Poonen, Bjorn 104
Porter, Thomas K 642
Post Office 175
Post-office trees 563—564 746
posting see “Insertion”
Pouring liquid 672
Power of merge 676 see
Powers, James 385
Pratt, Richard Don 310
Pratt, sorting method 91—93 104 113 235
Pratt, Vaughan Ronald 91 104 245 457 622 675 701
Prediction see “Forecasting”
Preferential arrangements 194
prefetching 369—373
Prefix 492
Prefix code 452—453
Prefix code, for all nonnegative integers 6
Prefix search see “Trie search”
Preorder merge 307—309
Prestet, Jean 24
Prime numbers 156 516 529 557 627
Primitive comparator networks 240 668
Principle 370 378
Principle of optimality 363 438
Pring, Edward John 564
Prins, Jan Fokko 618
Priority deques 157
Priority queues 148—152 156—158 253 646 705
Priority queues, merging 150 157
Priority search trees 578
Probability density functions 177
Probability distributions 105 399—401
Probability distributions, beta 586
Probability distributions, binomial 100—101 341 539 555
Probability distributions, fractal 400
Probability distributions, normal 45 69 650
Probability distributions, Pareto 401 405 710
Probability distributions, Poisson 555
Probability distributions, random 458
Probability distributions, uniform 6 16 20 47 127 606
Probability distributions, Yule 401 405
Probability distributions, Zipf 400 402 435 455
Probability generating functions 15—16 102 104 135 177 425 490 539 553 555 739
Prodinger, Helmut 576 634 644 648 726 726
Product of consecutive binomial coefficients 612
Proof of algorithms 49—51 112—113 315 323 355 677
Prusker, Francis 377
Prywes, Noah Shmarya 578
Pseudolines 670
Psi function  637 751
Puech, Claude Henri Clair Marie Jules 565 566 576
Pugh, William Worthington, Jr. 213 478
Punched cards 169—170 175 383—385
q-multinomial coefficients 32
Q-nomial coefficients 32 594 595
q-series 20 32 594—596 644
Quadrangle inequality 457
Quadratic probing 551
Quadratic selection 141
Quadruple systems 581 746
Quadtrees 565—566 581 745—746
Queries 559—582
Questionnaires 183
Queues 135 148—149 156 171 299 310 322—323
Quickfind 136
Quickfind, median-of-three 634
Quicksort 113—122 135—138 148 159 246 349—351 356 381 382 389 389 431 698
Quicksort, binary see “Radix exchange”
Quicksort, median-of-three 122 136 138 381 382
Quicksort, multikey 389 633 728
Quicksort, with equal keys 136 635—636
Rabbits 424
Rabin, Michael Oser 242
Radix exchange sort 122—128 130—133 136—138 159 177 351 382 389 500—501 509 698
Radix exchange sort, with equal keys 127—128 137
Radix insertion sort 176—177
Radix list sort 171—175 382
Radix sorting 5 169—179 180—181 343—348 351 359 374 381 385 389 421 502 698
Radix sorting, dual to merge sorting 345—348 359
Radix-2 sorting 387
Radke, Charles Edwin 297
Raiha, Kari-Jouko 717
Railway switching 168
Rains, Eric Michael 611
Rais, Bonita Marie 726
Raman Rajeev 634
Raman, Venkatesh 655
Ramanan, Prakash Viriyur 218
Ramanujan Iyengar, Srinivasa, function Q(n) 701
Ramshaw, Lyle Harold 729
Random data for sorting 20 47 76 383 391
Random probability distribution 458
Random probing, independent 548 555
Random probing, with secondary clustering 548 554
Randomized adversary: An adversary that flips coins 219
Randomized algorithms 121—122 351 455 517 519 557—558
Randomized binary search trees 478
Randomized data structures 478
Randomized striping 371—373 379 698
Randrianarimanana, Bruno 713
Raney, George Neal 297 298
Range queries 559 578
RANK field 471 476 479 713 718
ranking 181 see
Raver, Norman 729
Ravikumar, Balasubramanian 673
Rawlings, Don Paul 595
Ray Chaudhuri, Dwijendra Kumar 578
Read-back check 360
Read-backward balanced merge 327—328 334
Read-backward cascade merge 328 334
Read-backward polyphase merge 300—302 308 328 334 338 342
Read-backward radix sort 346—347
Read-forward oscillating sort 315—316 329 334
Reading tape backwards 299—317 349 356 387
Readings of a permutation 47
Real-Time applications 547
Rearrangements of a word see “Permutations of a multiset”
Rearranging records in place 80 178
Rebalancing a tree 461 463—464 473—474 479 see
Reciprocals 420
Records 4 392
Recurrence relations for strings 274—275 284 287 308
Recurrence relations, techniques for solving 120 135 137 168 185—186 205—206 224—225 283 356 424 430—431 467 490 502 506 604—605 638—639 648 674 688 725 737
Recursion induction 315
Recursion versus iteration 168 313 717
Recursive methods 114 214 218 243 313 350 592 596 713 715 717
Red-black trees 477
Redundant comparisons 182 240 242 245—246 391
Reed, Bruce Alan 643 713
reference counts 534
Reflection networks 670
Regnier, Mireille 565 632
Regular polygons 289
Reiner, Victor Schorr 719
Reingold, Edward Martin 207 476 480 715
Relaxed heaps 152
Remington Rand Corporation 385 387
removal see “Deletion”
Reorganizing a binary tree 458 480
Replacement selection 212 253—266 325 329 331—332 336 347 348 360 364—365 378
Replicated blocks 489
Replicated instructions 398 418 429 625 648 677
Reservoir 259—261 265
Restructuring 480
Reversal of data 65 72 310 670 701
Reverse lexicographic order 394
Rewinding tape 279—287 297 299—300 316 319—320 326 331 342 407
Ribenboim, Paulo 584
| Rice, Stephan Oswald 138
Richards, Ronald Clifford 479
Richmond, Lawrence Bruce 726
Riemann, Georg Friedrich Bernhard, integration 177 652
Riesel, Hans Ivar 406
Right-threaded trees 267 454—455 464
Right-to-left (or left-to-right) maxima or minima 12—13 27 82 86 100 105 156 624
Riordan, John 39 46 605 679 732 733 738
RISC computers 175 381 389—390
Rising, Hawley 128
Rivest, Ronald Linn 214 215 389 403 477 573—576 580 747
Roberts, David Caron 573
Robin Hood hashing 741—742
Robinson, Gilbert de Beauregard 58 60
Robson, John Michael 565 713
Rochester, Nathaniel 547
Rodgers, William Calhoun 704
Rodrigues, Benjamin Olinde 15 592
Roebuck, Alvah Curtis 757
Rogers, Lawrence Douglas 707
Rohnert, Hans 549
Rollett, Arthur Percy 593
Rooks 46—47 69
Rose, Alan 672
Roselle, David Paul 47 597
Rosenstiehl, Pierre 593
Rosier, Uwe 632
Rosser, John Barkley 672
Rost, Hermann 614 671
Rotations in a binary tree 481
Rotations in a binary tree, double 461 464 477
Rotations in a binary tree, single 461 464 477
Rotem, Doron 61
Rothe, Heinrich August 14 48 62
Rouche, Eugene, theorem 681
Roura Ferret, Salvador 478
Roving pointer 543
Rovner, Paul David 578
Royalties, use of 407
Rubin, Herman 728
Rudolph, Lawrence Set 673
Runs of a permutation 35—47 248 259—266 387
Russell, Robert C. 394
Russian roulette 21
Rustin, Randall 315 353
Sable, Jerome David 578
Sackman, Bertram Stanley 279 684
Sagan, Bruce Eli 48
Sager, Thomas Joshua 513
Sagiv, Yehoshua Chaim 721
Saks, Michael Ezra 452 660 673
Salveter, Sharon Caroline 477
Salvy, Bruno 565
Samadi, Behrokh 721
Samet, Hanan 566
Samplesort 122 720
Sampling 587
Samuel, Arthur Lee 547
Samuel, son of Elkanah 481
Sandelius, David Martin 656
Sankoff, David Lawrence 614
Sarnak, Neil Ivor 583
Sasson, Azra 369
Satellite information: Record minus key 4 74
Satisfiability 242
Saul, son of Kish 481
Sawtooth order 452
Sawyer, Thomas 747
SB-tree 489
Scatter storage 514
Schachinger, Werner 576
Schaeffer, Alejandro Alberto 708
Schaffer, Russel Warren 155 157 645
Schay, Geza, Jr. 538 555 729
Schensted, Craige Eugene 57—58 66
Scherk, Heinrich Ferdinand 644
Schkolnick, Mario 721
Schlegel, Stanislaus Ferdinand Victor 270
Schlumberger, Maurice Lorrain 366
Schmidt, Jeanette Pruzan 708 742
Schneider, Donovan Alfred 549
Schoenhage, Arnold 215 218
Schott, Rene Pierre 713
Schreier, Jozef 209
Schuetzenberger, Marcel Paul 17 21 39 55 57—58 66 68 70 670
Schulte Moenting, Jiirgen 192 659
Schur, Issai, function 611—612
Schwartz, Eugene Sidney 401
Schwartz, Jules 128
Scoville, Richard Arthur 47
Scrambling function 517 590 709
Search-and-insertion algorithm 392
Searching 392—583 see “Internal “Static “Symbol
Searching, by comparison of keys 398—399 409—491 546—547
Searching, by digits of keys 492—512
Searching, by key transformation 513—558
Searching, for closest match 9 394 408 563 566 581
Searching, for partial match 559—582
Searching, geometric data 563—566
Searching, history 395—396 420—422 453 547—549 578
Searching, methods see “B-trees Balanced “Binary “Chaining” “Fibonaccian “Interpolation “Open “Patricia” “Sequential “Tree “Trie
Searching, optimum 413 425 549 see “Optimum
Searching, parallel 425
Searching, related to sorting, v 2 393—394 409 660
Searching, text 511 572 578
Searching, two-dimensional 207
Sears, Richard Warren 757
Secant numbers 610—611
Secondary clustering 529 551 554
Secondary hash codes 741
Secondary key retrieval 395 559—582
Sedgewick, Robert 91 93 95 114 115 122 136 152 155 157 477 512 623 629 630 633 638 645 674 726
Seeding in a tournament 208
Seek time 358 362—365 368—369 407 562—563
Sefer Yetzirah 23
Seidel, Raimund 478
Selection of t largest 218—219 408
Selection of t largest, networks for 232—234 238
Selection of tth largest 136 207—219 472
Selection of tth largest, networks for 234 238
Selection sorting 54—55 73 138—158 222
Selection trees 141—144 252 256—258
Self-adjusting binary trees see “Splay trees”
Self-inverse permutations 599 see
Self-modifying programs 85 107 174 640
Self-organizing files 401—403 405—406 478 521 646
Selfridge, John Lewis 8
Senko, Michael Edward 487
Sentinel: A special value placed in a table, designed to be easily recognizable by the accompanying program 4 105 159 252 308 387 638
Separation sorting 343
Sequential allocation 96 149 163—164 170—171 386 459
Sequential file processing 2—3 6—10 248
Sequential search 396—409 423
Sets, testing equality 207
Sets, testing inclusion 393—394
Sevcik, Kenneth Clem 564
Seward, Harold Herbert 79 170 255 387 670 696
Sexagesimal number system 420
Seymour, Paul Douglas 402
Shackleton, Patrick 136
Shadow keys 588
Shamir, Ron 615
Shanks, Daniel Charles 591
Shannon, Claude Elwood, Jr. 442 457 712
Shapiro, Gerald Norris 226—227 229 243
Shapiro, Henry David 668
Shar, Leonard Eric 416 423 706
Shasha, Dennis Elliott 488.
Shearer, James Bergheim 660
Sheil, Beaumont Alfred 457
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå