Knuth D.E. — The art of computer programming (vol. 3 Sorting and Searching) :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Knuth D.E. — The art of computer programming (vol. 3 Sorting and Searching)

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

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

Название: The art of computer programming (vol. 3 Sorting and Searching)

Автор: Knuth D.E.

Аннотация:

The first revision of this third volume is the most comprehensive survey of classical computer techniques for sorting and searching. It extends the treatment of data structures in Volume 1 to consider both large and small databases and internal and external memories. The book contains a selection of carefully checked computer methods, with a quantitative analysis of their efficiency. Outstanding features of the second edition include a revised section on optimum sorting and new discussions of the theory of permutations and of universal hashing.

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

$-\infty$       4 142—144 156 214 663—664 685 707
$\infty$       4 138—139 257—258 263 521 624—625 646
$\infty$ as sentinel      159 252 308 324
$\phi$ (golden ratio), xiv      138 517—518 748—749
$\pi$ (circle ratio)      372 520 748—749
$\TeX$       iv vi—vii 531 722 780
${B}^{*}$ -trees      488
${B}^{+}$ -trees      486
${U}_{t}(n)$ and ${\hat{U}}_{t}(n)$       218 232 238
${V}_{t}(n)$ and ${\hat{V}}_{t}(n)$       209 232 238
${W}_{t}(n)$ and ${\hat{W}}_{t}(n)$       209 232 238
(2,4)-trees      477
(a,b)-trees      477
1/3—2/3 conjecture      197
2-d trees      565
2-descending sequence      451
2-ordered permutations      86—88 103 112—113 134
2—3 trees      476—477 480 483 715
80—20 rule      400—401 405 456
Abbreviated keys      512 551
Abel, limit theorem      740
Abel, Niels Henrik, binomial formula      552
Abraham, Chacko Thakadiparambil      578
Absorption laws      239
Adaptive sorting      389
Addition of apples to oranges      401
Addition of polynomials      165
Addition to a list      see “Insertion”
Address calculation sorting      99—102 104—105 176—177 380 389 698
Address table sorting      74—75 80
Adelson-Velsky, Georgii Maximovich      459 460
Adjacent transpositions      13 240 403 404 640 668
Adversaries      198—202 205—207 209—210 218 671
AF-heaps      152
Agarwal, Ramesh Chandra      359 389
Agenda      see “Priority queue”
Aggarwal, Alok      698
Aho, Alfred Vaino      476 479 652
Aigner, Martin      241
Ajtai, Miklos      228 673 740
al-Khwarizmi, Abu 'Abd Allah Muhammad ibn Musa      8
Aldous, David John      728
Alekseev, Vladimir Evgenievich      232 233 237 238
Alexanderson, Gerald Lee      599
Algol      454
Algorithms, analysis of      see “Analysis”
Algorithms, comparison of      see “Comparison”
Algorithms, proof of      see “Proof”
Allen, Brian Richard      478
Allen, Charles Grant Blairfindie      558
Alphabetic binary encoding      452—454
Alphabetic order      7 420—421 453
Altenkamp, Doris      713
Alternating runs      46
Amble, Ole      556
Amdahl, Gene Myron      547
American Library Association rules      7—8
Amortized cost      478 549
Amphisbaenic sort      347 388
Anagrams      9 see
Analysis of Algorithms      3 77—78 80 82 85—95 100—105 108—109 118—122 140 152—158 161—162 167—168 174—177 185—186 255—256 259—266 274—279 285—287 294—299 330—335 339—343 379 382 387—388 397—408 412—413 424—425 430—431 454—458 466—471 479—480 485—486 490 500—512 524—525 534—539 543—544 552—557 565—566 576 619 see
Analytical engine      180
AND (bitwise and)      134 531 629
Andre, Antoine Desire      68 605
Anti-stable sorting      347 615 650
Antisymmetric function      66
Anuyogadvara-sutra      23
Apollonius Sophista, son of Archibius      421
Appell, Paul Emile      679
Approximate equality      9 394—395
Aragon, Cecilia Rodriguez      478
Archimedes of Syracuse      13
Archimedes of Syracuse, solids      593
Arge, Lars Allan      489
Argument      392
Arisawa, Makoto      574
arithmetic overflow      6 519 585
Arithmetic progressions      517
Armstrong, Philip Nye      225 244 245 675
Arora, Sant Ram      455
Arpaci-Dusseau, Andrea Carol      390
Arpaci-Dusseau, Remzi Hussein      390
Ascents      35
Ashenhurst, Robert Lovett      344 348
Askey, Richard Allen      601
Associated Stirling numbers      266
Associative block designs      574—575 582
Associative law      24 35 239 461 592
Associative memories      392 579
Asymptotic methods      41—42 45 62—64 69 128—134 136—138 194—195 286—287 405 479 490 504—506 509—510 555—557 644
Asymptotic methods, limits of applicability      318
Attitude      73
Attributes      559
Attributes, binary      567—576
Attributes, compound      564 566—567
auf der Heide      see “Meyer auf der Heide”
Automatic programming      387
AVL trees      459 see
Avni, Haim      707
B-trees      482—491 549 563
Babbage, Charles      180
Baber, Robert Laurence      704
Babylonian mathematics      420
Bachrach, Ran      403
Backward reading      see “Read-backward”
Baeza-Yates, Ricardo Alberto      489 713 715
Bafna, Vineet      615
Bailey, Norman Thomas John      740
Balance factor      459 479
Balanced filing      576—578 581
Balanced incomplete block designs      576
Balanced merging      248—251 267 297 299—300 311 325 333 386—387 587
Balanced merging, with rewind overlap      297
Balanced radix sorting      343 386
Balanced trees      150—151 458—491 547 592 713
Balanced trees, weight-balanced      476 480
Balancing a binary tree      480
Balancing a k-d tree      566
Balbine, Guy de      528
Ball, Walter William Rouse      593
Ballot problem      61 66
Barnett, John Keith Ross      168
Barton, David Elliott      44 602 604 605
Barve, Rakesh Dilip      371
Barycentric coordinates      437
Basic query      569 574—576 579—582
Batcher, Kenneth Edward      111 223 226 230—232 235 381 389 667
batching      98 159 560 563
Baudet, Gerard      671
Bayer, Paul Joseph      454 458
Bayer, Rudolf      477 482 483 487 490 721
Bayes, Anthony John      346
Bell, Colin James      337
Bell, David Arthur      167 388 647
Bell, James Richard      531 532
Bellman, Richard Ernest      ix
Ben-Amram, Amir Mordechai      181
Bencher, Dennis Leo      312 313 316
Benchmarks      389—391
Bender, Edward Anton      605 609 696
Bennett, Brian Thomas      378
Bennett, Mary Katherine      718—719
Bent, Samuel Watkins      213 478 666
Bentley, Jon Louis      122 403 512 565—566 633 635
Berkeley, George      780
Berman, Joel David      669
Berners-Lee, Conway Maurice      98 453
Bernoulli, Jacques, numbers      506 602 637 750
Bernoulli, numbers, calculation of      611
Berra, Lawrence Peter "Yogi"      476

