|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J. (ed.), Meyer A.R., Nivat M. — Algorithms and Complexity, Volume A |
|
|
|
| Предметный указатель |
Reduction,  90
Reduction, algorithm 681
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 reduction, Turing 91
Reduction, transitive 79
Reduction, Turing 78
Reference function 198 (see
Reference machine 198
Register allocation 481
Register machine 22 24
Regular expression 259
REGULAR EXPRESSION INEQUIVALENCE 103
Regular expression, extended 260
Regular expression, matching 282
Regular language or set 233
Rejecting computation 8
Relation, computed 9
Relativation 81—82
Relativization 241
Relaxed heap 328
Reliability (of graphs) 108
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
Restriction 766
Restriction, random 767
Resultant 401
Rho method 687 (see also Pollard’s rho method)
Ring of tensor classes 653
RNC 133
Robertson — Seymour theory 547
Robot environment 393
Robot environment, fixed 397
Robot environment, partially known 418
Robot system 393
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
Satisfiability (Sat) 15 83
SATISFIABILITY (SAT), 2- 86
SATISFIABILITY (SAT), 3- 86
SATISFIABILITY (SAT), critical 93
SATISFIABILITY (SAT), parity 110
SATISFIABILITY (SAT), unique 93
Savitch’s theorem 13 40
sc 38
Scanning order 558
Scholz’ function 644
Search problem 70
Search tree 308
Search tree, binary 470
Search, bibliographic 278
Search, breadth-first 539
Search, depth-first 538
Searching 481
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
Security, parameter 727
Security, polynomial-time 732
Segment tree 368
Selection problem 329
Selection sort 470
Self-delimiting complexity 202
Self-delimiting description 201
Self-delimiting program 202
Semialgebraic sets 401
Semicomputable function 213
Semimeasure 213
Semimeasure, universal semicomputable 210
Semisorted table 307
Semisorting 965
sensing 393
Separable class (of graphs) 575
Separate chaining 493
Separation assumption 325
Separator 573
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
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
| Shunt 879—881 -917
Sieve algorithm, cubic 705
Sieve algorithm, linear 694
Sieve algorithm, quadratic 697
Sieve method, residue-list 693
Signature (of a graph) 579
Signature, digital 739
Signature, scheme 739
Silhouette 403
SIMDAG 50
Simple polygon 415
Simple set 207
Simplex algorithm 364
Simplicity of description 217
Simulation 9
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
Slice function 780
Smallest enclosing circle 363
Smoothness 677
Smoothness in class groups 683
Smoothness testing, rigorous 699
Smoothness testing, with elliptic curves 698
Snobol 261
Solomonoff — Levin distribution 210
Solving sparse systems of linear equations 683
Solving systems of linear equations 683
Sort, bitonic 890—892
Sort, bubble 467
Sort, bucket 892
Sort, distribution 496
Sort, heapsort 41
Sort, insertion 461
Sort, merge 467
Sort, quicksort 467
Sort, radix-exchange 470
Sort, selection 470
Sort, Shellsort 462
Sorter 811
Sorting 458
Sorting network 467
Sorting, (in VLSI theory) 864
Sorting, Boolean 786
Sorting, Jordan- 365
SP tree see Shortest path tree
Space 11
Space bound, constructive 168
Space bound, subconstructible 172
Space complexity 165
Space complexity class 11
Space complexity, prospective 177
Space complexity, realizable 177
Space measure 11
Space-bounded acceptance 11
Space-bounded Kolmogorov complexity 240
Span — P 110
Spanning tree, edge disjoint 557
Spanning tree, minimum (MST) 555
Sparse language or set 87
Sparse set 204
Specification method 197
Specification method, optimal 197
Speed-up theorem 173
Speed-up theorem, constant-factor 20
Speed-up, additive-constant 167
Speed-up, effective 175
Splay tree 320
SPRAM 961
Square 290
STACK 18 (see
Stack, popping 18
Stack, pushing 18
State 7
Stirling number 442
Stirling’s formula 446
Stochastic Turing machine 121
Storage Modification Machine 32
Straight-line code 915—917
Straight-line program 635
String matching 255
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
String, incompressible 200
String, random finite 201
String, random infinite 205—206
Strong component 919
Strong orientation 882
Strongly connected component 571
Strongly where-oblivious 843
Structure 778
Subcircuit 771
Subconstructible space bound 172
Subformula 792
subfunction 764.793
Subgraph isomorphism testing 574
Subgraph, maximal planar 531
Subresultant 401
Substitution method 638
Subtraction 899
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
Sunflower 782
Superconcentrator 660
Superconcentrator, weak 819
Sweep technique 346
switch 842
Switching energy 839
Symbolic determinant 922
Symbolic differentiation 480
Symmetric function 794
Symmetric Turing machine 128
Symmetry of information 209
System of linear equations 913—915 see
Systolic algorithm 864
Systolic algorithm, 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
|
|
|
| Реклама |
|
|
|
|
|
О проекте