|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J.V. — Handbook of Theoretical Computer Science: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Reduction, algorithm 681 710
Reduction, compatible 79
Reduction, logspace 15
Reduction, many-one 15
Reduction, master 16
Reduction, NC 132
Reduction, parsimonious 16
Reduction, polynomial-time 15
Reduction, polynomial-time Turing 79
Reduction, random 246
Reduction, randomized 117—119
Reduction, strongly nondeterministic polynomial-time Turing 91
Reduction, transitive 79
Reduction, Turing 78
Reference function (see also reference machine) 198 210
Reference machine 198 210
Register allocation 481
Register machine 22 24
Regular expression 259
REGULAR EXPRESSION INEQUIVALENCE 103 105 106
Regular expression, extended 260
Regular expression, matching 282
Regular language or set 233 260
Rejecting computation 8
Relation, computed 9
Relativation 81—82 143—144
Relativization 241 776
Relaxed heap 328
Reliability (of graphs) 108 122
Representation (of a graph) 527
Representation (of a graph), adjacency list 536
Representation (of a graph), adjacency matrix 532
Representation (of a graph), edge query 532
Representation (of a graph), implicit 535
Representation (of a graph), matrix 661
Representation (of a graph), minimum query 540
Representation (of a graph), minimum storage 539
Representation (of a graph), node query 536
Representation (of a graph), ordered list 536
Representation (of a graph), small circuit 535
Representation (of a graph), structural 537
Representation theory 636
Representation-based data structure 311
Residue-list sieve method 693
Resistive model 840
Resource bound 72 76
Resource bound, honest 184
Resource graph 956
Resource-bounded Kolmogorov complexity 236—241
Response function 846 847 853
Restriction 766 792
Restriction, random 767 792
Resultant 401 644
Rho method 687 (see also Pollard’s rho method)
Ring of tensor classes 653
RNC 133 904 922
Robertson — Seymour theory 547
Robot environment 393
Robot environment, fixed 397
Robot environment, partially known 418
Robot system 393 394
Robot system, mobile 414
Robotics 393
Root isolation 401
Rosenberg conjecture 229
Routing 808
Routing algorithm, deterministic 951
Routing algorithm, distributed 950
Routing algorithm, greedy 951
Routing algorithm, oblivious 951
Routing algorithm, randomized 951
Routing, global 808
Routing, local 808
Routing, permutation 950
Routing, randomized 951
Routing, two-phase 951
RSA 729
RTM see random Turing machine
Ruling set 878—879
Saddle-point method 451 457 502 506
Satisfiability (Sat) 15 83 240
SATISFIABILITY (SAT), critical 93
SATISFIABILITY (SAT), parity 110
SATISFIABILITY (SAT), three 86
SATISFIABILITY (SAT), two 86
SATISFIABILITY (SAT), unique 93
Savitch’s theorem 13 40 100
sc 38 127
Scanning order 558
Scholz’ function 644
Search problem 70
Search tree 308 481 488 491 492 512
Search tree, binary 470 481 514 520
Search, bibliographic 278
Search, breadth-first 539 881 894 919
Search, depth-first 538 881—883 924—925 929
Searching 481 488 491 492 512
Searching (a table) 231
Searching problem, decomposable 332
Searching, maze 418
Searching, path 396
Secret sharing 746
Secret-key cryptosystem 728
Security, computational 748
Security, information-theoretic 721 748
Security, parameter 727
Security, polynomial-time 732
Segment tree 368
Selection problem 329
Selection sort 470
Self-delimiting complexity 202 209—211
Self-delimiting description 201 202
Self-delimiting program 202
Semialgebraic sets 401
Semicomputable function 213
Semimeasure 213
Semimeasure, universal semicomputable 210 213
Semisorted table 307
Semisorting 965
sensing 393
Separable class (of graphs) 575
Separate chaining 493
Separation assumption 325
Separator 573 789 795 845 857
Separator, cycle 574
Separator, edge 574
Separator, planar 574
Separator, vertex 574
Sequential machine model 9
Set-union-find 517 (see also  )
Shared memory 9
Shared-memory machine 869
Shellsort 462
Shift register, linear feedback 736
Shifter 815
Shifting network 815
Shortest path 415 557 919
Shortest path tree (SP tree) 557
Shortest path, all pairs 560
Shortest path, amidst polyhedra 417
Shortest path, Euclidean 415
Shortest path, even/odd length 560
Shortest path, in a simple polygon 416
Shortest path, on a polyhedral surface 417
Shortest path, rectilinear 416
Shortest path, single source 557
Shortest path, weighted 416
Shrinking lemma 555
Shuffle-exchange network 862 948
Shunt 879—881 916—917
| Sieve algorithm, cubic 705
Sieve algorithm, linear 694
Sieve algorithm, quadratic 697 703
Sieve method, residue-list 693
Signature (of a graph) 579
Signature, digital 739
Signature, scheme 739
Silhouette 403
SIMDAG 50
Simple polygon 415 416
Simple set 207 214
Simplex algorithm 364
Simplicity of description 217
Simulation 9 962
Simulation, backward 31
Simulation, constant-delay 13
Simulation, constant-factor space overhead 13
Simulation, effective 13
Simulation, Hennie — Stearns 19
Simulation, linear-time 13
Simulation, polynomial-time 13 14
Simulation, real-time 13
Simulation, recursive 10
Single-output function 785
Singularity 447
Size function 25
Size of a Boolean circuit 75
Size of a branching program 796
Size of a formula 787
Size of a network 809
Size of a problem instance 72
SL 129
Slackness 945 960
Slice function 780
Smallest enclosing circle 363
Smoothness 677 690
Smoothness in class groups 683 702
Smoothness testing, rigorous 699
Smoothness testing, with elliptic curves 698 699
Snobol 261
Solomonoff — Levin distribution 210 213
Solving sparse systems of linear equations 683
Solving systems of linear equations 683
Sort, bitonic 890—892
Sort, bubble 467
Sort, bucket 892 894
Sort, distribution 496
Sort, heapsort 41
Sort, insertion 461
Sort, merge 467 471 892—893
Sort, quicksort 467 472
Sort, radix-exchange 470 491
Sort, selection 470
Sort, Shellsort 462
Sorter 811
Sorting 458 484 491 496
Sorting network 467 472 811 887 890—892 894
Sorting, (in VLSI theory) 864 865
Sorting, Boolean 786
Sorting, Jordan 365
SP tree see shortest path tree
Space 11
Space bound, constructible 168
Space bound, subconstructible 172 173
Space complexity 165 166 796
Space complexity class 11
Space complexity, prospective 177
Space complexity, realizable 177
Space measure 11
Space-bounded acceptance 11
Space-bounded Kolmogorov complexity 240 241 242
Span — P 110
Spanning tree, edge disjoint 557
Spanning tree, minimum (MST) 555
Sparse language or set 87
Sparse set 204 245 246
Specification method 197
Specification method, optimal 197
Speed-up theorem 173 183
Speed-up theorem, constant-factor 20
Speed-up, additive-constant 167
Speed-up, effective 175
Splay tree 320
SPRAM 961
Square 290
STACK 18 226
Stack, popping 18
Stack, pushing 18
State 7 843
Stirling number 442 443 445
Stirling’s formula 446 453
Stochastic Turing machine 121
Storage Modification Machine 32
Straight-line code 915—917 921
Straight-line program 635
String matching 255 257
String matching, approximate 293
String matching, with  differences 294
String matching, with mismatches 294
String matching, with don’t cares 294
String relation 69 70
String, compressible 214 242—246
String, incompressible 200
String, random finite 201 214
String, random infinite 205—206 220 221
Strong component 919
Strong orientation 882 885
Strongly connected component 571
Strongly where-oblivious 843
Structure 778
Subcircuit 771
Subconstructible space bound 172 173
Subformula 792
subfunction 764 793
Subgraph isomorphism testing 574
Subgraph, maximal planar 531
Subresultant 401
Substitution method 638
Subtraction 899 905 907—908
Subword tree 290
Successor RAM (SRAM) 24
Suffix tree 290
Sum, Boolean 786
Sum, check 725
Sum, Minkowski 411
Sum, power 644
Sum, prefix 875—881 885 907—908 931
Sunflower 782
Supercbncentrator 660 817
Supercbncentrator, weak 819
Sweep technique 346
switch 842
Switching energy 839 857
Symbolic determinant 922
Symbolic differentiation 480
Symmetric function 794
Symmetric Turing machine 128
Symmetry of information 209 211
System of linear equations 913—915 920—921;
Systolic algorithm 864
Table look-up 896—897
Tape 17
Tape cell 17
Tape cell, input 18
Tape cell, output 18
Tape cell, work 17
Tape, counter 18
Tape, higher-dimensional 18
Tape, queue 18
Tape, stack 18
|
|
|
| Реклама |
|
|
|
|
|
О проекте