Bertrand, Joseph Louis Frangois      605
Best possible      180
Best-fit allocation      480
Beta distribution      586
Betz, B.K.      268 288
Beus, Hiram Lynn      245—246
Bhaskara Acharya      23
Bhattacharya, Kailash Nath      745
Biased trees      478
Bienayme, Irenee Jules      605
Bierce, Ambrose Gwinnett      558
BINAC computer      386
Binary attributes      567—576
Binary computers      411
Binary insertion sort      82—83 97 183 186 193 225 386
Binary merging      203—204 206
Binary quicksort      see “Radix exchange”
Binary search      82 203 409—417 420 422—423 425 435 546 643
binary search trees      426—481 565
Binary search trees, optimum      436—454 456—458 478
Binary search trees, pessimum      457 711
Binary search, uniform      414—416 423
Binary tree      see also “Complete binary tree” “Extended
Binary tree, enumeration      60—61 157 295 467 479
Binary tree, triply linked      158 475
Binary tries      500—502
Binomial coefficients      30—31 87 190
Binomial probability distribution      100—101 341 539 555
Binomial queues      152
Binomial transforms      136—137 508
Biquinary number system      694
Birkhoff, Garrett      719
Birthday paradox      513 549
Bisection      410 see
Bit strings      561—562 572—573
Bit vectors      235
Bitner, James Richard      478 703
Bitonic sequence      231
Bitonic sorter      230—232 243 244
Bits of information      183 442—443
bitwise AND      111 531 589
Bjoerner, Anders      609
Blake, Ian Eraser      740
Blanks, algebra of      592
Bleier, Robert E.      578
Block designs      576—578
Blocks of records      258
Blocks of records, on disk      358—359 369
Blocks of records, on tape      318—320
Bloom, Burton H.      572—573 578 744
Blum, Manuel      214
Boas, Peter van Emde      152
Boehme McGraw, Elaine M.      547
Boerner, Hermann      669
Bollobas, Bela      645
Book of Creation      23
Boolean queries      559 562 564
Booth, Andrew Donald      396 400 422 453 454
Boothroyd, John      617
Borwein, Peter Benjamin      155
Bose, Raj Chandra      226 578 745
Bostic, Keith      177 652
Bottenbruch, Hermann      422 425
Bouricius, Willard Gail      195 223
Bourne, Charles Percy      395 578
Brandwood, Leonard      400
Brawn, Barbara Severa      698
Breaux, Nancy Ann Eleser      680
Brent, Richard Peirce      532—533 546 718
Briandais, Rene Edward de la      494
Brouwer, Andries Evert      575 747
Brown, John      7
Brown, Mark Robbin      152 479
Brown, Randy Lee      152
Brown, William Stanley      157
Bruhat, Frangois, order      628 670
Bruhat, weak      13 19 22 628 670
Bruijn, Nicolaas Govert de      130 138 603 668 670 671 744
Bryce, James Wares      385
Bubble sort      106—109 128—130 134 140 222—223 240 244 246—247 348—349 380 387 390
Bubble sort, multihead      244—245
Buchholz, Werner      396 548
Buchsbaum, Adam Louis      481
Bucket sorting      169
buckets      541—544 547—548 564 555
Buffering      339—343 387 488
Buffering, size of buffers      332—333 349 360 367—368 376—377
Bulk memory      356 see
Burge, William Herbert      279 297 337
Burkhard, Walter Austin      746
Burton, Robert      v
Butterfly network      227 236—237
C      426
Cache memory      389
Calendar queues      152
Cancellation laws      24
Canfield, Earl Rodney      673
cards      see also “Playing cards”
Cards, edge-notched      1 569—570 578
Cards, feature      569—570 578
Cards, machines for sorting      169—170 175 383—385
Carlitz, Leonard      39 47 613 620
Caron, Jacques      279 280 286 287
Carries      691
Carroll, Lewis (Dodgson, Charles Lutwidge)      216 584
Carter, John Lawrence      519 557 743
Carter, William Caswell      279 288 297
Cartesian trees      478
Cascade merge      288—300 311 326 333 338 389
Cascade merge, read-backward      328 334
Cascade merge, with rewind overlap      299 327 333—334 342
Cascade numbers      294—299
Cascading pseudo-radix sort      347
Catalan, Eugene Charles, numbers      61 295
Catenated search      407
Cawdrey (Cawdry), Robert      421
Cayley, Arthur      628 653
Celis Villegas, Pedro      741
cells      564
Census      383—386 395
Cesari, Yves      193 279
Chaining      520—525 542—544 547 553 557
Chaining, to reduce seek time      368—369
Chakravarti, Gurugovinda      23
Chandra, Ashok Kumar      422
Chang, Shi-Kuo      458
Chartres, Bruce Aylwin      156
Chase, Stephen Martin      196
Chazelle, Bernard Marie      583
Chebyshev, Pafnutii Lvovich      395
Chebyshev, polynomials      296 685
Chen, Wen-Chin      548
Cherkassky, Boris Vasilievich      152
Chessboard      14 46—47 69
Choice of data structure      95—96 141 151—152 163—164 170—171 459 561—567
Chow, David Kuo-kien      578
Christen, Claude Andre      204 658
Chronological order      372 379
Chung, Fan Rong King      402
Chung, Moon Jung      673
Church, Randolph      669
CI: MIX's comparison indicator      6
Cichelli, Richard James      513
Circular lists      407 729
Clausen, Thomas      157
Cleave, John Percival      400
Clement, Julien Stephane      728
Cliques      9
Closest match, search for      9 394 408 563 566 581
CMPA (compare rA)      585

1 2 3 4 5 6 7 8

О проекте